Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Общая характеристика. Динамические множества и словари

Динамические множества и словари

Дек

Особым типом последовательного списка с переменной длиной является дек (deque). Другие названия дека - двухсторонняя очередь, очередь с двумя концами (double ended queue). Дек – это такой последовательный список, в котором как включение, так и исключение могут выполняться с любого из двух концов.

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

Структура дека аналогична структуре обычной очереди. Однако применительно к деку вместо хвоста и головы говорят о правом и левом концах.

 


В разделе 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). В других случаях ключом является относительная позиция записи внутри таблицы, или имеется некоторая отдельная таблица ключей, которая содержит указатели на записи. Такие ключи называются внешнимиключами.

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

<== предыдущая лекция | следующая лекция ==>
Очередь | Общая характеристика и некоторые определения
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 529; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.