Однонаправленные списки

Задача.

Dispose(p).

Создать очередь из 10-ти вещественных чисел, вывести элементы на экран, предварительно их удалив.

 

program och;

type ukaz=^ochered;

ochered=record

inf:real;

uk:ukaz

end;

 

var BegUkaz, EndUkaz: ukaz;

i: byte;

 

ргосеdurе аdd(val: rеаl); {процедура создания и добавления

var p:ukaz; элемента в очередь}

begin

 

new(р);

р^.inf:= val;

р^.uk:= nil;

if EndUkaz=nil then BegUkaz:=p

else EndUkaz^.uk:=p;

EndUkaz:=p

 

end;

 

ргосеdurе del; {процедура удаления элемента из очереди }

var p:ukaz;

begin

 

p:= BegUkaz ;

BegUkaz:=p^.uk;

if BegUkaz=nil then EndUkaz:=nil; {если удаляется последний элемент}

EndUkaz:=nil;

dispose(p)

 

end;

 

begin

BegUkaz=nil; EndUkaz:=nil; {начальные установки}

for i:=1 to 10 do add(i); {создание очереди}

 

while BegUkaz<>nil do {вывод элементов и их удаление}

begin

writeln(‘значение=’, BegUkaz:=p^.uk;);

del;

end

end.

 

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

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

Каждая компонента списка определяется ключом. Обычно ключ – либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.

 

Основные отличия связного списка от стека и очереди следующие:

-для чтения доступна любая компонента списка;

-новые компоненты можно добавлять в любое место списка;

-при чтении компонента не удаляется из списка.

 

Более подробно рассмотрим работу со связанными списками на примере однонаправленного некольцевого списка.

Выделим типовые операции над списками:

· добавление звена в начало списка;

· удаление звена из начала списка;

· добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);

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

· проверка, пуст ли список;

· очистка списка;

· печать списка.

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