Блог

Главная - Вопросы по программированию - Реализация общего атрибута в рекурсивном типе данных, таком как ДЕРЕВО

Реализация общего атрибута в рекурсивном типе данных, таком как ДЕРЕВО

#recursion #data-structures #attributes #eiffel

Вопрос:

При реализации рекурсивной структуры данных, такой как ДЕРЕВО, мне нужен общий атрибут для каждого ДЕРЕВА, и мне интересно, как его реализовать:

  • Добавление атрибута в узел ДЕРЕВА повторяет атрибут для каждого узла, а не один раз для каждого ДЕРЕВА
  • Используя once атрибут, я получаю только один общий атрибут для всех деревьев, а не по одному на ДЕРЕВО.

Есть ли для этого какое-нибудь элегантное решение в стиле Эйфеля?

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

1. Это зависит от древовидной структуры. Например, возможно ли добраться до корневого узла из любого другого узла дерева? Если да, корневой узел может быть специальным с требуемым атрибутом, и все остальные узлы могут получить значение атрибута при необходимости, обратившись к корневому узлу.

2. В общем дереве вы не могли добраться до корневого узла, но в одной реализации вы действительно могли. Поэтому не могли бы вы набросать частичный ответ, когда корневой узел доступен из любого узла (возможно, с помощью именованного атрибута parent ).

Ответ №1:

Дерево имеет выделенный корневой узел, который может использоваться для хранения информации, относящейся ко всему дереву, а не к определенному узлу. Чтобы получить эту информацию, должна быть возможность добраться до корневого узла из любого другого узла дерева. Одним из возможных решений является наличие функции parent , которая возвращала бы родительский узел указанного узла (или Current для корневого). Затем функция, которая получает корневой узел, может выглядеть следующим образом

 root: TREE
        -- The root of the tree.
    local
        p: TREE
    do
        from
            Result := Current
            p := parent
        until
            Result = p -- `Result = Result.parent` when `Result` is root.
        loop
            Result := p
            p := p. parent
        end
    ensure
        Result.parent = Result -- `Result` has no other parent.
    end

Затем значение атрибута для конкретного дерева может быть извлечено из произвольного узла дерева n с n.root.my_attribute помощью .

Редактировать:

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

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

1. Так n является ли a TREE и my-attribute является ли частью TREE ? Если да, то нет ли my_attribute его ни в одном TREE узле? Если бы это было так, это не было бы ответом (вопросы эффективности оставлены в стороне).

2. @U. Windl Возможны различные реализации. В одном случае все узлы в дереве имеют один и тот же тип, атрибут присутствует в каждом узле, однако n.root.my_attribute гарантирует, что используется только одна версия. В другой реализации корневой каталог имеет выделенный тип. Каждый узел реализуется my_attribute как возвращаемая функция root.my_attribute , за исключением корневого узла, где он является фактическим атрибутом.

3. Даже с once атрибутом (это не решило бы проблему) Я боялся, что каждый узел TREE будет содержать POINTER соответствующую once функцию. В частности, то, что я имел в виду, было чем-то вроде одного бита ( BOOLEAN ). В C (для контраста) можно использовать битовое поле, скорее всего, там, где в любом случае есть несколько запасных битов (например, баланс дерева).

4. @U. Windl Вопрос нейтрален к языку, не стесняйтесь давать рабочий ответ на любом языке.

5. На самом деле я думаю о реализации на основе массива, которая значительно упростит подобные вещи.

Метки: ,