From 760a83108ff8caa7036c81d21d4dc4581de98860 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 30 Mar 2017 22:10:00 +0200 Subject: [PATCH] TP6: Use K&R coding style MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Also add n-ary tree insertion recursive function Signed-off-by: Jérôme Benoit --- TP6/arbres/ABR/ABR.c | 376 ++++++++++++++----------- TP6/arbres/arbre-n-aire/arbre_n_aire.c | 17 +- TP6/arbres/arbre-n-aire/dictionnaire | 5 + TP6/arbres/arbreB/arbreB.c | 219 +++++++------- 4 files changed, 345 insertions(+), 272 deletions(-) create mode 100644 TP6/arbres/arbre-n-aire/dictionnaire diff --git a/TP6/arbres/ABR/ABR.c b/TP6/arbres/ABR/ABR.c index 6064c00..b5d3956 100644 --- a/TP6/arbres/ABR/ABR.c +++ b/TP6/arbres/ABR/ABR.c @@ -8,159 +8,175 @@ typedef int element; typedef struct noeud { - element valeur; - struct noeud *gauche; - struct noeud *droit; + element valeur; + struct noeud *gauche; + struct noeud *droit; } NOEUD, *ABR; /* Creation d'un ABR vide */ -NOEUD *arbre_vide() +NOEUD *arbre_vide() { - return NULL; + return NULL; } /* Insertion/Ajout d'un nouvel element dans l'ABR */ -NOEUD *insere(NOEUD *p, element x) +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; + 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) +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); + 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) +void affiche(NOEUD * p) { - if(p) - { - affiche(p->gauche); - printf("%d ",p->valeur); - affiche(p->droit); - } + 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) +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); - } + int i; + + if (p) { + affiche_arbre(p->droit, col + 1); + for (i = 0; i < col; i++) + printf(" "); + printf("%d\n", p->valeur); + 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 *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; - } -} + 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) +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; - } + 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 *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; + 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 *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; + 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) +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; + 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) +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; + if (p) { + fwrite(p, sizeof(NOEUD), 1, fich); + p->gauche = sauve(p->gauche, fich); + p->droit = sauve(p->droit, fich); + } + return p; } @@ -169,79 +185,99 @@ NOEUD *sauve(NOEUD *p, FILE *fich) /*****************************************************************************/ 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); + 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); } diff --git a/TP6/arbres/arbre-n-aire/arbre_n_aire.c b/TP6/arbres/arbre-n-aire/arbre_n_aire.c index 16fd096..fecc499 100644 --- a/TP6/arbres/arbre-n-aire/arbre_n_aire.c +++ b/TP6/arbres/arbre-n-aire/arbre_n_aire.c @@ -59,15 +59,15 @@ NOEUD *insere_fin(char *mot, int i) NOEUD *insere(NOEUD * p, char *mot, int i) { /* i est l'indice de la lettre courante dans le mot */ - if (p == NULL) - return p = insere_fin(mot, i); - if (mot[i] == p->lettre) { - - return insere(p->fils, mot, i + 1); + if (p == NULL) { + return insere_fin(mot, i); } - //return insere (p->frere, mot, i); if (mot[i] > p->lettre) { return insere(p->frere, mot, i); + } else if (mot[i] == p->lettre) { + return insere(p->fils, mot, i + 1); + } else { + return insere_fin(mot, i); } } @@ -91,6 +91,7 @@ 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++) @@ -117,6 +118,7 @@ NOEUD *charge_dico(char *nom_fichier, int *nb_mots) char mot[N]; int i; p = NULL; + fp = fopen(nom_fichier, "rt"); if (fp == NULL) exit(-1); @@ -141,6 +143,7 @@ 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); @@ -155,6 +158,7 @@ int main(int argc, char *argv[]) char mot[N]; int nb_mots = 0; NOEUD *arbre = NULL; + //printf ("saisir un mot : "); //gets (mot); //printf ("\ninsertion de %s\n", mot); @@ -166,6 +170,7 @@ int main(int argc, char *argv[]) affiche_arbre(arbre, 0); if (recherche(arbre, "salut", 0)) printf("mot \"salut\" present\n"); + free(arbre); /* TODO */ } diff --git a/TP6/arbres/arbre-n-aire/dictionnaire b/TP6/arbres/arbre-n-aire/dictionnaire new file mode 100644 index 0000000..c87770f --- /dev/null +++ b/TP6/arbres/arbre-n-aire/dictionnaire @@ -0,0 +1,5 @@ +4 +salut +salutations +cela +ceci diff --git a/TP6/arbres/arbreB/arbreB.c b/TP6/arbres/arbreB/arbreB.c index 291e949..1567718 100644 --- a/TP6/arbres/arbreB/arbreB.c +++ b/TP6/arbres/arbreB/arbreB.c @@ -13,10 +13,10 @@ 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; +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. @@ -25,112 +25,139 @@ typedef struct page { /*****************************************************************************/ /* affichage d'un B-arbre */ -void affiche_B_arbre(PAGE *p, int l) +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); - } + 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 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 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); - } + 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); + while (x); } -/*****************************************************************************/ +/*****************************************************************************/ -- 2.34.1