Структуры данных. Линейные списки. Стек и очередь. Двоичные деревья



Скачать 118.46 Kb.
страница6/6
Дата06.11.2018
Размер118.46 Kb.
Название файла-
1   2   3   4   5   6
Линейные списки

Списком называется структура данных, каждый элемент которой связывается со следующим элементом посредством указателя. Элемент списка представлен записью, содержащей поле с данными Data и указатель Next на следующую запись.

Указатель у последнего элемента списка считаем равным nil Для работы со списком используется указатель на его первый элемент.

type

PList = ^List;



List = record

Data: DataType;

Next: PList;

end;


Var L: PList;

Добавление элемента в начало списка

list1

list2

4 шага добавления

New (Q);list3

Q^.Data:=D;list4

Q^.Next:=L;list5

L:=Qlist6

Добавление элемента в середину списка

после T^

New(Q);

Q^.Data:=D;

Q^.Next:=T^.Next;

T^.Next:=Q; list7

перед T^

New(Q);



Q^:=T^;

T^.Data:=D;

T^.Next:=Q;

Удаление элемента из начала списка

Q:=Llist8

L:=Q^.Next;list9

Dispose(Q);list10

Перебор элементов списка

Просмотр элементов списка осуществляется последовательно, начиная с первого элемента (головы).

Для перемещения вдоль списка воспользуемся переменной T, которая будет последовательно указывать на элементы списка.

T:=L;


while (T<>nil) do begin

writeln(T^.data);

T:=T^.next;

end;


Анализ списков

Быстро (с константной сложностью) выполняются операции добавления, удаления, объединения списков.

Медленно (с линейной) – обход списка. Перебор элементов возможен только в одном направлении. Если нужен перебор в обратном направлении, используются двунаправленные списки.

bilist1

Стек и очередь

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

Поделитесь с Вашими друзьями:
1   2   3   4   5   6


База данных защищена авторским правом ©rppna.ru 2017
обратиться к администрации

    Главная страница