From 249ff69760892dc8b5337bee9ad672c79325a42b Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Tue, 28 Mar 2017 21:55:43 +0200 Subject: [PATCH] Add latest implementation of tree algorithm in TP6 directory MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- TP6/arbres/AVL/AVL.c | 288 ++++++++++++++++++++++++ TP6/arbres/AVL/Makefile | 79 +++++++ TP6/arbres/arbreB/Makefile | 79 +++++++ TP6/arbres/arbreB/arbreB.c | 136 +++++++++++ TP6/hachage/chainage/Makefile | 79 +++++++ TP6/hachage/chainage/hachage_chainage.c | 88 ++++++++ TP6/hachage/lineaire/Makefile | 79 +++++++ TP6/hachage/lineaire/hachage_lineaire.c | 115 ++++++++++ TP6/tas/Makefile | 79 +++++++ TP6/tas/tas.c | 112 +++++++++ 10 files changed, 1134 insertions(+) create mode 100644 TP6/arbres/AVL/AVL.c create mode 100644 TP6/arbres/AVL/Makefile create mode 100644 TP6/arbres/arbreB/Makefile create mode 100644 TP6/arbres/arbreB/arbreB.c create mode 100644 TP6/hachage/chainage/Makefile create mode 100644 TP6/hachage/chainage/hachage_chainage.c create mode 100644 TP6/hachage/lineaire/Makefile create mode 100644 TP6/hachage/lineaire/hachage_lineaire.c create mode 100644 TP6/tas/Makefile create mode 100644 TP6/tas/tas.c diff --git a/TP6/arbres/AVL/AVL.c b/TP6/arbres/AVL/AVL.c new file mode 100644 index 0000000..d5f58b8 --- /dev/null +++ b/TP6/arbres/AVL/AVL.c @@ -0,0 +1,288 @@ +/*****************************************************************************/ +/* AVL */ +/*****************************************************************************/ + +#include +#include + +typedef int t_cle; + +typedef struct noeud { + t_cle cle; + int deseq; /* deseq = hauteur du ss-abre gauche + - hauteur du ss-arbre droit */ + struct noeud *gauche, *droit; + } N_AVL, *AVL; + + +/*****************************************************************************/ +AVL RG(AVL a) +{ + AVL b; + b = a->droit; + a->droit = b->gauche; + b->gauche = a; + return b; +} + + +/*****************************************************************************/ +AVL RD(AVL a) +{ + AVL b; + b = a->gauche; + a->gauche = b->droit; + b->droit = a; + return b; +} + + +/*****************************************************************************/ +AVL RGD(AVL a) +{ + a->gauche=RG(a->gauche); + return(RD(a)); +} + + +/*****************************************************************************/ +AVL RDG(AVL a) +{ + a->droit=RD(a->droit); + return(RG(a)); +} + + +/*****************************************************************************/ +AVL insere(AVL p,int x,int *verif) +{ + if (p == NULL) + {p = (N_AVL *)malloc(sizeof(N_AVL)); + if (p==NULL) exit(-1); + p->cle = x;p->gauche = NULL;p->droit = NULL; + p->deseq = 0; *verif = 1; + } + else if (x == p->cle) + printf("Insertion impossible ! %d est deja dans l'arbre\n",x); + + else if (x < p->cle) + {p->gauche = insere(p->gauche,x,verif); + if (*verif) {/* on a insere a gauche */ + switch (p->deseq) + {case -1 : p->deseq = 0; *verif = 0; break; + case 0 : p->deseq = 1; break; + case 1 : // reequilibrage + if (p->gauche->deseq==1) + {// rotation droite + printf("RD pour %6d\n",p->cle); + p=RD(p); + p->deseq = p->droit->deseq = 0; + *verif = 0; + } + else {/* rotation gauche droite */ + printf("RGD pour %6d\n",p->cle); + p=RGD(p); + switch (p->deseq) + {case -1 : p->droit->deseq=0; + p->gauche->deseq=1; + break; + case 0 : p->droit->deseq=0; + p->gauche->deseq=0; + break; + case 1 : p->droit->deseq=-1; + p->gauche->deseq=0; + } + p->deseq=0; *verif=0; + } + break; + } + + } + } + else + {p->droit = insere(p->droit,x,verif); + if (*verif) {/* on a insere a droite */ + switch (p->deseq) + {case 1 : p->deseq = 0; *verif = 0; break; + case 0 : p->deseq = -1; break; + case -1 : // reequilibrage + if (p->droit->deseq==-1) + {/* rotation gauche */ + printf("RG pour %6d\n",p->cle); + p=RG(p); + p->deseq = p->gauche->deseq = 0; + *verif = 0; + } + else {/* rotation droite gauche */ + printf("RDG pour %6d\n",p->cle); + p=RDG(p); + switch (p->deseq) + {case 1 : p->droit->deseq=-1; + p->gauche->deseq=0; + break; + case 0 : p->droit->deseq=0; + p->gauche->deseq=0; + break; + case -1 : p->droit->deseq=0; + p->gauche->deseq=1; + } + p->deseq=0; *verif=0; + } + break; + } + } + } + return(p); +} + + +/*****************************************************************************/ +AVL equigauche(AVL p,int *verif) +/* quand on entre dans la fonction, *verif = 1 */ +{ + switch (p->deseq) + {case 1 : p->deseq = 0; break; + case 0 : p->deseq = -1; *verif = 0; break; + case -1 : /* reequilibrage */ + if (p->droit->deseq <= 0) + {/* rotation gauche */ + printf("RG pour %6d\n",p->cle); + p = RG(p); + if (p->deseq == 0) {p->gauche->deseq = -1; p->deseq = 1; + *verif=0;} + else {//forcement p->deseq = -1 + p->deseq = p->gauche->deseq = 0; } + } + else + {/* rotation droite gauche */ + printf("RDG pour %6d\n",p->cle); + p = RDG(p); + switch (p->deseq) + {case 0 : p->droit->deseq = p->gauche->deseq =0; break; + case 1 : p->droit->deseq = -1; p->gauche->deseq = 0; + break; + case -1 : p->droit->deseq = 0; p->gauche->deseq = 1; + } + p->deseq = 0; + } + } +return p; +} + + +/*****************************************************************************/ +AVL equidroit(AVL p,int *verif) // quand on entre dans la fonction, verif = 1 +{ + switch (p->deseq) + {case -1 : p->deseq = 0; break; + case 0 : p->deseq = 1; *verif = 0; break; + case 1 : /* reequilibrage */ + if (p->gauche->deseq >= 0) + {/* rotation droite */ + printf("RD pour %6d\n",p->cle); + p = RD(p); + if (p->deseq == 0) {p->droit->deseq = 1; p->deseq = -1; + *verif=0; } + else {/* forcement p->deseq = 1 */ + p->deseq = p->droit->deseq = 0; } + } + else + {/* rotation gauche droite */ + printf("RGD pour %6d\n",p->cle); + p = RGD(p); + switch (p->deseq) + {case 0 : p->gauche->deseq = p->droit->deseq =0; break; + case 1 : p->gauche->deseq = 0; p->droit->deseq = -1; + break; + case -1 : p->gauche->deseq = 1; p->droit->deseq = 0; + } + p->deseq = 0; + } + } +return p; +} + + +/*****************************************************************************/ +AVL supmax(AVL p,AVL r,int *verif) +{ + AVL q; + if (r->droit == NULL) {p->cle = r->cle; + q = r; /* q : l'element a supprimer par free */ + r = r->gauche; + free(q); + *verif = 1; + } + else {r->droit = supmax(p,r->droit,verif); + if (*verif) r = equidroit(r,verif); + } + return r; +} + + +/*****************************************************************************/ +AVL supprime(AVL p,int x,int *verif) +{ + AVL q; + + if (p == NULL) + printf( "Suppression impossible ! %d n'est pas dans l'arbre\n",x); + else if (x == p->cle) { /* Suppression de p */ + if (p->droit == NULL) {q = p; p = p->gauche; + free(q); *verif = 1; } + else if (p->gauche == NULL) {q = p; p = p->droit; + free(q); *verif = 1; } + else {p-> gauche = supmax(p,p->gauche,verif); + if (*verif) p = equigauche(p,verif); + } + } + else if (x < p->cle) + {p->gauche = supprime(p->gauche,x,verif); + if (*verif) p = equigauche(p,verif); + } + else {p->droit = supprime(p->droit,x,verif); + if (*verif) p = equidroit(p,verif); + } + return p; +} + + +/*****************************************************************************/ +void affiche_arbre(AVL p, int col) +{ + int i; char esp=' '; + if (p) + {affiche_arbre(p->droit,col+6); + for (i=0;icle,p->deseq); + affiche_arbre(p->gauche,col+6); + }; + } + + + +/*****************************************************************************/ +main() + {AVL rac=NULL; + int x; + int verif; + do {printf("Entrez une cle: ");scanf("%d",&x); + if (x) {printf("Insertion de la cle %6d\n",x); + verif = 0; + rac = insere(rac,x,&verif); + affiche_arbre(rac,0); + } + } + while (x); + + do {printf("Entrez une cle: ");scanf("%d",&x); + if (x) {printf("Suppression de la cle %6d\n",x); + verif = 0; + rac = supprime(rac,x,&verif); + affiche_arbre(rac,0); + } + } + while (x); + } +/*****************************************************************************/ + diff --git a/TP6/arbres/AVL/Makefile b/TP6/arbres/AVL/Makefile new file mode 100644 index 0000000..61c2538 --- /dev/null +++ b/TP6/arbres/AVL/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=AVL +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/arbreB/Makefile b/TP6/arbres/arbreB/Makefile new file mode 100644 index 0000000..028f711 --- /dev/null +++ b/TP6/arbres/arbreB/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=arbreB +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/arbreB/arbreB.c b/TP6/arbres/arbreB/arbreB.c new file mode 100644 index 0000000..291e949 --- /dev/null +++ b/TP6/arbres/arbreB/arbreB.c @@ -0,0 +1,136 @@ +/*****************************************************************************/ +/* arbre B */ +/* Insertion dans un B-arbre d'ordre 2 */ +/*****************************************************************************/ +#include +#include + +/* declarations des types C pour definir les B-arbres d'ordre 2 */ + +#define ORDRE 2 +/* ordre du B-arbre */ + +typedef int t_cle; +/* les cles sont des entiers */ + +typedef struct page { + t_cle cle[2*ORDRE+1]; + struct page *fils[2*ORDRE+1]; + } PAGE; + +/* une page contient au maximum 2*ORDRE cles et a 2*ORDRE+1 fils. + cle[0] contient le nombre de cles contenues dans la page. + ces cles sont rangees dans le tableau cle[1..2*ORDRE] */ + + +/*****************************************************************************/ +/* affichage d'un B-arbre */ +void affiche_B_arbre(PAGE *p, int l) +{ + int i; char esp=' '; + if (p) {for (i=1;i<=l;i++) printf("%c",esp); + for (i=1;i<=p->cle[0];i++) printf("%6d",p->cle[i]); + printf("\n"); + for (i=0;i<=p->cle[0];i++) affiche_B_arbre(p->fils[i],l+4); + } +} + + +/*****************************************************************************/ +/* insertion de la cle x dans le B-arbre de racine a - v et pv designent + l'element (cle+pointeur) qui remonte au niveau superieur */ +int insertion(t_cle x, PAGE *a, t_cle *v, PAGE **pv) +{ + int h=0, gauche, droit, milieu, i, m; + t_cle u; + PAGE *pu, *b; + +if (a==NULL) {*v=x;*pv=NULL;h=1;} +else {/*recherche dichotomique */ + gauche=1; droit=a->cle[0]; + do {milieu = (gauche+droit)/2; + if (x<=a->cle[milieu]) droit=milieu-1; + if (x>=a->cle[milieu]) gauche=milieu+1; + } while(gauche<=droit); + if (gauche-droit==2) /* on a trouve x - on ne fait rien */ h=0; + else {/* x n'est pas sur cette page */ + h=insertion(x,a->fils[droit],&u,&pu); + if (h) {/* insertion de u en position droit+1 */ + m = a->cle[0]; + if (m<2*ORDRE) {m++;h=0; + for (i=m;i>=droit+2;i--) /*decalage */ + {a->cle[i]=a->cle[i-1]; + a->fils[i]=a->fils[i-1]; + } + a->cle[droit+1]=u; /* insertion */ + a->fils[droit+1]=pu; + a->cle[0]=m; + } + else {/* la page est pleine - on la coupe en deux */ + b=(PAGE *) malloc(sizeof(PAGE)); + if (b==NULL) {printf("Erreur allocation!\n");exit(-1); + } + if (droit<=ORDRE) + {/* insertion de u dans la page de gauche ie dans a */ + if (droit==ORDRE) {*v=u;*pv=pu;} + else {*v=a->cle[ORDRE];*pv=a->fils[ORDRE]; + for (i=ORDRE;i>=droit+2;i--) /*decalage */ + {a->cle[i]=a->cle[i-1]; + a->fils[i]=a->fils[i-1]; + } + a->cle[droit+1]=u; /* insertion du u dans a */ + a->fils[droit+1]=pu; + } + for (i=1;i<=ORDRE;i++) + {b->cle[i]=a->cle[i+ORDRE]; + b->fils[i]=a->fils[i+ORDRE]; + } + } + else {/* insertion dans la page droite */ + droit=droit-ORDRE; + *v=a->cle[ORDRE+1];*pv=a->fils[ORDRE+1]; + for (i=1;i<=droit-1;i++) + {b->cle[i]=a->cle[i+ORDRE+1]; + b->fils[i]=a->fils[i+ORDRE+1]; + } + b->cle[droit]=u; /* insertion de u dans b */ + b->fils[droit]=pu; + for (i=droit+1;i<=ORDRE;i++) + {b->cle[i]=a->cle[i+ORDRE]; + b->fils[i]=a->fils[i+ORDRE]; + } + } + a->cle[0]=b->cle[0]=ORDRE; + b->fils[0]=*pv; + *pv=b; + } + } + } +} +return h; +} + + +/*****************************************************************************/ +int main() +{ + PAGE *rac=NULL, *pu, *q; + t_cle x,u; + int h; + do {printf("Entrez une cle: ");scanf("%d",&x); + if (x) {printf("Insertion de la cle %6d\n",x); + h = insertion(x,rac,&u,&pu); + if (h) {q=rac; + rac=(PAGE *) malloc(sizeof(PAGE)); + if (rac==NULL) {printf("Erreur allocation!\n");exit(-1); + } + rac->cle[0]=1;rac->fils[0]=q; + rac->cle[1]=u;rac->fils[1]=pu; + } + affiche_B_arbre(rac,1); + } + } + while (x); +} +/*****************************************************************************/ + diff --git a/TP6/hachage/chainage/Makefile b/TP6/hachage/chainage/Makefile new file mode 100644 index 0000000..e5826a5 --- /dev/null +++ b/TP6/hachage/chainage/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=hachage_chainage +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/hachage/chainage/hachage_chainage.c b/TP6/hachage/chainage/hachage_chainage.c new file mode 100644 index 0000000..b971067 --- /dev/null +++ b/TP6/hachage/chainage/hachage_chainage.c @@ -0,0 +1,88 @@ +/******************************************************************************/ +/* Hachage par chainage */ +/******************************************************************************/ +#include +#include + +#define M 5 +/* on choisit M tres petit pour tester le programme, mais en realite, + M est tres grand */ + +typedef int element; + +typedef struct cellule {element valeur; + struct cellule *suivant; } Cellule, *Liste; + +typedef struct {Liste T[M]; } t_table; + +int h(element x) {return x%M; } +/* "mauvaise" fonction de hachage - juste pour tester le programme */ + +t_table init_table() + {t_table t; + int i; + for (i=0; ivaleur) return 1; + else p=p->suivant; + return 0; + } + +int inserer(element x, t_table *t) +/* retourne 0 si x est deja dans la table */ + {int i=h(x); + Cellule *p=t->T[i], *preced=NULL; + while (p) if (x==p->valeur) return 0; + else {preced = p; p=p->suivant; } + if (preced==NULL) {t->T[i]=(Cellule *)malloc(sizeof(Cellule)); + t->T[i]->valeur=x; + t->T[i]->suivant=NULL; + } + else {preced->suivant=(Cellule *)malloc(sizeof(Cellule)); + preced->suivant->valeur=x; + preced->suivant->suivant=NULL; + } + return 1; + } + +void visu(Liste L) + {if (L){printf("%d\t",L->valeur); + visu(L->suivant); + } + } + +void afficher(t_table t) + {Cellule *p; + int i; + for (i=0; i +#include + +#define VIDE 0 +#define OCCUPE 1 +#define LIBERE -1 +#define M 10 + +typedef struct {int cle; + int etat; + } t_elem; + +void affiche_tab(t_elem *tab) +{int i; + for (i = 0 ; i ",tab[i].cle,tab[i].etat); + printf("\n"); +} + +int h(int x) /* mauvaise fonction de hachage - juste pour tester */ +{return x%M;} + +int rechercher(int x,t_elem *tab) +/* retourne l'indice de x dans la table si x est present, -1 sinon */ +{int i=0,v=h(x); + while (i=M) v=0; + }; + +if ((tab[v].etat==OCCUPE) && (tab[v].cle==x)) /* x présent */ return v; + else /* x absent */ return -1; +} + +int supprimer(int x,t_elem *tab) +/* supprime x de la table, s'il est présent (et alors retourne son indice), + et ne fait rien si x est absent (et alors retourne -1) +*/ +{int v = rechercher(x,tab); + if (v!=-1) /*x present */ {tab[v].etat=LIBERE; return v; + } + else /* x absent */ return -1; +} + +int inserer(int x,t_elem *tab) +/* si x n'est pas dans la table, on l'insère a la première place vide ou liberee + rencontrée au cours des essais successifs (et on retourne son indice); + si x est déjà dans la table, on ne fait rien (et on retourne son indice); + si le tableau est plein, c'est que x n'a pu être insèré et on retourne -1 */ +{int i=0,lib=-1,v=h(x); + while (i=M) v=0; + /* on continue tant qu'on ne trouve pas x ou une place vide */ + } + + if (tab[v].etat==VIDE) + if (lib==-1) {tab[v].cle=x;tab[v].etat=OCCUPE;return v;} + else {tab[lib].cle=x;tab[lib].etat=OCCUPE;return lib;} + else return -1; +} + +int main () +{int i; + t_elem *tab; + +tab = (t_elem *)calloc((M),sizeof(t_elem)); +if (tab == NULL) {printf("memoire insuffisante\n"); exit(-1); } + +for (i=0;i <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> + 3 + <0,0> <0,0> <0,0> <3,1> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> + 5 + <0,0> <0,0> <0,0> <3,1> <0,0> <5,1> <0,0> <0,0> <0,0> <0,0> + 4 + <0,0> <0,0> <0,0> <3,1> <13,1> <5,1> <0,0> <0,0> <0,0> <0,0> + 9 + <0,0> <0,0> <0,0> <3,1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1> + 0 + <19,1> <0,0> <0,0> <3,1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1> + 3 + <19,1> <0,0> <0,0> <3,-1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1> +-1 + <19,1> <0,0> <0,0> <3,-1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1> + 3 + <19,1> <0,0> <0,0> <23,1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1> + 6 + <19,1> <0,0> <0,0> <23,1> <13,1> <5,1> <3,1> <0,0> <0,0> <9,1> + +*****************************************************************************/ + diff --git a/TP6/tas/Makefile b/TP6/tas/Makefile new file mode 100644 index 0000000..82685d0 --- /dev/null +++ b/TP6/tas/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=tas +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/tas/tas.c b/TP6/tas/tas.c new file mode 100644 index 0000000..c3edbd3 --- /dev/null +++ b/TP6/tas/tas.c @@ -0,0 +1,112 @@ +/******************************************************************************/ +/* tas */ +/******************************************************************************/ + +#include +#include + +#define MAX 11 + +typedef int TAS[MAX]; /* la case d'indice 0 n'est pas utilisee */ + + +/* affichage du tas */ +void affiche_tas(TAS t, int n, char *message) +{ + int i; + printf("%s \n",message); + for (i=1;i<=n;i++) printf("%5d ",t[i]); + printf("\n"); +} + + +/* initialisation du tas la valeur val */ +void init_tas(TAS t, int n, int val) +{ + int i; + for (i=0;i<=n;i++) t[i] = val; +} + + +/* descente de l'element se trouvant au sommet du tas, a l'indice 1 et pas 0 */ +void descente(TAS t, int g, int d) +{ + int i, j, x; /* i indice du pere - j indice du fils */ + x = t[g]; i =g ; j = 2*i; + while (j<= d) + { + if (j < d) if (t[j] < t[j+1]) j++; /* j indice du fils choisi */ + + if (x < t[j]) {t[i] = t[j]; i = j; j*=2;} + else break; + } + t[i] = x; +} + + +/* montee de l'element d'indice m */ +void montee(TAS t,int m, int n) +{ + int i, j, x; /* i indice du pere - j indice du fils */ + x = t[m]; j = m; i = j/2; + while (i>= 1) + { + if (x > t[i]) {t[j] = t[i]; j = i; i = j/2;} + else break; + } + t[j] = x; +} + + +/* remplacement de l'element d'indice m par nouv_val et mise a jour du tas */ +void change(TAS t, int nouv_val, int m, int n) +{ + if (nouv_val < t[m]) {t[m] = nouv_val; descente(t,m,n); } + else {t[m] = nouv_val; montee(t,m,n);} +} + + +/****************************************************************************/ +main() +{int n = MAX-1; + int i, g, d, x; + TAS t; + + srand(time(NULL)); + for (i=1;i<=n;i++) t[i] = rand()%MAX; + affiche_tas(t,n,"Le tableau initial"); + + g = (n / 2) + 1; d = n; + while (g > 1) descente(t,--g,d); + + affiche_tas(t,n,"Apres contruction du tas"); + change(t, 45, 7, 10); + affiche_tas(t,n,"Le tas apres change(t,45,7,10)"); + change(t, -5, 3, 10); + affiche_tas(t,n,"Le tas apres change(t,-5,3,10)"); + + while (d > 1) { + x=t[1]; /* le max */ + t[1]=t[d]; /* le dernier devient le premier du tableau */ + t[d]=x; /* le max est place a la fin du tableau */ + descente(t,g,--d); /* on fait descendre le nouveau premier elt a sa bonne place */ + } + affiche_tas(t,n,"Le tas apres le tri"); + + for (i=1;it[i+1]) {printf("Erreur tri\n");break;} +} + + +/*************************************************************************** +Le tableau initial + 10 7 1 9 4 7 3 2 4 10 +Apres contruction du tas + 10 10 7 9 7 1 3 2 4 4 +Le tas apres change(t,45,7,10) + 45 10 10 9 7 1 7 2 4 4 +Le tas apres change(t,-5,3,10) + 45 10 7 9 7 1 -5 2 4 4 +Le tas apres le tri + -5 1 2 4 4 7 7 9 10 45 +***************************************************************************/ + -- 2.34.1