Лекция: Линейный список. Реализация с использованием связных списков. Примеры применения.

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

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

Каждая компонента списка определяется ключом. Обычно ключ — либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.

Основные отличия связного списка от стека и очереди следующие:

• -для чтения доступна любая компонента списка;
• -новые компоненты можно добавлять в любое место списка;
• -при чтении компонента не удаляется из списка.

Над списками выполняются следующие операции:

• -начальное формирование списка (запись первой компоненты);
• -добавление компоненты в конец списка;
• -чтение компоненты с заданным ключом;
• -вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);
• -исключение компоненты с заданным ключом из списка.

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

Описание компоненты списка и переменных типа указатель дадим следующим образом:

type
PComp= ^Comp;
Comp= record
D:T;
pNext:PComp
end;
var
pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

где pBegin — указатель начала списка, pEnd — указатель конца списка, pCKey, pPreComp, pAux — вспомогательные указатели.

Начальное формирование списка, добавление компонент в конец списка выполняется так же, как и при формировании очереди.

Для чтения и вставки компоненты по ключу необходимо выполнить поиск компоненты с заданным ключом:

pCKey:=pBegin;
while (pCKey<>NIL) and (Key<>pCKey^.D) DO
pCKey:=pCKey^.pNext;

Здесь Key — ключ, тип которого совпадает с типом данных компоненты.
После выполнения этих операторов указатель pСKey будет определять компоненту с заданным ключом или такая компонента не будет найдена. Пусть pCKey определяет компоненту с заданным ключом. Вставка новой компоненты выполняется следующими операторами:

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

pCKey:=pBegin;
while (pCKey<>NIL) and (Key<>pCKey^.D) do
begin
pPreComp:=pCKey;
pCKey:=pCKey^.pNext
end;

Здесь указатель pCKey определяет компоненту с заданным ключом, указатель pPreComp содержит адрес предидущей компоненты.

Удаление компоненты с ключом Key выполняется оператором:

pPreComp^.pNext:=pCKey^.pNext;

Поиск в линейном списке. Назначение и варианты реализации.