Нелинейные динамические структуры. Деревья.

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

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

Работать с двусвязными списками намного проще чем с односвязными, так как мы можем двигаться по списку и слева направо (из начала в конец), и справа налево (из конца в начало). Но при этом мы должны будем запомнить и хранить уже два указателя: r – на начало списка и q – на конец списка.

Type point=^list;

List=record

X:byte;

Next, prev:point;

End;

2.Структура текста, разбитого на слова.

3.Двоичное дерево

можно представить так:

4.Направленный граф

можно представить так:

2. Текст – это связанная структура. Ее элементы представляют собой записи с тремя полями: первое поле содержит текстовую информацию (например, слово), второе поле либо указывает на первый элемент следующей строки, либо имеет значение Nil, третье – на следующий элемент данной строки.

3. Компонента двоичного дерева имеет также три поля: первое поле содержит основную информацию (число, символ, слово и т.д.), а второе и третье поля содержат ссылки на предыдущую и последующую компоненты дерева. Для некоторых компонентов дерева одно из этих полей либо оба имеют значение Nil.

4. Посредством ссылок можно выразить все связи в структуре, моделирующей направленный граф: вершинам графа соответствуют сами динамические переменные, а ребрам – ссылки.

Узлом называют переменную, содержащую два различных, отличных от Nil, значения указателя. Так, узловые элементы текста содержат ссылки на очередной элемент данной строки и на первый элемент следующей строки.

Нелинейные структуры удобны для задач поиска. Список упорядоченных элементов в виде двоичного дерева:

Узел 4 называется корнем дерева. Вход в дерево происходит только через корень. Для каждого узла различаются левое и правое поддеревья. Упорядоченность элементов следующая: элементы левого поддерева меньше узла и меньше элементов правого поддерева.

Время поиска в двоичном дереве сокращается по сравнению с линейной структурой с ~N до log₂N, где N – число узлов в дереве. Компоненту двоичного дерева можно представить переменной типа

Каждая такая переменная содержит три поля: поле целого значения – поле I, поле указателя на предыдущий (в смысле упорядоченности) элемент – поле pred и поле указателя на последующий элемент – поле succ.

Алгоритм построения дерева:

Всегда при добавлении вершины к дереву алгоритм начинает работу с корня. Если ее значение больше, чем значение корня, то идем по правым веточкам, если меньше – по левым, пока не найдется ей место

Алгоритм добавления вершины подобен алгоритму построения дерева.

Type tree=^elem;

Elem=record

K:byte;

Left, right: tree;

End;

Var p: tree;

New (p);

Удаление вершины:

- Нашли удаляемую вершину

- Идем шаг налево, и потом до конца направо, или один шаг вправо и до конца налево.

Обход дерева. Вывод информации на экран.