e8b32016e734782c2f7bddf889c4275cc3a203f8
1 /*****************************************************************************/
4 /* Representation d'un ensemble de mots sous forme d'arbre n-aire */
5 /*****************************************************************************/
12 /* nombre de caracteres max dans un mot */
15 typedef struct noeud
{
21 /* Recherche d'un mot dans l'arbre *****************************************/
22 bool recherche(NOEUD
* p
, char *mot
, int i
)
26 if (mot
[i
] == p
->lettre
) {
30 return recherche(p
->fils
, mot
, i
+ 1);
33 if (p
->lettre
> mot
[i
]) {
36 return recherche(p
->frere
, mot
, i
);
41 /* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/
42 NOEUD
*insere_fin(char *mot
, int i
)
44 /* i est l'indice de la lettre courante dans le mot */
45 printf("insere_fin %c, %i\n", mot
[i
], i
);
46 NOEUD
*p
= (NOEUD
*) malloc(sizeof(NOEUD
));
53 p
->fils
= insere_fin(mot
, i
+ 1);
57 /* Insertion d'un mot dans l'arbre ******************************************/
58 /* (on respecte l'ordre lexicographique des freres)**************************/
59 NOEUD
*insere(NOEUD
* p
, char *mot
, int i
)
61 /* i est l'indice de la lettre courante dans le mot */
63 return insere_fin(mot
, i
);
65 if (mot
[i
] > p
->lettre
) {
66 return insere(p
->frere
, mot
, i
);
67 } else if (mot
[i
] == p
->lettre
) {
68 return insere(p
->fils
, mot
, i
+ 1);
70 return insere_fin(mot
, i
);
74 /*****************************************************************************/
75 /* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre */
76 void affiche(NOEUD
* p
, char *mot
, int i
)
78 /* i est l'indice de la lettre courante dans le mot */
81 affiche(p
->fils
, mot
, i
+ 1);
85 affiche(p
->frere
, mot
, i
);
89 /* Visualisation de l'arbre n-aire *******************************************/
90 void affiche_arbre(NOEUD
* p
, int prof
)
91 /* prof est utilise pour decaller l'affichage avec des espaces (selon le niveau dans l'arbre) */
96 affiche_arbre(p
->frere
, prof
);
97 for (i
= 0; i
< prof
; i
++)
99 printf("%c\n", p
->lettre
);
100 affiche_arbre(p
->fils
, prof
+ 1);
104 /* Suppression d'un mot de l'arbre ********************************************/
105 /* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */
106 NOEUD
*supprime(NOEUD
* p
, char *mot
, int i
)
107 /* i est l'indice de la lettre courante dans le mot */
113 /* Destruction des arbres de racine p en recuperant la place occupee (free) par chacun des noeuds */
114 NOEUD
*detruis_arbre(NOEUD
* p
)
119 p
->fils
= detruis_arbre(p
->fils
);
120 p
->frere
= detruis_arbre(p
->frere
);
127 /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
128 NOEUD
*charge_dico(char *nom_fichier
, int *nb_mots
)
136 fp
= fopen(nom_fichier
, "rt");
139 fscanf(fp
, "%d", nb_mots
); /* sur la 1ere ligne du fichier, le nombre de mots */
140 for (i
= 0; i
< *nb_mots
; i
++) {
141 fscanf(fp
, "%s", mot
);
142 p
= insere(p
, mot
, 0);
148 /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
149 void affiche_fich(FILE * fp
, NOEUD
* p
, char *mot
, int i
)
152 /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */
155 /* Sauvegarde des mots de l'arbre dans un fichier ****************************/
156 void sauve_dico(NOEUD
* p
, char *nom_fichier
, int nb_mots
)
161 fp
= fopen(nom_fichier
, "wt");
164 fprintf(fp
, "%d\n", nb_mots
);
165 affiche_fich(fp
, p
, mot
, 0); /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */
169 /*****************************************************************************/
170 int main(int argc
, char *argv
[])
176 //printf ("saisir un mot : ");
178 //printf ("\ninsertion de %s\n", mot);
179 //arbre = insere (arbre, mot, 0);
180 arbre
= charge_dico("dictionnaire", &nb_mots
);
181 printf("\naffichage mots :\n");
182 affiche(arbre
, mot
, 0);
183 printf("\naffichage arbre :\n");
184 affiche_arbre(arbre
, 0);
185 if (recherche(arbre
, "salut", 0))
186 printf("mot \"salut\" present\n");
187 detruis_arbre(arbre
);
191 /* Exemple de trace d'execution *************************
193 saisir un mot : salut
212 **********************************************************/