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 /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
114 NOEUD
*charge_dico(char *nom_fichier
, int *nb_mots
)
122 fp
= fopen(nom_fichier
, "rt");
125 fscanf(fp
, "%d", nb_mots
); /* sur la 1ere ligne du fichier, le nombre de mots */
126 for (i
= 0; i
< *nb_mots
; i
++) {
127 fscanf(fp
, "%s", mot
);
128 p
= insere(p
, mot
, 0);
134 /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
135 void affiche_fich(FILE * fp
, NOEUD
* p
, char *mot
, int i
)
138 /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */
141 /* Sauvegarde des mots de l'arbre dans un fichier ****************************/
142 void sauve_dico(NOEUD
* p
, char *nom_fichier
, int nb_mots
)
147 fp
= fopen(nom_fichier
, "wt");
150 fprintf(fp
, "%d\n", nb_mots
);
151 affiche_fich(fp
, p
, mot
, 0); /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */
155 /*****************************************************************************/
156 int main(int argc
, char *argv
[])
162 //printf ("saisir un mot : ");
164 //printf ("\ninsertion de %s\n", mot);
165 //arbre = insere (arbre, mot, 0);
166 arbre
= charge_dico("dictionnaire", &nb_mots
);
167 printf("\naffichage mots :\n");
168 affiche(arbre
, mot
, 0);
169 printf("\naffichage arbre :\n");
170 affiche_arbre(arbre
, 0);
171 if (recherche(arbre
, "salut", 0))
172 printf("mot \"salut\" present\n");
177 /* Exemple de trace d'execution *************************
179 saisir un mot : salut
198 **********************************************************/