[c]déclaration d'une arbre n-aire
Fermé
amouna23
-
29 mars 2007 à 23:14
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 1 avril 2011 à 08:29
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 1 avril 2011 à 08:29
A voir également:
- [c]déclaration d'une arbre n-aire
- Arbre généalogique famille michelin - Télécharger - Généalogie
- Arbre à clochette 99000 ✓ - Forum Jeux vidéo
- Faire son arbre généalogique gratuit sans inscription ✓ - Forum Loisirs / Divertissements
- Arbre qui parle disney ✓ - Forum Cinéma / Télé
- Arbre genealogique windsor - Télécharger - Généalogie
2 réponses
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
30 mars 2007 à 20:07
30 mars 2007 à 20:07
Le plus simple c'est de faire une structure noeud contenant un tableau de pointeur sur des noeuds :
Il faut par contre veiller à bien allouer le tableau nodes de chaque noeud avant de créer des noeuds fils. Si n est défini dans un #define et constant pour tout noeud de l'arbre, tu peux directement faire une allocation statique (ce qui évitera les mallocs et les free) :
Bonne chance
struct node_t{
struct node_t ** nodes;
};
typedef struct node_t * tree_t;
Il faut par contre veiller à bien allouer le tableau nodes de chaque noeud avant de créer des noeuds fils. Si n est défini dans un #define et constant pour tout noeud de l'arbre, tu peux directement faire une allocation statique (ce qui évitera les mallocs et les free) :
#define N 10
struct node_t{
struct node_t * nodes[N];
};
typedef struct node_t * tree_t;
Bonne chance
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
1 avril 2007 à 23:48
1 avril 2007 à 23:48
Ben c'est pareil sauf que tu changes le struct node_t ** par une liste de struct node_t * :
Dans ton cas la donnée stockée dans chaque maillon de liste (de type void *) sera en fait un pointeur sur un noeud fils de l'arbre (struct noeud *). Ceci te forcera donc à faire des cast pour passer des void * aux struct noeud * et réciproquement, mais comme les pointeurs (quel que soit leur type) ne sont que des adresses (donc des objets de même taille), il n'y a pas de problème.
La donnée stockée dans un noeud_t est l'adresse de la donnée associée à ce noeud de l'arbre (par exemple le nom de la personne dans un arbre généalogique). Tu n'es pas obligé d'en mettre une, c'est à toi de voir.
Pour l'implémentation de la liste chainée il peut être intéressant d'utiliser une mini structure qui garde le début et la fin de la liste (en particulier ça évite de reparcourir la liste pour insérer un maillon à la fin) :
Bonne chance
// Implémentation d'une liste chaînée générique
// (liste chaînée de pointeurs génériques)
struct maillon_t{
void *donnee; // l'adresse de la donnée stockée dans le maillon
struct maillon_t *suivant; // le maillon suivant de la liste chaînée
};
// Implémentation d'un arbre générique
typedef maillon_t *liste_t;
struct noeud_t{
void *donnee; // l'adresse de la donnée stockée dans le noeud
liste_t noeuds_fils; // la liste des noeuds fils
};
typedef struct noeud_t *arbre_t;
Dans ton cas la donnée stockée dans chaque maillon de liste (de type void *) sera en fait un pointeur sur un noeud fils de l'arbre (struct noeud *). Ceci te forcera donc à faire des cast pour passer des void * aux struct noeud * et réciproquement, mais comme les pointeurs (quel que soit leur type) ne sont que des adresses (donc des objets de même taille), il n'y a pas de problème.
La donnée stockée dans un noeud_t est l'adresse de la donnée associée à ce noeud de l'arbre (par exemple le nom de la personne dans un arbre généalogique). Tu n'es pas obligé d'en mettre une, c'est à toi de voir.
Pour l'implémentation de la liste chainée il peut être intéressant d'utiliser une mini structure qui garde le début et la fin de la liste (en particulier ça évite de reparcourir la liste pour insérer un maillon à la fin) :
typedef struct liste_t{
struct maillon_t *debut; // le premier maillon de la liste
struct maillon_t *fin; // le dernier maillon de la liste
} liste_t;
Bonne chance
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
22 mars 2010 à 12:09
22 mars 2010 à 12:09
Justement, avec une liste, tu mets autant de fils que tu veux pour un noeud donné.
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
1 avril 2011 à 08:29
1 avril 2011 à 08:29
Imaginons que tu stockes un dictionnaire de mots dans ton arbre, par exemple les mots "ta" "tapis" et "tapir".
Alors la racine ne contient aucune donnée, et a un noeud fils.
Son fils contient la donnée 't' et un fils.
Son petit fils la donnée 'a' et deux fils.
- L'un dont la donnée est '\0' (mot "ta')
- L'autre dont la donnée est 'p' (mots commençant par "tap..."). Continuons à partir de ce noeud.
Son fils stocke la donnée 'i' et a deux fils.
- Le premier stocke la donnée 'r', et a lui-même un fils donc la donnée est '\0'. ("tapir")
- Le second stocke la donnée 's', et a lui-même un fils donc la donnée est '\0'. ("tapis")
Un mot est présent dans l'arbre si on arrive à parcourir successivement un noeud pour chaque lettre et que ce noeud (respectivement 'i', 'r' et 's' pour tapi, tapir, tapis) à un fils terminal (\0).
Bonne chance
Alors la racine ne contient aucune donnée, et a un noeud fils.
Son fils contient la donnée 't' et un fils.
Son petit fils la donnée 'a' et deux fils.
- L'un dont la donnée est '\0' (mot "ta')
- L'autre dont la donnée est 'p' (mots commençant par "tap..."). Continuons à partir de ce noeud.
Son fils stocke la donnée 'i' et a deux fils.
- Le premier stocke la donnée 'r', et a lui-même un fils donc la donnée est '\0'. ("tapir")
- Le second stocke la donnée 's', et a lui-même un fils donc la donnée est '\0'. ("tapis")
racine | 't' | 'a' \--'\0' | 'p' | 'i' \--'r'--'\0' | 's' | '\0'
Un mot est présent dans l'arbre si on arrive à parcourir successivement un noeud pour chaque lettre et que ce noeud (respectivement 'i', 'r' et 's' pour tapi, tapir, tapis) à un fils terminal (\0).
Bonne chance
31 mars 2007 à 13:23
merci pour ton aide mais je voudrais une déclaration chainée
(avec les cellules)
a+