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


Слияние списка и стражей - часть 2


Но могут возникнуть более серьезные проблемы:

  • Во многих случаях, как упоминалось, могут понадобиться двунаправленные списки, полностью симметричные с элементами класса BI_LINKABLE , имеющие ссылки на левого и правого соседа. Класс TWO_WAY_LIST (который, кстати, может быть написан как дважды наследуемый от LINKED_LIST, основываясь на технике дублируемого наследования) будет нуждаться как в левом, так и правом страже.
  • Связные деревья (см. лекцию 15 курса "Основы объектно-ориентированного программирования") представляют более серьезную проблему. Практически важным является класс TWO_WAY_TREE, задающий удобное представление деревьев с двумя ссылками (на родителя и потомка). Построенный на идеях, описываемых при представлении множественного наследования, класс объединяет понятия узла и дерева, так что он является наследником TWO_WAY_LIST и BI_LINKABLE. Но тогда каждый узел является списком, может быть двунаправленным и хранить обоих стражей.

Хотя во втором случае есть и другие способы решения проблемы - переобъявление структуры наследования - давайте попробуем получить лучшее из возможного.

Для нахождения решения зададимся неожиданным вопросом.

Заголовок и страж

Рис. 5.12.  Заголовок и страж

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

Можем ли мы заставить заголовок списка играть роль стража? Оказывается, можем. Все, что имеет LINKABLE - это поле item и ссылку right. Для стража необходима только ссылка, указывающая на первый элемент, так что, если поместить ее в заголовок, то она будет играть ту же роль, как когда она называлась first_element в первом варианте со стражами.


Начало  Назад  Вперед



Книжный магазин