10.Линейные списки. Очередь. Стек
..docЛинейные списки
Списком называется структура данных, каждый элемент которой связывается со следующим элементом посредством указателя. Элемент списка представлен записью, содержащей поле с данными Data и указатель Next на следующую запись.
Указатель у последнего элемента списка считаем равным nil Для работы со списком используется указатель на его первый элемент.
type
PList = ^List;
List = record
Data: DataType;
Next: PList;
end;
Var L: PList;
Добавление элемента в начало списка
4 шага добавления
New (Q);
Q^.Data:=D;
Q^.Next:=L;
L:=Q
Добавление элемента в середину списка
после T^
New(Q);
Q^.Data:=D;
Q^.Next:=T^.Next;
T^.Next:=Q;
перед T^
New(Q);
Q^:=T^;
T^.Data:=D;
T^.Next:=Q;
Удаление элемента из начала списка
Q:=L
L:=Q^.Next;
Dispose(Q);
Перебор элементов списка
Просмотр элементов списка осуществляется последовательно, начиная с первого элемента (головы).
Для перемещения вдоль списка воспользуемся переменной T, которая будет последовательно указывать на элементы списка.
T:=L;
while (T<>nil) do begin
writeln(T^.data);
T:=T^.next;
end;
Анализ списков
Быстро (с константной сложностью) выполняются операции добавления, удаления, объединения списков.
Медленно (с линейной) – обход списка. Перебор элементов возможен только в одном направлении. Если нужен перебор в обратном направлении, используются двунаправленные списки.
Стек и очередь
Стек - структура данных, в которой удалить можно только тот элемент, который был добавлен последним (LIFO).
Для реализации стека можно использовать линейный список, у которого сохранен указатель на голову списка. Операции добавления и удаления производятся в голове списка. У пустого стека указатель равен nil.
Очередь - структура данных, в которой удалить можно только тот элемент, который был добавлен первым (FIFO). Для реализации очереди используется линейный список с двумя указателями: на голову и хвост. Добавление происходит в хвост, а удаление - из головы списка.
Реализация стека массивом
Массив A[0..N-1]. Для стека требуется один указатель на голову h.
При добавлении элемента в голову стека записываем значение и увеличиваем указатель h.
A[h]:=k;
h:=(h+1) mod N;
Для удаления из головы стека требуется обратная операция:
h:=(h -1+N) mod N;
k:=A[h];
Реализация очереди массивом
Указатель на голову – h, на хвост – t.
Добавление в хвост очереди:
A[t]:=k;
t:=(t+1) mod N;
Удаление из головы очереди:
k:=A[h];
h:=(h+1) mod N;
Очередь пуста, если h=t.