Алгоритмический язык Паскаль (стр. 23 из 31)

procedure SOZDAN_STACK (var ST: SS);

var K: SS;

EL: integer;

begin

randomize;

EL:= random(10);

new(ST); ST:= nil;

while EL <> 0 do

begin

¦ new(K); K^.elem:= EL;

¦ k^.next:= ST; ST:= K;

¦ EL:= random(10);

end;

end.

ЗАМЕЧАНИЕ. Как видно из процедуры, организация очереди и стека отличается только порядком установления связи: предыдущий элемент очереди указывает на следующий, а следующий элемент стека ссылается на предыдущий.

Известно, что новый элемент всегда вставляется на первое место - в вершину стека. Отсюда получаем схему вставки звена в стек:

ST	*	Eln	*	…	EL1	nil
	Eln+1	*

Процедура имеет два параметра: ST - указатель на стек, EL - заносимый элемент:

PROCEDURE VSTAVKA_V_STACK(var ST: SS; EL: integer);

var K: SS;

begin

new(K); K^.elem:= EL;

K^.next:= ST; ST:= K

end.

Схематически процесс удаления можно изобразить так:

ST	*	Eln	*	Eln-1	*	…	EL1	nil

По схеме видно, что удаляется N-е звено (вершина стека), которое надо запомнить в специальной ячейке SKLAD:

procedure UDALENIE_IZ_STACK(var ST: SS; var SKLAD: integer);

begin

¦ SKLAD:= ST^.elem;

¦ ST:= ST^.next

end.

Мы видим, что здесь переменная ST начинает хранить ссылку на N-1 элемент.

Данная процедура имеет недостатки:

1) предполагается, что стек заведомо не пуст, иначе программа зависнет;

2) исключаемое звено не уничтожается, т.к. меняется только ссылка в переменной ST. Если таких удалений несколько, то память будет забита "мусором". Поэтому следует исключить элементы не только из списка, но и из памяти. Для этого можно использовать процедуру DISPOSE.

Указанные недостатки учтены в следующей процедуре:

procedure UDALENIE_MOD(var ST: SS; var SKLAD: integer);

var K: SS;

begin

¦ if ST = nil then writeln('стекпустой')

¦ else begin

¦ ¦ SKLAD:= ST^.elem; K:=ST;

¦ ¦ ST:= ST^.next; dispose(K);

end;

end.

Здесь мы ввели в употребление вспомогательную ссылочную переменную К, т.к. писать DISPOSE (ST) нельзя, ведь ST содержит ссылку на вершину стека.

Для извлечения из стека N-го элемента необходимо поступить так же, как при выборке элемента из файла, - "прокрутить" стек на N-1 позиций и затем извлечь N-й элемент. Для "прокрутки" стека можно воспользоваться процедурой UDALENIE, т.к. удаление в динамических структурах означает не уничтожение звеньев списка, а только передвижение указателя на следующий элемент.

Для написания этой процедуры следует уточнить, что под N-м элементом стека следует понимать элемент, отстоящий на N позиций от вершины стека:

procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;

N: integer);

var K: SS; i: integer;

begin

¦ K:= ST;

¦ for i:= 1 to N-1 do

¦ UDALENIE_IZ_STACK(K, SKLAD);

¦ SKLAD:= K^.elem;

end.

Для вывода на печать элементов стека можно воспользоваться процедурой печати для цепочки, т.к. в этом смысле цепочка ничем не отличается от стека. Отметим только, что элементы стека будут выведены в порядке, обратном его заполнению.

14.3 Дек

Дек - это двунаправленная очередь, т.е. линейный список, в котором все включения и исключения (и обычно всякий доступ) достигаются на обоих концах списка:

левый		второй		второй		правый
конец		слева		справа		конец
	EL1	EL2	..	..	Eln-1	Eln
включить		включить
или	или
исключить		исключить

Более точно следует представить так:

EL1	EL2	EL3	Eln
	*	*	*	…	*	nil
nil	*	*	*	…	*

Ôîðìèðîâàíèå äåêà

Для организации дека в виде динамической цепочки необходимо иметь следующие типы:

type SS = ^ZVENO;

ZVENO = record

ELEM: integer;

next: SS;

pred: SS;

end.

Очевидно, что дек обладает большей общностью, чем стек и очередь; он имеет некоторые общие свойства с каждой из этих структур. Существуют деки с ограниченным входом (реестры) и выходом (архивы). В таких деках соответственно включение и исключение допускается только в одном конце.

Строго говоря, при работе с деками достаточно иметь ссылку на один любой элемент. Однако для удобства создадим процедуру, при выходе из которой есть ссылки на оба конца дека:

procedure FORMIR_DEK_1(var L, R: SS);

var Z: SS; EL: integer;

begin

¦ new(L); read(L^.elem);

¦ L^.pred:= nil; R:= L; Z:= L;

¦ WHILE R^.elem <> 0 do

¦ begin

¦ ¦ new(R^.next); R:=R^.next;

¦ ¦ read(r^.elem); R^.pred:= Z; Z:= R;

¦ end;

¦ R^.next:= nil; readln;

end.

ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R – конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.

Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:

Звено 1		Звено 2
X	*	next	next	…
	…	pred	pred
ELi	ELi+1

При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:

procedure FORMIR_DEK_2(var L, R: SS);

begin

¦ randomize; new(L);

¦ L^.elem:= random (10);

¦ L^.pred:= nil; R:= L;