Двусвязные списки

Рис. 32. Создание стека на структуре односвязного циклического списка

Рис. 31. Создание очереди на структуре односвязного циклического списка

Рис. 30. Структура элементарного односвязного кольца

Рис. 29. Структура односвязного циклического списка с головным узлом

 

Элемент хранения односвязного циклического списка описывается следующим образом:

 

Type PList=^List; List= record info: word; link: pList; end;	{ указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи узла }
Var head: PList;	{ указатель на «голову» списка }
p: Plist;	{ вспомогательный указатель }

 

Выполнение условия head = nil означает, что односвязный циклический список не существует. Выполнение условия head ^. link = head означает, что односвязный циклический список существует, но является пустым, т.е. содержит только головной элемент. Пустой циклический список с головным элементом представляется структурой элементарного кольца (рис. 30).

 

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

 

 

 

 

 

 

 

 

 

Ниже приведена процедура создания односвязного циклического списка из n узлов.

 

Procedure Create_Cicl( var head: PList; n: byte ); var p: PList; i: byte; begin new( head ); head^.link:=head;	{ head – указатель на голову списка } { n – количество узлов в списке }     { создание элементарного кольца }
for i:=1 to n do begin	{ cоздание циклического списка из n узлов }
new( p );	{ создание узла списка }
readln(p^.info);	{ заполнение информационного поля узла }
p^.link:=head^.link;	{ установка связи между вставленным узлом и cписком}
head^.link:=p;	{ обновление поля связи головного узла }
end; end;

 

Т.к. в циклическом списке каждый элемент, в том числе первый и последний, имеют предшественника и последователя (“перед” первым элементом и “за” последним элементом находится голова), все n элементов списка создаются и включаются в список одинаково (см. процедуру Create_Cikl). Каким образом включаются узлы в список при выполнении процедуры Create_Cikl: “за” головным узлом или “перед” ним? Исключение первого или последнего узла циклического списка также не имеет никаких особенностей за счет использования головного элемента. Операции включения / исключения узлов в список произвольного вида, реализованный в виде циклического списка, выполняются так же, как в нецикличесом списке.

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

 

. . .
if head <> nil then begin	{ список существует? }
p:=head^.link;	{ установить вспомогательный указатель }
while ( p<> head ) and ( p^.info<> значение ) do < тело цикла >	{ поиск }
end;
. . .

 

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

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

 

 

Для достижения большей гибкости в работе с линейными списками можно включить в каждый узел два атрибута связи – указатели на следующий узел (т.е. на “правого соседа”) и на предыдущий узел (т.е. на “левого соседа”). Списки с двумя связями занимают больше памяти, чем односвязные, однако в процессе прохода по списку они дают возможность продвигаться как “вперед”, так и “назад”, что повышает эффективность реализации алгоритмов обработки списков.

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

 

Type PDlist=^ Dlist; Dlist= record info: word; next: pDlist; prev: pDlist end;

{ указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи со следующим узлом } { поле связи с предыдущим узлом }

 

В двусвязном нециклическом списке первый узел не имеет предшественника (поле связи prev первого узла равно NIL), а последний узел не имеет последователя (поле связи next последнего узла равно NIL). На первый узел двусвязного списка, имеющего нециклическую структуру, указывает указатель first: pDlist. Выполнение условия first = nil означает, что двусвязный нециклический список пуст. Структура двусвязного нециклического списка представлена на рис. 33.