Arbre a fils multiples

Bonsoir,

Mon objectif est de créer un arbre a n fils, n n'étant pas connu au moment de la compilation et lors de l’exécution du programme. Tout se fait donc par allocation dynamique.

J'ai donc une structure node :

Code:

---

1 2 3 4 5 6 7 8 9

typedef struct node_struct node;   struct node_struct{ int nb; // Le nombre que je veux stocker dans ma node   node** tabFils; // Le tableau de fils int nbFils; // Le nombre de fils };

---

Et 2 fonctions permettant d'initialiser une node :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

node* creerNULL_node(){ node* sortie = (node*) malloc (sizeof(node*)); sortie->nbFils = 0; return sortie; }   node* creer_node(int nb){ node* sortie = (node*) malloc (sizeof(node*)); sortie->nb = nb; sortie->nbFils = 0; sortie->tabFils[0] = creerNULL_node();   return sortie; }

---

Déjà, juste à partir de l'appel de creer_node(), le débogueur me crie dessus comme quoi je n'ai pas le droit de toucher à mon tabFils[0].
Ma question est : pourquoi cela ?

J'ai tâtonné ( ou plutôt, j'ai fais n'importe quoi en espérant que ça marche ) et maintenant, je désespère. Car ça ne marche pas dès la création d'une node.

Surtout qu'après j'ai ma fonction qui ajoute un fils qui, comme j'ai suivi le même raisonnement, devrait joyeusement planter :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

void pushFils_node(node* current,int nb){ if( current == NULL ){ printf("pushFils_node : current = NULL\n"); return; } node* newNode = creer_node(nb);   if( current->nbFils == 0 ){ printf("\n\nA\n"); current->tabFils[0] = newNode; current->nbFils += 1; } else { printf("\n\nB\n"); node* buffer = creerNULL_node(); buffer = (node*) realloc (current->tabFils, (current->nbFils+1) * sizeof(node));   if (buffer != NULL){ affiche_node(current);   current->tabFils[0] = buffer; affiche_node(current); current->tabFils[current->nbFils] = newNode; current->nbFils += 1;   affiche_node(current); } else { free (current->tabFils); puts ("Error (re)allocating memory"); exit (1); }   } }

---

Je vous remercie d'avance pour votre aide qui me permettra de sauvegarder ma santé mentale :mrgreen:

tu as qq confusions entre nodes, pointeurs sur nodes, et pointeurs sur tableaux de pointeurs sur nodes. c'est la joie du C.

ligne 9 tu fais ça :
node* sortie = (node*) malloc (sizeof(node*));
alors que ce que tu voudrais vraiment faire, c'est plutôt :
node* sortie = (node*) malloc (sizeof(node));
parce que tu veux que malloc alloue la taille nécessaire pour stocker une structure node complète, et pas seulement un pointeur vers cette structure.

lorsque tu fais sortie->tabFils[0] = creerNULL_node();
à ce stade, sortie->tabFils est un pointeur non initialisé, donc accéder au premier élément de ce tableau est très dangereux, tu dois d'abord "allouer un tableau de pointeurs", via un autre appel à malloc.

enfin, même si ce n'est pas relié à tes problèmes, cette façon de gérer un arbre à fils multiples n'est pas idéale, parce qu'elle est très ennuyeuse à maintenir, et coûte beaucoup d'allocations mémoires. une autre façon de faire, que perso je trouve plus simple, c'est de faire en sorte qu'une node parente ne contienne qu'un pointeur vers le premier de ses fils, et faire en sorte que chaque node contienne un pointeur vers un node "frère".

Citation:

---

enfin, même si ce n'est pas relié à tes problèmes, cette façon de gérer un arbre à fils multiples n'est pas idéale, parce qu'elle est très ennuyeuse à maintenir, et coûte beaucoup d'allocations mémoires. une autre façon de faire, que perso je trouve plus simple, c'est de faire en sorte qu'une node parente ne contienne qu'un pointeur vers le premier de ses fils, et faire en sorte que chaque node contienne un pointeur vers un node "frère".

---

J'avais commencé par cette méthode mais celle que je testais me plaisais plus.
Je dit bien "plaisais" car j'en ai ma claque des reallocs et des pointeurs sur des tableaux de pointeurs en C ( vivement que je reprenne mon C++, j'aurais toujours les mêmes histoires mais je m'en sortirais 20 fois mieux, me demandez pas pourquoi ).

Merci pour le rappel sur malloc, je mettais des * partout pour faire joli et ce n'était pas une bonne idée.