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