TP6/arbres/arbre_n_aire_c2/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 /* Création d'une fin de mot - liste chaînée suivant le lien fils **********/
  44 NOEUD *insere_fin(char *mot, int i)
  45 {
  46     NOEUD *p = (NOEUD *) malloc(sizeof(NOEUD));
  47
  48     if (p == NULL)
  49         exit(-1);
  50     p->lettre = mot[i];
  51     p->fils = NULL;
  52     p->frere = NULL;
  53     if (mot[i])
  54         p->fils = insere_fin(mot, i + 1);
  55     return p;
  56 }
  57
  58
  59 /* Insertion d'un mot dans l'arbre ******************************************/
  60 /* on respecte l'ordre lexicographique des frères **************************/
  61 NOEUD *insere(NOEUD * p, char *mot, int i)
  62 {
  63     NOEUD *p1;
  64
  65     if (p == NULL)
  66         p = insere_fin(mot, i);
  67     else if (p->lettre == mot[i])
  68         if (mot[i] != '\0')     /* if (mot[i]) */
  69             p->fils = insere(p->fils, mot, i + 1);
  70         else
  71             printf("Le mot est deja dans le dictionnaire\n");
  72     else if (p->lettre > mot[i]) {
  73         p1 = insere_fin(mot, i);
  74         p1->frere = p;
  75         p = p1;
  76     } else
  77         p->frere = insere(p->frere, mot, i);
  78     return p;
  79 }
  80
  81
  82 /*****************************************************************************/
  83 /* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre    */
  84 void affiche_fich(FILE * fp, NOEUD * p, char *mot, int i)
  85 {
  86     int j;
  87
  88     if (p) {
  89         mot[i] = p->lettre;
  90         if (!mot[i]) {
  91             for (j = 0; j < i; j++)
  92                 fprintf(fp, "%c", mot[j]);
  93             fprintf(fp, "\n");
  94         };
  95         affiche_fich(fp, p->fils, mot, i + 1);
  96         affiche_fich(fp, p->frere, mot, i);
  97     }
  98 }
  99
 100
 101 /* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre    */
 102 /* parcours en profondeur d'abord, prefixe (idem si infixe, voir la remarque plus loin) */
 103 void affiche(NOEUD * p, char *mot, int i)
 104 {
 105     int j;
 106
 107     if (p) {
 108         mot[i] = p->lettre;
 109         if (mot[i] == '\0')
 110             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 */
 111         affiche(p->fils, mot, i + 1);
 112         affiche(p->frere, mot, i);
 113     }
 114 }
 115
 116
 117 /*****************************************************************************/
 118 /* Visualisation de l'arbre n-aire - parcour "frère - racine - fils"         */
 119 void affiche_arbre(NOEUD * p, int prof)
 120 {
 121     int i;
 122
 123     if (p) {
 124         affiche_arbre(p->frere, prof);
 125         for (i = 0; i < prof; i++)
 126             printf(" ");
 127         printf("%c\n", p->lettre);
 128         affiche_arbre(p->fils, prof + 1);
 129     }
 130 }
 131
 132
 133 /*****************************************************************************/
 134 /* Attention à ne supprimer que la fin du mot qui n'est partagée par aucun
 135    autre mot de l'arbre                                                      */
 136 NOEUD *supprime(NOEUD * p, char *mot, int i)
 137 {
 138     NOEUD *p1;
 139
 140     if (p)
 141         if (p->lettre < mot[i])
 142             p->frere = supprime(p->frere, mot, i);
 143         else if (p->lettre == mot[i]) {
 144             p->fils = supprime(p->fils, mot, i + 1);
 145             if (!p->fils) {
 146                 p1 = p;
 147                 p = p->frere;
 148                 free(p1);
 149             }
 150         } else
 151             printf("%s n'est pas present\n", mot);
 152     return p;
 153 }
 154
 155
 156 NOEUD *detruis_arbre(NOEUD * p)
 157 {
 158     if (p == NULL)
 159         return p;
 160     else {
 161         p->fils = detruis_arbre(p->fils);
 162         p->frere = detruis_arbre(p->frere);
 163         free(p);
 164         p = NULL;
 165         return p;
 166     }
 167 }
 168
 169 /*****************************************************************************/
 170 NOEUD *charge_dico(char *nom_fichier, int *nb_mots)
 171 {
 172     NOEUD *p;
 173     FILE *fp;
 174     char mot[N];
 175     int i;
 176
 177     p = NULL;
 178     fp = fopen(nom_fichier, "rt");
 179     if (fp == NULL)
 180         exit(-1);
 181     fscanf(fp, "%d", nb_mots);  /* sur la 1ère ligne du fichier, le nombre de mots */
 182     for (i = 0; i < *nb_mots; i++) {
 183         fscanf(fp, "%s", mot);
 184         p = insere(p, mot, 0);
 185     }
 186     fclose(fp);
 187     return p;
 188 }
 189
 190
 191 /*****************************************************************************/
 192 void sauve_dico(NOEUD * p, char *nom_fichier, int nb_mots)
 193 {
 194     FILE *fp;
 195     char mot[N];
 196
 197     fp = fopen(nom_fichier, "wt");
 198     if (fp == NULL)
 199         exit(-1);
 200     fprintf(fp, "%d\n", nb_mots);
 201     affiche_fich(fp, p, mot, 0);
 202     fclose(fp);
 203 }
 204
 205
 206 /*****************************************************************************/
 207 char EstSeparateur(char c)
 208 {
 209     return (((c == '\'') || (c == '"') || (c == ',') || (c == ';')
 210              || (c == '.') || (c == '\n') || (c == '?') || (c == '!')
 211              || (c == ':') || (c == ' ') || (c == '\t') || (c == '-')
 212              || (c == '*') || (c == '+') || (c == '=') || (c == '\b')
 213              || (c == '{') || (c == '}') || (c == '(') || (c == ')')));
 214 }
 215
 216
 217 /****************************************************************************/
 218 /*  Lit un mot a partir du fichier fd.
 219   texte == <separateur>* <mot> <separateur>*
 220   mot = <caractere>*.
 221   Le mot est retourné sous une forme minuscule.
 222   Quant on a atteint la fin de fichier, la fonction retourne 0             */
 223 int Lectmot(FILE * fp, char *mot)
 224 {
 225     int i = 0;
 226     char c;
 227
 228     /* Lecture des separateurs */
 229     while (((c = (char) fgetc(fp)) != (char) EOF) && (EstSeparateur(c)));
 230
 231     /* Debut du mot */
 232     while (c != (char) EOF) {
 233         if (!EstSeparateur(c))
 234             mot[i++] = tolower(c);
 235         else
 236             break;
 237         c = (char) fgetc(fp);
 238     }
 239     mot[i] = '\0';
 240     return (i);
 241 }
 242
 243
 244 /****************************************************************************/
 245
 246 /* voici un autre programme principal pour procéder à une vérification
 247    orthographique interactive d'un texte.
 248
 249 Un exemple d'utilisation :
 250  ./arbre_n_aire dictionnaire.txt mondico.txt letexte.txt motsinconnus.txt
 251
 252 Les arguments de la ligne de commande sont :
 253    argv[1] est le nom du dictionnaire d'entree
 254    argv[2] est le nom du dictionnaire apres insertion des nouveaux mots
 255    argv[3] est le texte a verifier
 256    argv[4] est un fichier contenant la liste des mots inconnus du texte
 257 */
 258
 259 int main(int argc, char *argv[])
 260 {
 261     char mot[N];
 262     char rep;
 263     NOEUD *rac;
 264     FILE *fentree, *fsortie;
 265     int nb_mots;
 266
 267     if (argc != 5) {
 268         printf
 269             ("Usage: <prog> <dico_entree> <dico_sortie> <texte> <mots_inconnus>\n");
 270         exit(-1);
 271     };
 272
 273     rac = charge_dico(argv[1], &nb_mots);
 274
 275     /* pour afficher le dictionnaire charge (attention le dictionnaire peut etre volumineux */
 276     /* affiche_fich(stdout,rac,mot,0); */
 277     /* affiche_arbre(rac,0); */
 278
 279     fentree = fopen(argv[3], "rt");
 280     if (fentree == NULL)
 281         exit(-1);
 282     fsortie = fopen(argv[4], "wt");
 283     if (fsortie == NULL)
 284         exit(-1);
 285
 286     while (Lectmot(fentree, mot) > 0) {
 287         if (!cherche(rac, mot, 0)) {
 288             printf
 289                 ("Le mot <%s> n'est pas dans le dictionnaire - Dois-je l'inserer (o/n) ? ",
 290                  mot);
 291             scanf("%c", &rep);
 292             getchar();
 293             if (rep == 'o') {
 294                 rac = insere(rac, mot, 0);
 295                 nb_mots++;
 296             } else
 297                 fprintf(fsortie, "%s\n", mot);
 298         }
 299     }
 300
 301     fclose(fentree);
 302     fclose(fsortie);
 303
 304     sauve_dico(rac, argv[2], nb_mots);
 305
 306     /* pour tester la suppression */
 307     do {
 308         printf("Entrez un mot a supprimer (stop pour arreter) : ");
 309         scanf("%s", mot);
 310         if (strcmp(mot, "stop")) {
 311             rac = supprime(rac, mot, 0);
 312             affiche_fich(stdout, rac, mot, 0);
 313         }
 314     } while (strcmp(mot, "stop"));
 315
 316     detruis_arbre(rac);
 317 }
 318
 319 /****************************************************************************/