Линейные списки Под списком мы будем понимать конечный упорядоченный набор объектов произвольных размера и природы.
Связанные списки используются в двух основных случаях. если действительный размер списка неизвестен, то применяют связанный список. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего дискового файла.
Однонаправленный линейный список — это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список принимает указатель NIL, что говорит о том, что он последний.
модель списка при помощи определенной структуры данных, состоящей из динамических переменных.
Каждый элемент списка представим записью, которая состоит из двух полей:
-информационного поля или поля данных, которое в общем случае может содержать произвольное (фиксированное для данного типа элемента) количество полей разных типов;
- ссылки на следующий элемент списка.
Каждую такую пару будем называть звеном, а ссылки, содержащиеся в каждом из звеньев, будем использовать для соединения звеньев в цепочку. Такой способ представления упорядоченной последовательности элементов называется сцеплением.
Каждая компонента списка определяется ключом. Обычно ключ — это либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью информационного поля записи.
Над списками выполняются следующие операции:
-начальное формирование списка (запись первой компоненты); -добавление компоненты в конец списка;
-определение первого элемента в линейном списке; -чтение компоненты с заданным ключом; с заданным свойством;
-вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
-исключение компоненты с заданным ключом из списка. —упорядочивание узлов линейного списка в определенном порядке.
Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель,первая из которых определяет начало списка pBegin,
вторая — конец списка pEnd, остальные- вспомогательные, pCKey, pPreComp, pAux. Описание компоненты списка и переменных типа указатель дадим следующим образом:
type
PComp= ^Comp;
Comp= record
D:T; {Информационное поле}
pNext:PComp {Ссылка на следующую компоненту}
end;
var pBegin, pEnd, pCKey, pPreComp, pAux: PComp;
Однонаправленный кольцевой список — это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список имеет указатель на начало списка.
Формирование списка. Просмотр списка
Type
T:^TElem; Q:R;
TElem=record Q^.next:nil;
Inf:< тип >;{ integer} Repeat
Next:T; Q:=Q^.next;
End; Until q=nil;
Var R;Q:T; Q:=R;
R:=nil; While Q< >nil do
New(q); Q:=Q^.next;
Q^.inf:=1; {формирование инф.ч}
R:=Q; R- начало списка
While < условие формирования списка > do
Begin
New(Q^.next);
Q:=Q^.next;{формир. Инф.часть Q^.inf}
