B树专业课程设计专业资料.doc

课程设计成果

学院： 计算机工程学院 班 级：
学生姓名： 学 号：
设计地点（单位）
设计题目： B-树
完毕日期： 年 月 日

指引教师评语：

成绩(五级记分制)：
教师签名：

目 录
1 需求分析 1
1.1 系统目的 1
1.2 主体功能 1
1.3 开发环境 1
2概要设计 1
2.1 功能模块划分 1
2.2 系统流程图 2
3 详细设计 3
3.1 数据构造 3
3.2 模块设计 4
4 测试 7
4.1测试数据 7
4.2测试成果 7
5 总结 10
参照文献 11
附录 源程序代码 12

1 需求分析
1.1 系统目的
完毕B-树创立、查找、插入和删除。
1.2 主体功能
B-Trees是一类满足特殊条件M路查找树，它满足如下两个条件M路查找树：
1.所有叶节点高度相似。
2.除根之外所有节点都是半满，即该节点包括M/2或更多值。
3.树中每个节点都至多有M棵树。
4.所有叶子节点都出当前同一层，并且不带信息。
5.所有非终端节点中包括下列信息：
(n,A[0],K[1],A[1],K[2],A[2]K[3],A[3]…….K[n],A[n])
其中：K[i]为核心字，且K[i]<K[i+1];A[i]为指向自树指针，且A[i-1]所指子树中所有节点核心字均不大于K[i],A[n]所指子树中所有节点核心字均不不大于K[n]，n为核心字个数。
1.设计并实现B-Trees数据构造，包括其上基本操作，如节点插入和删除等。
2.实当前B-trees树上查找操作。
3.设计良好运营界面，可以实现重复操作。
1.3 开发环境
开发系统：Windows 系统，解决器规定最低奔腾解决器，内存32m，建议在i5解决器，128m内存配备下调试。
编译集成软件：Devc++开发软件。
Devc++是一种强大C/C++软件开发工具，操作简朴，使用非常广泛，称为诸多程序员首选开发工具。
2概要设计
2.1 功能模块划分
主函数即main()函数，重要实现B-Trees建立，建立一棵满足规定4节B-Trres树。
菜单简介函数即meau（）函数，重要涉及简介各个功能实现途径，并给操作者提供个操作界面。
插入元素函数即insertbtree(b)函数，重要有顾客通过界面输入要插入元素，一方面判断要插入元素与否已在B-Trees中，若不在则插入之。
删除函数即deletetree(b)函数，一方面判断要删除元素与否在B-Trees中若在该B-Trees中则删除。
查找函数即searchbtree(b)函数，由顾客通过界面输入一种元素，查找该元素与否在该B-Trees中，若在就输出它在节点位置。

图2.1 主函数流程图
2.2 系统流程图
B-树主程序流程如图2.2所示

图2.2 主程序流程图

B-树主程序流程如图2.3所示

图2.3 主程序流程图
3 详细设计
3.1 数据构造
B-树数据类型：
typedef struct BTNode
{
int keynum；//结点中核心字个数，即结点大小
struct BTNode *parent；//指向双亲指针
int key[m+1]；//核心字向量
struct BTNode *ptr[m+1]；//子树指针向量
}BTNode
3.2 模块设计
B-树插入新元素模块如图3.2所示。

图3.2 B-树插入元素函数流程图

B-树删除元素模块如图3.3所示。

图3.3 B-树删除元素函数流程图

B-树查找模块如图3.4所示。

图3.4 B-树查找元素模块流程图
B-树查找模块如图3.4所示。

图3.5 B-树查找元素模块流程图
4 测试
4.1测试数据
图表 4-1
序号
数据内容
阐明
显示截图
1
3
查找，要查元素在B-树中
图 4.2
2
5
查找，要查元素不在B-树中
图 4.3
3
32
插入，插入元素不在B树中
图 4.4
4
42
插入，插入元素在B-树中
图 4.5
5
61
删除，删除元素在B-树中
图 4.6
6
51
删除，删除元素不在B-树中
图 4.7
4.2测试成果
界面主菜单运营成果如图4.1所示。

图4.1 主界面运营
查询B-树中元素运营成果分两种也许一是要查元素在B-树中，另一种是不在。
要查元素在B-树中运营成果如图4.2所示。

图4.2 查找B-树已有元素
要查不在元素在B-树中运营成果如图4.3所示。

图4.3 查找B-树中没有元素
插入B-树中元素运营成果分两种也许一是要查元素在B-树中，另一种是不在。
要插入元素在B-树中运营成果如图4.4所示。

图4.4 插入B-树已有元素
要插入元素不在B-树中运营成果如图4.5所示。

图4.5 插入B-树中没有元素
插入B-树中元素运营成果分两种也许一是要查元素在B-树中，另一种是不在。
要删除元素在B-树中运营成果如图4.6所示。

图4.6 删除B-树中已有元素
要删除元素不在B-树中运营成果如图4.7所示。

图4.7 删除B-树中没有元素
退出B-树中元素运营成果如图4.8所示。

图4.8 退出运营主界面
5 总结
历时两周课程设计终于结束了，对于课程设计：
一方面，关于程序方面，我发现虽然对设计思路有了眉目，懂得了所要用到B-树某些知识，但是要把这些写成函数代码，其实还是一件非常不容易事情。再加上要完善设计思路，构造整个程序框架在内，都是一件工作量非常大工作。
幸好，有诸多资料可以在网路上搜到。因此课程设计第一天，咱们收集了诸多关于B-树资料，涉及几种不同思路程序代码，以及程序流程。然后咱们工作就变成：尽量看懂并整顿这些代码，然后再其基本上筛选需要功能，按照自己意愿来修改与完善。
在操作界面人性化上，我倒尽量做得很完善，无论从美观角度还是以便清晰操作，都实行了非常人性化方式。由于普通清晰程序人，懂得怎么操作以及该输入什么，而不清晰人却有很大也许在细节方面输入错误导致程序运营失败，或是主线不懂得应当怎么输入。因此，尽量人性化设计是非常有必要，让不懂程序人也可以对的操作运营。
在调试程序过程中，遇到了许多常识性问题，通过不断调试、改进，最后使程序可以运营，并且得到对的运营成果。在这个过程中，可以不断地发现问题，并且自己独立去解决多遇到问题，这是课程设计过程中所不可缺少精神。
最后，做再次一下总结。程序方面仍有为解决问题，但愿即便课设之后也可以努力将问题解决掉。然后B-树算法中，有些懂得怎么做却很难清晰回答出来问题，但愿可以再好好查找一下有关资料，将知识系统化、理论化、规范化。

参照文献
[1]顾泽元，刘文强编.数据构造.北京：北京航空航天大学出版社，.
[2]李素若，陈万华，游明坤编.数据构造（C语言描述），中华人民共和国水利水电出版社，.
[3]李素若，陈万华，游明坤编.数据构造习题解答及上机指引，中华人民共和国水利水电出版社，.
[4]谭浩强编.C语言设计.清华大学出版社，.

