TP6: Add ABR and tree n

[Algorithmic_C.git] / TP6 / arbres / arbre-n-aire / arbre_n_aire_a_completer.c

/*****************************************************************************/\r
/*                          arbre_n_aire.c                                   */\r
/*     Representation d'un ensemble de mots sous forme d'arbre n-aire        */\r
/*****************************************************************************/\r
\r
#include <stdio.h>\r
#include <stdlib.h>\r
#include <string.h>\r
\r
\r
/* nombre de caracteres max dans un mot */\r
#define N 30\r
\r
\r
typedef struct noeud {\r
 char lettre;\r
 struct noeud *fils;\r
 struct noeud *frere;\r
} NOEUD;\r
\r
\r
\r
/* Recherche d'un mot dans l'arbre *****************************************/ 	\r
int recherche(NOEUD *p, char *mot, int i)\r
{\r
 /* TODO */\r
 return 0;\r
}\r
\r
\r
\r
/* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/\r
NOEUD *insere_fin(char *mot, int i) /* i est l'indice de la lettre courante dans le mot */\r
{\r
 printf("insere_fin %c, %i\n", mot[i], i);\r
 NOEUD *p = (NOEUD *)malloc(sizeof(NOEUD));\r
 if(p == NULL) exit(-1);\r
 p->lettre = mot[i]; \r
 p->fils = NULL; \r
 p->frere = NULL;\r
 if(mot[i]) p->fils = insere_fin(mot, i+1);\r
 return p;\r
}\r
\r
\r
/* Insertion d'un mot dans l'arbre ******************************************/\r
/* (on respecte l'ordre lexicographique des freres)**************************/\r
NOEUD *insere(NOEUD *p, char *mot, int i) /* i est l'indice de la lettre courante dans le mot */\r
{\r
 /* TODO */\r
 if(p == NULL) p = insere_fin(mot, i);\r
 return p;\r
}\r
\r
	   \r
/*****************************************************************************/\r
/* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre    */\r
void affiche(NOEUD *p, char *mot, int i) /* i est l'indice de la lettre courante dans le mot */\r
{\r
 /* TODO */	\r
}\r
\r
\r
/* Visualisation de l'arbre n-aire *******************************************/\r
void affiche_arbre(NOEUD *p, int prof) /* prof est utilise pour decaller l'affichage avec des espaces  (selon le niveau dans l'arbre) */\r
{\r
 int i;\r
 if(p) \r
 {\r
  affiche_arbre(p->frere,prof);\r
  for (i=0;i<prof;i++) printf(" ");\r
  printf("%c\n",p->lettre);\r
  affiche_arbre(p->fils,prof+1);\r
 }\r
}\r
\r
\r
/* Suppression d'un mot de l'arbre ********************************************/\r
/* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */\r
NOEUD *supprime(NOEUD *p, char *mot, int i) /* i est l'indice de la lettre courante dans le mot */\r
{\r
 /* TODO */\r
 return p;\r
}\r
\r
\r
\r
/* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/\r
NOEUD *charge_dico(char *nom_fichier, int *nb_mots)\r
{\r
 NOEUD *p;\r
 FILE *fp;\r
 char mot[N];\r
 int i;\r
 	\r
 p = NULL;	\r
 fp = fopen(nom_fichier,"rt");\r
 if (fp == NULL) exit(-1);\r
 fscanf(fp,"%d",nb_mots); /* sur la 1ere ligne du fichier, le nombre de mots */\r
 for (i=0; i< *nb_mots; i++) \r
  {\r
   fscanf(fp,"%s",mot);\r
   p = insere(p, mot, 0); /* TODO il faut finir "insere" pour que "charge_dico" fonctionne */\r
  }\r
 fclose(fp);\r
 return p;\r
}\r
\r
\r
\r
/* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/\r
void affiche_fich(FILE *fp, NOEUD *p, char *mot, int i)\r
{	\r
 /* TODO */\r
 /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */\r
}\r
\r
\r
/* Sauvegarde des mots de l'arbre dans un fichier ****************************/\r
void sauve_dico(NOEUD *p, char *nom_fichier, int nb_mots)\r
{\r
 FILE *fp;\r
 char mot[N];\r
 	\r
 fp = fopen(nom_fichier,"wt");\r
 if (fp == NULL) exit(-1);\r
 fprintf(fp,"%d\n",nb_mots);\r
 affiche_fich(fp,p,mot,0); /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */\r
 fclose(fp);\r
}\r
\r
\r
\r
\r
/*****************************************************************************/\r
int main(int argc, char *argv[])\r
{\r
 char mot[N];\r
 NOEUD *arbre = NULL;\r
\r
 printf("saisir un mot : ");\r
 gets(mot); \r
\r
 printf("\ninsertion de %s\n", mot);\r
 arbre = insere(arbre, mot, 0);\r
\r
 printf("\naffichage arbre :\n");\r
 affiche_arbre(arbre, 0);\r
\r
 /* TODO */\r
\r
}\r
\r
\r
\r
/* Exemple de trace d'execution *************************\r
\r
saisir un mot : salut\r
\r
insertion de salut\r
insere_fin s, 0\r
insere_fin a, 1\r
insere_fin l, 2\r
insere_fin u, 3\r
insere_fin t, 4\r
insere_fin , 5\r
\r
affichage arbre :\r
s\r
 a\r
  l\r
   u\r
    t\r
     \r
... TODO ...\r
\r
**********************************************************/ 	\r
\r