Основные операции с линейными списками
Списком называется последовательность однотипных элементов, связанных между собой указателями. Будем считать, что элементы списка имеют тип tLE, указатели на элементы списка имеют тип pLE.
X: tLE p: pLE
Next |
Data |
Рисунок 13 Указатель на элемент списка
Поле Next является указателем на элемент списка и может занимать произвольное место в структуре элемента. Однако если оно является первым элементом структуры, то его адрес совпадает с адресом элемента списка, и это позволяет оптимизировать многие операции со списками. Поле Data содержит информацию, которая будет учитываться при сортировке.
Рассмотрим два вида списков: стек и очередь. Стек характеризуется тем, что новый элемент добавляется в начало последовательности, а удаляться может только первый элемент списка. При добавлении в очередь новый элемент ставится в конец списка, удаляется первый элемент последовательности.
Рассмотрим основные операции со стеком и очередью. Для работы со стеком необходимо иметь указатель на начало списка. Обозначим его Head. При работе с очередью требуется дополнительный указатель на конец очереди. Обозначим его Tail. Иногда при работе с очередью удобно объединять указатели Head и Tail в виде полей некоторой переменной Queue.
Добавление элемента по адресу р в стек.
Head
2) 1)
p
1) p→Next:=Head
2) Head:=p
Рисунок 14 Добавление в стек
Удаление из стека или очереди (при условии, что список не пуст, т.е. Head≠NIL)
p
Head 1)
2)
1) p:=Head
2) Head:=p→Next
<освободить память по адресу p>
Рисунок 15 Удаление из стека
Добавление элемента по адресу р в очередь.
H
ead
2)
Tail
1)
3)
p
Рисунок 16 Добавление в очередь
1) p→Next:=NIL
2) IF (Head≠NIL) Tail→Next:=p
ELSE Head:=p
FI
3) Tail:=p
Операцию добавления элемента в очередь можно оптимизировать в случае, если поле Next является первой компонентой элемента очереди и его адрес совпадает с адресом всего элемента. Зададим пустую очередь следующим образом:
Head
Tail:=@Head
Tail
Рисунок 17 Структура очереди
Эту операцию назовем инициализацией очереди. Тогда добавление элемента в очередь будет происходить в два раза быстрее:
Head 1) p
Tail
2)
Рисунок 18 Добавление в очередь
1) Tail->Next:=p
2) Tail:=p
Перемещение элемента из начала списка List в конец очереди Queue.
3)
List
1)
Head
Queue
2)
Tail
Рисунок 19 Перемещение элемента
1) Queue.Tail→Next:=List
2) Queue.Tail:=List
3) List:=List→Next