20##—20##学年第一学期
实践教学
课程名称:数据结构课程实践
指导教师:钱峰
专业班级:20##级 软件工程4班
教学部门:计算机学院
北京理工大学珠海学院
课程设计说明书
20##—2013 学年第一学期
题 目: B树与B+树及其操作
学 院: 计算机学院
专业班级: 软工四班
学 号: 110202041028
学生姓名: 宁 琳 琳
指导教师: 钱 峰
成 绩:
时 间:
20##年 10 月 16 日
课程设计成绩评定表
B树与B+树及其操作
摘 要
通过学习B树的相关知识了解B树的性质以及B树的构建、查找、插入、删除等操作,能用C或C++语言写出相关代码,并编译演示成功。
关键词:B树的构建、查找、插入、删除 结点分裂
目 录
摘要……………………………………………………………4
概要设计………………………………………………………6
1.数据结构设计……………………………………………6
2.算法设计…………………………………………………7
3.ADT描述…………………………………………………7
4.功能模块分析……………………………………………7
详细设计………………………………………………………9
1. 主要算法流程图………………………………………9
2. 数据存储结构设计……………………………………12
3. 界面设计………………………………………………13
参考文献………………………………………………………14
心得体会………………………………………………………15
教师评语………………………………………………………16
计算机学院课程设计答辩记录表……………………………17
附录……………………………………………………………18
概要设计
1.数据结构设计
B树又称为多路平衡查找树。
一棵度为m的B树称为m阶B树。一个结点有k个孩子时,必有k-1个关键字才能将子树中所有关键字划分为k个子集。B树中所有结点的孩子结点最大值称为B树的阶,通常用m表示。从查找效率考虑,一般要求m≥3。一棵m阶的B树或者是一棵空树,或者是满足下列要求的m叉树:
(1)根结点或者为叶子,或者至少有两棵子树,至多有m棵子树。
(2)除根结点外,所有非终端结点至少有ceil(m/2)棵子树,至多有m棵子树。
(3)所有叶子结点都在树的同一层上。
(4)每个结点的结构为:
(n,A0,K1,A1,K2,A2,…,Kn,An)
其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)。
Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。An所指子树中所有结点的关键字均大于Kn。
n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。
一般来说B树的结构如下所示:
2.算法设计
先定义一颗空树,题目给出的数据是{53,75,139,49,145,36,101},然后不断地调用插入算法来插入数据,完成构建。查找时,调用SearchBTree()函数来查找关键字;插入时,调用InsertBTree()函数来插入关键字,若插入后结点中关键字个数不符合要求,需用split()函数来调整。
3.ADT描述
ADT List{
数据对象:D:{ai|ai∈ElemSet,i=1,2,3, ……,n,n≥0}
数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2, ……,n}
基本操作:
CreatBTree(&T);
//构建一颗B树T
InsertBTree(T,K,q,i);
//在B树T上结点*q的key[i]和key[i+1]之间插入关键字K
SearchBTree(T,K);
//在B树T上查找关键字K
}ADT List;
4.功能模块分析
1、SearchBTree()函数:B树的查找过程:根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程:
若比结点的第一个关键字小,则查找在该结点第一个指针指向的结点进行;若等于结点中某个关键字,则查找成功;若在两个关键字之间,则查找在它们之间的指针指向的结点进行;若比该结点所有关键字大,则查找在该结点最后一个指针指向的结点进行;若查找已经到达某个叶结点,则说明给定值对应的数据记录不存在,查找失败。
2、Insert()函数:将所给关键字插入到正确节点的正确位置。代入指向所给关键字应该插入节点的指针、所给关键字、关键字应该插入的位置,然后再将该关键字插入到节点的正确位置上,节点关键字个数加1,返回指向该节点的指针q。
3、InsertBTree()函数:插入的过程分两步完成:
(1)利用前述的B-树的查找算法查找关键字的插入位置。若找到,则说明该关键字已经存在,直接返回。否则查找操作必失败于某个最低层的非终端结点上。
(2)判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足,则说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上。若不满足,说明该结点己没有空位置,需要把结点分裂成两个。
分裂的方法是:生成一新结点。把原结点上的关键字和k按升序排序后,从中间位置把关键字(不包括中间位置的关键字)分成两部分。左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过(m-1),则要再分裂,再往上插。直至这个过程传到根结点为止。
详细设计
1.主要算法流程图
SearchBTree()函数:
Insert()函数:
InsertBTree()函数:
2.数据存储设计
B树是一种平衡的多路查找树,存储结构可定义为:
3.界面设计
参考文献
[1]严蔚敏:《数据结构(C语言版)》[M],清华大学出版社20##年版,第238页。
[2]Thomas H.Cormen: 《算法导论 第二版》[M],机械工程出版社,第263页。
心得体会
这学期的课程设计我选了个最难的课题“B树与B+树及其操作”,正好也是老师没有讲过的,所以说自己在这个课题上废了很大劲,因为是没有学过的,所以自己就到处找相关资料来自学B树,有上网找相关课件,也有找别的书籍来学习B树的知识,大概用了四周的时间来学习,最后还是只弄懂了B树的相关知识,也许是自己能力有限吧,B树也只搞懂了概念,以及插入,查找这两个操作,删除的代码没有写出来,B+树压根就没看懂,所以也没有写代码,大部分时间全用在了B树上。虽然这个课题只完成了一部分,但是自己也尽力了,毕竟自己能力有限,老师没有讲过,全靠自学来的,所以自己也问心无愧了。
通过这学期的课程设计我明白了自己还有很多要学习的东西,不是说只学懂了课本上的知识就行了,还有很多老师没有讲到的知识也需要自己去学习,学无止境,不能为了考试而学习,要为了求知而学习。
教师评语
计算机学院课程设计答辩记录表
附录
B树与B+树及其操作源代码:
#include <stdio.h>
#include <malloc.h>
#include <iostream.h>
#define m 3
#define n 7
typedef struct BTNode
{
int keynum;
struct BTNode *parent;
int key[m+1];
struct BTNode *ptr[m+1];
}BTNode,*BTree;
typedef struct
{
BTNode *pt;
int i;
int tag;
}Result;
//在结点中查找关键字
int SearchNode(BTree p,int k)
{
int i=1;
while(i<=p->keynum)
{
if(k<p->key[i])
return i-1;
else
if(k==p->key[i])
return -1;
else i++;
}
return i-1;
}
//在B树中查找关键字k
Result SearchBTree(BTree t,int k)//t为B树根节点
{
BTree p=t,q=NULL;
int found=0;
int i=0;
Result result;
while(p&&!found)
{
i=SearchNode(p,k);
if(i==-1)
{
result.pt=p;
result.i=i;
result.tag=1;
return result;
}
while(p->ptr[i])
{
p=p->ptr[i];
i=SearchNode(p,k);
}
if(i>0&&p->key[i]==k)
found=1;
else
{
q=p;
p=p->ptr[i];
}
}
if(found)
{
result.pt=p;
result.i=i;
result.tag=1;
}
else
{
result.pt=q;
result.i=i;
result.tag=0;
}
return result;
}
//将关键字插入节点
BTree Insert(BTree q,int i,int x,BTree ap)
{
// insert the key X between the key[i] and key[i+1]
// at the pointer node q
int j;
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;
if(ap)
ap->parent=q;
q->keynum++;
return q;
}
//分裂节点
BTree split(BTree q,int s,BTree ap)
{
//move key[s+1...m],p->ptr[s...m] int the new pointer *ap
int i,j;
ap=(BTree)malloc(sizeof(BTNode));
ap->ptr[0]=q->ptr[s];
for(i=s+1,j=1;i<=q->keynum;i++,j++)
{
ap->key[j]=q->key[i];
ap->ptr[j]=q->ptr[i];
}
ap->keynum=q->keynum-s;
ap->parent=q->parent;
for(i=0;i<=q->keynum-s;i++)
if(ap->ptr[i])
ap->ptr[i]->parent=ap;
q->key[q->keynum]=0;
q->keynum=s-1;
return ap;
}
//建立新的节点
BTree NewRoot(BTree T,BTree p,int x,BTree ap)
{
T=(BTree)malloc(sizeof(BTNode));
T->keynum=1;
T->ptr[0]=p;
T->ptr[1]=ap;
T->key[1]=x;
if(p)
p->parent=T;
if(ap)
ap->parent=T;
T->parent=NULL;
return T;
}
//建立B-树
BTree InsertBTree(BTree T,int K,BTree q,int i)
{
// 在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K。
// 若引起结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B树。
BTree ap;
int finished, needNewRoot, s;
int x;
if(!q) // T是空树(参数q初值为NULL)
T=NewRoot(T,NULL,K,NULL); // 生成仅含关键字K的根结点*T
else
{
x=K; ap=NULL; finished=needNewRoot=0;
while(!needNewRoot&&!finished)
{
q=Insert(q,i,x,ap); // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1]
if(q->keynum< m)
finished = 1; // 插入完成
else
{ // 分裂结点*q
// 将q->key[s+1..m], q->ptr[s..m]和
// q->recptr[s+1..m]移入新结点*ap
s=(m+1)/2;
ap=split(q,s,ap);
x=q->key[s];
q->key[s]=0;
if(q->parent)
{ // 在双亲结点*q中查找x的插入位置
q=q->parent;
i=SearchNode(q, x);
}
else needNewRoot=1;
} // else
} // while
if(needNewRoot) // 根结点已分裂为结点*q和*ap
T=NewRoot(T,q,x,ap); // 生成新根结点*T,q和ap为子树指针
}
return T;
} // InsertBTree
//搜索指定节点
int found(BTree t,int k)
{
int i=1;
BTree p=t;
while(i<=p->keynum)
{
if(k==p->key[i])
return i;
else
if(k<p->key[i])
{
if(p->ptr[i-1])
{
p=p->ptr[i-1];
i=found(p,k);
return i;
}
else
return -1;
}
else
i++;
}
if(p->ptr[i-1])
{
p=p->ptr[i-1];
i=found(p,k);
return i;
}
return -1;
}
//先序遍历输出
void inorder(BTree t)
{
int i;
if(t!=NULL)
{
printf("( ");
for(i=1;i<=t->keynum;i++)
printf("%d ",t->key[i]);
printf(") ");
for(i=0;i<=t->keynum;i++)
if(t->ptr[i])
inorder(t->ptr[i]);
else i++;
}
}
int main()
{
cout<<"====================================================================="<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"******************************插入页面*******************************"<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"====================================================================="<<endl;
printf("\n");
printf("\n");
printf("\n");
BTree root=NULL;
Result result;
int i,x,array[n];
char ch[5];
printf("输入关键字序列\n");
for(i=0;i<n;i++)
{
printf("输入第%d个数据:\n",i+1);
scanf("%d",&array[i]);
}
i=0;
while(i<n)
{
result=SearchBTree(root,array[i]);//寻找关键字在B树中应该插入的位置
if(result.i==-1)
i++;
else
{
printf("将第%d个关键字 %d 插入B-树中;\n",i+1,array[i]);
root=InsertBTree(root,array[i],result.pt,result.i); //插入结点
i++;
}
}
printf("插入后的B树如下:\n");
inorder(root); //先序遍历
printf("\n");
printf("\n");
printf("\n");
cout<<"====================================================================="<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"******************************查找页面*******************************"<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"****************************** *******************************"<<endl;
cout<<"====================================================================="<<endl;
printf("\n");
printf("\n");
do
{
printf("请输入要查找的关键字:\n");
scanf("%d",&x);
i=found(root,x);
if(i!=-1)
printf("%d在节点中的序号---------[%d]\n",x,i);
if(i==-1)
printf("不能查找到关键字\n");
printf("是否继续查询?“是”请输入:1 “否”请输入:0\n");
scanf("%s",ch);
}while (ch[0]=='1');
}