附录 源程序代码
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define m 4 //B-树阶，设定为4
#define max 32767
typedef struct BTNode
{
int keynum； //结点中核心字个数，即结点大小
struct BTNode *parent； //指向双亲指针
int key[m+1]； //核心字向量
struct BTNode *ptr[m+1]; //子树指针向量
}BTNode,*BTree； //定义B-树节点构造
int data[20]={3,24,45,27,53,90,50,61,70,100,12,37,85,105,108,113,121,124,138,135}；
BTree T,R,R1；
int rag；
BTree searchtree(int k) //查找建树时要插入元素位置
{
int j；
BTree p1,q1；
p1=T；
while(p1)
{
for(j=1;j<m;j++)
if(p1->key[j]>k)
break；
q1=p1;
p1=p1->ptr[j-1]；
}
rag=j-1；
return q1；
}
void search(BTree p2,int a)
{
int j；
for(j=1;j<m;j++)
if(p2->key[j]>a)
break；
rag=j-1；
}
void zimeau() //简介菜单
{

printf("\t\t\n")；
printf("\t\t菜单简介\n")；
printf("\t\t\n")；
printf("\t\t1.查询结点信息\n")；
printf("\t\t2.插入新结点\n")；
printf("\t\t3.删除结点\n")；
printf("\t\t4.退出\n")；
printf("\t\t\n")；
}
int searchbtree(int k) //查询要查元素在树中，若树中有该元素则打印否则打印阐明无
{
int i,found=0；
BTree p；
p=T；
while((!found)&&(p->ptr[0]!=NULL))
{
for(i=1;i<m;i++)
if(k<=p->key[i])
break；
if(p->key[i]==k)
found=1；
else
p=p->ptr[i-1]；
}
if(p->ptr[0]==NULL)
for(i=1;i<m;i++)
if(k<=p->key[i])
break；
if(p->key[i]==k)
found=1；
if(found==0)
printf("\t\t此元素不在该B-树中\n");
else
{
printf("\t\t此元素元素在该B-树中\n")；
printf("\t\t该元素是B-树中结点第%d元素\n",i)；
}
return found；
}
void insertbtree(int x) //插入元素函数
{
int j,finished,s；
BTree q,p；
finished=0；
q=searchtree(x)； //查找要插入元素在B-树中位置
while(!finished)
{
if(q->keynum==0) //当要插入元素所在结点是根节点,且为新申请根结点
{
q->ptr[0]=p;q->ptr[1]=R;q->key[1]=x；
q->keynum++;p->parent=q;R->parent=q；
}
else if((q->keynum!=0)&&(q->ptr[0]!=NULL)) //当要插入元素所在结点是中间结点x
{
for(j=3;j>rag;j--)
{
q->key[j+1]=q->key[j];q->ptr[j+1]=q->ptr[j]；

}
q->ptr[j+1]=R;R->parent=q;q->key[j+1]=x;q->keynum++；
}
else //当插入元素所在结点是最下层结点时
{
for(j=3;j>rag;j--)
q->key[j+1]=q->key[j]；
q->key[j+1]=x;q->keynum++；
}
finished=0；
if(q->keynum<m) //当插入节点后，结点核心字数不大于m时,插入新元素完毕
finished=1；
else //当插入新结点后，结点核心字数不不大于m时将结点分裂
{
s=m/2+1;x=q->key[s];q->key[s]=max;q->keynum=s-1；
R=(BTNode*)malloc(sizeof(BTNode))； //新申请一种结点来存储分裂另一某些数据
R->key[1]=q->key[s+1]；
for(j=2;j<=m;j++)
{
R->key[j]=max;R->ptr[j]=NULL；
}
R->ptr[0]=q->ptr[s];R->ptr[1]=q->ptr[s+1]；
R->keynum=1;q->key[s+1]=max;p=q;q=q->parent；
if(!q)
{
R1=(BTNode*)malloc(sizeof(BTNode))； //新申请一种节点作为根节点
T=q=R1；q->keynum=0;q->parent=NULL；
for(j=1;j<=m;j++)
q->key[j]=max；
for(j=0;j<=m;j++)
q->ptr[j]=NULL；
}
else
search(q,x)； //在一种结点中查找要插入元素位置
}
}
}
void deletetree1(BTree q,int j) //当要删除节点是终端结点,j是要删除元素是节点地几种元素
{
int i,h；
BTree p,q0,q1；
p=q->parent；
for(h=0;h<m;h++)
if(p->ptr[h]==q)
break；
if(h==0)
q1=p->ptr[h+1]；
else
{
q0=p->ptr[h-1];q1=p->ptr[h+1]；
}
if(q->keynum>=m/2) //当节点数目不不大于m/2
for(i=j;i<m;i++)
q->key[i]=q->key[i+1]；
else
if((q->keynum<m/2)&&(q0->keynum>=2||q1->keynum>=2)) //当结点数目少于m/2但其左兄弟或右兄弟结点数目不不大于时
{
if(q1->keynum>=m/2) //右兄弟时
{
q->key[j]=p->key[h];p->key[h]=q1->key[0]；
for(i=0;i<m;i++)
q1->key[i]=q1->key[i+1]；
q1->keynum--；
}
else //左兄弟时
{
q->key[j]=p->key[h];p->key[h]=q0->key[q0->keynum]；
q0->key[q0->keynum]=q0->key[q0->keynum+1];q0->keynum--；
}

}
else //当结点数目少于m/2且其左兄弟和右兄弟结点数目不大于时
{
if(h==0) //当该节点只有有兄弟时
{
q->key[1]=p->key[1];q->key[2]=q1->key[1];q->keynum=2;free(q1)；
for(i=1;i<m;i++)
{
p->key[i]=p->key[i+1];p->key[i]=p->key[i+1]；
}
p->keynum--；
}
else //当该节点有左兄弟时
{
q->key[1]=p->key[h];q->key[2]=q0->key[1];q->keynum=2;free(q0)；
for(i=1;i<m;i++)
{
p->key[i]=p->key[i+1]；
p->ptr[i]=p->ptr[i+1]；
}
p->keynum--；
}
}
}
void deletetree2(BTree q,int j) //要插入节点是非终端结点
{
BTree p；
p=q；
while(q->ptr[0]) //找终端结点
{
q=q->ptr[j]；
if(q->ptr[0]!=NULL)
q=q->ptr[0]；
}
q=q->parent;p->key[j]=q->key[1]；
deletetree1(q,1)；
}
void deletetree(int k)
{
int i,found=0；
BTree p；
p=T；
while((!found)&&(p->ptr[0]!=NULL)) //找到要插入节点位置
{

for(i=1;i<m;i++)
if(k<=p->key[i])
break；
if(p->key[i]==k)
found=1；
else
p=p->ptr[i-1]；
}
if(p->ptr[0]==NULL)
for(i=1;i<m;i++)
if(k<=p->key[i]) //找到要插入节点位置
break；
if(p->ptr[0]==NULL)
deletetree1(p,i)； //当要删除元素是终端结点
else
deletetree2(p,i); //当插入节点不是终端结点
}
int searchbtree1(int k) //查询要删除元素与否在树中
{
int i,found=0；
BTree p；
p=T；
while((!found)&&(p->ptr[0]!=NULL))
{
for(i=1;i<m;i++)
if(k<=p->key[i])
break；
if(p->key[i]==k)
found=1；
else
p=p->ptr[i-1]；
}
if(p->ptr[0]==NULL)
for(i=1;i<m;i++)
if(k<=p->key[i])
break；
if(p->key[i]==k)
found=1； //返回值，1代表该元素在B-树中可以删除否则无法删除
return found；
}
int rumeau() //提供应读者自己选取
{

int c；
printf("\t\t\t\t请输入您选取：")；
scanf("%d",&c)；
return c；
}
void meau() //菜单选项函数
{
int a,b,rate；
printf("\t\t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n",3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)；
do{
zimeau()；
printf("\t\t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n",3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)；
a=rumeau()； //子菜单
switch(a)
{
case 1:system("cls")；
printf("\t\t请输入要查找元素:")；
scanf("%d",&b)；
rate=searchbtree(b)； //在B-树中查找元素函数
break；
case 2:system("cls")；
printf("\t\t请输入要插入元素:")；
scanf("%d",&b)；
rate=searchbtree(b)； //查询要插入元素与否在该B-树中
if(rate==0)
{
printf("\t\t该元素不在此B-树中，故可插入之")；
insertbtree(b)； //插入新元素函数
}
else
printf("\t\t该元素已在B-树中，不需要再插入\n")；
break；
case 3:system("cls")；
printf("\t\t请输入要删除元素:")；
scanf("%d",&b)；
rate=searchbtree1(b)；
if(rate==0)
printf("\t\t由于该元素不在此B-树中，故无法删除\n")；
else
{
printf("\t\t该元素在此B-树中，可删除\n")；
deletetree(b)； //删除B-树中元素调用函数
}
break；
}
}while(a!=4)；
}
void main()
{
int x,i,finished,s,j；
BTree q,p；
system("color 1B")； //背景颜色显示函数
T=(BTNode*)malloc(sizeof(BTNode));T->keynum=0；
for(i=0;i<3;i++)
{
T->key[i+1]=data[i];T->keynum++；
}
T->key[4]=max；
for(i=0;i<5;i++)
T->ptr[i]=NULL；
T->parent=NULL；
for(i=3;i<20;i++)
{
x=data[i];finished=0;q=searchtree(x)； //查找要插入元素在B-树中位置
while(!finished)
{
if(q->keynum==0) //当要插入元素所在结点是根节点,且为新申请根结点
{
q->ptr[0]=p;q->ptr[1]=R；
q->key[1]=x;q->keynum++;p->parent=q;R->parent=q；
}
else
if((q->keynum!=0)&&(q->ptr[0]!=NULL)) //当要插入元素所在结点是中间结点x
{
for(j=3;j>rag;j--)
{q->key[j+1]=q->key[j];q->ptr[j+1]=q->ptr[j];}
q->ptr[j+1]=R;R->parent=q;q->key[j+1]=x;q->keynum++；
}
else //当插入元素所在结点是最下层结点时
{
for(j=3;j>rag;j--)
q->key[j+1]=q->key[j]；
q->key[j+1]=x;q->keynum++；
}
finished=0；
if(q->keynum<m) //当插入节点后，结点核心字数不大于m时,插入新元素完毕
finished=1；
else //当插入新结点后，结点核心字数不不大于m时将结点分裂
{
s=m/2+1;x=q->key[s];q->key[s]=max;q->keynum=s-1；
R=(BTNode*)malloc(sizeof(BTNode))； //新申请一种结点来存储分裂另一某些数据
R->key[1]=q->key[s+1];
for(j=2;j<=m;j++)
{R->key[j]=max;R->ptr[j]=NULL;}
R->ptr[0]=q->ptr[s];R->ptr[1]=q->ptr[s+1]；
if(R->ptr[0]!=NULL)
{R->ptr[0]->parent=R;R->ptr[1]->parent=R;}
q->ptr[s]=NULL;q->ptr[s+1]=NULL;R->keynum=1；
q->key[s+1]=max;p=q;q=q->parent；
if(!q)
{
R1=(BTNode*)malloc(sizeof(BTNode))； //新申请一种节点作为根节点
T=q=R1；q->keynum=0;q->parent=NULL；
for(j=1;j<=m;j++)
q->key[j]=max；
for(j=0;j<=m;j++)
q->ptr[j]=NULL；
}
else
search(q,x)； //在一种结点中查找要插入元素位置
}
}
}
meau()； //主菜单
}