- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Представление дерева в памяти
Естественное представление дерева
Дерево может быть представлено в машинной памяти в форме многосвязного списка, в котором каждый логический указатель соответствует ребру древовидного графа. При таком представлении каждому узлу дерева ставится в соответствие элемент многосвязного списка, причем в каждом элементе резервируются следующие поля:
поля, содержащие полезные данные;
поле степени исхода;
поля логических указателей; их общее число в одном узле равно степени дерева, но в каждый момент времени количество непустых логических указателей равно степени исхода соответствующей вершины дерева.
На рисунке 9.3 показана логическая структура спискового представления дерева, изображенного на рисунке 9.1. Такое представление называют естественным представлением дерева. Все элементы дерева при этом имеют один и тот же тип. Тип элемента дерева, назовем этот тип Tvertex, называется базовым типом для дерева.
Рисунок 9.3 Естественное представление дерева
Теперь можно сформулировать рекурсивное определение дерева: дерево типа Tvertex это
а) либо пустое дерево,
б) либо некоторая вершина типа Tvertex, называемая корнем, с конечным числом связанных с ней поддеревьев, имеющих базовый тип Tvertex.
При естественном списковом представлении дерева обязательно должен быть организован указатель (курсор) на корневую вершину, обеспечивающий доступ к дереву. На рисунке 9.3 курсором корня является указатель Root. Иногда в элементе списка, соответствующем вершине дерева, размещают указатель, направленный к родительскому узлу, это упрощает реализацию некоторых алгоритмов обработки деревьев.
Базовый тип (Tvertex) и курсор корня (Root) для дерева степени 3 можно описать нотациями языка Pascal, представленными ниже. Очевидно, при таком объявлении типа Tvertex количество полей для размещения структурных указателей фиксируется описанием типа Pchild. Если имеются основания предполагать, что при выполнении операций в дереве степень дерева потребуется увеличить, то это нужно предусмотреть в описании типа Pchild.
Type
Pvertex = ^Tvertex;
Pchild = Array [0..2] Of Pvertex;
Tvertex = Record
Dat: <поля данных>;
CountChild: Integer;
arrPchild: Pchild;
End;
Var Root: Pvertex;
Представление дерева с помощью вектора
Возможно, самым простым представлением дерева будет одномерный массив (вектор), в котором каждый элемент соответствует отдельной вершине и содержит два поля: поле данных и поле курсора родителя. Поле курсора некоторого элемента будет содержать индекс того элемента, который является родителем данного элемента. Если предположить, что поле Dat предназначено для хранения меток вершин дерева, то векторное представление дерева, показанного на рисунке 9.1, может быть представлено рисунком 9.4.
Рисунок 9.4 Представление дерева с помощью вектора, в котором каждая вершина содержит курсор на вершину‑родитель в виде его индекса
Поскольку элемент-корень не имеет родительского узла, то его курсор равен -1, т. е. он не указывает ни на какую другую вершину дерева. Такое представление использует то свойство деревьев, что каждая вершина, отличная от корня, имеет только одного родителя. Используя это представление можно легко организовать переходы от вершины к ее родителю, от него к его родителю и т. д. С другой стороны, использование встроенных курсоров на родителей делает крайне сложными алгоритмы переходов от родителей к сыновьям.
Такой массив для дерева может быть объявлен следующим образом:
Type
Tvertex = Record
Dat: <поля данных>;
РarentCursor: Integer;
End;
Ttree = Array [0..maxVertex] Of Tvertex;
Var Tree: Ttree;
Если необходимо организовать переходы от родителей к сыновьям, то в дополнение к имеющимся полям (поле курсора на родителя можно оставить) следует добавить поля курсоров на сыновей, число которых соответствует максимально возможной степени дерева. В этом случае дерево можно описать следующим образом:
Type
TchildCursors = Array[0..maxChild] Of Integer;
Tvertex = Record
Dat: <поля данных>;
РarentCursor: Integer;
ChildCursors: TchildCursors;
End;
Ttree = Array [0..maxVertex] Of Tvertex;
Var Tree: Ttree;
В этом случае логическая структура дерева из рассматриваемого примера, может быть представлена рисунком 9.5.
Рисунок 9.5 Представление дерева с помощью вектора, в котором каждая вершина содержит курсоры как на родительские вершины, так и на вершины-сыновья
Очевидно, старшинство сыновей, на которые указывают курсоры, возрастает с увеличением индекса поля-массива ChildCursors. Несуществующим (пустым) ссылкам соответствует значение курсора -1.
Легко заметить, что повышение гибкости такого представления по сравнению с предыдущим вариантом векторной организации связано с дополнительными затратами памяти, вызванными необходимостью хранения пустых ссылок.