НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

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

До сих пор мы рассматривали линейные структуры динамических переменных.

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

а) Текст


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


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


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


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


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

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

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

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

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

Рис. 11
Рис. 11

Время поиска в двоичном дереве сокращается по сравнению с линейной структурой с


где N - число узлов в дереве. Компоненту двоичного дерева можно представить переменной типа


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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь