Книга: Основы объектно-ориентированного программирования

Одно- и двусвязные элементы

Одно- и двусвязные элементы

В следующем примере мы обратимся к базовым структурам данных. Рассмотрим библиотечный класс LINKABLE, описывающий односвязные элементы, используемые в LINKED_LIST - одной из реализаций списков. Вот частичное описание класса:

indexing
description: "Односвязные элементы списка"
class LINKABLE [G] feature
item: G
right: LINKABLE [G]
put_right (other: LINKABLE [G]) is
-- Поместить other справа от текущего элемента.
do right := other end
... Прочие компоненты ...
end

Рис. 16.7.  Односвязный элемент списка

Ряд приложений требуют двунаправленных списков. Класс TWO_WAY_LIST - наследник LINKED_LIST должен быть также наследником класса BI_LINKABLE, являющегося наследником класса LINKABLE.

Рис. 16.8.  Параллельные иерархии

Двусвязный элемент списка имеет еще одно поле:

Рис. 16.9.  Двусвязный элемент списка

В состав двунаправленных списков должны входить лишь двусвязные элементы (хотя последние, в силу полиморфизма, вполне можно внедрять и в однонаправленные структуры). Переопределив right и put_right, мы гарантируем однородность двусвязных списков.

indexing
description: "Элементы двусвязного списка"
class BI_LINKABLE [G] inherit
LINKABLE [G]
redefine right, put_right end
feature
left, right: BI_LINKABLE [G]
put_right (other: BI_LINKABLE [G]) is
-- Поместить other справа от текущего элемента.
do
right := other
if other /= Void then other.put_left (Current) end
end
put_left (other: BI_LINKABLE [G]) is
-- Поместить other слева от текущего элемента.
... Упражнение для читателя ...
... Прочие компоненты ...
invariant
right = Void or else right.left = Current
left = Void or else left.right = Current
end

(Попробуйте написать put_left. Здесь скрыта ловушка! См. приложение A.)

Оглавление книги