/*====================*\
| BTree.h |
\*====================*/
#ifndef _BTREE_H_
#define _BTREE_H_
#define NUM 3
#define KeyType int
#define Status int
typedef struct BTNode {
int keynum;
struct BTNode * parent;
KeyType key[NUM+1];
struct BTNode * ptr[NUM+1];
}BTNode,*BTree;
typedef struct {
BTNode * pt;
int i;
int tag;
}Result;
Result SearchBTree(BTree T, KeyType K);
Status InsertBTree(BTree &T, KeyType K, BTree q, int i);
Status CreateBTree(BTree &T, int size, int *key);
void PrintBTree(BTree T);
#endif
/*===================*\
| Btree.c |
\*===================*/
#include "BTree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
Result SearchBTree(BTree T,KeyType k)
{
Result result;
BTree p,pre;
Status found = false;
int i = 1;
p = T;
pre = NULL;
while (p && !found)
{
for(i=1;i<p->keynum;i++)
{
if (k <= p->key[i])
break;
}
if (k == p->key[i])
found = true;
else
{
pre = p;
p = p->ptr[i-1];
}
}
result.i = i-1;
if(found)
result.pt = p;
else
result.pt = pre;
result.tag = found;
return result;
}
Status InsertBTree(BTree &T,KeyType K, BTree q,int i)
{
int j, s;
KeyType x;
BTree ap, temp;
bool finished = false;
x = K;
ap = NULL;
while (q && !finished)
{
for (j = q->keynum; j > i; j --)
{
q->key[j + 1] = q->key[j];
q->ptr[j + 1] = q->ptr[j];
}
q->key[i + 1] = x;
q->ptr[i + 1] = ap;
q->keynum ++;
if (q->keynum < NUM)
finished = true;
else
{
s = NUM / 2 + 1;
x = q->key[s];
q->keynum = s - 1;
ap = (BTree)malloc(sizeof(BTNode));
assert(ap != NULL);
ap->keynum = NUM - s;
for ( j = 1; j <= NUM - s; j ++)
{
ap->key[j] = q->key[s + j];
ap->ptr[j - 1] = q->ptr[s + j - 1];
if (ap->ptr[j - 1]!= NULL)
ap->ptr[j - 1]->parent = ap;
}
ap->ptr[NUM - s] = q->ptr[NUM];
if (ap->ptr[NUM - s] != NULL)
ap->ptr[j - 1]->parent = ap;
q = q->parent; //向上分裂
if (q) //求出i的值
{
for (j = 1; j <= q->keynum && x > q->key[j]; j ++)
NULL;
ap->parent = q;
i = j - 1;
}
}//else
}//while
if (!finished) //q = NULL;
{
temp = (BTree)malloc(sizeof(BTNode));
assert(temp != NULL);
temp->parent = NULL;
temp->keynum = 1;
temp->key[1] = x;
temp->ptr[0] = T;
temp->ptr[1] = ap;
if (ap != NULL)
ap->parent = temp;
if (T != NULL)
T->parent = temp;
T = temp;
}
return true;
}
Status CreateBTree(BTree &T, int size, int *key)
{
Result result;
int i;
for (i = 0; i < size; i ++)
{
result = SearchBTree(T, key[i]);
if (!result.tag) //需要插入
if (!InsertBTree(T, key[i],result.pt, result.i))
return false;
}
return true;
}
void PrintBTree(BTree T)
{
int front,rear, i, count;
BTree Queue[1000], temp;
front = rear = 0;
Queue[rear ++] = T;
while (front < rear)
{
temp = Queue[front++];
if (temp != NULL)
{
count = 0;
for (i = 0; i <= temp->keynum; i ++)
if (temp->ptr[i] != NULL)
count ++;
printf("[%d]", count);
for ( i = 1; i <= temp->keynum; i ++)
printf("%d ", temp->key[i]);
printf("\n");
for (i = 0; i <= temp->keynum; i ++)
Queue[rear ++] = temp->ptr[i];
}
}
}
//////////////////////////////////////////////////////////////////////////
int main(void)
{
BTree T = NULL;
int key[15] = { 45, 24, 53, 90, 3, 12, 37, 50, 61, 70, 100, 30, 26, 85, 7};
CreateBTree(T, 15, key);
PrintBTree(T);
return 1;
}
分享到:
相关推荐
实现B树的增删改查,以一个例子进行演示,并附图解说明~~~
基于B树实现的图书管理系统
2019年期末课程设计,没有任何的引用资源,内含数据结构B树的基本操作接口,可以进行快速的查找。文件为VS工程文件夹。
基于B树实现的图书管理系统
B树为基本数据结构实现图书的借阅、归还、查询及搜索功能
步骤为数据库文件创建一个B+树索引: (1)生成数据文件, (2)为数据库文件的属性创建B+ 树文件。 (3)给定键值,通过B+树进行查找。同时比较与直接扫描表的性能差别。(利用B+树时可根据内存大小决定放置多少层次到...
B树的C++实现,实现了插入和删除操作。数据量比较大,可以根据需要修改main中的测试数组
主要为大家详细介绍了完整的B树算法Java实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
这个图书管理只是测试B-树,主要是B-树的实现算法。
网上很多程序没有注释,代码运行报错。所以精心重写了一下B树的实现。程序结构严谨,有详细的注释,运行没有问题,基于vs2013平台。对于刚学算法的人应该会有很大帮助。
B树索引实现歌曲管理系统,qt的界面。方便学弟学妹们软件设计。
数据结构课程设计时写的关于文件索引的程序,由于版本有些乱了,上传的这个可能有些问题,敬请谅解
NULL 博文链接:https://zhengliang.iteye.com/blog/2124907
B+树实现源码 B+树实现源码 B+树实现源码 B+树实现源码 B+树实现源码
在数据结构中,B树的算法程序实现是个难点,本程序代码供大家共享,反复使用
B树,C语言实现,添加到vc6.0中,可以执行的程序。
包括实验报告 编程环境:Vs Code 编程语言:C 利用C语言数据类型表示B树的抽象数据类型,以及B树的抽象数据类型的实现。 抽象数据类型树的定义:树的结构定义和树的一组基本操作
c语言的代码实现B+树。基于文件操作。模拟B+树的建立索引
B-树和B+树的C语言实现(数据结构)。
二级存储/磁盘存储中的B树实现 此实现基于书中B-Tree所采用的方法: 算法入门,第三版-Cormen,2011年 实现的方法: 克里特岛B树 插入 搜索 删除中 打印树 毁树 寻找最大 寻找敏 文件管理和B树存储: 该实现将...