Arbre et fichier en c Fermé

Question

Bonjour, je me permet de vous contacter parce que d'après vos interventions sur les sujets concernant les arbres, je me suis dit que vous pourriez peut être m'aider. D'abord suis debutant en ce domaine. En effet, je dispose d'une arbre très complexe manière: Racine==>64NoeudA==>64(NoeudB pour chq NoeudA)==>700(NoeudC pour chq NoeudB) ==>700(NoeudD pour chq NoeudC)==>1 Feuille(pour chq NoeudD). Vous voyez que c'est trop complexe pour quelqu'un qui n'a pas de notions en arbre. Sinon, tout ce que j'ai vu comme exemple parle de FilsGauche et FilsDroite. Est ce possible de faire N filles par Noeuds ?? J'ai vraiment besoin de ton aide. Merci d'avance. PS: Le sujet avait été diffuser comme message privé à mamiemando. On a proposé de le différer avant que chacun puisse en beneficier. Configuration: Windows Vista / Safari 532.5

youscoul · Answer

mamiemando 24 avr 2010 à 13:00 Alors l'idéal serait de poser ta question sur le forum afin que tout le monde puisse répondre et bénéficier de la réponse. Donc oui, c'est possible, en C tout est possible. Quelque soit le langage, pour manipuler un arbre il vaut mieux être à l'aise avec les appels récursifs, car c'est quasiment incontournable. Le plus simple dans ton cas serait d'utiliser systématiquement une structure de noeud permettant de manipuler un arbre n-aire, c'est à dire muni de n fils. typedef struct _node_t{ struct _node_t **children; unsigned num_children; } node_t; typedef struct _tree_t{ node_t *root; } tree_t; Ici num_children va me permettre de savoir combien mon noeud peut accueillir au plus de fils. On peut très bien imaginer que mon noeud puisse en héberger 64 mais que seuls 3 soient réellement fils de mon noeud. Après on peut imaginer que tu stockes dans un noeud des informations supplémentaires, par exemple sa profondeur dans l'arbre, tout dépend de ce que tu veux faire. Ainsi la structure de noeud pourrait être du genre : typedef enum _depht_t{ A, B, C, D} deph_t; typedef struct _node_t{ struct _node_t **children; unsigned num_children; depth_t depth; } node_t; Évidemment si chaque noeud héberge une donnée, il va falloir un champ pour l'accueillir. Si par exemple c'est un entier. De la même façon si tu as des informations communes à tout l'arbre à stocker, il suffira d'enrichir la structure tree_t. typedef struct _node_t{ struct _node_t **children; unsigned num_children; int value; } node_t; En fait en toute rigueur il faudrait même écrire un truc du genre : typedef struct _node_t{ struct _node_t **children; unsigned num_children; void *data; } node_t; ... et faire pointer data vers une structure du genre : typedef struct _data_t{ depth_t depth; int value; } data_t; Bref à toi de choisir la structure qui te paraît la plus adéquate. Je vais supposer qu'on utilise la première version. Maintenant comment ça se passe. Quand tu crées un noeud tu as intérêt à savoir combien de fils il va avoir pour pouvoir allouer un tableau de pointeurs bien dimensionnés (par exemple un tableau de 64 pointeurs si tu as 64 fils). Si tu ne sais pas trop au moment de construire le noeud combien il y a de fils il faudra utiliser soit des listes chaînes pour stocker les fils, soit réallouer le tableau de pointeur (avec la fonction realloc). Pour le moment on va supposer que tu sais combien de fils tu veux créer pour un noeud donné. Pour allouer ce tableau de pointeurs (de type node_t *, ie de type struct _node_t *) on va devoir faire une allocation dynamique avec la fonction malloc ou calloc. Et qui dit malloc dit free pour libérer la mémoire. Ici comme on veut initialiser notre tableau de pointeurs à NULL on peut utiliser directement calloc pour le champ children. node_t * new_node(unsigned num_children){ node_t *node = malloc(sizeof(node_t)); node->children = calloc(num_children,sizeof(node_t)); node->num_children = num_children; } Si tu veux passer la profondeur en paramètre, il faudra la rajouter en paramètre à new_node. Pour relâcher un noeud, il faut au préalable relâcher ses fils (s'il en a, ie que le pointeur du fils est non NULL). Si on relâche le noeud avant, on perdra l'adresse de ses fils et il ne sera plus possible de les relâcher (ça déclenchera sûrement une erreur mémoire de toute façon). void delete_node(node_t *node){ unsigned i; // Appel récursif : on détruit les fils avant le noeud courant for(i=0;inum_children;++i){ if(node->children[i]) delete_node(node); } // On relâche le noeud courant free(node->children); // relâche le calloc free(node); // relâche le malloc } Pour initialiser le ième fils d'un noeud, il faut désallouer le ième fils (s'il y en a déjà un) puis affecter au noeud le nouveau fils : void set_child(node_t *node, unsigned index, node_t *child){ if(i < num_children){ if(node->children[i]) delete_node(node->children[i]); node->children[i] = child; } } Et pour récupérer le ième fils d'un noeud : node_t *get_child(node_t *node, unsigned i){ if(i < num_children) return node->children[i]; } Il ne reste plus qu'à faire la même chose pour manipuler notre arbre : tree_t *new_tree(){ return calloc(1,sizeof(tree_t)); } void set_root(tree_t *tree, node_t *root){ if(tree->root) delete_node(tree->root); tree->root = root; } node_t *get_root(){ return tree->root; } void delete_tree(tree_t *tree){ if(tree->root) delete_node(tree->root); free(tree); } Voilà avec ça tu devrais pouvoir t'en sortir pour un arbre n-aire ! Dans ton cas, la fonction new_node pourrait être "wrappée" par une fonction new_node2 en passant la profondeur au lieu du nombre d'enfants. Attention à rajouter le champ depth dans la structure node_t : node_t *new_node2(depth_t depth){ unsigned num_children; switch(depth){ case A: num_children = 64; break; case B: num_children = 64; break; case C: num_children = 700; break; case D: num_children = 700; break; default: num_children = 1; break; } return new_node(num_children); } Bonne chance ;-)

Arbre et fichier en c

1 réponse

Discussions similaires