Общая характеристика. В разделе 1 (см. подраздел 1.2) структура данных определяется как множество данных и отношений между ними

В разделе 1 (см. подраздел 1.2) структура данных определяется как множество данных и отношений между ними. Множество – это фундаментальное понятие как в математике, так и в теории вычислительных машин. Тогда как математические множества остаются неизменными, множества которые обрабатываются в ходе выполнения алгоритмов, могут с течением времени разрастаться, уменьшаться, изменять отношения между элементами или подвергаться другим изменениям. Такие множества называются динамическими (dynamic) множествами. Динамические множества представляются динамическими структурами данных.

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

Первоочередное назначение словаря заключается в хранении элементов таким образом, чтобы их можно было легко и быстро обнаружить с помощью ключей. Мотивом для поиска является еще и то, что обычно каждый элемент в словаре помимо поискового ключа хранит дополнительную информацию, однако единственным способом ее получить является ключ. Например, словарь может хранить банковские счета. Каждый счет является объектом, который идентифицируется номером счета и хранит множество дополнительных сведений, включающих текущий баланс, имя и адрес владельца, историю вкладов и расходов. Приложение, которое будет работать со счетом, должно предоставлять его номер в качестве поискового ключа для получения информации, соответствующей счету из словаря.

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

Таким образом, словарь – это динамическое множество элементов, которые идентифицируются значениями ключей. Кроме ключа, каждый элемент словаря содержит сопутствующие данные (satellite data), которые находятся в других его полях, но не используются реализацией множества. Формально словарь D определяется как контейнер пар «ключ-элемент» (key, e), где key – ключ, а е – элемент.

8.2 Таблица – логическое представление словаря

Логически словарь представляется двумерной структурой, которая называется таблицей. Таблица – это множество записей (строк) одинакового формата. В дальнейшем будем считать, что все записи таблицы – одноуровневые. Каждая запись, входящая в таблицу является элементом таблицы. В реляционной алгебре элемент таблицы называется кортежем. Логической структурой таблицы является двумерная фигура, изображаемая в виде последовательности расположенных друг под другом строк одинаковой длины, соответствующих записям таблицы. Одно и то же поле всех записей таблицы образует ее графу или столбец. Пример таблицы приводится на рисунке 8.1.

Рисунок 8.1 - Структура таблицы

Имя столбца (имя одного и того же поля всех записей) называется атрибутом, а индивидуальные значения, появляющиеся в отдельных записях, – значениями атрибута.

В памяти таблица может быть организована по-разному: это может быть вектор записей, плекс, дерево и т. д. В любом случае структура таблицы представляется пользователю, оперирующему с таблицами, в таком виде, который показан на рисунке 8.1.

С каждой записью ассоциируется некоторый ключ (key), который используется для того, чтобы отличить одну запись от другой. Первичный ключ (master, unique key) определяется как такой атрибут, или набор атрибутов, который может быть использован для однозначной идентификации конкретной записи. Говорят, что первичный ключ является уникальным, т. е. никакие две записи в таблице не имеют одинакового значения первичного ключа. Первичный ключ не должен иметь дополнительных атрибутов. Это значит, что если произвольный атрибут исключить из первичного ключа, то оставшихся атрибутов будет недостаточно для однозначной идентификации отдельных элементов таблицы. Не следует путать первичный ключ с главным ключом (major key), по которому записи при сортировке упорядочиваются в первую очередь.

Поскольку любое поле записи может служить в качестве ключа в каком-либо конкретном приложении, то ключи не всегда должны быть уникальными. Например, если в некоторой таблице с фамилиями и адресами название города используется как ключ для некоторого поиска, то он, возможно, не будет уникальным, так как в таблице могут быть две записи с названием одного и того же города. Такой ключ называетсявторичнымключом (secondary, nonunique key).

Соответствие между записью и ключом может быть простым или сложным. В простейшем случае ключ представляется некоторым полем (или набором полей) внутри записи, располагающимся, возможно, с некоторым конкретным сдвигом от начала записи. Такой ключ называетсявнутреннимключом иливстроеннымключом (built-in key). В других случаях ключом является относительная позиция записи внутри таблицы, или имеется некоторая отдельная таблица ключей, которая содержит указатели на записи. Такие ключи называютсявнешнимиключами.

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