16.3. Работа со списками или очередями

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

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

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

Type TpL=^TL;

TL=Record

Inf:Tinf;

PL:TpL;

End;

Он в принципе ни чем не отличается от записи стека.

Для двухсвязного списка тип записи уже будет следующим:

Type TpL=^TL;

TL=Record

Inf:Tinf;

PL1,PL2:TpL;

End;

Здесь PL1 указывает на предшествующий элемент очереди, а PL2 – на стоящий за ним элемент очереди. Графически это можно представить следующим образом:

Рис.16.2. Структура очереди

Двухсвязный список очень легко позволяет продвигаться как вперед, так и назад по списку. Его легче редактировать. Рассмотрим несколько процедур работы с двухсвязными списками.

Процедура добавления нового элемента в виде строки в конец очереди:

Procedure Addl(var p:TPL; s:String);

Var Pt:TPL;

Begin

New(Pt); // Выделяем память под новый элемент

Pt^.inf:=s; // Записываем значение строки в новый элемент очереди

Pt^.PL2:=nil;// За последним элементом нет других элементов очереди

If p=nil then Pt^.PL1:=nil else Begin // Если это первый элемент очереди,

Pt^.PL1:=p; // то запоминаем указатель на предыдущий элемент очереди

P^.PL2:=Pt; // В предыдущем элементе записываем указатель на новый

End;

P:=Pt; // Возвращаем указатель на новый конец очереди

End;

Приведем теперь пример подпрограммы, которая удаляет из очереди элемент с заданным значением строки:

Procedure Dell(var p:TPL;var s:String);

// При выходе строка S должна быть пустой, если был удален элемент очереди

Var Pt:TPL;

Begin

Pt:=p; // Запоминаем конец очереди

While p<> nil do Begin // Открываем цикл прохода по очереди

If s=p^.inf then Begin // Нашли элемент для удаления

If p^.PL2=nil then Begin // Удаляем первый элемент с конца очереди

If p^.PL1<>nil then begin // Впереди есть элемент

// Следующий элемент очереди становится последним

p^.PL1^.PL2:=nil;

p:=p^.PL1; // Запоминаем указатель на новый последний элемент

end else p:=nil; // Удаляем единственный элемент очереди

dispose(pt); // Освобождаем память

s:=’’; // Очищаем строку поиска

P

Inf₃

PL1₃

PL2₃=Nil

Inf₂

PL1₂

PL2₂

Inf₁

PL1₁=Nil

PL2₁

End else If p^.PL1=nil then Begin // Удалять нужно последний элемент

P^.PL2^.PL1:=nil;

// Второй элемент очереди теперь не должен иметь впереди стоящего

Dispose(P); // Освобождаем память

P:=pt; // Возвращаем указатель на конец очереди

S:=’’; // Строку поиска полагаем равной пустой строке

End else Begin // Удалять нужно средний элемент очереди

p^.PL2^.PL1:=p^.PL1; // В сзади стоящем элементе очереди записыва–

// ем указатель на впереди стоящий элемент

p^.PL1^.PL2:=p^.PL2; // Во впереди стоящем элементе записываем

// указатель на новый, сзади стоящий элемент очереди

dispose(p); // Освобождаем память

s:=’’; // Очищаем строку поиска

p:=pt; // Возвращаем указатель на конец очереди

end;

End; // Закончили блок удаления элемента очереди

// Выходим из процедуры, если был удален элемент очереди

If s:=’’ then exit;

P:=p^.PL1; // Переходим на просмотр впереди стоящего элемента очереди

End; // Конец цикла просмотра элементов очереди

End;