帮我使用c语言写一个b+树
时间: 2023-04-07 15:01:35 浏览: 60
好的,我可以回答这个问题。B树是一种自平衡的树形数据结构,通常用于数据库和文件系统中。以下是一个简单的C语言实现B树的代码示例:
```
#include <stdio.h>
#include <stdlib.h>
#define M 4
struct node {
int n; // 节点中关键字的数量
int keys[M-1]; // 关键字数组
struct node *p[M]; // 子节点指针数组
};
struct node *root = NULL;
void insert(int key);
void split(struct node *x, int i);
void insert_nonfull(struct node *x, int key);
void traverse(struct node *x);
int main() {
int i, n, key;
printf("Enter the number of keys: ");
scanf("%d", &n);
printf("Enter the keys: ");
for (i = 0; i < n; i++) {
scanf("%d", &key);
insert(key);
}
printf("The B-tree is: ");
traverse(root);
printf("\n");
return 0;
}
void insert(int key) {
struct node *r = root;
if (r == NULL) {
root = malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = key;
} else {
if (r->n == M-1) {
struct node *s = malloc(sizeof(struct node));
root = s;
s->n = 0;
s->p[0] = r;
split(s, 0);
insert_nonfull(s, key);
} else {
insert_nonfull(r, key);
}
}
}
void split(struct node *x, int i) {
struct node *z = malloc(sizeof(struct node));
struct node *y = x->p[i];
int j;
z->n = M/2 - 1;
for (j = 0; j < M/2 - 1; j++) {
z->keys[j] = y->keys[j+M/2];
}
if (y->p[0] != NULL) {
for (j = 0; j < M/2; j++) {
z->p[j] = y->p[j+M/2];
}
}
y->n = M/2 - 1;
for (j = x->n; j >= i+1; j--) {
x->p[j+1] = x->p[j];
}
x->p[i+1] = z;
for (j = x->n-1; j >= i; j--) {
x->keys[j+1] = x->keys[j];
}
x->keys[i] = y->keys[M/2-1];
x->n++;
}
void insert_nonfull(struct node *x, int key) {
int i = x->n-1;
if (x->p[0] == NULL) {
while (i >= 0 && key < x->keys[i]) {
x->keys[i+1] = x->keys[i];
i--;
}
x->keys[i+1] = key;
x->n++;
} else {
while (i >= 0 && key < x->keys[i]) {
i--;
}
i++;
if (x->p[i]->n == M-1) {
split(x, i);
if (key > x->keys[i]) {
i++;
}
}
insert_nonfull(x->p[i], key);
}
}
void traverse(struct node *x) {
int i;
if (x != NULL) {
for (i = 0; i < x->n; i++) {
traverse(x->p[i]);
printf("%d ", x->keys[i]);
}
traverse(x->p[i]);
}
}
```
这个代码实现了B树的插入操作,并且可以输出B树的所有关键字。