X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=TP6%2Farbres%2FarbreB%2FarbreB.c;h=156771838b435b26afe014e7dc300ac6242d047d;hb=760a83108ff8caa7036c81d21d4dc4581de98860;hp=291e9495a8138b98fea86795c722c3c21d6ffea8;hpb=e06ddf2d662693efef1a0060797f169947ff3d9d;p=Algorithmic_C.git 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); } -/*****************************************************************************/ +/*****************************************************************************/