В односвязном списке поле INF - информационное поле, данные, NEXT -указатель на следующий элемент списка.
Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который по формату отличен от остальных элементов.
В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.
Рис. 13 - Структура односвязного списка
Кольцевой список, может быть организован на основе как односвязного, так и двухсвязного списков.
Кольцевой односвязный список получается из обычного односвязного спичка путем присваивания указателю последнего элемента списка значение указателя начала списка (рис. 14)
Рис. 14 – Структура кольцевого односвязный список
Операции, производимые над односвязными списками:
· вставка в начало односвязного списка
Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенерировать пустой элемент (P=GetNode). Информационному полю этого элемента присвоить значение D (INFO(P)=s:D), значению указателя на этот элемент присвоить значение указателя на начало списка (Ptr(P) = Lst), значению указателя начала списка присвоить значение указателя Р (Lst = Р).
· удаление элемента из начала односвязного списка
надо удалить первый элемент списка, но запомнить ин формацию, содержащуюся в поле Info этого элемента. Для этого введем указатель Р, который будет указывать на уда ляемый элемент (Р = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение Указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).
· любая структура информационной части списка:
type data = ...;
· элемент односвязного списка (sll - single linked list): единственный список с использованием указателей
type
sllptr = ^slltype; { указатель в односвязном списке }
slltype = record { элемент односвязного списка }
inf : data; { информационная часть }
next : sllptr; { указатель на следующий элемент }
end;
Обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону.
Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. (рис. 15)
рис. 15 - Структура линейного двухсвязного списка
Поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil
Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка.
Кольцевой двусвязный список. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.
В двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются, как показано на рис.16.
Рис. 16 - Структура кольцевого двухсвязного списка
При работе с такими списками несколько упрощаются некоторые процедуры, выполняемые над списком.
Однако, при просмотре такого списка следует принять некоторых мер предосторожности, чтобы не попасть в бесконечный цикл
В памяти список представляет собой совокупность дескриптора и одинаковых по размеру и формату записей, размещенных произвольно в некоторой области памяти и связанных друг с другом в линейно упорядоченную цепочку с помощью указателей.
Запись содержит информационные поля и поля указателей на соседние элементы списка, причем некоторыми полями информационной части могут быть указатели на блоки памяти с дополнительной информацией, относящейся к элементу списка.
Дескриптор списка реализуется в виде особой записи и содержит информацию о списке:
· адрес начала списка,
· код структуры,
· имя списка,
· текущее число элементов в списке,
· описание элемента и т.д., и т.п.
Дескриптор может находиться в той же области памяти, в которой располагаются элементы списка, или для него выделяется какое-нибудь другое место.
