Главная » Java, Структуры данных и алгоритмы » Абстрактный тип данных «словарь»

0

Словарь хранит пары «ключ-элемент» (к,е), где к — ключ, а е — элемент. Для обеспечения полноты универсальности будем считать, что ключ и элемент могут быть представлены любыми типами объектов (см. рис. 8.1). Например, словарь сведений о студентах (имя, адрес, оценки по предметам) в качестве ключей может использовать номера студенческих билетов. В некоторых приложениях ключом может служить сам элемент. Например, в словаре простых чисел в качестве ключей (и, конечно, элементов) могут использоваться сами числа.

Рис. 8.1. Концептуальная иллюстрация АТД «словарь». Пользователь присваивает каждой дискете ключ (наклейку). Получаемые объекты (дискеты с наклейками) вводятся в словарь (коробку для дискет). Впоследствии ключи используются для поиска или удаления дискет

Различают два типа словарей: неупорядоченный и упорядоченный. В обоих случаях ключ используется в качестве идентификатора, предписанного данному элементу пользователем или приложением. В упорядоченном словаре для ключей устанавливаются правила отношений полного упорядочения, для чего применяются дополнительные методы, отвечающие за соблюдение этих отношений. Упорядоченный словарь определяет относительное соотношение двух ключей с помощью компаратора (см. п. 7.1.4), предоставляемого словарю в качестве параметра метода конструктора упорядоченного словаря. В неупорядоченном (обычном) словаре также предполагаются упорядоченные отношения между ключами, но при этом используется обычное сравнение ключей.

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

АТД «словарь»

Как абстрактный тип данных, словарь D поддерживает следующие методы:

size(): возвращает количество объектов в D. Input: отсутствует; Output: целое число. isEmpty(): проверяет, является ли D пустым.

Input: отсутствует; Output: boolean. elements(): возвращает элементы, хранящиеся в D.

Input: отсутствует; Output: итератор объектов (элементы).

keys(): возвращает ключи, хранящиеся в D.

Input: отсутствует; Output: итератор объектов (ключи). findElement(A;): если D содержит объект с ключом, равным к, то возвращается элемент этого объекта, в противном случае возвращается специальный элемент NO_SUCH_KEY. Input: объект (ключ); Output: объект (элемент). findAHElements(A;): возвращает итератор всех элементов с ключами, равными к.

Input: объект (ключ); Output: итератор (элементов), insertItem(A;,e): вводит в Z) объект с элементом е и ключом к.

Input: объекты к (ключ) и е (элемент); Output: отсутствует.

removeElement(A;): удаляет из D объект с ключом, равным к, и возвращает его элемент. Если в D такой элемент отсутствует, возвращается специальный объект NO_SUCH_KEY. Input: объект (ключ); Output: объект (элемент).

remove AllElements(/;): удаляет из D объекты с ключом, равным к, возвращает итератор их элементов. Input: объект (ключ); Output: итератор (элементов).

Если операции findElement(A:) и removeElement(A;) не выполняются (то есть словарь D не содержит объекта с ключом, равным к), согласно общепринятой договоренности возвращается специальный элемент NO_SUCH_KEY. Этот элемент принято называть сигнальным сообщением (sentinel). Можно было бы применять альтернативную возможность и возвращать null. Но в таком случае не удастся хранить в словаре D объект с нулевым элементом. Еще одним вариантом при запросе отсутствующего в словаре ключа может быть генерация специального исключения. Тем не менее это не самый удачный сйособ, поскольку в запросе отсутствующей в словаре информации нет ничего необычного. Более того, генерация и перехват исключений обычно происходит медленнее по сравнению с возвратом специального элемента. Следовательно, использование такого элемента эффективнее с точки зрения производительности (и в этом случае — концептуально более обоснованно).

Обратите внимание, что, как уже указывалось, словарь D может содержать различные объекты с одинаковыми ключами. В подобном случае операции fmdElement(A:) и removeElement(/:) возвращают произвольный элемент, ключ которого равен к. Точно так же, если требуется сохранить объект е в словаре таким образом, чтобы объект явился одновременно и ключом, то е должно задаваться с помощью метода insertltem(e,e).

Пример 8.1. Ниже приводятся результаты серии операций над изначально пустым словарем, хранящим целочисленные ключи и односимвольные элементы. Столбец «словарь» несколько вводит в заблуждение, поскольку в нем показаны объекты, отсортированные по ключам. Для словаря это не обязательно. Способ сортировки объектов в словаре зависит от реализации.

Определители равенства

Каждая операция стандартного словаря, приведенного выше, требует наличия некоего механизма определения равенства двух ключей. При работе с упорядоченным словарем для этого применяется компараторный метод are Equal (rf. 7.1.4), ассоциируемый со словарем. Для обычных словарей используем определитель равенства (equality tester) — объект, поддерживающий операцию are Equal над ключами.

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии