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 /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
 114 NOEUD *charge_dico(char *nom_fichier, int *nb_mots)
 115 {
 116     NOEUD *p;
 117     FILE *fp;
 118     char mot[N];
 119     int i;
 120     p = NULL;
 121
 122     fp = fopen(nom_fichier, "rt");
 123     if (fp == NULL)
 124         exit(-1);
 125     fscanf(fp, "%d", nb_mots);  /* sur la 1ere ligne du fichier, le nombre de mots */
 126     for (i = 0; i < *nb_mots; i++) {
 127         fscanf(fp, "%s", mot);
 128         p = insere(p, mot, 0);
 129     }
 130     fclose(fp);
 131     return p;
 132 }
 133
 134 /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
 135 void affiche_fich(FILE * fp, NOEUD * p, char *mot, int i)
 136 {
 137     /* TODO */
 138     /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */
 139 }
 140
 141 /* Sauvegarde des mots de l'arbre dans un fichier ****************************/
 142 void sauve_dico(NOEUD * p, char *nom_fichier, int nb_mots)
 143 {
 144     FILE *fp;
 145     char mot[N];
 146
 147     fp = fopen(nom_fichier, "wt");
 148     if (fp == NULL)
 149         exit(-1);
 150     fprintf(fp, "%d\n", nb_mots);
 151     affiche_fich(fp, p, mot, 0);        /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */
 152     fclose(fp);
 153 }
 154
 155 /*****************************************************************************/
 156 int main(int argc, char *argv[])
 157 {
 158     char mot[N];
 159     int nb_mots = 0;
 160     NOEUD *arbre = NULL;
 161
 162     //printf ("saisir un mot : ");
 163     //gets (mot);
 164     //printf ("\ninsertion de %s\n", mot);
 165     //arbre = insere (arbre, mot, 0);
 166     arbre = charge_dico("dictionnaire", &nb_mots);
 167     printf("\naffichage mots :\n");
 168     affiche(arbre, mot, 0);
 169     printf("\naffichage arbre :\n");
 170     affiche_arbre(arbre, 0);
 171     if (recherche(arbre, "salut", 0))
 172         printf("mot \"salut\" present\n");
 173     free(arbre);
 174     /* TODO */
 175 }
 176
 177 /* Exemple de trace d'execution *************************
 178
 179 saisir un mot : salut
 180
 181 insertion de salut
 182 insere_fin s, 0
 183 insere_fin a, 1
 184 insere_fin l, 2
 185 insere_fin u, 3
 186 insere_fin t, 4
 187 insere_fin , 5
 188
 189 affichage arbre :
 190 s
 191  a
 192   l
 193    u
 194     t
 195
 196 ... TODO ...
 197
 198 **********************************************************/