- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Включение и исключение в дереве
Рассмотрим некоторые особенности операций включения и исключения в любом m‑арном дереве.
Включение в дереве
Включаемым в дерево объектом является некоторое (другое) дерево, которое затем станет поддеревом. При выполнении операции включения должны быть заданы:
включаемое поддерево (т. е. в памяти должна существовать соответствующая древовидная структура),
та вершина исходного дерева, к которой «подвешивается» в качестве ветви включаемое дерево и
индекс, назначаемый поддереву и определяющий старшинство его корня среди сыновей вершины подключения.
В результате операции включения поддерева Y в вершину Х исходного дерева степень исхода вершины Х увеличивается на единицу и у этой вершины появляется еще один сын. При этом в общем случае потребуется заново перенумеровать вершины-сыновья узла X.
Исключение в дереве
Исключаемым объектом, применительно к произвольному дереву, является некоторое поддерево. В операции исключения следует указать вершину исходного дерева, играющую роль корня исключаемого поддерева, и номер (или индекс) исключаемого поддерева, поскольку одна вершина в зависимости от ее степени исхода может играть роль корня для разных поддеревьев.
Пусть Х некоторая вершина произвольного дерева, а вершины, Y1 ..., Yn ее сыновья. Тогда исключение i-ого поддерева вершины Х означает уменьшение степени исхода Х на единицу и удаление из исходного дерева ветви Х Yi , и поддерева, корнем которого служит вершина Yi. В результате такого удаления вершина Х может стать листом.
Поиск
Поиск: определение и общая терминология
Любая таблица (словарь) содержит информацию, которая может быть полезна при решении каких-либо информационных задач. Часто для решения задачи требуется не вся содержащаяся в таблице информация, а лишь несколько записей или даже одна запись. И для того чтобы получить доступ к требуемой записи, необходимо ее найти, т. е. выполнить поиск в таблице.
Дадим определение. Поиск (searching, retrieval) это алгоритм, который воспринимает некоторый аргумент ArgSearch и пытается локализовать (найти, определить) запись, ключ которой равен ArgSearch. Значение ArgSearch называется аргументом поиска.
Алгоритм поиска может возвратить всю найденную запись или чаще всего может возвратить некоторый указатель на эту запись. Поиск, по завершении которого найдена запись с ключом, равным аргументу поиска, называется успешным или результативным. Успешный поиск часто завершается извлечением. Однако возможно, что поиск некоторого конкретного аргумента в таблице является неудачным (безрезультатным), т. е. в данной таблице не существует записи с этим аргументом в качестве ключа. В этом случае такой алгоритм может возвратить некоторую специальную «пустую запись» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или к установке во флаге некоторого конкретного значения, которое указывает, что искомая запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с аргументом ArgSearch в качестве ключа. Алгоритм, который выполняет эту функцию, называется алгоритмом поиска и вставки.
В некоторых случаях бывает желательно вставить некоторую запись с первичным ключом Key в некоторую таблицу без первоначального поиска другой записи с этим же самым ключом. Такая ситуация могла бы возникнуть, если бы уже было определено, что такой записи нет в файле. В таких случаях необходимо различать ситуации, относящиеся к поиску, к вставке или к поиску со вставкой.
Как указывалось ранее, таблица может быть физически организована по-разному. Это может быть массив записей, связанный список, дерево или даже граф. Поскольку различные методы поиска могут соответствовать различным организациям таблиц, то таблица часто строится, исходя из соображений конкретного метода поиска. Такая таблица может полностью располагаться в оперативной памяти, или во вспомогательной памяти, или там и там. Ясно, что для разных организаций таблиц необходимы различные методы поиска. Методы поиска, при которых вся таблица постоянно находится в оперативной памяти, называются методами внутреннего поиска, а те методы, для которых большая часть таблицы хранится во вспомогательной памяти (такой, как диск или лента), называются методами внешнего поиска. Мы будем рассматривать только внутренний поиск.
Ниже рассматриваются алгоритмы (методы) операций в таблицах. Некоторые алгоритмы поясняются программными текстами, написанными на алгоритмическом языке Pascal. Поэтому необходимо определить некоторые переменные и структуру таблицы.
В языке Pascal имеется тип, подходящий для описания типа элементов таблицы, – это тип Record (запись), следовательно, тип элемента таблицы может быть задан, например, как
Type
(10.1)
Key: Word;
{описания других полей}
end;
где Key это поле-ключ, в котором размещается значение ключа, идентифицирующее элемент,
«другие поля» поля для размещения тех полезных данных, которые должны содержаться в записи.
Излагаемые ниже методы оперируют с отдельными записями таблицы, используя единственно возможный способ доступа к записям – доступ по ключу. Значит ключ «с точки зрения» этих методов единственная существенная компонента, и нет необходимости как-то описывать остальные поля. Выбор в качестве типа ключа целого типа (Word) достаточно произволен; точно так же можно использовать и любой тип, на котором задано отношение порядка.
Тип таблицы определим как
TTable = Array [0.. HighIndex] Of TElement; (10.2а)
Тогда сама таблица может быть определена как
Var a: TTable; (10.2б)
иначе говоря, таблица представляется как последовательность элементов а[0], a[1],…, a[HighIndex], каждый из которых является записью типа TElement. Представление таблицы в виде массива необязательно; для нас важен порядок следования элементов, который задается с помощью индекса.
Зададим некоторые переменные:
N, HighIndex: Integer;
где N количество активных элементов, HighIndex максимальное значение индекса активного элемента. Индексы вектора а начинаются с нуля, поэтому HighIndex = N - 1.