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

¦ ¦ K^.elem:= EL; K^.next:= nil;

¦ ¦ R^.next:= K; R:= K;

¦ ¦ EL:= random(10);

¦ end;

end.

ЗАМЕЧАНИЕ. Из программы видно, что L всегда хранит начало очереди, а R - ее конец. Процедура имеет два возвращаемых параметра, которые идентифицируют получаемую с ее помощью очередь. Первый параметр L позволяет начать просмотр очереди или удалить из нее элемент, а второй R - добавить новый элемент (согласно правилу работы с очередями).

Заметим также, что эта процедура формирует очередь из однозначных чисел и признаком конца очереди является число 0. Она предполагает формирование пустой очереди, состоящей из одного нулевого звена:

L,R

*

0

nil

Если пустой очередью считать очередь без единого звена, то процедура принимает вид:

procedure FORMIR_OTCHERED_2 (var L, R: SS);

var K: SS;

EL1, EL2: integer;

begin

¦ {Формирование первого звена очереди }

¦ randomize; EL1:= random(10);

¦ if EL1= 0 then begin L:= nil; R:= L end

¦ else begin new(K);

¦ L:= K; R:= K; K^.next:= nil;

¦ K^.elem:= EL1;

¦ { Помещение очередного элемента в очередь }

¦ EL2:=random(10);

¦ while EL2<>0 do

¦ begin

¦ new(K);

¦ K^.elem:= EL2; K^.next:= nil;

¦ R^.next:= K; R:= K; EL2:= random(10);

¦ end; end;

end.

Одним из приемов работы с очередями является доступ к ее элементу, в частности, сравнение элемента с каким-то числом или вывод его на печать. Исходя из идеологии построения очереди видно, что выборка любого элемента, как и в файле последовательного доступа, возможна только путем просмотра всех элементов очереди, начиная с ее начала. Это легко сделать, зная ссылки на начало и конец очереди. Наличие двух ссылок очень удобно для просмотра очереди (поиска нужного элемента или вывода его на печать). Действительно, в этом случае достаточно организовать цикл с изменением некоторой ссылочной переменной от значения L до значения R.

Таким образом, если необходимо обработать очередь, то следует указать для нее две переменные, где хранятся ссылки на начало и конец. Эти переменные берутся либо непосредственно из программы формирования очереди, либо как выходные параметры процедуры формирования, рассмотренной выше. Ниже следует процедура распечатки элементов очереди, сформированной процедурой пункта 14.1.1:

procedure VIVOD_OTCHERED (var L, R: SS);

var K: SS;

begin

¦ if (L^.elem= 0) or (L= nil) then

¦ writeln('Очеpедьпуста ! ')

¦ else begin

¦ ¦ K:= L;

¦ ¦ write('Элементы очереди: ');

¦ ¦ while K <> R^.next do

¦ ¦ begin

¦ ¦ ¦ write (K^.elem, ' ');

¦ ¦ ¦ K:= K^.next;

¦ ¦ end;

¦ end;

end.

ЗАМЕЧАНИЕ. В данной процедуре знание ссылки R на конец очереди совсем не обязательно. Здесь можно обойтись только ссылкой на начало, а в цикле WHILE в качестве условия взять сравнение значения переменной K с NIL: WHILE K <> NIL.

Добавление нового звена EL к очереди происходит справа (используется указатель R). Рассмотрим сначала алгоритм:

ОПЕРАТОРЫ	ПОЯСНЕНИЕ
read(el); new(K);
K^.next:=nil;	K	*	el	nil
K^.elem:=el;
	L	*	el1	*
	…	…	…	…	…
R^.next:=K;	R	*	elN	*
	el	nil
K
	L	X	el1	*
	…	…	…	…	…
R:=K;	elN	*
	R	X	el	nil
K

Запишем теперь процедуру добавления звена к очереди:

procedure DOBAV_OTCHERED (EL:integer; var L, R: SS);

var K: SS;

begin

¦ if L^.elem = 0 then R^.elem:= EL

¦ else if L = nil then

¦ begin

¦ ¦ new(K);L:= K;

¦ ¦ R:= K;

¦ ¦ K^.next:= nil;

¦ ¦ K^.elem:= EL

¦ end

¦ else begin

¦ ¦ new(K);

¦ ¦ K^.elem:=el;

¦ ¦ K^.next:=nil;

¦ ¦ R^.next:=K;

¦ ¦ R:=K

¦ end;

end.

ЗАМЕЧАНИЕ. В данной процедуре сначала проверяется, является ли очередь пустой. Если пустая очередь имеет нулевое звено,то оно заполняется элементом EL. Если же она не содержит звеньев, то создается одно звено по тем же правилам, как при формировании очереди. В общем случае к последнему звену очереди добавляется новое звено.

Исключение звена из очереди происходит слева – используется указатель L - и осуществляется одним оператором: L:=L^.next. При такой операции, однако, память не освобождается. Для ее освобождения необходимо дополнительно использовать процедуру DISPOSE.

L	*	el1	*
	el2	*
	…
R	*	elN	nil

procedure UDALENIE_OTCHERED (var l, r:ss);

begin

¦ if l=nil then writeln('Очеpедьпуста !')

¦ else l:=l^.next

end.

ОБЩЕЕ ЗАМЕЧАНИЕ. В рассмотренных процедурах признаком конца очереди являлось число 0. Если очередь заполняется символами, то для этого нужно выбрать свой признак конца, например, ".". Для ввода символов, как и для ввода чисел, также можно использовать датчик случайных чисел. Но в этом случае он должен генерировать коды ASCII, которые затем с помощью функции преобразования типов CHR трансформировать в сами символы.

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

Заметим, кстати, что все сказанное о формировании очереди распространяется и на другие типы линейных списков.

14.2 Стек

Стек - это структура данных, которая обеспечивает доступ к списку по принципу LIFO (от первых букв английской фразы "Last Input First Output"): последним вошел, первым вышел. Компонента извлекается из стека таким образом, что первой выбирается та, которая была помещена последней.

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

Значением указателя, представляющего стек как единый объект, является ссылка на ВЕРШИНУ стека. Последнее звено цепочки – стека содержит в поле ссылок значение NIL.

STACK

*

elN

*

…

el2

*

el2

nil

Если стек пуст, то значением указателя является ссылка NIL.

Перед началом заполнения стека его необходимо сделать пустым, т.е. выполнить "обнуление" указателя стека: STACK:= NIL.

Над стеком, как и над очередью, допустимы следующие операции:

1) формирование;

2) занесение нового элемента;

3) удаление элемента;

4) доступ (только для просмотра) к N-му звену стека.

Заметим, кстати, что занесение и удаление происходят в стеке исключительно в его вершине.

ОПЕРАТОРЫ	ПОЯСНЕНИЕ
Var ST:SS;
EL:integer;
K:SS;	ST	*	nil
Begin
New(ST);
ST:=nil;
New(K);	K	*
Randomize;
EL:=random(10);
K^.elem:=el;	K	*	el1	nil
K^.next:=ST;
	K	*	el1	nil
ST:=K;
	ST	*
New(K);	K	*
EL:=random(10);	K	*	el2	*
K^.elem:=EL;
	ST	*	el1	nil
K^.next:=ST;
ST:=K;	K	*	el2	*
	ST	*	el1	nil

Запишем теперь саму процедуру формирования стека: