C: Как добавить узлы в дерево в цикле? - PullRequest
Новая
       30

C: Как добавить узлы в дерево в цикле?

0 голосов
/ 21 марта 2011

Я сделал древовидную структуру, которая имеет только корень. Затем пользователь сам может создавать узлы и добавлять их как дочерние к корню или другому существующему узлу. Вот как выглядит структура: 

#define MAXCHILDREN 5      //max children a node can have

typedef struct node{
    unsigned int id;
    struct node* parent;
    struct node* children[MAXCHILDREN];
}node;

typedef struct spantree{
    node root;
}spantree;

Теперь я хочу создать 4 узла и добавить их в качестве дочерних в корень. Вот что я сделал, что не работает должным образом: 

for (i=0; i<4; i++){
        node newNode;
        newNode.id=i;
        addChild(&newNode, &Root);  
    }

Это не работает, как при запуске

showChildId (0, & root); // где первое число обозначает первого ребенка, второго ребенка и т. д.

showChildId (1, & root);

и т.д.

Я получаю тот же идентификатор, который означает, что добавлен только один ребенок. Итак, как мне продолжать создавать 4 различных узлов и добавлять их к родителю (в данном случае корень) в цикле?

Ответы [ 3 ]

3 голосов
/ 21 марта 2011

Вы добавляете временные значения в дочерний список: 

node newNode;

Это создает значение в стеке, которое существует только до следующего '}'.Следующая итерация, скорее всего, будет повторно использовать тот же кусок памяти для нового объекта.Вам нужно динамически создавать объект, а не выделять его стеком: 

node *newNode = malloc sizeof (node);
newNode->id = i;
addChild (newNode, &Root);

Вам необходимо убедиться, что узлы освобождены правильно, иначе вы потеряете память.Функция, которая освобождает память узла, должна рекурсивно вызывать себя для каждого дочернего узла.

1 голос
/ 21 марта 2011

В отличие от Алексис, я не вижу ничего прямо здесь на этом уровне алгоритма, но я не уверен, что вы пропускаете детали или запутались. 

for (i=0; i<4; i++){ // I think you mean 5 here -- or rather MAXCHILDREN.
        node newNode; // This is a temporary on the stack.
        newNode.id=i;
        addChild(&newNode, &Root);   // &newNode is a pointer to that temporary.
    }

Таким образом, addChild каждый раз получает указатель на временный новый узел. Это произойдет по одному адресу в стеке, поэтому все они будут указывать на одно и то же место. Таким образом, они все будут иметь одинаковый идентификатор. Возможно, к тому времени это расположение стека было перезаписано, поэтому оно может быть совершенно случайным. 

for (i=0; i<MAXCHILDREN; i++){
        node *newNode = new node(); // C++, or use malloc if you're stuck in C
        newNode->id=i;
        addChild(newNode, &Root);  
    }

Должен приблизить вас к тому, что вы хотите сделать.

1 голос
/ 21 марта 2011

Для меня это похоже на домашнюю работу, поэтому я постараюсь дать совет, а не окончательный ответ.

В этом цикле: 

for (i=0; i<4; i++){
    node newNode;   // <-- newNode is created on the stack here .
    newNode.id=i;
    addChild(&newNode, &Root);  
                    // <-- and is removed from the stack here.
}

newNode создается в стеке на каждой итерации цикла и действует только до конца итерации.

Чтобы он работал дольше, вам нужно выделить для него память в куче. Посмотрите на malloc() и free().

...