Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
69
Добавлен:
06.02.2015
Размер:
1.16 Mб
Скачать

Линейные списки

Списком называется структура данных, каждый элемент которой связывается со следующим элементом посредством указателя. Элемент списка представлен записью, содержащей поле с данными 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.