TP6/arbres/arbre_n_aire_c1/arbre_n_aire_correction.c

   1 /*****************************************************************************/
   2 /*                          arbre_n_aire.c                                   */
   3 /*               Representation de mots sous forme d'arbre n-aire            */
   4 /*****************************************************************************/
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <ctype.h>
  10
  11 #define N 30
  12
  13
  14 typedef struct noeud {
  15     char lettre;
  16     struct noeud *fils;
  17     struct noeud *frere;
  18 } NOEUD;
  19
  20
  21 /* Recherche d'un mot dans l'arbre *****************************************/
  22 NOEUD *cherche(NOEUD * p, char *mot, int i)
  23 {
  24     if (p == NULL)
  25         return NULL;
  26     if (p->lettre == mot[i]) {
  27         if (mot[i])
  28             return cherche(p->fils, mot, i + 1);
  29         else
  30             return p;
  31     } else if (p->lettre > mot[i])
  32         return NULL;
  33     else
  34         return cherche(p->frere, mot, i);
  35 }
  36
  37 /***************************************************************************/
  38 NOEUD *recherche(NOEUD * p, char *mot)
  39 {
  40     return cherche(p, mot, 0);
  41 }
  42
  43
  44 /* Création d'une fin de mot - liste chaînée suivant le lien fils **********/
  45 NOEUD *insere_fin(char *mot, int i)
  46 {
  47     NOEUD *p = (NOEUD *) malloc(sizeof(NOEUD));
  48
  49     if (p == NULL)
  50         exit(-1);
  51     p->lettre = mot[i];
  52     p->fils = NULL;
  53     p->frere = NULL;
  54     if (mot[i])
  55         p->fils = insere_fin(mot, i + 1);
  56     return p;
  57 }
  58
  59
  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)
  63 {
  64     NOEUD *p1;
  65
  66     if (p == NULL)
  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);
  71         else
  72             printf("Le mot est deja dans le dictionnaire\n");
  73     else if (p->lettre > mot[i]) {
  74         p1 = insere_fin(mot, i);
  75         p1->frere = p;
  76         p = p1;
  77     } else
  78         p->frere = insere(p->frere, mot, i);
  79     return p;
  80 }
  81
  82
  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)
  86 {
  87     int j;
  88
  89     if (p) {
  90         mot[i] = p->lettre;
  91         if (!mot[i]) {
  92             for (j = 0; j < i; j++)
  93                 fprintf(fp, "%c", mot[j]);
  94             fprintf(fp, "\n");
  95         };
  96         affiche_fich(fp, p->fils, mot, i + 1);
  97         affiche_fich(fp, p->frere, mot, i);
  98     }
  99 }
 100
 101
 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)
 105 {
 106     int j;
 107
 108     if (p) {
 109         mot[i] = p->lettre;
 110         if (mot[i] == '\0')
 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);
 114     }
 115 }
 116
 117
 118 /*****************************************************************************/
 119 /* Visualisation de l'arbre n-aire - parcour "frère - racine - fils"         */
 120 void affiche_arbre(NOEUD * p, int prof)
 121 {
 122     int i;
 123
 124     if (p) {
 125         affiche_arbre(p->frere, prof);
 126         for (i = 0; i < prof; i++)
 127             printf(" ");
 128         printf("%c\n", p->lettre);
 129         affiche_arbre(p->fils, prof + 1);
 130     }
 131 }
 132
 133
 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)
 138 {
 139     NOEUD *p1;
 140
 141     if (p)
 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);
 146             if (!p->fils) {
 147                 p1 = p;
 148                 p = p->frere;
 149                 free(p1);
 150             }
 151         } else
 152             printf("%s n'est pas present\n", mot);
 153     return p;
 154 }
 155
 156 /*****************************************************************************/
 157 NOEUD *charge_dico(char *nom_fichier, int *nb_mots)
 158 {
 159     NOEUD *p;
 160     FILE *fp;
 161     char mot[N];
 162     int i;
 163
 164     p = NULL;
 165     fp = fopen(nom_fichier, "rt");
 166     if (fp == NULL)
 167         exit(-1);
 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);
 172     }
 173     fclose(fp);
 174     return p;
 175 }
 176
 177
 178 /*****************************************************************************/
 179 void sauve_dico(NOEUD * p, char *nom_fichier, int nb_mots)
 180 {
 181     FILE *fp;
 182     char mot[N];
 183
 184     fp = fopen(nom_fichier, "wt");
 185     if (fp == NULL)
 186         exit(-1);
 187     fprintf(fp, "%d\n", nb_mots);
 188     affiche_fich(fp, p, mot, 0);
 189     fclose(fp);
 190 }
 191
 192
 193 /*****************************************************************************/
 194 char EstSeparateur(char c)
 195 {
 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 == ')')));
 201 }
 202
 203
 204 /****************************************************************************/
 205 /*  Lit un mot a partir du fichier fd.
 206   texte == <separateur>* <mot> <separateur>*
 207   mot = <caractere>*.
 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)
 211 {
 212     int i = 0;
 213     char c;
 214
 215     /* Lecture des separateurs */
 216     while (((c = (char) fgetc(fp)) != (char) EOF) && (EstSeparateur(c)));
 217
 218     /* Debut du mot */
 219     while (c != (char) EOF) {
 220         if (!EstSeparateur(c))
 221             mot[i++] = tolower(c);
 222         else
 223             break;
 224         c = (char) fgetc(fp);
 225     }
 226     mot[i] = '\0';
 227     return (i);
 228 }
 229
 230
 231 /*****************************************************************************/
 232 int main(int argc, char *argv[])
 233 {
 234     char mot[N];
 235     NOEUD *arbre = NULL;
 236
 237     /* test insertion */
 238     do {
 239         printf("\nEntrez un mot a inserer (0 pour arreter) : ");
 240         scanf("%s", mot);
 241         if (strcmp(mot, "0")) {
 242             printf("insertion de %s\n", mot);
 243             arbre = insere(arbre, mot, 0);
 244         }
 245     } while (strcmp(mot, "0"));
 246
 247     /* test affichage */
 248     printf("\naffichage arbre :\n");
 249     affiche_arbre(arbre, 0);
 250
 251     printf("\nmots dans l'arbre :\n");
 252     affiche(arbre, mot, 0);
 253
 254     /* test suppression */
 255     do {
 256         printf("\nEntrez un mot a supprimer (0 pour arreter) : ");
 257         scanf("%s", mot);
 258         if (strcmp(mot, "0")) {
 259             printf("suppression de %s\n", mot);
 260             arbre = supprime(arbre, mot, 0);
 261             affiche(arbre, mot, 0);
 262         }
 263     } while (strcmp(mot, "0"));
 264
 265     /* affiche_fich(stdout,arbre,mot,0); */
 266
 267 }
 268
 269 /* exemple d'execution ***
 270 Entrez un mot a inserer (0 pour arreter) : baba
 271 insertion de baba
 272
 273 Entrez un mot a inserer (0 pour arreter) : baobab
 274 insertion de baobab
 275
 276 Entrez un mot a inserer (0 pour arreter) : bonjour
 277 insertion de bonjour
 278
 279 Entrez un mot a inserer (0 pour arreter) : salut
 280 insertion de salut
 281
 282 Entrez un mot a inserer (0 pour arreter) : salopette
 283 insertion de salopette
 284
 285 Entrez un mot a inserer (0 pour arreter) : salutation
 286 insertion de salutation
 287
 288 Entrez un mot a inserer (0 pour arreter) : 0
 289
 290 affichage arbre :
 291 s
 292  a
 293   l
 294    u
 295     t
 296      a
 297       t
 298        i
 299         o
 300          n
 301
 302
 303    o
 304     p
 305      e
 306       t
 307        t
 308         e
 309
 310 b
 311  o
 312   n
 313    j
 314     o
 315      u
 316       r
 317
 318  a
 319   o
 320    b
 321     a
 322      b
 323
 324   b
 325    a
 326
 327
 328 mots dans l'arbre :
 329 baba
 330 baobab
 331 bonjour
 332 salopette
 333 salut
 334 salutation
 335
 336 Entrez un mot a supprimer (0 pour arreter) : ba
 337 suppression de ba
 338 ba n'est pas present
 339 baba
 340 baobab
 341 bonjour
 342 salopette
 343 salut
 344 salutation
 345
 346 Entrez un mot a supprimer (0 pour arreter) : baoba
 347 suppression de baoba
 348 baoba n'est pas present
 349 baba
 350 baobab
 351 bonjour
 352 salopette
 353 salut
 354 salutation
 355
 356 Entrez un mot a supprimer (0 pour arreter) : baobab
 357 suppression de baobab
 358 baba
 359 bonjour
 360 salopette
 361 salut
 362 salutation
 363 Entrez un mot a supprimer (0 pour arreter) : salut
 364 suppression de salut
 365 baba
 366 bonjour
 367 salopette
 368 salutation
 369
 370 Entrez un mot a supprimer (0 pour arreter) : 0 */