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