TP6/arbres/arbre-n-aire/arbre_n_aire.c

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