Arbre et fichier en c
Fermé
youscoul
Messages postés
125
Date d'inscription
dimanche 10 août 2008
Statut
Membre
Dernière intervention
7 janvier 2013
-
25 avril 2010 à 16:17
youscoul Messages postés 125 Date d'inscription dimanche 10 août 2008 Statut Membre Dernière intervention 7 janvier 2013 - 25 avril 2010 à 16:21
youscoul Messages postés 125 Date d'inscription dimanche 10 août 2008 Statut Membre Dernière intervention 7 janvier 2013 - 25 avril 2010 à 16:21
A voir également:
- Arbre et fichier en c
- Fichier rar - Guide
- Fichier host - Guide
- Fichier iso - Guide
- Comment réduire la taille d'un fichier - Guide
- Ouvrir fichier .bin - Guide
1 réponse
youscoul
Messages postés
125
Date d'inscription
dimanche 10 août 2008
Statut
Membre
Dernière intervention
7 janvier 2013
4
25 avril 2010 à 16:19
25 avril 2010 à 16:19
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;i<node->num_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 ;-)
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;i<node->num_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 ;-)
25 avril 2010 à 16:21
D'accord avec ça, je vais essayer. Mais tu me donnes un peu de temps pour mes réponses afin de comprendre et commencer à l'adapter à mon cas. Aussi, je vais transferer le sujet sur le forum sous le même titre. Il y a un detail que j'ai oublié d'ajouter. Mon arbre reste statique EN STRUCTURE une fois établit, donc j'aurai pas à supprimer ou d'ajouter des noeuds supplementaires. Pour cela, je voudrai construire toute l'arbre en numerotant de manière unique chaque noeud dans le degré de profondeur. Donc on pourra utiliser ta methode ci dessous que j'ai ajouté deux champs void*Data, et pointeur sur père:
typedef enum _depht_t{ A, B, C, D} deph_t;
typedef struct _node_t{
struct _node_t **children;
unsigned num_children;
depth_t depth;
void*Data; //
struct _node_t*pere; // Pour que chq fils connaisse son pere
} node_t;
Ma question est, est ce possible de construire tout l'arbre avant de commencer à travailler avec ?.