TP6/arbres/arbre_n_aire/arbre_n_aire.c

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