Программный модуль, реализующий операции

   создания, обработки, просмотра содержимого списка

Uses Crt;
Type PList = ^ List;		{ описание элемента хранения узла списка и }
List = record				{ указателя на узел списка }
info: word; link: plist;
end;
var f: PList; cod,n: byte; sum: word;
Procedure Create1(var first: PList;                                 n: byte); var p: PList; i: byte; begin first:=nil;				{ first – указатель на первый узел списка }   { n – количество узлов в списке }   { создание пустого списка }
for i:=1 to n do begin
new(p);				{ создание узла списка }
write(‘Значение инф. поля‘, i, ‘-го элемента списка = ‘);
readln(p^.info);				{ заполнение информационного поля узла }
p^.link:=first;	{ установка связи между вставленным узлом и списком }
first:=p;			{ новое значение указателя на первый узел }
end; end;
Procedure Print(first: PList);		{ просмотр информац. полей узлов списка }
var p: PList; i: byte;
begin i:=0;
while (p <> nil) do begin
inc(i);
writeln(‘Информационное поле ‘, i, ‘-го элемента списка = ‘, p^.info);
p:=p^.link;
end;
end;
Procedure Work(first: PList; var s: word);					{ суммирование значений информ. }
var p: PList;				{ полей узлов списка }
begin s:=0;
while (p <> nil) do begin
s:=s+p^.info; p:=p^.link;
end;
end;
Procedure Destroy(var first: PList);				{ разрушение списка }
begin
...
end;
Procedure Message;				{ вспомогательная процедура }
begin
writeln(‘Список пуст‘); write(‘Нажмите любую клавишу‘); readkey
end;
begin
f:=nil;				{ первоначально список пуст }
repeat Clrscr;
writeln(‘1-Создание 2-Просмотр 3–Обработка 4–Разрушение 5-Выход‘);
write(‘Код действия = ‘); readln(cod);
case cod of
1: begin				{ создание списка }
write(‘Количество узлов в списке = ‘); readln(n);
Сreate(f,n); write(‘Нажмите любую клавишу‘); readkey
end;
2: begin				{ просмотр списка }
if f=nil then Message
else begin
Print(f); write(‘Нажмите любую клавишу‘); readkey
end;
3: begin				{ обработка списка }
if f=nil then Message
else begin
Work(f,sum); writeln(‘Сумма значений инф. полей = ‘, sum);
write(‘Нажмите любую клавишу‘); readkey
end;
4: begin				{ разрушение списка }
if f=nil then Message
else begin
Destroy(f); writeln(‘Список разрушен‘);
write(‘Нажмите любую клавишу‘); readkey
end;
5: Destroy(f)				{ выход }
end;
until (cod = 5); Clrscr
end.

 

Односвязные циклические списки

 

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

 

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

 

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

 

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

 

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

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

 

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

 

                                 

 

 

 

Рис. 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.

 

 

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

 

Нециклическая структура двусвязного списка порождает те же проблемы при включении / исключении первого и последнего узлов, что и структура односвязного нециклического списка.

На практике более широко применяются двусвязные циклические списки. В двусвязном циклическом списке поле связи next его последнего элемента не содержит значения NIL, а указывает на первый узел списка и поле связи prev его первого элемента также не содержит значения NIL, а указывает на последний узел списка. В целях удобства обработки в структуру двусвязного циклического списка включают специальный дополнительный узел с особым содержанием информационного поля (на рис. 34 это поле заштриховано), называемый “головой“ списка или “сторожем“. Заметим, что “левым соседом” первого узла двусвязного циклического списка является его последний узел, а “правым соседом” его последнего узла является первый узел, т.к. информационное поле головного узла имеет особое содержание (а нередко и вовсе не используется). Так что функция “сторожа” в двусвязном циклическом списке оказывается чисто технологической и полностью аналогичной функции “сторожа” в односвязном циклическом списке. Структура двусвязного циклического списка приведена на рис. 34.

 

 

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

 

 

var head: pDlist;	{ указатель на голову списка }
p: pDlist;	{ вспомогательный указатель }

 

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

 

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

 

Для любого узла двусвязного циклического списка, на который установлен указатель p (в том числе, и для головного), справедливо выражение: p^.next^.prev = p^.prev^.next = p;