bfed52c9dc89f0c26bb2cca9a57cbf4b04388f32
1 /*****************************************************************************/
3 /* Representation d'un ensemble de mots sous forme d'arbre n-aire */
4 /*****************************************************************************/
11 /* nombre de caracteres max dans un mot */
14 typedef struct noeud
{
20 /* Recherche d'un mot dans l'arbre *****************************************/
21 bool recherche(NOEUD
* p
, char *mot
, int i
)
25 if (mot
[i
] == p
->lettre
) {
29 return recherche(p
->fils
, mot
, i
+ 1);
32 if (p
->lettre
> mot
[i
]) {
35 return recherche(p
->frere
, mot
, i
);
40 /* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/
41 NOEUD
*insere_fin(char *mot
, int i
)
43 /* i est l'indice de la lettre courante dans le mot */
44 printf("insere_fin %c, %i\n", mot
[i
], i
);
45 NOEUD
*p
= (NOEUD
*) malloc(sizeof(NOEUD
));
52 p
->fils
= insere_fin(mot
, i
+ 1);
56 /* Insertion d'un mot dans l'arbre ******************************************/
57 /* (on respecte l'ordre lexicographique des freres)**************************/
58 NOEUD
*_insere(NOEUD
* p
, char *mot
, int i
)
60 /* i est l'indice de la lettre courante dans le mot */
62 return insere_fin(mot
, i
);
64 if (mot
[i
] > p
->lettre
) {
65 return _insere(p
->frere
, mot
, i
);
66 } else if (mot
[i
] == p
->lettre
) {
67 return _insere(p
->fils
, mot
, i
+ 1);
68 } else if (mot
[i
] < p
->lettre
) {
69 return _insere(p
->fils
, mot
, i
);
73 NOEUD
*insere(NOEUD
* p
, char *mot
, int i
)
75 p
= _insere(p
, mot
, i
);
79 /*****************************************************************************/
80 /* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre */
81 void affiche(NOEUD
* p
, char *mot
, int i
)
83 /* i est l'indice de la lettre courante dans le mot */
86 affiche(p
->fils
, mot
, i
+ 1);
90 affiche(p
->frere
, mot
, i
);
94 /* Visualisation de l'arbre n-aire *******************************************/
95 void affiche_arbre(NOEUD
* p
, int prof
)
96 /* prof est utilise pour decaller l'affichage avec des espaces (selon le niveau dans l'arbre) */
101 affiche_arbre(p
->frere
, prof
);
102 for (i
= 0; i
< prof
; i
++)
104 printf("%c\n", p
->lettre
);
105 affiche_arbre(p
->fils
, prof
+ 1);
109 /* Suppression d'un mot de l'arbre ********************************************/
110 /* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */
111 NOEUD
*supprime(NOEUD
* p
, char *mot
, int i
)
112 /* i est l'indice de la lettre courante dans le mot */
118 /* Destruction des arbres de racine p en recuperant la place occupee (free) par chacun des noeuds */
119 NOEUD
*detruis_arbre(NOEUD
* p
)
124 p
->fils
= detruis_arbre(p
->fils
);
125 p
->frere
= detruis_arbre(p
->frere
);
132 /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
133 NOEUD
*charge_dico(char *nom_fichier
, int *nb_mots
)
141 fp
= fopen(nom_fichier
, "rt");
144 fscanf(fp
, "%d", nb_mots
); /* sur la 1ere ligne du fichier, le nombre de mots */
145 for (i
= 0; i
< *nb_mots
; i
++) {
146 fscanf(fp
, "%s", mot
);
147 p
= insere(p
, mot
, 0);
153 /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
154 void affiche_fich(FILE * fp
, NOEUD
* p
, char *mot
, int i
)
156 /* i est l'indice de la lettre courante dans le mot */
159 affiche_fich(fp
, p
->fils
, mot
, i
+ 1);
160 if (mot
[i
] == '\0') {
161 fprintf(fp
, "%s\n", mot
);
163 affiche_fich(fp
, p
->frere
, mot
, i
);
167 /* Sauvegarde des mots de l'arbre dans un fichier ****************************/
168 void sauve_dico(NOEUD
* p
, char *nom_fichier
, int nb_mots
)
173 fp
= fopen(nom_fichier
, "wt");
176 fprintf(fp
, "%d\n", nb_mots
);
177 affiche_fich(fp
, p
, mot
, 0);
181 /*****************************************************************************/
182 int main(int argc
, char *argv
[])
188 //printf ("saisir un mot : ");
190 //printf ("\ninsertion de %s\n", mot);
191 //arbre = insere (arbre, mot, 0);
192 arbre
= charge_dico("dictionnaire", &nb_mots
);
193 printf("\naffichage mots :\n");
194 affiche(arbre
, mot
, 0);
195 printf("\naffichage arbre :\n");
196 affiche_arbre(arbre
, 0);
197 if (recherche(arbre
, "salut", 0))
198 printf("mot \"salut\" present\n");
199 sauve_dico(arbre
, "dictionnaire_debug", nb_mots
);
200 detruis_arbre(arbre
);
202 affiche_arbre(arbre
, 0);
206 /* Exemple de trace d'execution *************************
208 saisir un mot : salut
227 **********************************************************/