678451771dfdc3b44a187b89d5f8be012fc98a2d
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
);
63 } else if (p
->lettre
== mot
[i
]) {
65 p
->fils
= insere(p
->fils
, mot
, i
+ 1);
67 printf("The word is already here\n");
69 } else if (p
->lettre
> mot
[i
]) {
70 NOEUD
*p1
= insere_fin(mot
, i
);
74 p
->frere
= insere(p
->frere
, 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 */
115 if (p
->lettre
< mot
[i
]) {
116 p
->frere
= supprime(p
->frere
, mot
, i
);
117 } else if (p
->lettre
== mot
[i
]) {
118 p
->fils
= supprime(p
->fils
, mot
, i
+ 1);
129 /* Destruction des arbres de racine p en recuperant la place occupee (free) par chacun des noeuds */
130 NOEUD
*detruis_arbre(NOEUD
* p
)
135 p
->fils
= detruis_arbre(p
->fils
);
136 p
->frere
= detruis_arbre(p
->frere
);
143 /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
144 NOEUD
*charge_dico(char *nom_fichier
, int *nb_mots
)
152 fp
= fopen(nom_fichier
, "rt");
155 fscanf(fp
, "%d", nb_mots
); /* sur la 1ere ligne du fichier, le nombre de mots */
156 for (i
= 0; i
< *nb_mots
; i
++) {
157 fscanf(fp
, "%s", mot
);
158 p
= insere(p
, mot
, 0);
164 /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
165 void affiche_fich(FILE * fp
, NOEUD
* p
, char *mot
, int i
)
167 /* i est l'indice de la lettre courante dans le mot */
170 affiche_fich(fp
, p
->fils
, mot
, i
+ 1);
171 if (mot
[i
] == '\0') {
172 fprintf(fp
, "%s\n", mot
);
174 affiche_fich(fp
, p
->frere
, mot
, i
);
178 /* Sauvegarde des mots de l'arbre dans un fichier ****************************/
179 void sauve_dico(NOEUD
* p
, char *nom_fichier
, int nb_mots
)
184 fp
= fopen(nom_fichier
, "wt");
187 fprintf(fp
, "%d\n", nb_mots
);
188 affiche_fich(fp
, p
, mot
, 0);
192 /*****************************************************************************/
193 int main(int argc
, char *argv
[])
199 //printf ("saisir un mot : ");
201 //printf ("\ninsertion de %s\n", mot);
202 //arbre = insere (arbre, mot, 0);
203 arbre
= charge_dico("dictionnaire", &nb_mots
);
204 printf("\naffichage mots :\n");
205 affiche(arbre
, mot
, 0);
206 printf("\naffichage arbre :\n");
207 affiche_arbre(arbre
, 0);
208 if (recherche(arbre
, "salut", 0))
209 printf("mot \"salut\" present\n");
210 sauve_dico(arbre
, "dictionnaire_debug", nb_mots
);
211 supprime(arbre
, "zazou", 0);
212 affiche_arbre(arbre
, 0);
213 detruis_arbre(arbre
);
215 affiche_arbre(arbre
, 0);
219 /* Exemple de trace d'execution *************************
221 saisir un mot : salut
240 **********************************************************/