--- /dev/null
+/*****************************************************************************/\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
repositories / Algorithmic_C.git / blobdiff