请用C语言实现B+数的数据结构,写在一个文件中,有插入,删除,打印操作
时间: 2024-03-15 15:46:26 浏览: 48
基于C++实现(控制台)实现链表的插入、删除、打印等操作的函数(线程安全型数据结构)【100012475】
由于B+树是一种复杂的数据结构,如果完整地实现B+树,代码会非常长。此处我们提供一个简单的B+树实现,仅包含了插入、删除和打印三种操作。
```c
#include <stdio.h>
#include <stdlib.h>
#define M 3
typedef struct BPlusNode {
int key[M + 1]; // 关键字数组
int is_leaf; // 是否是叶子节点
int num; // 关键字个数
struct BPlusNode* child[M + 1]; // 子节点数组
} BPlusNode;
// 创建节点
BPlusNode* create_node() {
BPlusNode* node = (BPlusNode*)malloc(sizeof(BPlusNode));
node->is_leaf = 0;
node->num = 0;
for (int i = 0; i <= M; i++) {
node->child[i] = NULL;
}
return node;
}
// 查找关键字所在的节点和位置
void search(BPlusNode* root, int key, BPlusNode** node, int* pos) {
BPlusNode* p = root;
while (p->is_leaf == 0) {
int i = 0;
while (i < p->num && key >= p->key[i]) {
i++;
}
p = p->child[i];
}
int i = 0;
while (i < p->num && key > p->key[i]) {
i++;
}
*node = p;
*pos = i;
}
// 分裂节点
void split(BPlusNode** node, int pos) {
BPlusNode* p = *node;
BPlusNode* q = create_node();
q->is_leaf = p->is_leaf;
q->num = M - pos - 1;
for (int i = 0; i < q->num; i++) {
q->key[i] = p->key[i + pos + 1];
}
if (p->is_leaf == 1) {
for (int i = 0; i < q->num; i++) {
q->child[i] = p->child[i + pos + 1];
}
}
p->num = pos + 1;
for (int i = p->num; i <= M; i++) {
p->key[i] = 0;
p->child[i] = NULL;
}
if (p->is_leaf == 0) {
for (int i = p->num; i <= M; i++) {
p->child[i] = NULL;
}
}
for (int i = (*node)->num; i >= pos + 1; i--) {
(*node)->child[i + 1] = (*node)->child[i];
}
(*node)->child[pos + 1] = q;
for (int i = (*node)->num - 1; i >= pos; i--) {
(*node)->key[i + 1] = (*node)->key[i];
}
(*node)->key[pos] = p->key[pos];
(*node)->num++;
}
// 插入关键字
void insert(BPlusNode** root, int key) {
BPlusNode* p = NULL;
int pos = 0;
search(*root, key, &p, &pos);
if (p->num < M) {
for (int i = p->num; i > pos; i--) {
p->key[i] = p->key[i - 1];
}
p->key[pos] = key;
p->num++;
} else {
split(&p, pos);
if (key >= p->key[pos]) {
pos++;
}
insert(&(p->child[pos]), key);
}
}
// 删除关键字
void remove_key(BPlusNode** node, int pos) {
BPlusNode* p = *node;
for (int i = pos + 1; i < p->num; i++) {
p->key[i - 1] = p->key[i];
}
p->num--;
}
// 合并节点
void merge(BPlusNode** node, int pos) {
BPlusNode* p = *node;
BPlusNode* q = p->child[pos];
BPlusNode* r = p->child[pos + 1];
q->key[q->num] = p->key[pos];
q->num++;
for (int i = 0; i < r->num; i++) {
q->key[q->num + i] = r->key[i];
}
if (r->is_leaf == 0) {
for (int i = 0; i <= r->num; i++) {
q->child[q->num + i] = r->child[i];
}
}
remove_key(&p, pos);
for (int i = pos; i < p->num; i++) {
p->child[i + 1] = p->child[i + 2];
}
p->child[p->num + 1] = NULL;
if (p->num == 0) {
*node = q;
free(p);
}
}
// 删除关键字
void delete(BPlusNode** root, int key) {
if (*root == NULL) {
return;
}
BPlusNode* p = NULL;
int pos = 0;
search(*root, key, &p, &pos);
if (p->is_leaf == 1 && p->key[pos] == key) {
remove_key(&p, pos);
} else if (p->is_leaf == 0) {
if (p->child[pos]->num >= M) {
BPlusNode* q = p->child[pos];
while (q->is_leaf == 0) {
q = q->child[q->num];
}
p->key[pos] = q->key[q->num - 1];
delete(&(p->child[pos]), q->key[q->num - 1]);
} else if (p->child[pos + 1]->num >= M) {
BPlusNode* q = p->child[pos + 1];
while (q->is_leaf == 0) {
q = q->child[0];
}
p->key[pos] = q->key[0];
delete(&(p->child[pos + 1]), q->key[0]);
} else {
merge(&p, pos);
delete(&(p->child[pos]), key);
}
}
}
// 打印节点
void print_node(BPlusNode* node) {
if (node->is_leaf == 1) {
for (int i = 0; i < node->num; i++) {
printf("%d ", node->key[i]);
}
} else {
for (int i = 0; i < node->num; i++) {
print_node(node->child[i]);
printf("%d ", node->key[i]);
}
print_node(node->child[node->num]);
}
}
// 打印B+树
void print(BPlusNode* root) {
print_node(root);
printf("\n");
}
int main() {
BPlusNode* root = NULL;
insert(&root, 10);
insert(&root, 20);
insert(&root, 30);
insert(&root, 40);
insert(&root, 50);
insert(&root, 60);
insert(&root, 70);
insert(&root, 80);
print(root);
delete(&root, 20);
delete(&root, 40);
delete(&root, 60);
print(root);
return 0;
}
```
在上述代码中,我们使用了一个结构体 `BPlusNode` 来表示B+树中的节点。其中,`key` 数组用来存储关键字,`is_leaf` 表示是否是叶子节点,`num` 表示节点中关键字的数量,`child` 数组表示子节点。
我们实现了 `create_node` 函数来创建一个节点, `search` 函数用来查找关键字所在的节点和位置。 `insert` 函数用来插入关键字,如果节点未满,直接插入;否则,分裂节点,然后递归地插入。 `split` 函数用来分裂节点。 `remove_key` 函数用来删除关键字。 `merge` 函数用来合并节点。 `delete` 函数用来删除关键字,如果关键字在叶子节点中,直接删除;否则,如果关键字在非叶子节点中,用其右子树中最小的关键字代替,并递归地删除该关键字;如果右子树中最小的关键字不足以代替该关键字,就从左右子树中选择一个关键字合并节点,然后递归地删除该关键字。 `print` 函数用来打印B+树。
阅读全文