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