Занимательные факты о представителях фауны (стр. 25 )

               P, Q: Adr2; {В Р будет храниться адрес заглавного звена, в Q – адрес текущего звена}

               B: Boolean;

       Begin

               B := False; {B – логическая переменная (факт наличия искомого элемента)}

               P := Adr; {В P занесен адрес заглавного звена}

               Iskadr := Nil;

               Q:=P^.Adrcled; {В Q занесен адрес первого звена}

               While (P<>Q) And Not B Do {Поиск, пока не дошли до заглавного звена и не нашли искомый элемент}

                       Begin

                               If Q^.Element = Elem Then {Найден искомый элемент}

                                       Begin

                                               B := True;

                                               Iskadr := Q {Адрес искомого элемента}

                                       End;

                               Q := Q^.Adrcled {Переход к следующему звену}

                       End;

               Poisk := B {Возвращаемое значение}

       End;

7.3. Очереди и стеки

В программировании имеется структура данных, называемая очередью. Понятие очереди в программировании аналогично понятию реальной очереди из повседневной жизни.

Очередь является динамической структурой. Длина очереди и набор образующих ее элементов изменяется с течением времени.

Над очередью определены две операции:

занесение элемента в очередь (заказа на обслуживание); выбор элемента из очереди (для его обслуживания); выбранный элемент из очереди исключается.

В очереди доступны две позиции: ее начало (из этой позиции выбирается элемент из очереди) и конец (в эту позицию помещается заносимый в очередь элемент).

Различают два основные вида очередей, отличающиеся по дисциплине (способу) обслуживания находящихся в них элементов.

В первом виде очередей заказ, поступивший в очередь первым, выбирается первым для обслуживания и удаляется из очереди. Это дисциплину обслуживания очереди называют FIFO (First In – First Out – первый в очередь – первый из очереди).

Во втором виде очередей заказ, поступивший в очередь последним, выбирается первым для обслуживания и удаляется из очереди. Эту дисциплину обслуживания называют LIFO (Last In – First Out – последний в очередь – первый из очереди).

Очередь второго вида называется стеком.

7.3.1. Очередь LIFO

Наиболее часто в программировании используются очереди второго вида – стеки. Принцип их работы – «Последний пришел – первый вышел».

В стеке доступна единственная позиция, называемая вершиной стека – это позиция, в которой находится последний по времени поступления в стек элемент.

Наиболее быстрое выполнение операций над стеком обеспечивает его представление в виде динамической цепочки звеньев (однонаправленного списка). Вершиной стека обычно является первое звено цепочки. Заглавное звено в цепочке стека не нужно, так как в стеке доступна только его вершина.

При использовании структуры однонаправленного списка стек задается с помощью описания типа, приведенного в примере 7.7, и дополнительно может быть введен тип указателя, представляющего стек как единую структуру, то есть ссылка на вершину стека Stek:

Type

<Задание стека по примеру 7.7>;

       Stek = Adres1;

Реальный стек вводится с помощью описания переменной:

Var

       St: Stek;

Схематично стек изображается аналогично цепочке (рисунок 7.15).

Рисунок 7.15 – Схематичное представление стека

К началу использования стека его нужно сделать пустым:

St := Nil;

А. Занесение элемента в стек

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Алгоритм занесения элемента в стек:

Создание нового звена. Занесение в новое звено элемента. Занесение в новое звено адреса предыдущей вершины стека. Созданное звено сделать вершиной стека.

Пример 7.13.

Процедура занесения элемента в стек. Первый параметр задает нужный стек (если их несколько), второй – заносимое в него значение.

Procedure Zanes (Var St: Stek; El:<Тип_элемента_стека>);

       Var

               Q: Adres1;

       Begin

{1}        New (Q);

{2}        Q^.Element := El;

{3}        Q^.Adrcled := St;

{4}        St := Q

End;

Номера операторов в данной программе соответствуют номерам этапов алгоритма занесения элемента в стек.

Б. Выбор элемента из стека

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Алгоритм выбора элемента из стека:

Прочитать значение из вершины стека. Запомнить ссылку на старую вершину. Исключить первое звено из стека. Уничтожить первое звено.

Пример 7.14.

Процедура выбора элемента из стека. Первый параметр задает нужный стек (если их несколько), во второй передается значение из вершины стека.

Procedure Vibor (Var St: Stek; Var A: <Тип_элементов_стека>);

       Var

               Q: Adres1;

       Begin

{1}        A := St^.Element;

{2}        Q := St;

{3}        St := St^.Adrcled;

{4}        Dispose (Q)

End;

Номера операторов в данной программе соответствуют номерам этапов алгоритма выбора элемента из стека.

Если необходимо ускорить процедуру выбора, то операторы Q := St и Dispose(Q) можно не применять. Однако это приведет к неэффективному использованию памяти.

В. Создание стека

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Для создания стека может быть использована процедура Zanes из примера 7.13.

Пример 7.15.

Создание стека. Ввод исходного текста в стек. Признак окончания текста – точка.

…

Var

       St: Adres1;

       Bykva: Char;

Begin

       St := Nil;

       Read (Bykva);

       While Bykva <>’.’ Do

               Begin

                       Zanes (St, Bykva);

                       Read (Bykva)

               End

End.

7.3.2. Очередь FIFO

Принцип работы – “Первый пришел, первый вышел”.

Для организации такой очереди используются две ссылочные переменные типа Adres1 (см. пример 7.7): Left – для указания начала и Right – для указания конца очереди.

Добавление элемента в очередь осуществляется в соответствии со значением Right. Затем значение Right изменяется и указывает на последний занесенный элемент.

Выборка элементов из очереди происходит, исходя из значения Left. Затем Left изменяется и указывает на следующий элемент очереди.

Если в очереди один элемент, значение Right равно значению Left. Такое равенство может использоваться как признак окончания очереди при последовательном выборе элементов из нее.

А. Занесение элемента в очередь

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Алгоритм занесения элемента в очередь:

Cоздание нового звена. Занесение в последнее звено адреса нового звена. Занесение Nil в поле Adrcled нового звена. Занесение элемента в информационное поле нового звена. Созданное звено сделать концом очереди.

Пример 7.16.

Процедура занесения элемента в очередь. Первый параметр – Right – адрес последнего занесенного элемента, второй – заносимое в очередь значение.

Procedure Dobavl (Var Right: Adres1; El: <Тип_элементов_очереди>);

       Var

               Q: Adres1;

       Begin

{5}        New (Q);        {1-й этап алгоритма занесения}

{6}        Right^.Adrcled := Q;        {2-й этап алгоритма занесения}

{7}        Q^.Adrcled := Nil;        {3-й этап алгоритма занесения}

{8}        Q^.Element := El;        {4-й этап алгоритма занесения}

{9}        Right:=Q        {5-й этап алгоритма занесения}

       End;

Б. Выбор элемента из очереди

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Алгоритм выбора элемента из очереди:

Чтение значения из начала очереди. Запоминание ссылки на начало очереди. Исключение первого звена из начала очереди. Уничтожение первого звена.

Пример 7.17.

Процедура выбора элемента из очереди. Параметр Left используется для передачи адреса начала очереди. В параметр Elem передается значение из начала очереди.