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 /*****************************************************************************/
 158 NOEUD *charge_dico(char *nom_fichier, int *nb_mots)
 159 {
 160     NOEUD *p;
 161     FILE *fp;
 162     char mot[N];
 163     int i;
 164
 165     p = NULL;
 166     fp = fopen(nom_fichier, "rt");
 167     if (fp == NULL)
 168         exit(-1);
 169     fscanf(fp, "%d", nb_mots);  /* sur la 1ère ligne du fichier, le nombre de mots */
 170     for (i = 0; i < *nb_mots; i++) {
 171         fscanf(fp, "%s", mot);
 172         p = insere(p, mot, 0);
 173     }
 174     fclose(fp);
 175     return p;
 176 }
 177
 178
 179 NOEUD *detruis_arbre(NOEUD * p)
 180 {
 181     if (p == NULL)
 182         return p;
 183     else {
 184         p->fils = detruis_arbre(p->fils);
 185         p->frere = detruis_arbre(p->frere);
 186         free(p);
 187         p = NULL;
 188         return p;
 189     }
 190 }
 191
 192
 193 /*****************************************************************************/
 194 void sauve_dico(NOEUD * p, char *nom_fichier, int nb_mots)
 195 {
 196     FILE *fp;
 197     char mot[N];
 198
 199     fp = fopen(nom_fichier, "wt");
 200     if (fp == NULL)
 201         exit(-1);
 202     fprintf(fp, "%d\n", nb_mots);
 203     affiche_fich(fp, p, mot, 0);
 204     fclose(fp);
 205 }
 206
 207
 208 /*****************************************************************************/
 209 char EstSeparateur(char c)
 210 {
 211     return (((c == '\'') || (c == '"') || (c == ',') || (c == ';')
 212              || (c == '.') || (c == '\n') || (c == '?') || (c == '!')
 213              || (c == ':') || (c == ' ') || (c == '\t') || (c == '-')
 214              || (c == '*') || (c == '+') || (c == '=') || (c == '\b')
 215              || (c == '{') || (c == '}') || (c == '(') || (c == ')')));
 216 }
 217
 218
 219 /****************************************************************************/
 220 /*  Lit un mot a partir du fichier fd.
 221   texte == <separateur>* <mot> <separateur>*
 222   mot = <caractere>*.
 223   Le mot est retourné sous une forme minuscule.
 224   Quant on a atteint la fin de fichier, la fonction retourne 0             */
 225 int Lectmot(FILE * fp, char *mot)
 226 {
 227     int i = 0;
 228     char c;
 229
 230     /* Lecture des separateurs */
 231     while (((c = (char) fgetc(fp)) != (char) EOF) && (EstSeparateur(c)));
 232
 233     /* Debut du mot */
 234     while (c != (char) EOF) {
 235         if (!EstSeparateur(c))
 236             mot[i++] = tolower(c);
 237         else
 238             break;
 239         c = (char) fgetc(fp);
 240     }
 241     mot[i] = '\0';
 242     return (i);
 243 }
 244
 245
 246 /*****************************************************************************/
 247 int main(int argc, char *argv[])
 248 {
 249     char mot[N];
 250     NOEUD *arbre = NULL;
 251
 252     /* test insertion */
 253     do {
 254         printf("\nEntrez un mot a inserer (0 pour arreter) : ");
 255         scanf("%s", mot);
 256         if (strcmp(mot, "0")) {
 257             printf("insertion de %s\n", mot);
 258             arbre = insere(arbre, mot, 0);
 259         }
 260     } while (strcmp(mot, "0"));
 261
 262     /* test affichage */
 263     printf("\naffichage arbre :\n");
 264     affiche_arbre(arbre, 0);
 265
 266     printf("\nmots dans l'arbre :\n");
 267     affiche(arbre, mot, 0);
 268
 269     /* test suppression */
 270     do {
 271         printf("\nEntrez un mot a supprimer (0 pour arreter) : ");
 272         scanf("%s", mot);
 273         if (strcmp(mot, "0")) {
 274             printf("suppression de %s\n", mot);
 275             arbre = supprime(arbre, mot, 0);
 276             affiche(arbre, mot, 0);
 277         }
 278     } while (strcmp(mot, "0"));
 279
 280     /* affiche_fich(stdout,arbre,mot,0); */
 281     detruis_arbre(arbre);
 282
 283 }
 284
 285 /* exemple d'execution ***
 286 Entrez un mot a inserer (0 pour arreter) : baba
 287 insertion de baba
 288
 289 Entrez un mot a inserer (0 pour arreter) : baobab
 290 insertion de baobab
 291
 292 Entrez un mot a inserer (0 pour arreter) : bonjour
 293 insertion de bonjour
 294
 295 Entrez un mot a inserer (0 pour arreter) : salut
 296 insertion de salut
 297
 298 Entrez un mot a inserer (0 pour arreter) : salopette
 299 insertion de salopette
 300
 301 Entrez un mot a inserer (0 pour arreter) : salutation
 302 insertion de salutation
 303
 304 Entrez un mot a inserer (0 pour arreter) : 0
 305
 306 affichage arbre :
 307 s
 308  a
 309   l
 310    u
 311     t
 312      a
 313       t
 314        i
 315         o
 316          n
 317
 318
 319    o
 320     p
 321      e
 322       t
 323        t
 324         e
 325
 326 b
 327  o
 328   n
 329    j
 330     o
 331      u
 332       r
 333
 334  a
 335   o
 336    b
 337     a
 338      b
 339
 340   b
 341    a
 342
 343
 344 mots dans l'arbre :
 345 baba
 346 baobab
 347 bonjour
 348 salopette
 349 salut
 350 salutation
 351
 352 Entrez un mot a supprimer (0 pour arreter) : ba
 353 suppression de ba
 354 ba n'est pas present
 355 baba
 356 baobab
 357 bonjour
 358 salopette
 359 salut
 360 salutation
 361
 362 Entrez un mot a supprimer (0 pour arreter) : baoba
 363 suppression de baoba
 364 baoba n'est pas present
 365 baba
 366 baobab
 367 bonjour
 368 salopette
 369 salut
 370 salutation
 371
 372 Entrez un mot a supprimer (0 pour arreter) : baobab
 373 suppression de baobab
 374 baba
 375 bonjour
 376 salopette
 377 salut
 378 salutation
 379 Entrez un mot a supprimer (0 pour arreter) : salut
 380 suppression de salut
 381 baba
 382 bonjour
 383 salopette
 384 salutation
 385
 386 Entrez un mot a supprimer (0 pour arreter) : 0 */