многоходовое дерево распределения памяти дочерних элементов

Я пытаюсь построить многоходовое дерево в C. Я застрял в выделении памяти для детей. У меня есть вектор, который содержит отцов каждого узла. Вот мой код:

#define MAX_CHILDS 10

int t[10] = {1, 2, 4, 1, -1, 3, 2, 1, 0, 4};
NODE *root;
NODE *v[MAX_CHILDS];

//add children for specified node
void ADD_REF(int i) {
    v[i]->children[v[i]->child_count] = v[t[i]];
    v[i]->child_count++;
}

//creates the tree
NODE *T1(int n, int *t) {
    int root = 0;
    for (int i = 0; i < n; i++) {
        v[i] = (NODE *) malloc(sizeof(NODE));
        v[i]->info = i;
        v[i]->child_count = 0;
        v[i]->children = (NODE **) malloc(sizeof(NODE)); // I think the problem is here
    }

    for (int i = 0; i<n; i++) {
        if (t[i] == -1)
            root = i;
        else 
            ADD_REF(i);
    }

    return v[root];
}

void main() {
    root = T1(MAX_CHILDS, t);   
    print_tree(root, 0); // prints the tree
}

Вот структура УЗЛА:

typedef struct NODE {
    int info;                   
    int child_count;            
    struct NODE **children; 
} NODE;

Я точно не уверен, что проблема в выделении памяти. По моей логике должно работать.


c algorithm multiway-tree
person smotru    schedule 14.05.2014    source источник
comment
В чем собственно вопрос?   -  person Rahul Shardha    schedule 14.05.2014
comment
Я точно не знаю, как динамически выделять память вектору узлов, так как не знаю, сколько узлов будет.   -  person smotru    schedule 14.05.2014
comment
Почему бы и нет? info и child_count — это целые числа, а children — это просто указатель.   -  person Rahul Shardha    schedule 14.05.2014
comment
Я новичок в C, но заметил 2 вещи. У вас есть один указатель в каждом узле. Следовательно, он будет вести себя как связанный список, а не как многостороннее дерево. Во-вторых, почему вы используете два *. Разве вы не должны использовать только один?   -  person Rahul Shardha    schedule 14.05.2014
comment
2x* представляет собой вектор типа NODE   -  person smotru    schedule 14.05.2014
comment
Хм. Не знал этого. Я думаю, вам нужно решить, сколько путей это дерево. У него должен быть НЕКОТОРЫЙ предел. Либо определенный пользователем, либо предопределенный в вашей программе.   -  person Rahul Shardha    schedule 14.05.2014
comment
Таким образом, каждый узел знает своих дочерних элементов в дочернем векторе. Единственная разница между этим и бинарным деревом поиска должна заключаться в динамическом выделении памяти для дочерних элементов (насколько я понимаю)   -  person smotru    schedule 14.05.2014
comment
Почему бы не использовать фиксированное число (как я сказал выше), определяемое пользователем или предустановленное (2 для двоичного). Затем при выделении памяти иметь предустановку для узла **, т.е. не делать его вектором. сделайте его массивом размера. Ваш существующий код должен работать.   -  person Rahul Shardha    schedule 14.05.2014
comment
Я не могу использовать предопределенный размер на этом. Это необходимо для моей задачи.   -  person smotru    schedule 14.05.2014
comment
Ok. Затем предложите пользователю ввести данные. Как Enter a number to make a "number" way tree. Затем назначьте это число как размер массива   -  person Rahul Shardha    schedule 14.05.2014

Ответы (1)


arrow_upward
0
arrow_downward

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

Это было решение:

void ADD_REF(int i) {
    v[t[i]]->children[v[t[i]]->child_count] = v[i];
    v[t[i]]->child_count++;
}
person smotru    schedule 14.05.2014