From 5f72f302ec8c14ce895f993e2d2ca33df95c94ee Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Wed, 29 Mar 2017 13:30:15 +0200 Subject: [PATCH] TP6: Add ABR and tree n MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- TP6/arbres/ABR/ABR.c | 317 ++++++++++++++++++ TP6/arbres/ABR/Makefile | 79 +++++ TP6/arbres/arbre-n-aire/Makefile | 79 +++++ .../arbre-n-aire/arbre_n_aire_a_completer.c | 178 ++++++++++ 4 files changed, 653 insertions(+) create mode 100644 TP6/arbres/ABR/ABR.c create mode 100644 TP6/arbres/ABR/Makefile create mode 100644 TP6/arbres/arbre-n-aire/Makefile create mode 100644 TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c diff --git a/TP6/arbres/ABR/ABR.c b/TP6/arbres/ABR/ABR.c new file mode 100644 index 0000000..6064c00 --- /dev/null +++ b/TP6/arbres/ABR/ABR.c @@ -0,0 +1,317 @@ +/*****************************************************************************/ +/* ABR : arbres binaires de recherche */ +/*****************************************************************************/ + +#include +#include + +typedef int element; + +typedef struct noeud { + element valeur; + struct noeud *gauche; + struct noeud *droit; +} NOEUD, *ABR; + + +/* Creation d'un ABR vide */ +NOEUD *arbre_vide() +{ + return NULL; +} + + +/* Insertion/Ajout d'un nouvel element dans l'ABR */ +NOEUD *insere(NOEUD *p, element x) +{ + if(p == NULL) + { + p = (NOEUD *)malloc(sizeof(NOEUD)); + p->valeur = x; + p->gauche = NULL; + p->droit = NULL; + } + else if (x == p->valeur) printf("%d est deja dans l'arbre\n",x); + else if (x < p->valeur) p->gauche = insere(p->gauche,x); + else p->droit = insere(p->droit,x); + return p; +} + + +/* Recherche d'un element dans l'ABR */ +int recherche(NOEUD *p, element x) +{ + if(p == NULL) return 0; + if(x == p->valeur) return 1; + if(x < p->valeur) return recherche(p->gauche,x); + else return recherche(p->droit,x); +} + + +/* Affichage du contenu de l'ABR en ordre croissant (par parcours profondeur infixe) */ +void affiche(NOEUD *p) +{ + if(p) + { + affiche(p->gauche); + printf("%d ",p->valeur); + affiche(p->droit); + } +} + + +/* Affichage de l'arbre (sous forme arborescente) */ +void affiche_arbre(NOEUD *p, int col) +{ + int i; + if(p) + { + affiche_arbre(p->droit,col+1); + for (i=0;ivaleur); + affiche_arbre(p->gauche,col+1); + } +} + + +/* Copie d'arbre (on cree physiquement le double de l'arbre de racine p) */ +NOEUD *copie_arbre(NOEUD *p) +{ + NOEUD *q; + if(p == NULL) return NULL; + else + { + q = (NOEUD *)malloc(sizeof(NOEUD)); + q->valeur = p->valeur; + q->gauche = copie_arbre(p->gauche); + q->droit = copie_arbre(p->droit); + return q; + } +} + + +/* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds */ +NOEUD *detruis_arbre(NOEUD *p) +{ + if(p == NULL) return p; + else + { + p->gauche = detruis_arbre(p->gauche); + p->droit = detruis_arbre(p->droit); + free(p); + p = NULL; + return p; + } +} + + +/* Maximum d'un sous-arbre de racine p (i.e., le noeud le plus a droite) */ +NOEUD *max(NOEUD *p, NOEUD *r) +{ + NOEUD *q; + if (r->droit == NULL) + { + p->valeur = r->valeur; + q = r; /* q : l'element a supprimer par free */ + r = r->gauche; + free(q); + } + else r->droit = max(p,r->droit); + return r; +} + + +/* Suppression du noeud de valeur x dans l'arbre de racine p. + Suppression d'un noeud interne : la valeur du noeud a supprimer est + remplacee par celle du noeud le plus a droite de son sous-arbre gauche */ +NOEUD *supprime(NOEUD *p, element x) +{ + NOEUD *q; + if(p == NULL) printf("%d n'est pas dans l'arbre\n",x); + else + if(x == p->valeur) + { /* suppression de p */ + if (p->droit == NULL) {q = p ; p = p->gauche; free(q); } + else if (p->gauche == NULL) {q = p ; p = p->droit; free (q); } + else p-> gauche = max(p,p->gauche); + } + else if (x < p->valeur) p->gauche = supprime(p->gauche,x); + else p->droit = supprime(p->droit,x); + return p; +} + + +/* Chargement d'un arbre depuis un fichier */ +NOEUD *charge(NOEUD *p, FILE *fich) +{ + if (p) {p = (NOEUD *)malloc(sizeof(NOEUD)); + fread(p,sizeof(NOEUD),1,fich); + p->gauche = charge(p->gauche,fich); + p->droit = charge(p->droit,fich); + } + return p; +} + + +/* Sauvegarde d'un arbre dans un fichier */ +NOEUD *sauve(NOEUD *p, FILE *fich) +{ + if (p) {fwrite(p,sizeof(NOEUD),1,fich); + p->gauche = sauve(p->gauche,fich); + p->droit = sauve(p->droit,fich); + } + return p; +} + + + + +/*****************************************************************************/ +main() +{ + NOEUD *abr; /* on peut travailler sur 3 arbres */ + NOEUD *abr2 = NULL; + char c; + int i, j; + element x; + char nom_fich[20]; + FILE *fich; + +printf("Commandes (une lettre) possibles : v arbre_vide ; r rechercher ; i inserer ; c copier ; d detruire ; a afficher contenu ; A affiche arborescence ; s supprimer ; C charger ; S sauvegarder)\n"); + + do { + printf("Commande ? "); + c = getchar(); + switch(c) + { + case 'v' : abr = arbre_vide(); break; + + case 'r' : printf("indiquer l'element a rechercher : "); + scanf("%d",&x); + if (recherche(abr,x) == 0) printf("pas trouve\n"); + else printf("trouve\n"); + break; + + case 'i' : printf("indiquer l'element a inserer : "); + scanf("%d",&x); + abr = insere(abr,x); + break; + + case 'c' : abr2 = copie_arbre(abr); + break; + + case 'd' : abr = detruis_arbre(abr); + if(abr2) abr2 = detruis_arbre(abr2); + break; + + case 'a' : affiche(abr); + if(abr2) {printf("\nLa copie : \n"); + affiche(abr2);}; + break; + + case 'A' : affiche_arbre(abr,1); + if(abr2) {printf("\nLa copie : \n"); + affiche_arbre(abr2,1);}; + break; + + case 's' : printf("indiquer l'element a supprimer : "); + scanf("%d",&x); + abr = supprime(abr,x); + break; + + case 'C' : printf("indiquer le nom de fichier pour le chargement : "); + scanf("%s",nom_fich); + if ((fich = fopen(nom_fich,"rb")) != NULL) + {abr = (NOEUD *)malloc(sizeof(NOEUD)); + abr = charge(abr,fich); + fclose(fich); + }; + break; + + case 'S' : printf("indiquer le nom de fichier pour la sauvegarde : "); + scanf("%s",nom_fich); + if ((fich = fopen(nom_fich,"wb")) != NULL) + {abr = sauve(abr,fich); + abr = NULL; + fclose(fich); + }; + break; + + case 'q' : exit(0); + } + printf("\n"); c = getchar(); + } + while (1); +} + + +/* Trace d'execution ************************************** +Commandes (une lettre) possibles : v arbre_vide ; r rechercher ; i inserer ; c copier ; d detruire ; a afficher contenu ; A affiche arborescence ; s supprimer ; C charger ; S sauvegarder) +Commande ? v + +Commande ? i +indiquer l'element a inserer : 2 + +Commande ? i +indiquer l'element a inserer : 6 + +Commande ? i +indiquer l'element a inserer : 4 + +Commande ? i +indiquer l'element a inserer : 5 + +Commande ? i +indiquer l'element a inserer : 1 + +Commande ? i +indiquer l'element a inserer : 0 + +Commande ? a +0 1 2 4 5 6 +Commande ? A + 6 + 5 + 4 + 2 + 1 + 0 + +Commande ? r +indiquer l'element a rechercher : 4 +trouve + +Commande ? r +indiquer l'element a rechercher : 3 +pas trouve + +Commande ? s +indiquer l'element a supprimer : 4 + +Commande ? a +0 1 2 5 6 +Commande ? A + 6 + 5 + 2 + 1 + 0 + +Commande ? S +indiquer le nom de fichier pour la sauvegarde : sauv.txt + +Commande ? C +indiquer le nom de fichier pour le chargement : sauv.txt + +Commande ? a +0 1 2 5 6 +Commande ? A + 6 + 5 + 2 + 1 + 0 + +Commande ? q + +******************************************************************************/ diff --git a/TP6/arbres/ABR/Makefile b/TP6/arbres/ABR/Makefile new file mode 100644 index 0000000..2a8b729 --- /dev/null +++ b/TP6/arbres/ABR/Makefile @@ -0,0 +1,79 @@ +# Sample Makefile to build simple project. +# +# This Makefile expect all source files (.c) to be at the same level, in the +# current working directory. +# +# It will automatically generate dependencies, compile all files, and produce a +# binary using the provided name. +# +# Set BINARY_NAME to the name of the binary file to build. +# Set BUILD_TYPE to either debug or release +# +# Automatic dependencies code from: +# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr +BINARY_NAME=ABR +BUILD_TYPE=debug + +# ==================================== +# DO NOT CHANGE STUFF BEYOND THIS LINE +# ==================================== + +all: $(BINARY_NAME) + +CC=gcc +LD=gcc + +WARN_FLAGS = -Wall -Wextra +STD_FLAG = -std=c11 + +ifeq ($(BUILD_TYPE),debug) +BUILDDIR := .build/debug +DEBUG_FLAG = -g +STRIP_FLAG = +OPTI_FLAG = -O0 +else +BUILDDIR := .build/release +DEBUG_FLAG = +STRIP_FLAG = -s +OPTI_FLAG = -O3 +endif + +CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG) +LDFLAGS := $(LDFLAGS) $(STRIP_FLAG) + +OBJDIR := $(BUILDDIR)/objs +$(shell mkdir -p $(OBJDIR)) + +SRCS=$(wildcard *.c) +OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS)) + +DEPDIR := $(BUILDDIR)/deps +$(shell mkdir -p $(DEPDIR)) +DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td +POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d + +$(BINARY_NAME): $(OBJS) + @echo "[LD ] $@" + @$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@ + +$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d + @echo "[C ] $*" + @$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@ + @$(POSTCOMPILE) + +$(DEPDIR)/%.d: ; + +.PRECIOUS: $(DEPDIR)/%.d + +include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS)))) + +clean: + @echo "[CLN]" + -@rm -r $(BUILDDIR) + -@rm $(BINARY_NAME) + +disassemble: $(BINARY_NAME) + objdump -d $< | less + +symbols: $(BINARY_NAME) + objdump -t $< | sort | less diff --git a/TP6/arbres/arbre-n-aire/Makefile b/TP6/arbres/arbre-n-aire/Makefile new file mode 100644 index 0000000..6b0ec52 --- /dev/null +++ b/TP6/arbres/arbre-n-aire/Makefile @@ -0,0 +1,79 @@ +# Sample Makefile to build simple project. +# +# This Makefile expect all source files (.c) to be at the same level, in the +# current working directory. +# +# It will automatically generate dependencies, compile all files, and produce a +# binary using the provided name. +# +# Set BINARY_NAME to the name of the binary file to build. +# Set BUILD_TYPE to either debug or release +# +# Automatic dependencies code from: +# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr +BINARY_NAME=arbre_n_aire +BUILD_TYPE=debug + +# ==================================== +# DO NOT CHANGE STUFF BEYOND THIS LINE +# ==================================== + +all: $(BINARY_NAME) + +CC=gcc +LD=gcc + +WARN_FLAGS = -Wall -Wextra +STD_FLAG = -std=c11 + +ifeq ($(BUILD_TYPE),debug) +BUILDDIR := .build/debug +DEBUG_FLAG = -g +STRIP_FLAG = +OPTI_FLAG = -O0 +else +BUILDDIR := .build/release +DEBUG_FLAG = +STRIP_FLAG = -s +OPTI_FLAG = -O3 +endif + +CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG) +LDFLAGS := $(LDFLAGS) $(STRIP_FLAG) + +OBJDIR := $(BUILDDIR)/objs +$(shell mkdir -p $(OBJDIR)) + +SRCS=$(wildcard *.c) +OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS)) + +DEPDIR := $(BUILDDIR)/deps +$(shell mkdir -p $(DEPDIR)) +DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td +POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d + +$(BINARY_NAME): $(OBJS) + @echo "[LD ] $@" + @$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@ + +$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d + @echo "[C ] $*" + @$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@ + @$(POSTCOMPILE) + +$(DEPDIR)/%.d: ; + +.PRECIOUS: $(DEPDIR)/%.d + +include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS)))) + +clean: + @echo "[CLN]" + -@rm -r $(BUILDDIR) + -@rm $(BINARY_NAME) + +disassemble: $(BINARY_NAME) + objdump -d $< | less + +symbols: $(BINARY_NAME) + objdump -t $< | sort | less 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 new file mode 100644 index 0000000..4d4b97f --- /dev/null +++ b/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c @@ -0,0 +1,178 @@ +/*****************************************************************************/ +/* 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 ... + +**********************************************************/ + -- 2.34.1