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

0

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

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

Методы контейнера, описанные в его АТД, можно отнести к четырем основным категориям:

•          методы запросов возвращают информацию о контейнере или его отдельных элементах (например, метод size). Эта информация, как правило, имеет логический или целый тип;

•          методы доступа возвращают элементы или позиции контейнера (например, метод first в последовательности);

•          методы обновления изменяют контейнер, добавляя элементы (например, метод вектора insertAtRank), удаляя элементы (например, метод дека deque) или изменяя отношения между элементами (например, метод списка swapElements).

Кроме того, конкретная реализация контейнера должна поддерживать

•          методы конструктора, создающие экземпляр контейнера. Например, в классе NodeList описан конструктор, который возвращает пустой список (см. фрагмент кода 5.8).

Инспектирующие контейнеры

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

Очевидно, что инспектирующие контейнеры не могут быть использованы, если в ходе выполнения операций над контейнером его элементы должны изменяться. Однако с помощью иерархии наследования можно применить все возможности защиты инспектирующих контейнеров.и в то же время применять методы обновления. Рассмотрим, например, АТД «вектор» из п. 5.1.1. Его можно реструктуризировать следующим образом (рис. 5.10):

Рис. 5.10. Иерархия наследования в Java, интерфейс Sequence наследует Sequence

Переопределенный АТД «вектор» функционально эквивалентен прежнему, то есть содержит те же методы, однако имеет простой и надежный способ защиты его экземпляров. В частности, можно обратиться к экземпляру вектора vect с помощью переменной типа inspectable vector (инспектирующий вектор), то есть в этом случае над vect будут выполняться только методы запроса и доступа. Таким же образом можно изменить АТД «список» и «последовательность», используя соответствующие инспектирующие варианты.

Структура иерархии последовательностей

После обособления методов обновления от остальных методов необходимо провести реструктуризацию иерархической организации АТД «вектор», «список» и «последовательность», представленной в п. 5.3.1. Для этого введем новый суперинтерфейс InspectableContainer, который опйсывает общие методы size, isEmpty и elements. Используя возможности множественного наследования интерфейсов, в конечном итоге получаем схему организаций, показанную на рис. 5.11. Упражнение 3-5.16 предлагает расширить иерархию АТД, включив в нее стеки, очереди и деки, рассмотренные в главе 4.

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

По теме:

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