数据结构课程设计
实习报告
题 目:
学 号:
姓 名:
年 级:
学 院:
专 业:
完成日期:
授课教师:
1.题目
B树的表示及基本操作
2.要求
参考书中的示例代码,以整数表示每个记录的关键字.为简单起见,每个记录可以只包含一个关键字(即其他的字段可以不定义).
从空树开始,依次输入各关键字,建立相应的B树.
并实现B树中关键字的插入及删除.
同时将树型显示在屏幕上.全部关键字插入完毕时显示树型,之后每完成一次插入或删除操作后也显示当前的树型.
假设B树中不存在重复的关键字.
程序运行时,当要输入数据时必须在屏幕上给出输入的格式要求(中英文均可).当有输出显示时,也需要将输出的内容做必要的解释.
3.程序实现
3.1程序运行及编译环境
Windows操作系统,VC++6.0
3.2程序描述
程序通过B树的存储结构,实现了B树的构造,显示,关键字的插入删除等基本索引功能.
程序工程内共包括B_Tree.h,B_Tree.cpp,B_TreeMain.cpp三个文件.
B_Tree.h:定义了B_树的结点类型,通过常量给出B_树的阶树
B_Tree.cpp:B_树的初始化程序void InitMBTree(MBNode *& MT)
B_树是否为空的控制程序bool MBTreeEmpty(MBNode * MT)
B_树关键字的插入程序void InsertMBTree(MBNode*& MT,KeyType K)(查找插入函数void FindInsert(MBNode* mt,KeyType K,MBNode*& Tp,int& Pos)作为插入函数功能的一部分单独封装)
B_树关键字的删除程序bool DeleteMBTree(MBNode*&MT,KeyType K)(查找删除函数void FindDelete(MBNode* mt,KeyType K,MBNode *& Tp)作为删除函数功能的一部分单独封装)
B_树的关键字遍历输出函数(中序遍历):void TravelMBTree(MBNode* MT)
B_树的的清除函数:void ClearMBTree(MBNode *& MT)
B_树的树形显示函数(广度优先遍历):void DisplayMBTree(MBNode * MT)
B_TreeMain.cpp:与用户交互的主程序
3.3实现功能
介绍该程序应具有的功能,可采用IPO图(即输入一处理一输出图)的形式.
说明:如果该程序只有单一功能时可以直接描述其输入项,输出项等等各个部分,否则按照各个子功能模块分别介绍.
3.3.1子功能模块1
实现功能:
向B_树中插入新结点,并调整树形
程序代码:
void FindInsert(MBNode* mt,KeyType K,MBNode*& Tp,int& Pos)
{
int i;
MBNode * p;
//查找K应该插入的结点和该结点中的下标位置
while(mt!=NULL){
i=1;
while(K>mt->key[i]) i++;
if(K==mt->key[i]){Tp=NULL;return;}//关键字已经存在
else {
p=mt;
mt=mt->ptr[i-1];
}
}
//把K应插入的结点指针赋给Tp,下标位置赋给Pos
Tp=p;Pos=i;
}
//向树根指针为MT的B树插入关键字
void InsertMBTree(MBNode*& MT,KeyType K)
{
//当B树为空时的处理情况
if(MT==NULL){
MT=new MBNode;
MT->keynum=1;
MT->parent=NULL;
MT->key[1]=K;
MT->key[2]=MAXKEY;
MT->ptr[0]=MT->ptr[1]=NULL;
return;
}
MBNode *tp;int pos;
//从B树上查找插入位置
FindInsert(MT,K,tp,pos);
//关键字已存在,无需插入
if(tp==NULL){
cout<<"关键字"<
for(i=n;i>=pos;i--){
tp->key[i+1]=tp->key[i];
tp->ptr[i+1]=tp->ptr[i];
}
//把一个插入关键字放入tp结点的pos下标位置
tp->key[pos]=K;
tp->ptr[pos]=ap;
//使p结点的关键字的个数增1
tp->keynum++;
//若插入后结点中关键字个数超过所允许的最大值,则完成插入
if(n+1key[n+2]=MAXKEY;
return;
}
//计算出m/2的向上取整值
int j;
j=int(ceil(double(m)/2));
//建立新分裂的结点,该结点含有m-j个关键字
ap=new MBNode;
ap->keynum=m-j; ap->parent=tp->parent;
//复制关键字和记录位置
for(i=1;ikeynum;i++){
ap->key[i]=tp->key[j+i];
}
//复制指针
for(i=0;ikeynum;i++){
ap->ptr[i]=tp->ptr[j+i];
if(ap->ptr[i]!=NULL) ap->ptr[i]->parent=ap;
}
ap->key[m-j+1]=MAXKEY; //最大值放入所有关键字后
tp->keynum=j-1; //修改tp结点中的关键字个数
K=tp->key[j]; //建立新的待向双亲结点插入关键字
tp->key[j]=MAXKEY; //在tp结点的所有关键字最后放入最大关键字
//若条件成立,则需建立新的树根结点,所以退出循环
if(tp->parent==NULL) break;
//求出新的关键字在双亲结点的插入位置
tp=tp->parent;
i=1;
while(K>tp->key[i]) i++;
pos=i;
}
//建立新的树根结点
MT=new MBNode;
MT->keynum=1;
MT->parent=NULL;
MT->key[1]=K; MT->key[2]=MAXKEY;
MT->ptr[0]=tp; MT->ptr[1]=ap;
tp->parent=ap->parent=MT;
}
3.3.1.1 输入项
通过程序台的交互由用户选择一次插入一个关键字或是插入多个关键字,插入一个关键字则直接在提示下输入关键字,若插入多个关键字则在提示下首先输入要插入关键字的个数,以回车表示已的关键字的输入完毕.输入关键字为int型.
3.3.1.2输出项
插入函数返回插入关键字后的B_树根节点指针,可通过主程序与用户的交换选择遍历输出所有关键字,或者是输出一棵B_树.
3.3.1.3数据结构的定义
3.3.1全局数据结构
3.3.2 局部数据结构
3.3.1.4算法及程序说明
程序包括两个函数void InsertMBTree(MBNode*& MT,KeyType K)和void FindInsert(MBNode* mt,KeyType K,MBNode*& Tp,int& Pos).
1.void FindInsert(MBNode* mt,KeyType K,MBNode*& Tp,int& Pos) 功能:从B_树mt上查找关键字为K的插入位置,由Tp带回指向K所在结点的指针,由Pos带回插入K在Tp结点中的下标位置
2.void InsertMBTree(MBNode*& MT,KeyType K)功能:向树根指针为MT的B树插入关键字,具体过程请见下面的流程图:
图3-1 插入函数的流程图
3.3.1.5接口设计
该块函数的实现程序输入当前B_树的树根MT,以及待插入的关键字K,返回的是修改后的树根MT(在函数的参数中MT被定义为可双向传值的).
3.3.2子功能模块2
实现功能:
从B_树中删除结点,并调整树形
程序代码:
//从mt树上查找待删除的关键字所在的结点,若为非叶子结点则调换到叶子结点上
//由Tp指针指向该结点
void FindDelete(MBNode* mt,KeyType K,MBNode *& Tp)
{
int i;
//从树根结点起查找待删除关键字K所在的节点
while(mt!=NULL){
i=1;
while(K>mt->key[i]) i++;
if(K==mt->key[i]) break;
mt=mt->ptr[i-1];
}
//若mt树中不存在关键字K则Tp返回空值
if(mt==NULL){Tp=NULL;return;}
//若关键字K所在的结点为叶子,则删除它后由Tp带回结点地址
if(mt->ptr[i]==NULL){
int n=mt->keynum;
for(int j=i+1;jkey[j-1]=mt->key[j];
}
mt->keynum--;
mt->key[n]=MAXKEY;
Tp=mt;
return;
}
//在非叶子结点上查找成功,则继续查找该结点的中序前驱结点和
//中序前驱关键字,作对调和删除后,有Tp带回叶子结点的地址
Tp=mt; //用Tp暂存K所在非叶子结点的地址
MBNode* q=mt;
mt=mt->ptr[i-1]; //用q作为mt的前驱结点指针
while(mt!=NULL){
q=mt;
mt=mt->ptr[mt->keynum];
}
Tp->key[i]=q->key[q->keynum]; //把中序前驱关键字赋给被删除关键字的位置
q->key[q->keynum]=MAXKEY; //把最大关键字放入q结点的最后位置
q->keynum--; //q结点中关键字个数减1
Tp=q; //由Tp带回被删除关键字的叶子结点
return;
}
//从B_树中删除关键字K,删除成功返回真,否则返回假
bool DeleteMBTree(MBNode*&MT,KeyType K)
{
//若树为空,则返回假表示删除失败
if(MT==NULL) return false;
//调用FindDelete函数,由tp带回被删除一个关键字的叶子结点的地址
MBNode* tp;
FindDelete(MT,K,tp);
//若MT树中没有可删除的关键字则返回假表示删除失败
if(tp==NULL) return false;
//进行删除后的循环处理
while(1){
//把tp结点中的关键字个数赋给n
int n=tp->keynum;
//若删除后的关键字个数不小于最低限,则返回真表示删除成功
if(n>=ceil(double(m)/2)-1) return true;
//当tp结点为整个B_树的根结点时,若结点中无关键字,则应删除
//根结点,使整个B_树减少一层,否则直接返回
if(tp->parent==NULL){
if(n==0){
MT=MT->ptr[0];
if(MT!=NULL)
MT->parent=NULL;
delete tp;
return true;
}
else return true;
}
//用up指向tp的双亲结点,lp和rp拟指向tp的左右兄弟节点
MBNode *lp,*rp,*up=tp->parent;
int i=0,j;
//查找tp指针在双亲节点中的下标位置
while(up->ptr[i]!=tp) i++;
//从左兄弟结点中调剂关键字
if(i>0&&up->ptr[i-1]->keynum>ceil(double(m)/2)-1){
//lp指向tp的左兄弟结点
lp=up->ptr[i-1];
//修改tp结点
for(j=n;j>=1;j--)
tp->key[j+1]=tp->key[j];
for(j=n;j>=0;j--)
tp->ptr[j+1]=tp->ptr[j];
tp->key[n+2]=MAXKEY;
tp->key[1]=up->key[i];
tp->ptr[0]=lp->ptr[lp->keynum];
if(tp->ptr[0]!=NULL) tp->ptr[0]->parent=tp;
tp->keynum++;
//修改up结点
up->key[i]=lp->key[lp->keynum];
//修改lp结点
lp->key[lp->keynum]=MAXKEY;
lp->keynum--;
//删除成功返回真
return true;
}
//从右兄弟结点中调剂关键字
if(ikeynum&&up->ptr[i+1]->keynum>ceil(double(m)/2)-1){
//rp指向tp的右兄弟结点
rp=up->ptr[i+1];
//修改tp结点
tp->keynum++;
tp->key[n+1]=up->key[i+1];
tp->ptr[n+1]=rp->ptr[0];
if(tp->ptr[n+1]!=NULL) tp->ptr[n+1]->parent=tp;
tp->key[n+2]=MAXKEY;
//修改up结点
up->key[i+1]=rp->key[1];
//修改rp结点
for(j=2;jkeynum;j++){
rp->key[j-1]=rp->key[j];
}
for(j=1;jkeynum;j++)
rp->ptr[j-1]=rp->ptr[j];
rp->key[rp->keynum]=MAXKEY;
rp->keynum--;
//删除成功返回真
return true;
}
//tp结点同左兄弟结点lp合并
if(i>0){
//lp指向tp结点的左兄弟
lp=up->ptr[i-1];
//把lp结点中关键字个数赋给n1
int n1=lp->keynum;
//修改lp结点
lp->key[n1+1]=up->key[i];
for(j=1;jkey[n1+1+j]=tp->key[j];
}
for(j=0;jptr[n1+1+j]=tp->ptr[j];
if(lp->ptr[n1+1+j]!=NULL)
lp->ptr[n1+1+j]->parent=lp;
}
lp->key[n1+n+2]=MAXKEY;
lp->keynum=n1+n+1;
//删除tp结点
delete tp;
//修改up结点
for(j=i+1;jkeynum;j++){
up->key[j-1]=up->key[j];
up->ptr[j-1]=up->ptr[j];
}
up->key[up->keynum]=MAXKEY;
up->keynum--;
//双亲结点成为被删除关键字的节点,把它赋给tp
tp=up;
}
//tp结点同右兄弟结点rp合并,此时i必然为0,tp无左兄弟
else{
//rp指向tp结点的右兄弟
rp=up->ptr[1];
//把rp结点中关键字个数赋n2
int n2=rp->keynum;
//把rp结点中的每个关键字后移n+1位置
for(j=n2;j>=1;j--){
rp->key[n+1+j]=rp->key[j];
}
for(j=n2;j>=0;j--)
rp->ptr[n+1+j]=rp->ptr[j];
//把双亲结点中的一个记录的索引项下移
rp->key[n+1]=up->key[1];
//把tp结点的每个关键字写入到rp结点中空出的位置上
for(j=1;jkey[j]=tp->key[j];
}
for(j=0;jptr[j]=tp->ptr[j];
if(rp->ptr[j]!=NULL) rp->ptr[j]->parent=rp;
}
//把最大关键之放入rp结点的所有关键字之后
rp->key[n2+n+2]=MAXKEY;
//修改rp结点的关键字个数
rp->keynum=n2+n+1;
//删除tp节点
delete tp;
//修改up结点
for(j=2;jkeynum;j++){
up->key[j-1]=up->key[j];
}
for(j=1;jkeynum;j++)
up->ptr[j-1]=up->ptr[j];
up->key[up->keynum]=MAXKEY;
up->keynum--;
//双亲结点成为被删除关键字的结点,把它赋给tp
tp=up;
}
}
}
3.3.2.1 输入项
通过程序台的交互由用户选择一次删除一个关键字或是删除多个关键字,删除一个关键字则直接在提示下删除关键字,若删除多个关键字则在提示下首先输入要删除关键字的个数,以回车表示已的关键字的输入完毕.输入关键字为int型.
3.3.2.2输出项
删除函数返回插入关键字后的B_树根节点指针,可通过主程序与用户的交换选择遍历输出所有关键字,或者是输出一棵B_树.
3.3.2.3数据结构的定义
3.3.1全局数据结构
3.3.2 局部数据结构
3.3.2.4算法及程序说明
程序包括两个函数void FindDelete(MBNode* mt,KeyType K,MBNode *& Tp)和bool DeleteMBTree(MBNode*&MT,KeyType K).
1. void FindDelete(MBNode* mt,KeyType K,MBNode *& Tp) 功能:从B_树mt上查找关键字为K的插入位置,由Tp带回指向K所在结点的指针,由Pos带回插入K在Tp结点中的下标位置.
流程图:
图3-2 查找删除函数FindDelete的流程图
2. bool DeleteMBTree(MBNode*&MT,KeyType K)功能:从B_树中删除关键字K,删除成功返回真,否则返回假
流程图:
图3-3 删除函数DeleteMBTree
3.3.2.5接口设计
输入当前B_树的树根MT,以及待删除的关键字K,返回是否删除成功,同时返回的是修改后的树根MT(在函数的参数中MT被定义为可双向传值的).
3.3.3子功能模块3
实现功能:
显示B_树
程序代码:
//利用层序遍历输出B_树
void DisplayMBTree(MBNode * MT)
{
//定义两个队列分别用来存放相邻两行的结点关键字,QueueNumber来记录队列的项数值
//定义CurrentNode存放当前结点
if(MT==NULL) return;
int i,QueueNumber1=0,QueueNumber2=0;
MBNode *Queue1[20],*Queue2[20],*CurrentNode1,*CurrentNode2;
//将根结点加入Queue1
Queue1[QueueNumber1]=MT;
QueueNumber1++;
//循环输出树
while(QueueNumber1>0||QueueNumber2>0){
while(QueueNumber1>0)
{
//将Queue1队首结点出队,保存至CurrentNode1结点
CurrentNode1=Queue1[0];
QueueNumber1--;
//Queue1中其他结点依次前移
i=0;
while(i
Queue1[i]=Queue1[i+1];
i++;
}
//输出CurrentNode1结点中关键字的数值
i=0;
while(ikeynum)
{
cout<<"|";
cout
}
cout
i=0;
while(ikeynum)
{
Queue2[QueueNumber2]=CurrentNode1->ptr[i];
QueueNumber2++;
i++;
}
}
}
cout<0)
{
//将Queue2队首结点出队,保存至CurrentNode2结点
CurrentNode2=Queue2[0];
QueueNumber2--;
//Queue2中其他结点依次前移
i=0;
while(i
Queue2[i]=Queue2[i+1];
i++;
}
//输出CurrentNode2结点中关键字的数值
i=0;
while(ikeynum)
{
cout<<"|";
cout
}
cout
i=0;
while(ikeynum)
{
Queue1[QueueNumber1]=CurrentNode2->ptr[i];
QueueNumber1++;
i++;
}
}
}
cout<
cout<
3.3.2.1 输入项
树根结点
3.3.2.2输出项
通过程序台显示一棵B_树
3.3.3.3数据结构的定义
3.3.1全局数据结构
3.3.2 局部数据结构
3.3.3.4算法及程序说明
该段程序用层序遍历的方法输出一棵B_树到屏幕
流程图:
图3-4 输出显示函数流程图
3.3.3.5接口设计
由MT带入当前B_树的树根,无返回值,直接向屏幕输出B_树.
3.4运行结果
图3-5 与用户交互的界面
图3-6 插入一组数据的输入方法及显示结果
图3-7 插入一个关键字的交换及输出结果
图3-8 插入失败的显示结果
图3-9 删除一个关键字成功
图3-10 删除一个关键字失败
图3-11 删除一组关键字
3.5尚未解决的问题
说明在本程序的设计中应该解决而尚未解决的问题.
注:本程序中还有一些其他的功能为本实验没有要求的,均可以正常使用,可用来检验结果是否正确
第页