1 /*****************************************************************************/
3 /* Representation de mots sous forme d'arbre n-aire */
4 /*****************************************************************************/
14 typedef struct noeud
{
21 /* Recherche d'un mot dans l'arbre *****************************************/
22 NOEUD
*cherche(NOEUD
* p
, char *mot
, int i
)
26 if (p
->lettre
== mot
[i
]) {
28 return cherche(p
->fils
, mot
, i
+ 1);
31 } else if (p
->lettre
> mot
[i
])
34 return cherche(p
->frere
, mot
, i
);
37 /***************************************************************************/
38 NOEUD
*recherche(NOEUD
* p
, char *mot
)
40 return cherche(p
, mot
, 0);
43 /* Création d'une fin de mot - liste chaînée suivant le lien fils **********/
44 NOEUD
*insere_fin(char *mot
, int i
)
46 NOEUD
*p
= (NOEUD
*) malloc(sizeof(NOEUD
));
54 p
->fils
= insere_fin(mot
, i
+ 1);
59 /* Insertion d'un mot dans l'arbre ******************************************/
60 /* on respecte l'ordre lexicographique des frères **************************/
61 NOEUD
*insere(NOEUD
* p
, char *mot
, int i
)
66 p
= insere_fin(mot
, i
);
67 else if (p
->lettre
== mot
[i
])
68 if (mot
[i
] != '\0') /* if (mot[i]) */
69 p
->fils
= insere(p
->fils
, mot
, i
+ 1);
71 printf("Le mot est deja dans le dictionnaire\n");
72 else if (p
->lettre
> mot
[i
]) {
73 p1
= insere_fin(mot
, i
);
77 p
->frere
= insere(p
->frere
, mot
, i
);
82 /*****************************************************************************/
83 /* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre */
84 void affiche_fich(FILE * fp
, NOEUD
* p
, char *mot
, int i
)
91 for (j
= 0; j
< i
; j
++)
92 fprintf(fp
, "%c", mot
[j
]);
95 affiche_fich(fp
, p
->fils
, mot
, i
+ 1);
96 affiche_fich(fp
, p
->frere
, mot
, i
);
101 /* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre */
102 /* parcours en profondeur d'abord, prefixe (idem si infixe, voir la remarque plus loin) */
103 void affiche(NOEUD
* p
, char *mot
, int i
)
110 printf("%s\n", mot
); /* ici ou apres l'appel sur le fils ('\0' n'a pas de fils , donc l'appel sur le fils n'affichera rien */
111 affiche(p
->fils
, mot
, i
+ 1);
112 affiche(p
->frere
, mot
, i
);
117 /*****************************************************************************/
118 /* Visualisation de l'arbre n-aire - parcour "frère - racine - fils" */
119 void affiche_arbre(NOEUD
* p
, int prof
)
124 affiche_arbre(p
->frere
, prof
);
125 for (i
= 0; i
< prof
; i
++)
127 printf("%c\n", p
->lettre
);
128 affiche_arbre(p
->fils
, prof
+ 1);
133 /*****************************************************************************/
134 /* Attention à ne supprimer que la fin du mot qui n'est partagée par aucun
135 autre mot de l'arbre */
136 NOEUD
*supprime(NOEUD
* p
, char *mot
, int i
)
141 if (p
->lettre
< mot
[i
])
142 p
->frere
= supprime(p
->frere
, mot
, i
);
143 else if (p
->lettre
== mot
[i
]) {
144 p
->fils
= supprime(p
->fils
, mot
, i
+ 1);
151 printf("%s n'est pas present\n", mot
);
156 NOEUD
*detruis_arbre(NOEUD
* p
)
161 p
->fils
= detruis_arbre(p
->fils
);
162 p
->frere
= detruis_arbre(p
->frere
);
169 /*****************************************************************************/
170 NOEUD
*charge_dico(char *nom_fichier
, int *nb_mots
)
178 fp
= fopen(nom_fichier
, "rt");
181 fscanf(fp
, "%d", nb_mots
); /* sur la 1ère ligne du fichier, le nombre de mots */
182 for (i
= 0; i
< *nb_mots
; i
++) {
183 fscanf(fp
, "%s", mot
);
184 p
= insere(p
, mot
, 0);
191 /*****************************************************************************/
192 void sauve_dico(NOEUD
* p
, char *nom_fichier
, int nb_mots
)
197 fp
= fopen(nom_fichier
, "wt");
200 fprintf(fp
, "%d\n", nb_mots
);
201 affiche_fich(fp
, p
, mot
, 0);
206 /*****************************************************************************/
207 char EstSeparateur(char c
)
209 return (((c
== '\'') || (c
== '"') || (c
== ',') || (c
== ';')
210 || (c
== '.') || (c
== '\n') || (c
== '?') || (c
== '!')
211 || (c
== ':') || (c
== ' ') || (c
== '\t') || (c
== '-')
212 || (c
== '*') || (c
== '+') || (c
== '=') || (c
== '\b')
213 || (c
== '{') || (c
== '}') || (c
== '(') || (c
== ')')));
217 /****************************************************************************/
218 /* Lit un mot a partir du fichier fd.
219 texte == <separateur>* <mot> <separateur>*
221 Le mot est retourné sous une forme minuscule.
222 Quant on a atteint la fin de fichier, la fonction retourne 0 */
223 int Lectmot(FILE * fp
, char *mot
)
228 /* Lecture des separateurs */
229 while (((c
= (char) fgetc(fp
)) != (char) EOF
) && (EstSeparateur(c
)));
232 while (c
!= (char) EOF
) {
233 if (!EstSeparateur(c
))
234 mot
[i
++] = tolower(c
);
237 c
= (char) fgetc(fp
);
244 /****************************************************************************/
246 /* voici un autre programme principal pour procéder à une vérification
247 orthographique interactive d'un texte.
249 Un exemple d'utilisation :
250 ./arbre_n_aire dictionnaire.txt mondico.txt letexte.txt motsinconnus.txt
252 Les arguments de la ligne de commande sont :
253 argv[1] est le nom du dictionnaire d'entree
254 argv[2] est le nom du dictionnaire apres insertion des nouveaux mots
255 argv[3] est le texte a verifier
256 argv[4] est un fichier contenant la liste des mots inconnus du texte
259 int main(int argc
, char *argv
[])
264 FILE *fentree
, *fsortie
;
269 ("Usage: <prog> <dico_entree> <dico_sortie> <texte> <mots_inconnus>\n");
273 rac
= charge_dico(argv
[1], &nb_mots
);
275 /* pour afficher le dictionnaire charge (attention le dictionnaire peut etre volumineux */
276 /* affiche_fich(stdout,rac,mot,0); */
277 /* affiche_arbre(rac,0); */
279 fentree
= fopen(argv
[3], "rt");
282 fsortie
= fopen(argv
[4], "wt");
286 while (Lectmot(fentree
, mot
) > 0) {
287 if (!cherche(rac
, mot
, 0)) {
289 ("Le mot <%s> n'est pas dans le dictionnaire - Dois-je l'inserer (o/n) ? ",
294 rac
= insere(rac
, mot
, 0);
297 fprintf(fsortie
, "%s\n", mot
);
304 sauve_dico(rac
, argv
[2], nb_mots
);
306 /* pour tester la suppression */
308 printf("Entrez un mot a supprimer (stop pour arreter) : ");
310 if (strcmp(mot
, "stop")) {
311 rac
= supprime(rac
, mot
, 0);
312 affiche_fich(stdout
, rac
, mot
, 0);
314 } while (strcmp(mot
, "stop"));
319 /****************************************************************************/