Главная » Java, Структуры данных и алгоритмы » Поддержка локаторов в словаре

0

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

Локаторные методы словаря

Набор операций, применяемых словарем, Д можно расширить методами, использующими локаторы. Вначале введем методы, подобные используемым в очередях с приоритетами, то есть insert(A;,e), remove(/),

replaceElement(/,e) и replace Key (l,к) (п. 7.4.1). Затем определим следующие специфические для словаря локаторные методы:

find(&): возвращает локатор объекта с ключом к или специальный локатор NO_SUCH__KEY, если такого объекта не существует. Input: объект (ключ); Output: локатор. findAll(A:): возвращает итератор локаторов всех объектов с ключом к. Input: объект (ключ); Output: итератор (локаторов).

И наконец, введем локаторные методы, специфические для упорядоченного словаря:

beforе(/): возвращает локатор объекта с ключом, наибольшим в D и меньшим /.кеу(). Input: локатор; Output: локатор. after(/): возвращает локатор объекта с ключом, наименьшим в D и большим /.кеу(). Input: локатор; Output: локатор. closestBefore(A;): возвращает локатор объекта с ключом, наибольшим в D и меньшим или равным к. Input: локатор; Output: локатор. closestAfter(A;): возвращает локатор объекта с ключом, наименьшим в D и большим или равным к. Input: локатор; Output: локатор. first(): возвращает локатор объекта с наименьшим ключом в D.

Input: отсутствует; Output: локатор. last(): возвращает локатор объекта с наибольшим ключом в D. Input: отсутствует; Output: локатор.

Описанные методы возвращают локатор BOUNDARY_VIOLATION при попытке получить доступ к объекту, расположенному перед объектом с наименьшим ключом, или к объекту, расположенному после объекта с наибольшим ключом. Такое может случиться, например, при вызове before(first) или after(last).

Контейнеры на основе ключей

Как абстрактные типы данных, очереди с приоритетами и словари используют при хранении понятие парных объектов «ключ-элемент», поддерживают локаторную модель и содержат несколько общих методов. Ниже речь пойдет о более универсальном типе данных, названном контейнер на основе ключей (key-based container), представляющем собой контейнер объектов «ключ-элемент», доступ к которым осуществляется посредством методов работы с ключами.

Возвращаясь к понятию инспектирующего контейнера (inspectable container) (раздел 5.6), определим Java-интерфейс для контейнера на основе ключей (рис. 8.13): InspectableContainer, InspectableKeyBasedContainer, KeyBasedContainer, InspectablePriorityQueue, InspectableDictionary, Dictionary, InspectablerderedDictionary и OrderedDictionary.

Рис. 8.13. Иерархия наследования АТД, представляющего контейнер на основе ключей. Показаны только методы доступа через локаторы и методы обновления

Реализация локаторных методов словаря

Реализацию словаря, созданную на основе хеш-таблицы, регистрационного файла, поисковой таблицы и skip-списка, обсуждавшихся в этой главе, можно расширить с помощью подхода, аналогичного примененному при расширении реализации очереди с приоритетами в п. 7.4.2. А именно, реализуем локатор, дополнив объект «ключ-элемент» позиционной ссылкой. Это возможно, поскольку локаторы привязываются к объектам (в действительности они хранят объекты), и требуется отслеживать позиции размещения объектов и обновлять позиционные ссылки в локаторах. Оставим вопрос расширения для упражнений.

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

По теме:

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