Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Назад к абстрактным типам данных
Насыщенные утверждениями отложенные классы хорошо подходят для представления АТД. Прекрасный пример - отложенный класс для стеков. Мы уже описывали процедуру put, сейчас приведем возможную версию полного описания этого класса.
indexing description: "Стеки (распределительные структуры с дисциплиной Last-in, First-Out), % %не зависящие от выбора представления" deferred class STACK [G] feature -- Доступ count: INTEGER is -- Число элементов. deferred end item: G is -- Последний вставленный элемент. require not_empty: not empty deferred end feature - Отчет о статусе empty: BOOLEAN is -- Стек пустой? do Result:= (count = 0) end full: BOOLEAN is -- Стек заполнен? deferred end feature - Изменение элемента put (x: G) is -- Втолкнуть x на вершину. require not full deferred ensure not_empty: not empty pushed_is_top: item = x one_more: count = old count + 1 end remove is -- Вытолкнуть верхний элемент. require not empty deferred ensure not_full: not full one_less: count = old count - 1 end change_top (x: T) is -- Заменить верхний элемент на x require not_empty: not empty do remove; put (x) ensure not_empty: not empty new_top: item = x same_number_of_items: count = old count end wipe_out is -- Удалить все элементы. deferred ensure no_more_elements: empty end invariant non_negative_count: count >= 0 empty_count: empty = (count = 0) end
Этот класс показывает, как можно реализовать эффективную процедуру, используя отложенные: например, процедура change_top реализована в виде последовательных вызовов процедур remove и put. (Такая реализация для некоторых представлений, например, для массивов, может оказаться не самой лучшей, но эффективные потомки класса STACK могут ее переопределить.) Если сравнить класс STACK со спецификацией соответствующего АТД, приведенной в Ошибка! Недопустимый объект гиперссылки., то обнаружится удивительное сходство. Подчеркнем, в частности, соответствие между функциями АТД и компонентами класса, и между пунктом PRECONDITIONS и предусловиями процедур. Аксиомы представлены в постусловиях процедур и в инварианте класса. Добавление операций change_top, count и wipe_out в данном случае несущественно, так как они легко могут быть включены в спецификацию АТД (см. упражнение У6.8). Отсутствие явного эквивалента функции new из АТД также несущественно, так как созданием объектов будут заниматься процедуры-конструкторы в эффективных потомках этого класса. Остаются три существенных отличия. Первое из них - это введение функции full, рассчитанной на реализации с ограниченным числом элементов стека, например, на реализацию массивами. Это типичный пример ограничения, которое несущественно на уровне спецификации, но необходимо для разработки практических систем. Отметим однако, что это отличие между АТД и отложенным классом можно легко устранить, включив в спецификацию АТД средства для охвата ограниченных стеков. При этом общность не будет потеряна, так как некоторые реализации (например, с помощью списков) могут реализовывать full тривиальными процедурами, всегда возвращающими ложь. Второе отличие, отмеченное при обсуждении разработки по контракту, состоит в том, что спецификация АТД полностью аппликативна (функциональна), она включает функции без побочных эффектов. А отложенный класс, несмотря на его абстрактность, является императивным (процедурным), например put определена как процедура, изменяющая стек, а не как функция, которая берет в качестве аргумента один стек и возвращает другой. Наконец, как тоже уже отмечалось, механизм утверждений недостаточно выразителен для некоторых аксиом АТД. Из четырех аксиом стеков Для всех x: G, s: STACK [G],
item (put (s, x)) = x
remove (put (s, x)) = s
empty (new)
not empty (put (s, x))
все, кроме (2), имеют прямые эквиваленты среди утверждений. (Мы предполагаем, что для (3) процедуры-конструкторы у потомков обеспечат выполнение условия empty). Причины таких ограничений уже были объяснены и были намечены возможные пути их преодоления - языки формальных спецификаций IFL.
Отложенные классы как частичные интерпретации: классы поведения
Не все отложенные классы так близки к АТД как STACK. В промежутке между полностью абстрактным классом, таким как STACK, в котором все существенные компоненты отложены, и эффективным классом, таким как FIXED_STACK, описывающим единственную реализацию АТД, имеется место для реализаций АТД с различной степенью завершенности. Типичным примером является иерархия реализаций таблиц, которая помогла нам понять роль частичной общности при изучении повторного использования. Первоначальный рисунок, показывающий отношения между вариантами, можно сейчас перерисовать в виде диаграммы наследования.
Рис. 14.13. Варианты понятия "таблица" Наиболее общий класс TABLE является полностью или почти полностью отложенным, так как на этом уровне мы можем объявить несколько компонентов, но не можем предложить никакой существенной их реализации. Среди вариантов имеется класс SEQUENTIAL_TABLE, представляющий таблицы, в которые элементы вставляются последовательно. Примерами таких таблиц являются массивы, связанные списки и последовательные файлы. Соответствующие им классы в нижней части рисунка являются эффективными. Особый интерес представляют такие классы как SEQUENTIAL_TABLE. Этот класс все еще отложенный, но его статус находится посредине между полностью отложенным статусом как у класса TABLE и полностью эффективным как у ARRAY_TABLE. У него достаточно информации, чтобы позволить себе реализацию некоторых специфических алгоритмов, например, в нем можно полностью реализовать последовательный поиск:
has (x: G): BOOLEAN is -- x имеется в таблице? do from start until after or else equal (item, x) loop forth end Result:= not after end
Эта функция эффективна, хотя ее алгоритм использует отложенные компоненты. Компоненты start (поместить курсор в первую позицию), forth (сдвинуть курсор на одну позицию), item (значение элемента в позиции курсора), after (находится ли курсор за последним элементом?) являются отложенными в классе SEQUENTIAL_TABLE и в каждом из показанных на рисунке потомков этого класса они реализуются по-разному. Эти реализации были приведены при обсуждении повторного использования. Например класс ARRAY_TABLE может представлять курсор числом i, так что процедура start реализуется как i:= 1, а item как t @ i и т.д. Отметим важность включения предусловия и постусловия компонента forth, а также инварианта объемлющего класса для гарантирования того, что все будущие реализации будут удовлетворять одной и той же базовой спецификации. Эти утверждения приводились ранее в этой лекции (в несколько ином контексте для класса LIST, но непосредственно применимы и здесь). Это обсуждение в полной степени показывает соответствие между классами и АТД: [x]. Полностью отложенный класс, такой как TABLE, соответствует АТД. [x]. Полностью эффективный класс, такой как ARRAY_TABLE, соответствует реализации АТД. [x]. Частично отложенный класс, такой как SEQUENTIAL_TABLE, соответствует семейству реализаций (или, что эквивалентно, частичной реализации) АТД. Такой класс как SEQUENTIAL_TABLE, аккумулирующий черты, свойственные нескольким вариантам АТД, можно назвать классом поведения (behavior class). Классы поведения предоставляют важные образцы для конструирования ОО-ПО.
Date: 2015-12-13; view: 388; Нарушение авторских прав |