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);
44 /* Création d'une fin de mot - liste chaînée suivant le lien fils **********/
45 NOEUD
*insere_fin(char *mot
, int i
)
47 NOEUD
*p
= (NOEUD
*) malloc(sizeof(NOEUD
));
55 p
->fils
= insere_fin(mot
, i
+ 1);
60 /* Insertion d'un mot dans l'arbre ******************************************/
61 /* on respecte l'ordre lexicographique des frères **************************/
62 NOEUD
*insere(NOEUD
* p
, char *mot
, int i
)
67 p
= insere_fin(mot
, i
);
68 else if (p
->lettre
== mot
[i
])
69 if (mot
[i
] != '\0') /* if (mot[i]) */
70 p
->fils
= insere(p
->fils
, mot
, i
+ 1);
72 printf("Le mot est deja dans le dictionnaire\n");
73 else if (p
->lettre
> mot
[i
]) {
74 p1
= insere_fin(mot
, i
);
78 p
->frere
= insere(p
->frere
, mot
, i
);
83 /*****************************************************************************/
84 /* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre */
85 void affiche_fich(FILE * fp
, NOEUD
* p
, char *mot
, int i
)
92 for (j
= 0; j
< i
; j
++)
93 fprintf(fp
, "%c", mot
[j
]);
96 affiche_fich(fp
, p
->fils
, mot
, i
+ 1);
97 affiche_fich(fp
, p
->frere
, mot
, i
);
102 /* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre */
103 /* parcours en profondeur d'abord, prefixe (idem si infixe, voir la remarque plus loin) */
104 void affiche(NOEUD
* p
, char *mot
, int i
)
111 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 */
112 affiche(p
->fils
, mot
, i
+ 1);
113 affiche(p
->frere
, mot
, i
);
118 /*****************************************************************************/
119 /* Visualisation de l'arbre n-aire - parcour "frère - racine - fils" */
120 void affiche_arbre(NOEUD
* p
, int prof
)
125 affiche_arbre(p
->frere
, prof
);
126 for (i
= 0; i
< prof
; i
++)
128 printf("%c\n", p
->lettre
);
129 affiche_arbre(p
->fils
, prof
+ 1);
134 /*****************************************************************************/
135 /* Attention à ne supprimer que la fin du mot qui n'est partagée par aucun
136 autre mot de l'arbre */
137 NOEUD
*supprime(NOEUD
* p
, char *mot
, int i
)
142 if (p
->lettre
< mot
[i
])
143 p
->frere
= supprime(p
->frere
, mot
, i
);
144 else if (p
->lettre
== mot
[i
]) {
145 p
->fils
= supprime(p
->fils
, mot
, i
+ 1);
152 printf("%s n'est pas present\n", mot
);
156 /*****************************************************************************/
157 NOEUD
*charge_dico(char *nom_fichier
, int *nb_mots
)
165 fp
= fopen(nom_fichier
, "rt");
168 fscanf(fp
, "%d", nb_mots
); /* sur la 1ère ligne du fichier, le nombre de mots */
169 for (i
= 0; i
< *nb_mots
; i
++) {
170 fscanf(fp
, "%s", mot
);
171 p
= insere(p
, mot
, 0);
178 /*****************************************************************************/
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);
193 /*****************************************************************************/
194 char EstSeparateur(char c
)
196 return (((c
== '\'') || (c
== '"') || (c
== ',') || (c
== ';')
197 || (c
== '.') || (c
== '\n') || (c
== '?') || (c
== '!')
198 || (c
== ':') || (c
== ' ') || (c
== '\t') || (c
== '-')
199 || (c
== '*') || (c
== '+') || (c
== '=') || (c
== '\b')
200 || (c
== '{') || (c
== '}') || (c
== '(') || (c
== ')')));
204 /****************************************************************************/
205 /* Lit un mot a partir du fichier fd.
206 texte == <separateur>* <mot> <separateur>*
208 Le mot est retourné sous une forme minuscule.
209 Quant on a atteint la fin de fichier, la fonction retourne 0 */
210 int Lectmot(FILE * fp
, char *mot
)
215 /* Lecture des separateurs */
216 while (((c
= (char) fgetc(fp
)) != (char) EOF
) && (EstSeparateur(c
)));
219 while (c
!= (char) EOF
) {
220 if (!EstSeparateur(c
))
221 mot
[i
++] = tolower(c
);
224 c
= (char) fgetc(fp
);
231 /****************************************************************************/
233 /* voici un autre programme principal pour procéder à une vérification
234 orthographique interactive d'un texte.
236 Un exemple d'utilisation :
237 ./arbre_n_aire dictionnaire.txt mondico.txt letexte.txt motsinconnus.txt
239 Les rguments de la ligne de commande sont :
240 argv[1] est le nom du dictionnaire d'entree
241 argv[2] est le nom du dictionnaire apres insertion des nouveaux mots
242 argv[3] est le texte a verifier
243 argv[4] est un fichier contenant la liste des mots inconnus du texte
246 int main(int argc
, char *argv
[])
251 FILE *fentree
, *fsortie
;
256 ("Usage: <prog> <dico_entree> <dico_sortie> <texte> <mots_inconnus>\n");
260 rac
= charge_dico(argv
[1], &nb_mots
);
262 /* pour afficher le dictionnaire charge (attention le dictionnaire peut etre volumineux */
263 /* affiche_fich(stdout,rac,mot,0); */
264 /* affiche_arbre(rac,0); */
266 fentree
= fopen(argv
[3], "rt");
269 fsortie
= fopen(argv
[4], "wt");
273 while (Lectmot(fentree
, mot
) > 0) {
274 if (!cherche(rac
, mot
, 0)) {
276 ("Le mot <%s> n'est pas dans le dictionnaire - Dois-je l'inserer (o/n) ? ",
281 rac
= insere(rac
, mot
, 0);
284 fprintf(fsortie
, "%s\n", mot
);
291 sauve_dico(rac
, argv
[2], nb_mots
);
293 /* pour tester la suppression */
295 printf("Entrez un mot a supprimer (stop pour arreter) : ");
297 if (strcmp(mot
, "stop")) {
298 rac
= supprime(rac
, mot
, 0);
299 affiche_fich(stdout
, rac
, mot
, 0);
301 } while (strcmp(mot
, "stop"));
304 /****************************************************************************/