数据结构设计性实验报告
课程名称数据结构实验
题目名称B 树（难度1.4）
学生学院 计算机学院
专业班级
学 号
姓名 指导教师黄剑锋
2015年 06月25日
B 树抽象数据类型实现
一、设计简介
本次设计在AnyviewCL 自由编程平台上实现了B 树的6种基本操作，并根据这个基本操作设计了友好的交际界面，操作简单易懂，并在AnyviewCL 自由编程平台上可视化测试B 树各个基本操作，保证了各基本的操作算法的正确性。
经在AnyviewCL 自由编程平台严格测试后，将本设计移植到Visual C++ 6.0平台生成可运行程序，并进行各个基本操作的测试，保证了程序运行的稳定性。
其中数据来源为一组在0~1000内的int 型随机数，但数据由typedefintKeyType 定义，若需要改变数据类型，只需要将int 替换成所需的数据类型即可。
二、抽象数据类型定义及各种基本操作的描述 ADT BTree{
数据对象：D 是具有相同特征的数据元素集合。
数据关系：
若D 为空集，则称为空树；
（1）树中每个结点最多含有m 棵子树；
（2）若根结点不是叶子结点，则至少有2个子树；
（3）除根结点之外的所有非终端结点至少有┌m/2┐棵子树；
（4）每个非终端结点中包含信息：（n ，A0，K1，A1，K2，A2，…，Kn ，An ）。其中：
1）Ki （1
2）指针Ai （0
3）关键字的个数n 必须满足：┌m/2┐-1
（5）所有的叶子节点都在同一层，子叶结点不包含任何信息。
基本操作P ：
CreatBTree(&T, n, m);
初始条件：初始化关键字个数n 大于等于0，B 树的阶数m 大于3小于等于20。 操作结果：构建一棵阶数为m ，含有n 个关键字的B 树。
SearchBTree(T, k, &p);
初始条件：树T 存在。
操作结果：在m 阶B 树t 上查找关键字k ，返回(pt,i,tag) 。
InsertBTree(&T, k, p->pt, p->i, m);
初始条件：树T 存在，p->pt指向T 中某个结点
操作结果：在B 树T 上结点p->pt的key[i]和key[i+1]之间插入关键字k DeleteBTree(p->pt, p->i, m, T);
初始条件：树T 存在，p->pt指向T 中某个结点
操作结果：删除B 树T 上结点p->pt的关键字k
PrintBTree(T);
初始条件：树T 存在
操作结果：中序遍历B 树
DestroyBTree(T)
初始条件：树T 存在
操作结果：销毁B 树
}ADTBTree
三、存储结构定义
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedefintKeyType;
typedefint Status;
typedefstruct
{
KeyType key;
char data;
}Record;
typedefstructBTNode
{
intkeynum; // 结点中关键字个数，即结点的大小
structBTNode *parent; // 指向双亲结点
KeyType key[21]; // 关键字向量，0号单元未用 structBTNode *ptr[21]; // 子树指针向量
Record *recptr[21]; // 记录指针向量，0号单元未用 }BTNode, *BTree; // B树结点和B 树的类型
typedefstruct
{
BTNode *pt; // 指向找到的结点
int i; // 1..m，在结点中的关键字序号
int tag; // 1:查找成功，0:查找失败
}restype,*result; // 在B 树的查找结果类型
四、关键算法设计流程图
主函数：MAIN();
功能：确定B 树阶数与初始结点数，提供基本的菜单功能选择
函数名：intSearchNode(BTree p, int k);
功能：在节点中查找关键字，返回该关键字在节点中的位置。
函数名：voidSearchBTree(BTree t, int k, result &SearchBTree);
功能：在m 阶B 树t 上查找关键码k ，返回(pt,i,tag)。
函数名：void split(BTree&q, int s, BTree&ap);
功能：将结点q 分裂成两个结点，前一半保留，后一半移入新生结点ap 。
函数名：voidnewroot(BTree&t, BTree p, int x, BTreeap);
功能：生成新的根结点。
函数名：void Insert(BTree&q, int i, int x, BTreeap);
功能：将关键字ap 分别插入到q->key[i+1]和q->ptr[i+1]中。
函数名：voidInsertBTree(BTree&t, int k, BTree q, int i, int m);
功能：在B 树t 上结点*q的key[i]和key[i+1]之间插入关键字k 。
函数名：void Successor(BTree&p, int i);
功能：由后继最下层非终端结点的最小关键字代替结点中关键字key[i]。
函数名：void Remove(BTree&p, int i);
功能：从结点p 中删除key[i]。
函数名：void Restore(BTree&p, int i, int m, BTree&T); 功能：调整B 树。
函数名：voidDeleteBTree(BTree p, int i, int m, BTree&T); 功能：删除B 树T 上结点p 的关键字k 。
五、 程序测试
1、AnyviewCL 自由编程平台上测试结果 1）3阶B 树的测试：
此时B 树的结构为：
进行查找操作：
进行插入操作：
插入后B 树的结构为：
进行删除操作（直接删除关键字）：
删除关键字618后B 树的结构为：
此时对B 树进行打印操作：
继续进行删除操作：（删后结点与左兄弟合并）
删除关键字798后B 树的结构为：
继续进行删除操作：（直接删除关键字）
删除关键字796后B 树的结构为：
继续进行删除操作：（删后结点与右兄弟合并、父节点与左兄弟合并）
删除关键字580后B 树的结构为：
继续进行删除操作：（删后结点与左兄弟合并、父节点与右兄弟合并，树的高度减1）
删除关键字281后B 树的结构为：
进行B 树的销毁：
此时AnyviewCL 的演示区情况为：
2）5阶B 树的测试：
初始化B 树的结构后，B 树的结构为：
进行插入操作：
插入关键字580后B 树的结构为：
进行删除操作：（删后结点与右兄弟合并）
删除关键字21后B 树的结构为：
继续进行删除操作：（寻找后继结点并与之交换，删后向左兄弟借关键字）
删除关键字596后B 树的结构为：
进行打印B 树操作：
2、在Visual C++ 6.0平台测试： B 树设置界面：
进行B 树初始话操作：
进行打印B 树操作：
进行查找操作：
进行插入操作：
插入关键字588后的B 树结构为：
进行删除操作：
删除关键字532后的B 树结构为：
进行销毁B 树操作：
销毁后B 树为空，无法打印：
退出程序操作：
六、思考与小结
1、B 树的高度：
若N>=1，则对任意一棵包含N 个关键字、高度为h 、阶数为m 的B 树：
1）因为B 树中每个结点最多有m 棵子树，m-1个关键字，所以在一棵高度为h 的m 阶B 树中的关键字个数应满足：N=logm(N+1);
2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B 树的高度可达到最大，此时有h
2、复杂度：
每次查找共需访问O(logmN)个结点，由此可知，对存有N 个关键字的m 阶B 树的每次查找，耗时不超过O(logmN)。
七、总结和体会
本次设计主要在AnyviewCL 自由编程平台上进行编程，通过深入学习课本提供的查找与插入算法后，我很轻易地写出了构建的算法，再根据递归的知识完成了B 树的中序遍历算法和销毁算法。本次设计的难点在于B 树的调整算法，B 树在插入的过程中可能发生上溢，此时需要通过分裂结点来处理，在此过程中B 树可能出现长高。而在删除的过程中则可能发生下溢，此时需要分：借左兄弟、借右兄弟、与左兄弟合并、与右兄弟这四种调整方式来处理，并要处理合并后根结点为空的情况，在此过程中B 树可能出现高度降低。
在该平台的可视化调试功能的帮助严格测试了下各个基本操作的算法设计，改进算法中一些可能出现的错误，保证了代码的正确性。然后将代码移植到Visual C++ 6.0中，编译并运行后，初始化B 树时程序出现异常代码:c0000005，在Dubug 模式下找到原因是操作了未经初始化的对象，而代码本身在AnyviewCL 自由编程平台上是可以顺利运行的，后来经过对几个关键指针的初始化Bug 顺利排除。究其原因可能是AnyviewCL 平台在实现可视化的过程已经对所有运用到的指针都进行了初始化。
总而言之，在这次设计中我深入理解了B 树的各项基本操作，也很好地锻炼了自己的动手能力，收获匪浅。
八、程序关键源码
//BTree for Visual C++ 6.0
//By：2013级计算机科学与技术3班3113005867方典禹
//包含文件BTree.cpp 、Operation.h 、 BTree.cpp
Datastructure.h
//*******************定义数据类型***********************//
BTree.cpp
//*******************主函数***********************//
Operation.h
#include "Datastructure.h"
//******************************基本操作函数****************************// intSearchNode(BTree p, int k)
//在p->key[1..keynum]找p->key[i]key[i+1]，并返回i
{
int i = 1;
while(i keynum&& k > p->key[i]) i++;
return i;
}
voidSearchBTree(BTree t, int k, result &SearchBTree)
// 在m 阶B 树t 上查找关键码k ，返回(pt,i,tag)。
// 若查找成功，则特征值tag=1，指针pt 所指结点中第i 个关键码等于k ；否则，
// 特征值tag=0,等于k 的关键码记录应插入在指针pt 所指结点中第i 个和第i+1个关键码间 {
int i = 0, found = 0;
BTree p = t, q = NULL; // 初始，p 指向待查结点，q 指向p 的双亲
while(p != NULL && 0 == found)
{
i = SearchNode(p, k); // 在p->key[1..keynum]找p->key[i]key[i+1] if(i>0 && p->key[i] == k)
found = 1; // 找到待查关键字
else
{
q = p;
p = p->ptr[i-1];
}
}
if(1 == found) // 查找成功
{
SearchBTree ->pt = p;
SearchBTree -> i = i;
SearchBTree -> tag = 1;
}
else // 查找不成功，返回key 的插入位置i
{
SearchBTree ->pt = q;
SearchBTree -> i = i;
SearchBTree -> tag = 0;
}
}
void split(BTree&q, int s, BTree&ap)
// 将结点q 分裂成两个结点，前一半保留，后一半移入新生结点ap
{
int i, j, n = q ->keynum;
ap = (BTNode*)malloc(sizeof(BTNode)); // 生成新结点ap
ap ->ptr[0] = q ->ptr[s];
for(i = s + 1, j = 1; i
{
ap -> key[j] = q -> key[i];
ap ->ptr[j] = q ->ptr[i];
}
ap ->keynum = n - s;
ap -> parent = q -> parent;
for(i = 0; i
if(ap ->ptr[i])
ap ->ptr[i] -> parent = ap;
q ->keynum = s - 1; // q的前一半保留，修改keynum
}
voidnewroot(BTree&t, BTree p, int x, BTreeap)
// 生成新的根结点
{
t = (BTNode*)malloc(sizeof(BTNode));
t ->keynum = 1;
t ->ptr[0] = p;
t ->ptr[1] = ap;
t -> key[1] = x;
if(p!=NULL)
p -> parent = t;
if(ap!=NULL)
ap -> parent = t;
t -> parent = NULL; // 新根的双亲是空指针
}
void Insert(BTree&q, int i, int x, BTreeap)
{
intj,n = q ->keynum;
for(j = n; j >= i; j--)
{
q ->key[j+1] = q -> key[j];
q ->ptr[j+1] = q ->ptr[j];
}
q -> key[i] = x;
q ->ptr[i] = ap;
if(ap!=NULL)
ap -> parent = q;
q ->keynum++;
}
voidInsertBTree(BTree&t, int k, BTree q, int i, int m)
// 在B 树t 上结点*q的key[i]和key[i+1]之间插入关键字k
// 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T 仍是m 阶的B 树 {
int x, s;
BTreeap;
int finished = 0, neednewroot = 0;
if(NULL==q)
newroot(t, NULL, k, NULL);
else
{
x = k; ap = NULL;
while(0 == neednewroot&& 0 == finished)
{
Insert(q, i, x, ap); // key和ap 分别插到q->key[i+1]和q->ptr[i+1]
if(q->keynum
finished = 1; // 插入完成
else // 分裂结点q
{
s = (m+1)/2;
split(q, s, ap);
x = q -> key[s];
if(q -> parent)
{
q = q -> parent;
i = SearchNode(q, x); // 在双亲结点*q中查找x 的插入位置 }
elseneednewroot = 1;
}
}
if(1 == neednewroot) // t是空树或者根结点已分裂为结点q 和ap
newroot(t, q, x, ap); // 生成含信息(t,x,ap)的新的根结点root
}
}
void Successor(BTree&p, int i)
//由后继最下层非终端结点的最小关键字代替结点中关键字key[i]
{
BTNode *u;
while(NULL != u ->ptr[0]) //找出关键字的后继
{
u = u ->ptr[0];
}
p -> key[i] = u -> key[1];
p = u;
}
void Remove(BTree&p, int i)
//从结点p 中删除key[i]
{
intj,n = p ->keynum;
for(j = i; j
{
p -> key[j] = p -> key[j+1];
p ->ptr[j] = p ->ptr[j+1];
}
//free(p ->ptr[n]);
//p ->ptr[n] = NULL;
p ->keynum -- ;
}
void Restore(BTree&p, int i, int m, BTree&T)
//调整B 树
{
int j;
BTreeap = p -> parent;
BTreelc, rc, pr;
int finished = 0, r = 0;
while(0 == finished)
{
r = 0;
while(ap ->ptr[r] != p) //确定p 在ap 子树的位置
r++;
if(r == 0)
{
r++;
lc = NULL;
rc = ap ->ptr[r];
}
else if(r == ap ->keynum)
{
rc = NULL;
}
else
{
lc = ap ->ptr[r-1];
rc = ap ->ptr[r+1];
}
if(r > 0 &&lc != NULL && (lc ->keynum> (m - 1) / 2)) //向左兄弟借关键字
{
p ->keynum ++;
for(j = p ->keynum; j > 1; j--) //结点关键字右移
{
p -> key[j] = p -> key[j-1];
p ->ptr[j] = p ->ptr[j-1];
}
p -> key[1] = ap -> key[r]; //父亲插入到结点
p ->ptr[1] = p ->ptr[0];
p ->ptr[0] = lc ->ptr[lc ->keynum];
if(NULL != p ->ptr[0]) //修改p 中的子女的父结点为p
p ->ptr[0] -> parent = p;
ap -> key[r] = lc -> key[lc ->keynum]; //左兄弟上移到父亲位置
lc ->keynum --;
finished = 1;
break;
}
else if(ap ->keynum> r &&rc != NULL && (rc ->keynum> (m - 1) / 2)) //向右兄弟借关键字 {
p ->keynum ++;
p -> key[p ->keynum] = ap -> key[r]; //父亲插入到结点
p ->ptr[p ->keynum] = rc ->ptr[0];
if(NULL != p ->ptr[p ->keynum]) //修改p 中的子女的父结点为p
p ->ptr[p ->keynum] -> parent = p;
ap -> key[r] = rc -> key[1]; //右兄弟上移到父亲位置
rc ->ptr[0] = rc ->ptr[1];
for(j = 1; j keynum; j++) //右兄弟结点关键字左移
{
rc -> key[j] = rc -> key[j+1];
rc ->ptr[j] = rc ->ptr[j+1];
}
rc ->keynum --;
finished = 1;
break;
}
r = 0;
while(ap ->ptr[r] != p) //重新确定p 在ap 子树的位置
r++;
if(r > 0 && (ap ->ptr[r-1] ->keynum
{
lc = ap ->ptr[r - 1];
p ->keynum ++;
for(j = p ->keynum; j > 1; j-- ) //将p 结点关键字和指针右移1位 {
p -> key[j] = p -> key[j-1];
p ->ptr[j] = p ->ptr[j-1];
}
p -> key[1] = ap -> key[r]; //父结点的关键字与p 合并
p ->ptr[1] = p ->ptr[0]; //从左兄弟右移一个指针
ap ->ptr[r+1] = lc;
for(j = 1; j keynum + p ->keynum; j++) //将结点p 中关键字和指针移到p 左兄弟中
{
lc->key[lc ->keynum + j] = p -> key[j];
lc->ptr[lc ->keynum + j] = p ->ptr[j];
}
if(p ->ptr[0]) //修改p 中的子女的父结点为lc
{
for(j = 1; j keynum; j++)
p ->ptr[p ->keynum + j] -> parent = lc;
}
lc ->keynum = lc ->keynum + p ->keynum; //合并后关键字的个数
ap ->keynum--;
pr = p;
free(pr); //释放p 结点空间
pr = NULL;
p = lc;
}
else //与右兄弟合并
{
rc = ap ->ptr[r + 1];
if(r == 0)
r ++;
p ->keynum ++;
p -> key[p ->keynum] = ap -> key[r]; //父结点的关键字与p 合并 p ->ptr[p ->keynum] = rc ->ptr[0]; //从右兄弟左移一个指针
rc ->keynum = p ->keynum + rc ->keynum; //合并后关键字的个数
ap ->ptr[r-1] = rc;
for(j = 1; j keynum - p ->keynum); j++) //将p 右兄弟关键字和指针右移
{
rc->key[p ->keynum + j] = rc -> key[j];
rc->ptr[p ->keynum + j] = rc ->ptr[j];
}
for(j = 1; j keynum; j++) //将结点p 中关键字和指针移到p 右兄弟中
{
rc->key[j] = p -> key[j];
rc->ptr[j] = p ->ptr[j];
}
rc->ptr[0] = p ->ptr[0];
if(p ->ptr[0]) //修改p 中的子女的父结点为rc
{
for(j = 1; j keynum; j++)
p ->ptr[p ->keynum + j] -> parent = rc;
}
for(j = r; j keynum; j++) //将父结点中关键字和指针左移 {
ap -> key[j] = ap -> key[j + 1];
ap ->ptr[j] = ap ->ptr[j + 1];
}
ap ->keynum--; //父结点的关键字个数减1
pr = p;
free(pr); //释放p 结点空间
pr = NULL;
p = rc;
}
ap = ap -> parent;
if(p -> parent ->keynum>= (m-1)/2 || (NULL == ap&& p -> parent ->keynum>0))
finished = 1;
else if(NULL == ap) //若调整后出现空的根结点，则删除该根结点，树高减1 {
pr = T;
T = p; //根结点下移
free(pr);
pr = NULL;
finished = 1;
}
p = p -> parent;
}
}
voidDeleteBTree(BTree p, int i, int m, BTree&T)
// 删除B 树T 上结点p 的关键字k
if(p->ptr[i-1]!=NULL) // 若不是最下层非终端结点
{
Successor(p, i); // 由后继最下层非终端结点的最小关键字代替它 DeleteBTree(p, 1, m, T); // 变成删除最下层非终端结点中的最小关键字 }
else // 若是最下层非终端结点
{
Remove(p, i); // 从结点p 中删除key[i]
if(p->keynum
Restore(p, i, m, T); // 调整B 树
}
}
//中序遍历B 树
voidPrintBTree(BTree t)
{
int i = 1;
if(NULL != t)
{
while(i keynum)
{
PrintBTree(t ->ptr[i-1]);
printf("%d ", t -> key[i]);
i++;
}
PrintBTree(t ->ptr[i-1]);
}
}
//销毁B 树
voidDestroyBTree(BTree t)
{
int i = 1;
if(NULL != t)
{
while(i keynum)
{
DestroyBTree(t ->ptr[i-1]);
free(t ->ptr[i-1]);
i++;
}
DestroyBTree(t ->ptr[i-1]);
}
//初始化B 树
voidCreatBTree(BTree&T, int n, int m)
{
inti,j;
result p = NULL;
p = (restype *)malloc(sizeof(restype));
//srand( (unsigned)time( NULL ) ); //初始化随机数 if(0 == n)
printf("初始化成功，该B 树为空树。\n");
else
{
for(j = 0; j
{
i = rand()%1000;
SearchBTree(T, i, p); //查找插入位置
InsertBTree(T, i, p->pt, p->i, m); //进行插入
}
printf("初始化成功!\n");
}
}
intmenu_select() //选择菜单
{
int i;
printf("********************* B 树 **********************\n"); printf("*******************menu select********************\n"); printf(" 1. 初始化B 树 \n");
printf(" 2. 查找元素 \n");
printf(" 3. 插入元素 \n");
printf(" 4. 删除元素 \n");
printf(" 5. 打印B 树 \n");
printf(" 6. 销毁B 树 \n");
printf(" 0. 退出程序 \n");
printf("**************************************************\n"); printf("***********By:2013级计算机科学与技术3班***********\n"); printf("*************** 3113005867 方典禹 ***************\n"); printf("**************************************************\n"); do
{
printf("\n\t请输入操作B 树方法：\n");
scanf("%d",&i);
}while(i 6); //此处为判断输入
return i; }
数据结构设计性实验报告
课程名称数据结构实验
题目名称B 树（难度1.4）
学生学院 计算机学院
专业班级
学 号
姓名 指导教师黄剑锋
2015年 06月25日
B 树抽象数据类型实现
一、设计简介
本次设计在AnyviewCL 自由编程平台上实现了B 树的6种基本操作，并根据这个基本操作设计了友好的交际界面，操作简单易懂，并在AnyviewCL 自由编程平台上可视化测试B 树各个基本操作，保证了各基本的操作算法的正确性。
经在AnyviewCL 自由编程平台严格测试后，将本设计移植到Visual C++ 6.0平台生成可运行程序，并进行各个基本操作的测试，保证了程序运行的稳定性。
其中数据来源为一组在0~1000内的int 型随机数，但数据由typedefintKeyType 定义，若需要改变数据类型，只需要将int 替换成所需的数据类型即可。
二、抽象数据类型定义及各种基本操作的描述 ADT BTree{
数据对象：D 是具有相同特征的数据元素集合。
数据关系：
若D 为空集，则称为空树；
（1）树中每个结点最多含有m 棵子树；
（2）若根结点不是叶子结点，则至少有2个子树；
（3）除根结点之外的所有非终端结点至少有┌m/2┐棵子树；
（4）每个非终端结点中包含信息：（n ，A0，K1，A1，K2，A2，…，Kn ，An ）。其中：
1）Ki （1
2）指针Ai （0
3）关键字的个数n 必须满足：┌m/2┐-1
（5）所有的叶子节点都在同一层，子叶结点不包含任何信息。
基本操作P ：
CreatBTree(&T, n, m);
初始条件：初始化关键字个数n 大于等于0，B 树的阶数m 大于3小于等于20。 操作结果：构建一棵阶数为m ，含有n 个关键字的B 树。
SearchBTree(T, k, &p);
初始条件：树T 存在。
操作结果：在m 阶B 树t 上查找关键字k ，返回(pt,i,tag) 。
InsertBTree(&T, k, p->pt, p->i, m);
初始条件：树T 存在，p->pt指向T 中某个结点
操作结果：在B 树T 上结点p->pt的key[i]和key[i+1]之间插入关键字k DeleteBTree(p->pt, p->i, m, T);
初始条件：树T 存在，p->pt指向T 中某个结点
操作结果：删除B 树T 上结点p->pt的关键字k
PrintBTree(T);
初始条件：树T 存在
操作结果：中序遍历B 树
DestroyBTree(T)
初始条件：树T 存在
操作结果：销毁B 树
}ADTBTree
三、存储结构定义
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedefintKeyType;
typedefint Status;
typedefstruct
{
KeyType key;
char data;
}Record;
typedefstructBTNode
{
intkeynum; // 结点中关键字个数，即结点的大小
structBTNode *parent; // 指向双亲结点
KeyType key[21]; // 关键字向量，0号单元未用 structBTNode *ptr[21]; // 子树指针向量
Record *recptr[21]; // 记录指针向量，0号单元未用 }BTNode, *BTree; // B树结点和B 树的类型
typedefstruct
{
BTNode *pt; // 指向找到的结点
int i; // 1..m，在结点中的关键字序号
int tag; // 1:查找成功，0:查找失败
}restype,*result; // 在B 树的查找结果类型
四、关键算法设计流程图
主函数：MAIN();
功能：确定B 树阶数与初始结点数，提供基本的菜单功能选择
函数名：intSearchNode(BTree p, int k);
功能：在节点中查找关键字，返回该关键字在节点中的位置。
函数名：voidSearchBTree(BTree t, int k, result &SearchBTree);
功能：在m 阶B 树t 上查找关键码k ，返回(pt,i,tag)。
函数名：void split(BTree&q, int s, BTree&ap);
功能：将结点q 分裂成两个结点，前一半保留，后一半移入新生结点ap 。
函数名：voidnewroot(BTree&t, BTree p, int x, BTreeap);
功能：生成新的根结点。
函数名：void Insert(BTree&q, int i, int x, BTreeap);
功能：将关键字ap 分别插入到q->key[i+1]和q->ptr[i+1]中。
函数名：voidInsertBTree(BTree&t, int k, BTree q, int i, int m);
功能：在B 树t 上结点*q的key[i]和key[i+1]之间插入关键字k 。
函数名：void Successor(BTree&p, int i);
功能：由后继最下层非终端结点的最小关键字代替结点中关键字key[i]。
函数名：void Remove(BTree&p, int i);
功能：从结点p 中删除key[i]。
函数名：void Restore(BTree&p, int i, int m, BTree&T); 功能：调整B 树。
函数名：voidDeleteBTree(BTree p, int i, int m, BTree&T); 功能：删除B 树T 上结点p 的关键字k 。
五、 程序测试
1、AnyviewCL 自由编程平台上测试结果 1）3阶B 树的测试：
此时B 树的结构为：
进行查找操作：
进行插入操作：
插入后B 树的结构为：
进行删除操作（直接删除关键字）：
删除关键字618后B 树的结构为：
此时对B 树进行打印操作：
继续进行删除操作：（删后结点与左兄弟合并）
删除关键字798后B 树的结构为：
继续进行删除操作：（直接删除关键字）
删除关键字796后B 树的结构为：
继续进行删除操作：（删后结点与右兄弟合并、父节点与左兄弟合并）
删除关键字580后B 树的结构为：
继续进行删除操作：（删后结点与左兄弟合并、父节点与右兄弟合并，树的高度减1）
删除关键字281后B 树的结构为：
进行B 树的销毁：
此时AnyviewCL 的演示区情况为：
2）5阶B 树的测试：
初始化B 树的结构后，B 树的结构为：
进行插入操作：
插入关键字580后B 树的结构为：
进行删除操作：（删后结点与右兄弟合并）
删除关键字21后B 树的结构为：
继续进行删除操作：（寻找后继结点并与之交换，删后向左兄弟借关键字）
删除关键字596后B 树的结构为：
进行打印B 树操作：
2、在Visual C++ 6.0平台测试： B 树设置界面：
进行B 树初始话操作：
进行打印B 树操作：
进行查找操作：
进行插入操作：
插入关键字588后的B 树结构为：
进行删除操作：
删除关键字532后的B 树结构为：
进行销毁B 树操作：
销毁后B 树为空，无法打印：
退出程序操作：
六、思考与小结
1、B 树的高度：
若N>=1，则对任意一棵包含N 个关键字、高度为h 、阶数为m 的B 树：
1）因为B 树中每个结点最多有m 棵子树，m-1个关键字，所以在一棵高度为h 的m 阶B 树中的关键字个数应满足：N=logm(N+1);
2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B 树的高度可达到最大，此时有h
2、复杂度：
每次查找共需访问O(logmN)个结点，由此可知，对存有N 个关键字的m 阶B 树的每次查找，耗时不超过O(logmN)。
七、总结和体会
本次设计主要在AnyviewCL 自由编程平台上进行编程，通过深入学习课本提供的查找与插入算法后，我很轻易地写出了构建的算法，再根据递归的知识完成了B 树的中序遍历算法和销毁算法。本次设计的难点在于B 树的调整算法，B 树在插入的过程中可能发生上溢，此时需要通过分裂结点来处理，在此过程中B 树可能出现长高。而在删除的过程中则可能发生下溢，此时需要分：借左兄弟、借右兄弟、与左兄弟合并、与右兄弟这四种调整方式来处理，并要处理合并后根结点为空的情况，在此过程中B 树可能出现高度降低。
在该平台的可视化调试功能的帮助严格测试了下各个基本操作的算法设计，改进算法中一些可能出现的错误，保证了代码的正确性。然后将代码移植到Visual C++ 6.0中，编译并运行后，初始化B 树时程序出现异常代码:c0000005，在Dubug 模式下找到原因是操作了未经初始化的对象，而代码本身在AnyviewCL 自由编程平台上是可以顺利运行的，后来经过对几个关键指针的初始化Bug 顺利排除。究其原因可能是AnyviewCL 平台在实现可视化的过程已经对所有运用到的指针都进行了初始化。
总而言之，在这次设计中我深入理解了B 树的各项基本操作，也很好地锻炼了自己的动手能力，收获匪浅。
八、程序关键源码
//BTree for Visual C++ 6.0
//By：2013级计算机科学与技术3班3113005867方典禹
//包含文件BTree.cpp 、Operation.h 、 BTree.cpp
Datastructure.h
//*******************定义数据类型***********************//
BTree.cpp
//*******************主函数***********************//
Operation.h
#include "Datastructure.h"
//******************************基本操作函数****************************// intSearchNode(BTree p, int k)
//在p->key[1..keynum]找p->key[i]key[i+1]，并返回i
{
int i = 1;
while(i keynum&& k > p->key[i]) i++;
return i;
}
voidSearchBTree(BTree t, int k, result &SearchBTree)
// 在m 阶B 树t 上查找关键码k ，返回(pt,i,tag)。
// 若查找成功，则特征值tag=1，指针pt 所指结点中第i 个关键码等于k ；否则，
// 特征值tag=0,等于k 的关键码记录应插入在指针pt 所指结点中第i 个和第i+1个关键码间 {
int i = 0, found = 0;
BTree p = t, q = NULL; // 初始，p 指向待查结点，q 指向p 的双亲
while(p != NULL && 0 == found)
{
i = SearchNode(p, k); // 在p->key[1..keynum]找p->key[i]key[i+1] if(i>0 && p->key[i] == k)
found = 1; // 找到待查关键字
else
{
q = p;
p = p->ptr[i-1];
}
}
if(1 == found) // 查找成功
{
SearchBTree ->pt = p;
SearchBTree -> i = i;
SearchBTree -> tag = 1;
}
else // 查找不成功，返回key 的插入位置i
{
SearchBTree ->pt = q;
SearchBTree -> i = i;
SearchBTree -> tag = 0;
}
}
void split(BTree&q, int s, BTree&ap)
// 将结点q 分裂成两个结点，前一半保留，后一半移入新生结点ap
{
int i, j, n = q ->keynum;
ap = (BTNode*)malloc(sizeof(BTNode)); // 生成新结点ap
ap ->ptr[0] = q ->ptr[s];
for(i = s + 1, j = 1; i
{
ap -> key[j] = q -> key[i];
ap ->ptr[j] = q ->ptr[i];
}
ap ->keynum = n - s;
ap -> parent = q -> parent;
for(i = 0; i
if(ap ->ptr[i])
ap ->ptr[i] -> parent = ap;
q ->keynum = s - 1; // q的前一半保留，修改keynum
}
voidnewroot(BTree&t, BTree p, int x, BTreeap)
// 生成新的根结点
{
t = (BTNode*)malloc(sizeof(BTNode));
t ->keynum = 1;
t ->ptr[0] = p;
t ->ptr[1] = ap;
t -> key[1] = x;
if(p!=NULL)
p -> parent = t;
if(ap!=NULL)
ap -> parent = t;
t -> parent = NULL; // 新根的双亲是空指针
}
void Insert(BTree&q, int i, int x, BTreeap)
{
intj,n = q ->keynum;
for(j = n; j >= i; j--)
{
q ->key[j+1] = q -> key[j];
q ->ptr[j+1] = q ->ptr[j];
}
q -> key[i] = x;
q ->ptr[i] = ap;
if(ap!=NULL)
ap -> parent = q;
q ->keynum++;
}
voidInsertBTree(BTree&t, int k, BTree q, int i, int m)
// 在B 树t 上结点*q的key[i]和key[i+1]之间插入关键字k
// 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T 仍是m 阶的B 树 {
int x, s;
BTreeap;
int finished = 0, neednewroot = 0;
if(NULL==q)
newroot(t, NULL, k, NULL);
else
{
x = k; ap = NULL;
while(0 == neednewroot&& 0 == finished)
{
Insert(q, i, x, ap); // key和ap 分别插到q->key[i+1]和q->ptr[i+1]
if(q->keynum
finished = 1; // 插入完成
else // 分裂结点q
{
s = (m+1)/2;
split(q, s, ap);
x = q -> key[s];
if(q -> parent)
{
q = q -> parent;
i = SearchNode(q, x); // 在双亲结点*q中查找x 的插入位置 }
elseneednewroot = 1;
}
}
if(1 == neednewroot) // t是空树或者根结点已分裂为结点q 和ap
newroot(t, q, x, ap); // 生成含信息(t,x,ap)的新的根结点root
}
}
void Successor(BTree&p, int i)
//由后继最下层非终端结点的最小关键字代替结点中关键字key[i]
{
BTNode *u;
while(NULL != u ->ptr[0]) //找出关键字的后继
{
u = u ->ptr[0];
}
p -> key[i] = u -> key[1];
p = u;
}
void Remove(BTree&p, int i)
//从结点p 中删除key[i]
{
intj,n = p ->keynum;
for(j = i; j
{
p -> key[j] = p -> key[j+1];
p ->ptr[j] = p ->ptr[j+1];
}
//free(p ->ptr[n]);
//p ->ptr[n] = NULL;
p ->keynum -- ;
}
void Restore(BTree&p, int i, int m, BTree&T)
//调整B 树
{
int j;
BTreeap = p -> parent;
BTreelc, rc, pr;
int finished = 0, r = 0;
while(0 == finished)
{
r = 0;
while(ap ->ptr[r] != p) //确定p 在ap 子树的位置
r++;
if(r == 0)
{
r++;
lc = NULL;
rc = ap ->ptr[r];
}
else if(r == ap ->keynum)
{
rc = NULL;
}
else
{
lc = ap ->ptr[r-1];
rc = ap ->ptr[r+1];
}
if(r > 0 &&lc != NULL && (lc ->keynum> (m - 1) / 2)) //向左兄弟借关键字
{
p ->keynum ++;
for(j = p ->keynum; j > 1; j--) //结点关键字右移
{
p -> key[j] = p -> key[j-1];
p ->ptr[j] = p ->ptr[j-1];
}
p -> key[1] = ap -> key[r]; //父亲插入到结点
p ->ptr[1] = p ->ptr[0];
p ->ptr[0] = lc ->ptr[lc ->keynum];
if(NULL != p ->ptr[0]) //修改p 中的子女的父结点为p
p ->ptr[0] -> parent = p;
ap -> key[r] = lc -> key[lc ->keynum]; //左兄弟上移到父亲位置
lc ->keynum --;
finished = 1;
break;
}
else if(ap ->keynum> r &&rc != NULL && (rc ->keynum> (m - 1) / 2)) //向右兄弟借关键字 {
p ->keynum ++;
p -> key[p ->keynum] = ap -> key[r]; //父亲插入到结点
p ->ptr[p ->keynum] = rc ->ptr[0];
if(NULL != p ->ptr[p ->keynum]) //修改p 中的子女的父结点为p
p ->ptr[p ->keynum] -> parent = p;
ap -> key[r] = rc -> key[1]; //右兄弟上移到父亲位置
rc ->ptr[0] = rc ->ptr[1];
for(j = 1; j keynum; j++) //右兄弟结点关键字左移
{
rc -> key[j] = rc -> key[j+1];
rc ->ptr[j] = rc ->ptr[j+1];
}
rc ->keynum --;
finished = 1;
break;
}
r = 0;
while(ap ->ptr[r] != p) //重新确定p 在ap 子树的位置
r++;
if(r > 0 && (ap ->ptr[r-1] ->keynum
{
lc = ap ->ptr[r - 1];
p ->keynum ++;
for(j = p ->keynum; j > 1; j-- ) //将p 结点关键字和指针右移1位 {
p -> key[j] = p -> key[j-1];
p ->ptr[j] = p ->ptr[j-1];
}
p -> key[1] = ap -> key[r]; //父结点的关键字与p 合并
p ->ptr[1] = p ->ptr[0]; //从左兄弟右移一个指针
ap ->ptr[r+1] = lc;
for(j = 1; j keynum + p ->keynum; j++) //将结点p 中关键字和指针移到p 左兄弟中
{
lc->key[lc ->keynum + j] = p -> key[j];
lc->ptr[lc ->keynum + j] = p ->ptr[j];
}
if(p ->ptr[0]) //修改p 中的子女的父结点为lc
{
for(j = 1; j keynum; j++)
p ->ptr[p ->keynum + j] -> parent = lc;
}
lc ->keynum = lc ->keynum + p ->keynum; //合并后关键字的个数
ap ->keynum--;
pr = p;
free(pr); //释放p 结点空间
pr = NULL;
p = lc;
}
else //与右兄弟合并
{
rc = ap ->ptr[r + 1];
if(r == 0)
r ++;
p ->keynum ++;
p -> key[p ->keynum] = ap -> key[r]; //父结点的关键字与p 合并 p ->ptr[p ->keynum] = rc ->ptr[0]; //从右兄弟左移一个指针
rc ->keynum = p ->keynum + rc ->keynum; //合并后关键字的个数
ap ->ptr[r-1] = rc;
for(j = 1; j keynum - p ->keynum); j++) //将p 右兄弟关键字和指针右移
{
rc->key[p ->keynum + j] = rc -> key[j];
rc->ptr[p ->keynum + j] = rc ->ptr[j];
}
for(j = 1; j keynum; j++) //将结点p 中关键字和指针移到p 右兄弟中
{
rc->key[j] = p -> key[j];
rc->ptr[j] = p ->ptr[j];
}
rc->ptr[0] = p ->ptr[0];
if(p ->ptr[0]) //修改p 中的子女的父结点为rc
{
for(j = 1; j keynum; j++)
p ->ptr[p ->keynum + j] -> parent = rc;
}
for(j = r; j keynum; j++) //将父结点中关键字和指针左移 {
ap -> key[j] = ap -> key[j + 1];
ap ->ptr[j] = ap ->ptr[j + 1];
}
ap ->keynum--; //父结点的关键字个数减1
pr = p;
free(pr); //释放p 结点空间
pr = NULL;
p = rc;
}
ap = ap -> parent;
if(p -> parent ->keynum>= (m-1)/2 || (NULL == ap&& p -> parent ->keynum>0))
finished = 1;
else if(NULL == ap) //若调整后出现空的根结点，则删除该根结点，树高减1 {
pr = T;
T = p; //根结点下移
free(pr);
pr = NULL;
finished = 1;
}
p = p -> parent;
}
}
voidDeleteBTree(BTree p, int i, int m, BTree&T)
// 删除B 树T 上结点p 的关键字k
if(p->ptr[i-1]!=NULL) // 若不是最下层非终端结点
{
Successor(p, i); // 由后继最下层非终端结点的最小关键字代替它 DeleteBTree(p, 1, m, T); // 变成删除最下层非终端结点中的最小关键字 }
else // 若是最下层非终端结点
{
Remove(p, i); // 从结点p 中删除key[i]
if(p->keynum
Restore(p, i, m, T); // 调整B 树
}
}
//中序遍历B 树
voidPrintBTree(BTree t)
{
int i = 1;
if(NULL != t)
{
while(i keynum)
{
PrintBTree(t ->ptr[i-1]);
printf("%d ", t -> key[i]);
i++;
}
PrintBTree(t ->ptr[i-1]);
}
}
//销毁B 树
voidDestroyBTree(BTree t)
{
int i = 1;
if(NULL != t)
{
while(i keynum)
{
DestroyBTree(t ->ptr[i-1]);
free(t ->ptr[i-1]);
i++;
}
DestroyBTree(t ->ptr[i-1]);
}
//初始化B 树
voidCreatBTree(BTree&T, int n, int m)
{
inti,j;
result p = NULL;
p = (restype *)malloc(sizeof(restype));
//srand( (unsigned)time( NULL ) ); //初始化随机数 if(0 == n)
printf("初始化成功，该B 树为空树。\n");
else
{
for(j = 0; j
{
i = rand()%1000;
SearchBTree(T, i, p); //查找插入位置
InsertBTree(T, i, p->pt, p->i, m); //进行插入
}
printf("初始化成功!\n");
}
}
intmenu_select() //选择菜单
{
int i;
printf("********************* B 树 **********************\n"); printf("*******************menu select********************\n"); printf(" 1. 初始化B 树 \n");
printf(" 2. 查找元素 \n");
printf(" 3. 插入元素 \n");
printf(" 4. 删除元素 \n");
printf(" 5. 打印B 树 \n");
printf(" 6. 销毁B 树 \n");
printf(" 0. 退出程序 \n");
printf("**************************************************\n"); printf("***********By:2013级计算机科学与技术3班***********\n"); printf("*************** 3113005867 方典禹 ***************\n"); printf("**************************************************\n"); do
{
printf("\n\t请输入操作B 树方法：\n");
scanf("%d",&i);
}while(i 6); //此处为判断输入
return i; }