Как представить эти «древовидные» данные?

Question

У меня есть некоторые данные (не то, чтобы эти данные действительно существовали до тех пор, пока я не решил это ...) Мне нужно иметь возможность манипулировать внутри моей программы. Однако я не могу найти подходящую структуру для хранения этого.

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

Я подумал об использовании древовидной структуры, где у каждого элемента есть родитель (кроме корня) и несколько дочерних элементов, например:

Input
|
node---
|  |  |
|  |  Output
|  |
|  Node---Output
|  |---Output
|
Node----Node
|        |
Node     Output    

Однако я вижу ряд проблем с этим, таких как отсутствие ввода или его удаление / изменение / и т.д. ...

Это наглядный пример. > Является входным узлом O и выводит [].
http://unisonmodules.co.uk/wjnewbery/data.png

@ Каждый, кто предлагает использовать древовидную структуру, как я уже упоминал

Если дерево действительно подходит, как мне преодолеть проблемы, когда у данного набора данных нет даже ввода / корня, как, например, ниже. Что происходит потом? Нужно ли полностью перестраивать дерево, если входной узел / точка / что-либо меняется (через удаление, затем добавление)? Как мне это сделать?

http://unisonmodules.co.uk/wjnewbery/data2.png

Я посмотрю на графики.

Answer 1

Кажется, вам действительно нужно больше структуры свободной формы, чем дерева. Каждый узел может иметь несколько узлов, связанных с ним; каждое соединение имеет направление. К любому узлу может быть подключен вход или выход. При создании и обновлении дерева вам не нужно вводить циклические соединения, а только один ввод.

Структуры могут быть многосвязными списками и иметь следующий вид:

            struct Node {
              NodeContentType type;  //Input, Output, None.
              InOutNode* content;    //pointer to input or output
              Link* links;           //pointer to first connection (if any), NULL if none.
            }

            struct Link {
              Node* node;  //node this connection links to.
              Link* next;  //pointer to next connection
            }

Пример дерева:

 INPUT
 |
 root
 |
 branch1---leaf2---output2
 |
 leaf1
 |
 output1

может пойти так: (порядок явно неправильный ...)

            Node root    = { Input, &input_function, &link1 };
            Link link1   = { &branch1, NULL };
            Node branch1 = { None,  NULL, &link2 };
            Link link2   = { &leaf1, &link3 };
            Link link3   = { &leaf2, NULL };
            Node leaf1   = { Output, &output_function1, NULL };
            Node leaf2   = { Output, &output_function2, NULL };

Answer 2

Composite pattern может быть очень полезным здесь. Вы можете реализовать узлы как своего рода контейнер, который снова содержит выходные данные или объекты узлов. В ссылке вы увидите больше фрагментов кода в качестве подсказки к реализации.

Answer 3

Создайте класс Node, который имеет значение и массив братьев и сестер. Массив братьев и сестер может быть пустым, в этом случае это узел значения. Значение может быть нулевым, в этом случае это соединение.

Answer 4

Вы можете создать класс следующим образом:

enum NodeType
{ Node, Output };

class TreeElement
{
  NodeType myType;
  union
  {
    Node myNode;
    Output myOutput;
  } NodeVariant;
};

Классы Node и Output взяты из вашего списка.Разница в том, что класс Node может содержать список TreeElement экземпляров.Этот список представляет дочерние элементы.