Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку – на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных. Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи может выступать в качестве ключа: при упорядочивании списка по алфавиту ключом будет фамилия, а при поиске, например, ветеранов труда ключом будет стаж. Ключи разных элементов списка могут совпадать.
Над списками можно выполнять следующие операции:
· начальное формирование списка (создание первого элемента);
· добавление элемента в конец списка;
· чтение элемента с заданным ключом;
· вставка элемента в заданное место списка (до или после элемента с заданным ключом);
· удаление элемента с заданным ключом;
· упорядочивание списка по ключу.
Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало списка, вторая – конец списка, остальные – вспомогательные.
Рассмотрим двунаправленный линейный список. Для простоты допустим, что список состоит из целых чисел. Описание компоненты списка и переменных типа указатель дадим следующим образом:
Type
PComp= ^Comp;
Comp = record
D : integer;
Next, Pred : PComp
end;
Var
pBeg, pEnd, pKey, pPreComp, pAux: PComp;
где pBeg – указатель начала списка, pEnd – указатель конца списка, pKey, pPreComp, pAux – вспомогательные указатели.
1. Начальное формирование очереди выполняется следующими операторами:
New(pBeg);
pBeg^.Next:=NIL;
pBeg^.Pred:=NIL;
Read(pBeg^.D);
pEnd:=pBeg;
2. Добавление компоненты производится в конец списка с использованием вспомогательного указателя:
New(pAux);
Read(pAux^.D);
pAux^.Pred:=pEnd;
pEnd^.Next:=pAux;
pEnd:=pAux;
pEnd^.Next :=NIL;
Добавление последующих компонент производится аналогично.
3.
Для чтения и вставки компоненты по ключу необходимо выполнить поиск компоненты с заданным ключом:
pKey:=pBeg;
while (pKey<>NIL) and (Key<>pKey^.D) do
pKey:=pKey^.Next;
или
pKey:=pEnd;
while (pKey<>NIL) and (Key<>pKey^.D) do
pKey:=pKey^.Pred;
Здесь Key – ключ, тип которого совпадает с типом данных компоненты.
После выполнения этих операторов указатель pKey будет определять компоненту с заданным ключом или такая компонента не будет найдена.
4. Пусть pKey определяет компоненту с заданным ключом. Вставка новой компоненты выполняется следующими операторами:
New(pAux);
Read(pAux^.D);
pAux^.Next:=pKey^.Next;
pKey^.Next^.Pred := pAux;
pKey^.Next:=pAux;
pAux^.Pred:=pKey;
5. Удаление из списка происходит по-разному в зависимости от того, находится элемент в начале списка, в середине или в конце. Если удаляется первый элемент списка, следует скорректировать указатель pBeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле Next первого элемента. Новый начальный элемент списка должен иметь в своем поле указателя на предыдущий элемент значение nil.
pBeg := pBeg^.Next;
pBeg^.Pred := nil;
Если удаляемый элемент находится в конце списка, требуется сместить указатель pEnd конца списка на предыдущий элемент, адрес которого можно получить из поля Pred последнего элемента. Кроме того, нужно обнулить (присвоить nil) для нового последнего элемента указатель на следующий элемент.
pEnd := pEnd^.Pred;
pEnd^.Next := nil;
Если удаление происходит из середины списка, то единственное, что надо сделать, – обеспечить двустороннюю связь предыдущего и последующего элементов. Удаление компоненты с ключом Key:
pKey^.Pred^.Next := pKey^.Next;
pKey^.Next^.Pred := pKey^.Pred;
После корректировки указателей память из-под удаленных элементов освобождается:
Для удаления компоненты с заданным ключом из односвязного списка необходимо при поиске нужной компоненты помнить адрес предшествующей:
pKey:=pBeg;
while (pKey<>NIL) and (Key<>pKey^.D) do
Begin
pPreComp:=pKey;
pKey:=pKey^.Next
end;
Здесь указатель pKey определяет компоненту с заданным ключом Key, указатель pPreComp содержит адрес предыдущей компоненты. Удаление компоненты с ключом Key выполняется операторами:
pPreComp^.Next:=pKey^.Next;
pKey^.Next^.Pred:=pPreComp;
Стеки
Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек работает по принципу LIFO (Last-In, First-Out) – поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
- начальное формирование стека (запись первой компоненты);
- добавление компоненты в стек;
- выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая – вспомогательная. Пусть описание этих переменных имеет вид:
Type
PStack= ^TStack;
TStack = record
D : integer;
Link : PStack;
end;
var pTop, pAux: PStack;
где pTop – указатель вершины стека; pAux – вспомогательный указатель.
Начальное формирование стека выполняется следующими операторами:
New(pTop)
pTop^.Link := nil;
pTop^.D:=D1;
Последний оператор или группа операторов записывает содержимое поля данных первой компоненты.
Добавление компоненты в стек производится с использованием вспомогательного указателя:
New(pAux);
pAux^.Link:=pTop;
pTop:=pAux;
pTop^.D:=D2;
Добавление последующих компонент производится аналогично.
Выборка компонент из стека. Пусть к моменту начала выборки стек содержит три компоненты:
Первый оператор или группа операторов осуществляет чтение данных из компоненты - вершины стека. Второй оператор изменяет значение указателя вершины стека:
D3:=pTop^.D;
pTop:=pTop^.pNext;
Таким образом, при чтении компонент исключается из стека.
1. Начальное формирование очереди выполняется следующими операторами:
2. Добавление компоненты производится в конец списка с использованием вспомогательного указателя:
