- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Динамические множества и словари
Общая характеристика
В разделе 1 (см. подраздел 1.2) структура данных определяется как множество данных и отношений между ними. Множество – это фундаментальное понятие как в математике, так и в теории вычислительных машин. Тогда как математические множества остаются неизменными, множества которые обрабатываются в ходе выполнения алгоритмов, могут с течением времени разрастаться, уменьшаться, изменять отношения между элементами или подвергаться другим изменениям. Такие множества называются динамическими (dynamic) множествами. Динамические множества представляются динамическими структурами данных.
Некоторые алгоритмы, предназначенные для обработки множеств, требуют выполнения операций нескольких различных видов. Например, во многих алгоритмах используется набор операций, который ограничивается возможностью вставлять элементы в множество, удалять их, а также проверять, принадлежит ли множеству тот или иной элемент. Для выполнения последней (третьей) из названных операций во множестве организуется поиск. Динамическое множество, поддерживающее перечисленные операции, называется словарем (dictionary).
Первоочередное назначение словаря заключается в хранении элементов таким образом, чтобы их можно было легко и быстро обнаружить с помощью ключей. Мотивом для поиска является еще и то, что обычно каждый элемент в словаре помимо поискового ключа хранит дополнительную информацию, однако единственным способом ее получить является ключ. Например, словарь может хранить банковские счета. Каждый счет является объектом, который идентифицируется номером счета и хранит множество дополнительных сведений, включающих текущий баланс, имя и адрес владельца, историю вкладов и расходов. Приложение, которое будет работать со счетом, должно предоставлять его номер в качестве поискового ключа для получения информации, соответствующей счету из словаря.
Компьютерный словарь подобен своему бумажному аналогу в том смысле, что оба используются для поиска информации. Однако компьютерный словарь более динамичен, так как поддерживает операции вставки, удаления и изменения содержимого элементов. Следовательно, программный тип данных, определяющий словарь, должен иметь методы вставки, удаления и поиска элементов по ключам.
Таким образом, словарь – это динамическое множество элементов, которые идентифицируются значениями ключей. Кроме ключа, каждый элемент словаря содержит сопутствующие данные (satellite data), которые находятся в других его полях, но не используются реализацией множества. Формально словарь D определяется как контейнер пар «ключ-элемент» (key, e), где key – ключ, а е – элемент.
Таблица – логическое представление словаря
Логически словарь представляется двумерной структурой, которая называется таблицей. Таблица – это множество записей (строк) одинакового формата. В дальнейшем будем считать, что все записи таблицы – одноуровневые. Каждая запись, входящая в таблицу является элементом таблицы. В реляционной алгебре элемент таблицы называется кортежем. Логической структурой таблицы является двумерная фигура, изображаемая в виде последовательности расположенных друг под другом строк одинаковой длины, соответствующих записям таблицы. Одно и то же поле всех записей таблицы образует ее графу или столбец. Пример таблицы приводится на рисунке 8.1.
Рисунок 8.1 Структура таблицы
Имя столбца (имя одного и того же поля всех записей) называется атрибутом, а индивидуальные значения, появляющиеся в отдельных записях, – значениями атрибута.
В памяти таблица может быть организована по-разному: это может быть вектор записей, плекс, дерево и т. д. В любом случае структура таблицы представляется пользователю, оперирующему с таблицами, в таком виде, который показан на рисунке 8.1.
С каждой записью ассоциируется некоторый ключ (key), который используется для того, чтобы отличить одну запись от другой. Первичный ключ (master, unique key) определяется как такой атрибут, или набор атрибутов, который может быть использован для однозначной идентификации конкретной записи. Говорят, что первичный ключ является уникальным, т. е. никакие две записи в таблице не имеют одинакового значения первичного ключа. Первичный ключ не должен иметь дополнительных атрибутов. Это значит, что если произвольный атрибут исключить из первичного ключа, то оставшихся атрибутов будет недостаточно для однозначной идентификации отдельных элементов таблицы. Не следует путать первичный ключ с главным ключом (major key), по которому записи при сортировке упорядочиваются в первую очередь.
Поскольку любое поле записи может служить в качестве ключа в каком-либо конкретном приложении, то ключи не всегда должны быть уникальными. Например, если в некоторой таблице с фамилиями и адресами название города используется как ключ для некоторого поиска, то он, возможно, не будет уникальным, так как в таблице могут быть две записи с названием одного и того же города. Такой ключ называется вторичным ключом (secondary, nonunique key).
Соответствие между записью и ключом может быть простым или сложным. В простейшем случае ключ представляется некоторым полем (или набором полей) внутри записи, располагающимся, возможно, с некоторым конкретным сдвигом от начала записи. Такой ключ называется внутренним ключом или встроенным ключом (built-in key). В других случаях ключом является относительная позиция записи внутри таблицы, или имеется некоторая отдельная таблица ключей, которая содержит указатели на записи. Такие ключи называются внешними ключами.
В реляционной базе данных каждая таблица хранится в отдельном файле. Поэтому таблицу в литературе часто называют файлом. Структура такого файла довольно проста, поскольку все записи имеют одинаковый формат.