From 89bde9ead46dabc9fc95629602035482bca29145 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 30 Mar 2017 14:29:27 +0200 Subject: [PATCH] TP6: Add search function to arbre_n_aire.c MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- .../arbre-n-aire/arbre_n_aire_a_completer.c | 373 +++++++++--------- 1 file changed, 195 insertions(+), 178 deletions(-) diff --git a/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c b/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c index 4d4b97f..7b2d186 100644 --- a/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c +++ b/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c @@ -1,178 +1,195 @@ -/*****************************************************************************/ -/* arbre_n_aire.c */ -/* Representation d'un ensemble de mots sous forme d'arbre n-aire */ -/*****************************************************************************/ - -#include -#include -#include - - -/* nombre de caracteres max dans un mot */ -#define N 30 - - -typedef struct noeud { - char lettre; - struct noeud *fils; - struct noeud *frere; -} NOEUD; - - - -/* Recherche d'un mot dans l'arbre *****************************************/ -int recherche(NOEUD *p, char *mot, int i) -{ - /* TODO */ - return 0; -} - - - -/* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/ -NOEUD *insere_fin(char *mot, int i) /* i est l'indice de la lettre courante dans le mot */ -{ - printf("insere_fin %c, %i\n", mot[i], i); - NOEUD *p = (NOEUD *)malloc(sizeof(NOEUD)); - if(p == NULL) exit(-1); - p->lettre = mot[i]; - p->fils = NULL; - p->frere = NULL; - if(mot[i]) p->fils = insere_fin(mot, i+1); - return p; -} - - -/* Insertion d'un mot dans l'arbre ******************************************/ -/* (on respecte l'ordre lexicographique des freres)**************************/ -NOEUD *insere(NOEUD *p, char *mot, int i) /* i est l'indice de la lettre courante dans le mot */ -{ - /* TODO */ - if(p == NULL) p = insere_fin(mot, i); - return p; -} - - -/*****************************************************************************/ -/* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre */ -void affiche(NOEUD *p, char *mot, int i) /* i est l'indice de la lettre courante dans le mot */ -{ - /* TODO */ -} - - -/* Visualisation de l'arbre n-aire *******************************************/ -void affiche_arbre(NOEUD *p, int prof) /* prof est utilise pour decaller l'affichage avec des espaces (selon le niveau dans l'arbre) */ -{ - int i; - if(p) - { - affiche_arbre(p->frere,prof); - for (i=0;ilettre); - affiche_arbre(p->fils,prof+1); - } -} - - -/* Suppression d'un mot de l'arbre ********************************************/ -/* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */ -NOEUD *supprime(NOEUD *p, char *mot, int i) /* i est l'indice de la lettre courante dans le mot */ -{ - /* TODO */ - return p; -} - - - -/* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/ -NOEUD *charge_dico(char *nom_fichier, int *nb_mots) -{ - NOEUD *p; - FILE *fp; - char mot[N]; - int i; - - p = NULL; - fp = fopen(nom_fichier,"rt"); - if (fp == NULL) exit(-1); - fscanf(fp,"%d",nb_mots); /* sur la 1ere ligne du fichier, le nombre de mots */ - for (i=0; i< *nb_mots; i++) - { - fscanf(fp,"%s",mot); - p = insere(p, mot, 0); /* TODO il faut finir "insere" pour que "charge_dico" fonctionne */ - } - fclose(fp); - return p; -} - - - -/* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/ -void affiche_fich(FILE *fp, NOEUD *p, char *mot, int i) -{ - /* TODO */ - /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */ -} - - -/* Sauvegarde des mots de l'arbre dans un fichier ****************************/ -void sauve_dico(NOEUD *p, char *nom_fichier, int nb_mots) -{ - FILE *fp; - char mot[N]; - - fp = fopen(nom_fichier,"wt"); - if (fp == NULL) exit(-1); - fprintf(fp,"%d\n",nb_mots); - affiche_fich(fp,p,mot,0); /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */ - fclose(fp); -} - - - - -/*****************************************************************************/ -int main(int argc, char *argv[]) -{ - char mot[N]; - NOEUD *arbre = NULL; - - printf("saisir un mot : "); - gets(mot); - - printf("\ninsertion de %s\n", mot); - arbre = insere(arbre, mot, 0); - - printf("\naffichage arbre :\n"); - affiche_arbre(arbre, 0); - - /* TODO */ - -} - - - -/* Exemple de trace d'execution ************************* - -saisir un mot : salut - -insertion de salut -insere_fin s, 0 -insere_fin a, 1 -insere_fin l, 2 -insere_fin u, 3 -insere_fin t, 4 -insere_fin , 5 - -affichage arbre : -s - a - l - u - t - -... TODO ... - -**********************************************************/ - +/*****************************************************************************/ + +/* arbre_n_aire.c */ +/* Representation d'un ensemble de mots sous forme d'arbre n-aire */ +/*****************************************************************************/ + +#include +#include +#include +#include + +/* nombre de caracteres max dans un mot */ +#define N 30 + +typedef struct noeud +{ + char lettre; + struct noeud *fils; + struct noeud *frere; +} NOEUD; + +/* Recherche d'un mot dans l'arbre *****************************************/ +bool +recherche (NOEUD * p, char *mot, int i) +{ + if (p == NULL) + return false; + if (mot[i] == p->lettre) + { + if (mot[i] == '\0') + { + return true; + } + else + { + return recherche (p->fils, mot, i + 1); + } + } + else + { + if (p->lettre > mot[i]) + { + return false; + } + else + { + return recherche (p->frere, mot, i); + } + } +} + +/* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/ +NOEUD * +insere_fin (char *mot, int i) +{ + /* i est l'indice de la lettre courante dans le mot */ + printf ("insere_fin %c, %i\n", mot[i], i); + NOEUD *p = (NOEUD *) malloc (sizeof (NOEUD)); + if (p == NULL) + exit (-1); + p->lettre = mot[i]; + p->fils = NULL; + p->frere = NULL; + if (mot[i]) + p->fils = insere_fin (mot, i + 1); + return p; +} + +/* Insertion d'un mot dans l'arbre ******************************************/ +/* (on respecte l'ordre lexicographique des freres)**************************/ +NOEUD * +insere (NOEUD * p, char *mot, int i) +{ /* i est l'indice de la lettre courante dans le mot */ + /* TODO */ + if (p == NULL) + p = insere_fin (mot, i); + return p; +} + +/*****************************************************************************/ +/* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre */ +void +affiche (NOEUD * p, char *mot, int i) +{ /* i est l'indice de la lettre courante dans le mot */ + /* TODO */ +} + +/* Visualisation de l'arbre n-aire *******************************************/ +void +affiche_arbre (NOEUD * p, int prof) + /* prof est utilise pour decaller l'affichage avec des espaces (selon le niveau dans l'arbre) */ +{ + int i; + if (p) + { + affiche_arbre (p->frere, prof); + for (i = 0; i < prof; i++) + printf (" "); + printf ("%c\n", p->lettre); + affiche_arbre (p->fils, prof + 1); + } +} + +/* Suppression d'un mot de l'arbre ********************************************/ +/* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */ +NOEUD * +supprime (NOEUD * p, char *mot, int i) + /* i est l'indice de la lettre courante dans le mot */ +{ + /* TODO */ + return p; +} + +/* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/ +NOEUD * +charge_dico (char *nom_fichier, int *nb_mots) +{ + NOEUD *p; + FILE *fp; + char mot[N]; + int i; + p = NULL; + fp = fopen (nom_fichier, "rt"); + if (fp == NULL) + exit (-1); + fscanf (fp, "%d", nb_mots); /* sur la 1ere ligne du fichier, le nombre de mots */ + for (i = 0; i < *nb_mots; i++) + { + fscanf (fp, "%s", mot); + p = insere (p, mot, 0); /* TODO il faut finir "insere" pour que "charge_dico" fonctionne */ + } + fclose (fp); + return p; +} + +/* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/ +void +affiche_fich (FILE * fp, NOEUD * p, char *mot, int i) +{ + /* TODO */ + /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */ +} + +/* Sauvegarde des mots de l'arbre dans un fichier ****************************/ +void +sauve_dico (NOEUD * p, char *nom_fichier, int nb_mots) +{ + FILE *fp; + char mot[N]; + fp = fopen (nom_fichier, "wt"); + if (fp == NULL) + exit (-1); + fprintf (fp, "%d\n", nb_mots); + affiche_fich (fp, p, mot, 0); /* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */ + fclose (fp); +} + +/*****************************************************************************/ +int +main (int argc, char *argv[]) +{ + + char mot[N]; + NOEUD *arbre = NULL; + printf ("saisir un mot : "); + gets (mot); + printf ("\ninsertion de %s\n", mot); + arbre = insere (arbre, mot, 0); + printf ("\naffichage arbre :\n"); + affiche_arbre (arbre, 0); + /* TODO */ +} + +/* Exemple de trace d'execution ************************* + +saisir un mot : salut + +insertion de salut +insere_fin s, 0 +insere_fin a, 1 +insere_fin l, 2 +insere_fin u, 3 +insere_fin t, 4 +insere_fin , 5 + +affichage arbre : +s + a + l + u + t + +... TODO ... + +**********************************************************/ -- 2.34.1