Commit | Line | Data |
---|---|---|
89bde9ea JB |
1 | /*****************************************************************************/ |
2 | ||
3 | /* arbre_n_aire.c */ | |
4 | /* Representation d'un ensemble de mots sous forme d'arbre n-aire */ | |
5 | /*****************************************************************************/ | |
6 | ||
7 | #include <stdio.h> | |
8 | #include <stdlib.h> | |
9 | #include <string.h> | |
10 | #include <stdbool.h> | |
11 | ||
12 | /* nombre de caracteres max dans un mot */ | |
13 | #define N 30 | |
14 | ||
15 | typedef struct noeud | |
16 | { | |
17 | char lettre; | |
18 | struct noeud *fils; | |
19 | struct noeud *frere; | |
20 | } NOEUD; | |
21 | ||
22 | /* Recherche d'un mot dans l'arbre *****************************************/ | |
23 | bool | |
24 | recherche (NOEUD * p, char *mot, int i) | |
25 | { | |
26 | if (p == NULL) | |
27 | return false; | |
28 | if (mot[i] == p->lettre) | |
29 | { | |
30 | if (mot[i] == '\0') | |
31 | { | |
32 | return true; | |
33 | } | |
34 | else | |
35 | { | |
36 | return recherche (p->fils, mot, i + 1); | |
37 | } | |
38 | } | |
39 | else | |
40 | { | |
41 | if (p->lettre > mot[i]) | |
42 | { | |
43 | return false; | |
44 | } | |
45 | else | |
46 | { | |
47 | return recherche (p->frere, mot, i); | |
48 | } | |
49 | } | |
50 | } | |
51 | ||
52 | /* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/ | |
53 | NOEUD * | |
54 | insere_fin (char *mot, int i) | |
55 | { | |
56 | /* i est l'indice de la lettre courante dans le mot */ | |
57 | printf ("insere_fin %c, %i\n", mot[i], i); | |
58 | NOEUD *p = (NOEUD *) malloc (sizeof (NOEUD)); | |
59 | if (p == NULL) | |
60 | exit (-1); | |
61 | p->lettre = mot[i]; | |
62 | p->fils = NULL; | |
63 | p->frere = NULL; | |
64 | if (mot[i]) | |
65 | p->fils = insere_fin (mot, i + 1); | |
66 | return p; | |
67 | } | |
68 | ||
69 | /* Insertion d'un mot dans l'arbre ******************************************/ | |
70 | /* (on respecte l'ordre lexicographique des freres)**************************/ | |
71 | NOEUD * | |
72 | insere (NOEUD * p, char *mot, int i) | |
dfa8da5e JB |
73 | { |
74 | /* i est l'indice de la lettre courante dans le mot */ | |
89bde9ea JB |
75 | /* TODO */ |
76 | if (p == NULL) | |
77 | p = insere_fin (mot, i); | |
78 | return p; | |
79 | } | |
80 | ||
81 | /*****************************************************************************/ | |
82 | /* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre */ | |
83 | void | |
84 | affiche (NOEUD * p, char *mot, int i) | |
dfa8da5e JB |
85 | { |
86 | /* i est l'indice de la lettre courante dans le mot */ | |
7a4d5d57 JB |
87 | if (p != NULL) |
88 | { | |
89 | mot[i] = p->lettre; | |
90 | affiche (p->fils, mot, i + 1); | |
91 | if (mot[i] == '\0') | |
92 | { | |
93 | printf ("%s\n", mot); | |
94 | } | |
95 | affiche (p->frere, mot, i); | |
96 | } | |
89bde9ea JB |
97 | } |
98 | ||
99 | /* Visualisation de l'arbre n-aire *******************************************/ | |
100 | void | |
101 | affiche_arbre (NOEUD * p, int prof) | |
dfa8da5e | 102 | /* prof est utilise pour decaller l'affichage avec des espaces (selon le niveau dans l'arbre) */ |
89bde9ea JB |
103 | { |
104 | int i; | |
105 | if (p) | |
106 | { | |
107 | affiche_arbre (p->frere, prof); | |
108 | for (i = 0; i < prof; i++) | |
109 | printf (" "); | |
110 | printf ("%c\n", p->lettre); | |
111 | affiche_arbre (p->fils, prof + 1); | |
112 | } | |
113 | } | |
114 | ||
115 | /* Suppression d'un mot de l'arbre ********************************************/ | |
116 | /* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */ | |
117 | NOEUD * | |
118 | supprime (NOEUD * p, char *mot, int i) | |
dfa8da5e | 119 | /* i est l'indice de la lettre courante dans le mot */ |
89bde9ea JB |
120 | { |
121 | /* TODO */ | |
122 | return p; | |
123 | } | |
124 | ||
125 | /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/ | |
126 | NOEUD * | |
127 | charge_dico (char *nom_fichier, int *nb_mots) | |
128 | { | |
129 | NOEUD *p; | |
130 | FILE *fp; | |
131 | char mot[N]; | |
132 | int i; | |
133 | p = NULL; | |
134 | fp = fopen (nom_fichier, "rt"); | |
135 | if (fp == NULL) | |
136 | exit (-1); | |
137 | fscanf (fp, "%d", nb_mots); /* sur la 1ere ligne du fichier, le nombre de mots */ | |
138 | for (i = 0; i < *nb_mots; i++) | |
139 | { | |
140 | fscanf (fp, "%s", mot); | |
141 | p = insere (p, mot, 0); /* TODO il faut finir "insere" pour que "charge_dico" fonctionne */ | |
142 | } | |
143 | fclose (fp); | |
144 | return p; | |
145 | } | |
146 | ||
147 | /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/ | |
148 | void | |
149 | affiche_fich (FILE * fp, NOEUD * p, char *mot, int i) | |
150 | { | |
151 | /* TODO */ | |
152 | /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */ | |
153 | } | |
154 | ||
155 | /* Sauvegarde des mots de l'arbre dans un fichier ****************************/ | |
156 | void | |
157 | sauve_dico (NOEUD * p, char *nom_fichier, int nb_mots) | |
158 | { | |
159 | FILE *fp; | |
160 | char mot[N]; | |
161 | fp = fopen (nom_fichier, "wt"); | |
162 | if (fp == NULL) | |
163 | exit (-1); | |
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 */ | |
166 | fclose (fp); | |
167 | } | |
168 | ||
169 | /*****************************************************************************/ | |
170 | int | |
171 | main (int argc, char *argv[]) | |
172 | { | |
89bde9ea JB |
173 | char mot[N]; |
174 | NOEUD *arbre = NULL; | |
175 | printf ("saisir un mot : "); | |
176 | gets (mot); | |
177 | printf ("\ninsertion de %s\n", mot); | |
178 | arbre = insere (arbre, mot, 0); | |
7a4d5d57 JB |
179 | printf ("\naffichage mots:\n"); |
180 | affiche (arbre, mot, 0); | |
89bde9ea JB |
181 | printf ("\naffichage arbre :\n"); |
182 | affiche_arbre (arbre, 0); | |
7a4d5d57 JB |
183 | if (recherche (arbre, "toto", 0)) |
184 | printf ("mot present\n"); | |
89bde9ea JB |
185 | /* TODO */ |
186 | } | |
187 | ||
188 | /* Exemple de trace d'execution ************************* | |
189 | ||
190 | saisir un mot : salut | |
191 | ||
192 | insertion de salut | |
193 | insere_fin s, 0 | |
194 | insere_fin a, 1 | |
195 | insere_fin l, 2 | |
196 | insere_fin u, 3 | |
197 | insere_fin t, 4 | |
198 | insere_fin , 5 | |
199 | ||
200 | affichage arbre : | |
201 | s | |
202 | a | |
203 | l | |
204 | u | |
205 | t | |
206 | ||
207 | ... TODO ... | |
208 | ||
209 | **********************************************************/ |