TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.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 {
  17   char lettre;
  18   struct noeud *fils;
  19   struct noeud *frere;
  20 } NOEUD;
  21
  22 /* Recherche d'un mot dans l'arbre *****************************************/
  23 bool
  24 recherche (NOEUD * p, char *mot, int i)
  25 {
  26   if (p == NULL)
  27     return false;
  28   if (mot[i] == p->lettre)
  29     {
  30       if (mot[i] == '\0')
  31         {
  32           return true;
  33         }
  34       else
  35         {
  36           return recherche (p->fils, mot, i + 1);
  37         }
  38     }
  39   else
  40     {
  41       if (p->lettre > mot[i])
  42         {
  43           return false;
  44         }
  45       else
  46         {
  47           return recherche (p->frere, mot, i);
  48         }
  49     }
  50 }
  51
  52 /* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/
  53 NOEUD *
  54 insere_fin (char *mot, int i)
  55 {
  56   /* i est l'indice de la lettre courante dans le mot */
  57   printf ("insere_fin %c, %i\n", mot[i], i);
  58   NOEUD *p = (NOEUD *) malloc (sizeof (NOEUD));
  59   if (p == NULL)
  60     exit (-1);
  61   p->lettre = mot[i];
  62   p->fils = NULL;
  63   p->frere = NULL;
  64   if (mot[i])
  65     p->fils = insere_fin (mot, i + 1);
  66   return p;
  67 }
  68
  69 /* Insertion d'un mot dans l'arbre ******************************************/
  70 /* (on respecte l'ordre lexicographique des freres)**************************/
  71 NOEUD *
  72 insere (NOEUD * p, char *mot, int i)
  73 {                               /* i est l'indice de la lettre courante dans le mot */
  74   /* TODO */
  75   if (p == NULL)
  76     p = insere_fin (mot, i);
  77   return p;
  78 }
  79
  80 /*****************************************************************************/
  81 /* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre    */
  82 void
  83 affiche (NOEUD * p, char *mot, int i)
  84 {                               /* i est l'indice de la lettre courante dans le mot */
  85   /* TODO */
  86 }
  87
  88 /* Visualisation de l'arbre n-aire *******************************************/
  89 void
  90 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     {
  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 *
 107 supprime (NOEUD * p, char *mot, int i)
 108   /* i est l'indice de la lettre courante dans le mot */
 109 {
 110   /* TODO */
 111   return p;
 112 }
 113
 114 /* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
 115 NOEUD *
 116 charge_dico (char *nom_fichier, int *nb_mots)
 117 {
 118   NOEUD *p;
 119   FILE *fp;
 120   char mot[N];
 121   int i;
 122   p = NULL;
 123   fp = fopen (nom_fichier, "rt");
 124   if (fp == NULL)
 125     exit (-1);
 126   fscanf (fp, "%d", nb_mots);   /* sur la 1ere ligne du fichier, le nombre de mots */
 127   for (i = 0; i < *nb_mots; i++)
 128     {
 129       fscanf (fp, "%s", mot);
 130       p = insere (p, mot, 0);   /* TODO il faut finir "insere" pour que "charge_dico" fonctionne */
 131     }
 132   fclose (fp);
 133   return p;
 134 }
 135
 136 /* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
 137 void
 138 affiche_fich (FILE * fp, NOEUD * p, char *mot, int i)
 139 {
 140   /* TODO */
 141   /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */
 142 }
 143
 144 /* Sauvegarde des mots de l'arbre dans un fichier ****************************/
 145 void
 146 sauve_dico (NOEUD * p, char *nom_fichier, int nb_mots)
 147 {
 148   FILE *fp;
 149   char mot[N];
 150   fp = fopen (nom_fichier, "wt");
 151   if (fp == NULL)
 152     exit (-1);
 153   fprintf (fp, "%d\n", nb_mots);
 154   affiche_fich (fp, p, mot, 0); /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */
 155   fclose (fp);
 156 }
 157
 158 /*****************************************************************************/
 159 int
 160 main (int argc, char *argv[])
 161 {
 162
 163   char mot[N];
 164   NOEUD *arbre = NULL;
 165   printf ("saisir un mot : ");
 166   gets (mot);
 167   printf ("\ninsertion de %s\n", mot);
 168   arbre = insere (arbre, mot, 0);
 169   printf ("\naffichage arbre :\n");
 170   affiche_arbre (arbre, 0);
 171   /* TODO */
 172 }
 173
 174 /* Exemple de trace d'execution *************************
 175
 176 saisir un mot : salut
 177
 178 insertion de salut
 179 insere_fin s, 0
 180 insere_fin a, 1
 181 insere_fin l, 2
 182 insere_fin u, 3
 183 insere_fin t, 4
 184 insere_fin , 5
 185
 186 affichage arbre :
 187 s
 188  a
 189   l
 190    u
 191     t
 192
 193 ... TODO ...
 194
 195 **********************************************************/