Нелинейные структуры

Введение в динамическую переменную двух и более полей указателей создает возможность получать нелинейные структуры.

Примеры нелинейных структур:

a) Текст

Текст

б) Двоичное дерево

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

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

Схема двоичного дерева

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

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

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

Схема направленного графа

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

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

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

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

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

Список упорядоченных элементов в виде двоичного дерева

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

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

birec = record
	I: integer;
	pred, succ: intp
end;

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

Добавить комментарий