11.6 Использование указателей для работы со списками
Список — одна из распространенных на практике структур данных. Список — упорядоченная структура, каждый элемент которой содержит ссылку(ки), связывающую(ие) его с некоторыми другими элементами списка, например, со следующим и (или) предыдущим элементом(ами).
Примерами списков являются стеки, очереди, двух- и многосвязные списки, деревья, графы общего вида.
Для организации списков используются указатели на записи, состоящие из двух смысловых частей: основной и дополнительной. Основная часть содержит информацию, подлежащую обработке. В дополнительной части находится ссылка(и) на связанный(ые) с этим элементом элемент(ы) списка. Начало списка (адрес) указывается в переменной, которая всегда присутствует в программе обработки списков (если элементов в списке нет — пустое значение).
11.6.1 Работа со стеками
Стек — список с одной точкой доступа к его элементам, которая называется вершиной стека. Добавить или убрать элемент можно только через его вершину. Принцип работы стека — LIFO (Last In First Out) — последним пришел, первым ушел.
Схема работы со стеком:
Type
Ukaz = ^Stack ;
Stack = Record
Inf : Integer ; { информационная часть }
Next : Ukaz { дополнительная часть }
end ;
Var
Versh, Rab : Ukaz ;
Value : Integer ;
Procedure Sozd_Stack ; { первоначальная организация стека }
Begin
Versh := Nil ;
While True do
Begin
Read ( Value ) ;
If Value = 999
then Exit ;
New ( Rab ) ;
Rab^.Next := Versh ;
Rab^.Inf := Value ;
Versh := Rab
End
End ;
Procedure Dobavl_Stack ; { добавление элементов в стек }
Begin
While True do
Begin
Read ( Value ) ;
If Value = 999
then Exit ;
New (Rab ) ;
Rab^.Next := Versh ;
Rab^.Inf := Value ;
Versh := Rab
End
End ;
Procedure Udal_Stack ; { Удаление последнего элемента стека }
Begin
Rab := Versh ;
Versh := Versh^.Next ;
Dispose (Rab )
End ;
Procedure Print_Stack ; { Обработка (вывод) элементов стека }
Begin
Rab := Versh ;
While Rab <> Nil do
Begin
WriteLn ( Rab^.Inf ) ;
Rab := Rab^.Next
End
End ;
11.6.2 Работа с очередями
Очередь — список, в один конец которого добавляются элементы, а из другого — изымаются. Принцип работы очереди — FIFO (First In First Out) — первым пришел, первым ушел. Для организации такой структуры используются уже две переменные — для указания начала и конца очереди.
Схема работы с очередью:
Type
Ukaz = ^Och ;
Och = Record
Inf : Integer ; { информационная часть }
Next : Ukaz { дополнительная часть }
end ;
Var
Beg, En, Rab : Ukaz ;
Value : Integer ;
Procedure Sozd_Och ; { первоначальная организация очереди }
Begin
Read ( Value ) ;
If Value = 999
then Exit ;
New ( Rab ) ;
Rab^.Next := Nil ;
Rab^.Inf := Value ;
Beg := Rab ;
En := Rab ;
While True do
Begin
Read ( Value ) ;
If Value = 999
then Exit ;
New ( Rab ) ;
Rab^.Next := Nil ;
Rab^.Inf := Value ;
En^.Next := Rab ;
En := Rab
End
End ;
Procedure Dobavl_Och ; { добавление элементов в очередь }
Begin
While True do
Begin
Read ( Value ) ;
If Value = 999
then Exit ;
New ( Rab ) ;
Rab^.Next := Nil ;
Rab^.Inf := Value ;
En^.Next := Rab ;
En := Rab
End
End ;
Procedure Udal_Och ; { Удаление первого элемента из очереди }
Begin
Rab := Beg ;
Beg := Beg^.Next ;
Dispose ( Rab )
End ;
Procedure Print_Och ; { Обработка (вывод) элементов очереди }
Begin
Rab := Beg ;
While Rab <>Nil do
Begin
WriteLn (Rab^.Inf) ;
Rab := Rab^.Next
End
End ;