TP6: Use K&R coding style
[Algorithmic_C.git] / TP6 / arbres / arbreB / arbreB.c
CommitLineData
249ff697
JB
1/*****************************************************************************/
2/* arbre B */
3/* Insertion dans un B-arbre d'ordre 2 */
4/*****************************************************************************/
5#include <stdio.h>
6#include <stdlib.h>
7
8/* declarations des types C pour definir les B-arbres d'ordre 2 */
9
10#define ORDRE 2
11/* ordre du B-arbre */
12
13typedef int t_cle;
14/* les cles sont des entiers */
15
760a8310
JB
16typedef struct page {
17 t_cle cle[2 * ORDRE + 1];
18 struct page *fils[2 * ORDRE + 1];
19} PAGE;
249ff697
JB
20
21/* une page contient au maximum 2*ORDRE cles et a 2*ORDRE+1 fils.
22 cle[0] contient le nombre de cles contenues dans la page.
23 ces cles sont rangees dans le tableau cle[1..2*ORDRE] */
24
25
26/*****************************************************************************/
27/* affichage d'un B-arbre */
760a8310 28void affiche_B_arbre(PAGE * p, int l)
249ff697 29{
760a8310
JB
30 int i;
31 char esp = ' ';
32 if (p) {
33 for (i = 1; i <= l; i++)
34 printf("%c", esp);
35 for (i = 1; i <= p->cle[0]; i++)
36 printf("%6d", p->cle[i]);
37 printf("\n");
38 for (i = 0; i <= p->cle[0]; i++)
39 affiche_B_arbre(p->fils[i], l + 4);
40 }
249ff697
JB
41}
42
43
44/*****************************************************************************/
45/* insertion de la cle x dans le B-arbre de racine a - v et pv designent
46 l'element (cle+pointeur) qui remonte au niveau superieur */
760a8310 47int insertion(t_cle x, PAGE * a, t_cle * v, PAGE ** pv)
249ff697 48{
760a8310
JB
49 int h = 0, gauche, droit, milieu, i, m;
50 t_cle u;
51 PAGE *pu, *b;
52
53 if (a == NULL) {
54 *v = x;
55 *pv = NULL;
56 h = 1;
57 } else { /* recherche dichotomique */
58 gauche = 1;
59 droit = a->cle[0];
60 do {
61 milieu = (gauche + droit) / 2;
62 if (x <= a->cle[milieu])
63 droit = milieu - 1;
64 if (x >= a->cle[milieu])
65 gauche = milieu + 1;
66 } while (gauche <= droit);
67 if (gauche - droit == 2) /* on a trouve x - on ne fait rien */
68 h = 0;
69 else { /* x n'est pas sur cette page */
70 h = insertion(x, a->fils[droit], &u, &pu);
71 if (h) { /* insertion de u en position droit+1 */
72 m = a->cle[0];
73 if (m < 2 * ORDRE) {
74 m++;
75 h = 0;
76 for (i = m; i >= droit + 2; i--) { /* decalage */
77 a->cle[i] = a->cle[i - 1];
78 a->fils[i] = a->fils[i - 1];
79 }
80 a->cle[droit + 1] = u; /* insertion */
81 a->fils[droit + 1] = pu;
82 a->cle[0] = m;
83 } else { /* la page est pleine - on la coupe en deux */
84 b = (PAGE *) malloc(sizeof(PAGE));
85 if (b == NULL) {
86 printf("Erreur allocation!\n");
87 exit(-1);
88 }
89 if (droit <= ORDRE) { /* insertion de u dans la page de gauche ie dans a */
90 if (droit == ORDRE) {
91 *v = u;
92 *pv = pu;
93 } else {
94 *v = a->cle[ORDRE];
95 *pv = a->fils[ORDRE];
96 for (i = ORDRE; i >= droit + 2; i--) { /* decalage */
97 a->cle[i] = a->cle[i - 1];
98 a->fils[i] = a->fils[i - 1];
99 }
100 a->cle[droit + 1] = u; /* insertion du u dans a */
101 a->fils[droit + 1] = pu;
102 }
103 for (i = 1; i <= ORDRE; i++) {
104 b->cle[i] = a->cle[i + ORDRE];
105 b->fils[i] = a->fils[i + ORDRE];
106 }
107 } else { /* insertion dans la page droite */
108 droit = droit - ORDRE;
109 *v = a->cle[ORDRE + 1];
110 *pv = a->fils[ORDRE + 1];
111 for (i = 1; i <= droit - 1; i++) {
112 b->cle[i] = a->cle[i + ORDRE + 1];
113 b->fils[i] = a->fils[i + ORDRE + 1];
114 }
115 b->cle[droit] = u; /* insertion de u dans b */
116 b->fils[droit] = pu;
117 for (i = droit + 1; i <= ORDRE; i++) {
118 b->cle[i] = a->cle[i + ORDRE];
119 b->fils[i] = a->fils[i + ORDRE];
120 }
121 }
122 a->cle[0] = b->cle[0] = ORDRE;
123 b->fils[0] = *pv;
124 *pv = b;
125 }
126 }
127 }
128 }
129 return h;
249ff697
JB
130}
131
132
133/*****************************************************************************/
134int main()
135{
760a8310
JB
136 PAGE *rac = NULL, *pu, *q;
137 t_cle x, u;
138 int h;
139 do {
140 printf("Entrez une cle: ");
141 scanf("%d", &x);
142 if (x) {
143 printf("Insertion de la cle %6d\n", x);
144 h = insertion(x, rac, &u, &pu);
145 if (h) {
146 q = rac;
147 rac = (PAGE *) malloc(sizeof(PAGE));
148 if (rac == NULL) {
149 printf("Erreur allocation!\n");
150 exit(-1);
151 }
152 rac->cle[0] = 1;
153 rac->fils[0] = q;
154 rac->cle[1] = u;
155 rac->fils[1] = pu;
156 }
157 affiche_B_arbre(rac, 1);
158 }
249ff697 159 }
760a8310 160 while (x);
249ff697 161}
249ff697 162
760a8310 163/*****************************************************************************/