Двунаправленные списки

Туре

PStroka = ^{^}Stroka; Stroka = record

Info:string;

Sled: PStroka; End;.

Здесь вначале объявлен типизированный указатель (pstroka) с базовым типом запись (stroka), а затем сам базовый тип. Звездочка на рис. 40 пред-

ставляет указатель Sled, a info - содержательную информацию. Следует обратить внимание, что синтаксически разрешается вначале объявлять ука­затель на несуществующий базовый тип, который обязательно далее должен быть объявлен.

Рис- 40

Построим теперь список, например, из трех элементов. Пусть перемен­ные si, 82, S3 содержат некоторую полезную информацию в виде строк, и пусть объявлены переменные: Var spisok, P:PStroka;. Переменная Spisok будет использована для хранения всего списка, ар- вспомогатель­ный указатель. Напишем такой код для решения задачи:

New(Spisok); {Начало списка}

Spisok^A. Info:=S1; {Запись строки SI в список}

New(P); {Новый элемент списка}

P^.Info:=S2; {Запись строки S2 в элемент Р}

Spisok^.Sled:=P; {Подключение элемента два в список}

New(P); {Третий элемент списка}

P^.Info:=S3; {Запись строки S3 в элемент Р}

Spisok^. Sled^.Sled:=P; { Подключение элемента 3 в список}

P^.sled:=nil; {Конец списка}

P:=nil; {Теперь указатель Р не нужен}

В соответствии с этим кодом процесс формирования списка можно представить схематично так, как изображено на рис. 41.

Рис. 41

Связанный список дает варианты альтернативного представления масси­вов. Отличие заключается в том, что число элементов в списке заранее неиз­вестно. Однако на этапе вьшолнения программы памяти под список выделя­ется ровно столько, сколько требуется для записи его элементов.

Основными операциями, которые выполняются при работе с динамиче­скими структурами данных, являются следующие: добавление элемента, исключение элемента, поиск заданного элемента.

Структура двунаправленного связанного списка приводится на рис. 42. Данная структура соответствует следующему объявлению:

Type PStroka = ^AStroka; Stroka = record

Info:string;

Pred,Sled: PStroka; End;.

Рис. 42

Для построения связей между отдельными элементами списка исполь­зуются два указателя: Pred - связь с предыдущим элементом и sled - связь с последующим элементом. Соответственно имеет место ограничение связей элементов списка и слева, и справа с помощью пустого указателя nil. По­строим список из трех элементов, как в Предыдущем случае, и при условиях предыдущей задачи.

New(Spisok); Spisok^A.Info:=S1; Spisok^A.Pred:=nil; Hew (P); P^A.Info:=S2; P^A.Pred:=Spisok; Spisok^A.Sled:=P; New{P); P^A.Info:=S3; P^A.Pred:=Spisok^A.Sled; Spisok^A.Sled^A.Sled:=P; P^A.sled:=nil; P:=nil;.

{Начало списка}

{Запись строки SI в список}

{Ограничение связей списка слева}

{Новый элемент списка}

{Запись строки S2 в элемент Р}

{Связь с предыдущим элементом}

{Подключение элемента два в список}

{Третий элемент списка}

{Запись строки S3 в элемент Р}

{Связь с предыдущим элементом}

{Подключение элемента 3 в список}

{Конец списка}

На основе двунаправленного списка возможно формирование кольцевых связанных списков, когда самый первый элемент списка ссылается на по­следний элемент, а последний - на первый элемент.

Тогда получим структуру дерева, представленную на рис. 43. Структуру би­нарного дерева синтаксически можно объявить следующим образом:

СТЕКИ, ОЧЕРЕДИ

Предполагается, что элементы в списках могут добавляться и извлекать­ся в произвольном порядке. Существуют списки с заранее заданными проце­дурами добавления и извлечения элементов. Это стеки и очереди. Очередью называется однонаправленный или двунаправленный связанный список с процедурой работы FIFO - First In, First Out (первым пришел, первым ушел). В списках типа очередь элемент добавляется в конец списка, а извле­кается из начала списка. Стек - связанный список с процедурой работы LIFO - Last In, First Out (последним пришел, первым ушел). Элементы стека добавляются в конец списка и извлекаются из конца списка.

Идентифицируется очередь с помощью двух указателей: запоминается начало очереди и конец списка. Стек можно идентифицировать одним указа­телем, помечая дно стека с помощью nil.

БИНАРНЫЕ ДЕРЕВЬЯ

Содержательную информацию часто требуется как-то ранжировать. С целью ранжирования информации вводится понятие ключа. Например, в шахматных программах очередные ходы помечают с помощью числовых критериев оценки текущей позиции. Одним из способов представления ран­жированной информации является бинарное дерево.

Бинарное дерево, по определению, - это иерархическая структура, схе­матично представляемая, например, так, как показано на рис. 43.

Рис.43

Бинарное дерево имеет узлы, в которые может входить одна ветвь, а вы­ходить не более двух (бинарное). Верхняя вершина не имеет входа и называ­ется корнем. Построить бинарное дерево можно следующим образом. Пусть имеется набор числовых оценок для некоторого ключа, например, такой: 35, 86, 49, 27, 31, 56, 62, 44, 29, 26, 33, 88. Примем, что вправо по ходу дерева, начиная от корня, значение ключа увеличивается, а влево - уменьшается.

Дата добавления: 2014-12-29