广工数据结构实验设计报告BTree

数据结构设计性实验报告课程名称数据结构实验题目名称B树〔难度1.4〕学生学院计算机学院专业班级学号姓名指导教师黄剑锋2023年06月25日B树抽象数据类型实现一、设计简介本次设计在AnyviewCL自由编程平台上实现了B树的6种根本操作，并根据这个根本操作设计了友好的交际界面，操作简单易懂，并在AnyviewCL自由编程平台上可视化测试B树各个根本操作，保证了各根本的操作算法的正确性。经在AnyviewCL自由编程平台严格测试后，将本设计移植到VisualC++6.0平台生成可运行程序，并进行各个根本操作的测试，保证了程序运行的稳定性。其中数据来源为一组在0~1000内的int型随机数，但数据由typedefintKeyType定义，假设需要改变数据类型，只需要将int替换成所需的数据类型即可。二、抽象数据类型定义及各种根本操作的描述ADTBTree{数据对象：D是具有相同特征的数据元素集合。数据关系：假设D为空集，那么称为空树；〔1〕树中每个结点最多含有m棵子树；〔2〕假设根结点不是叶子结点，那么至少有2个子树；〔3〕除根结点之外的所有非终端结点至少有┌m/2┐棵子树；〔4〕每个非终端结点中包含信息：〔n，A0，K1，A1，K2，A2，…，Kn，An〕。其中：1〕Ki〔1<=i<=n〕为关键字，且关键字按升序排序；2〕指针Ai〔0<=i<=n〕指向子树的根结点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1；3〕关键字的个数n必须满足：┌m/2┐-1<=n<=m-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]之间插入关键字kDeleteBTree(p->pt,p->i,m,T);初始条件：树T存在，p->pt指向T中某个结点操作结果：删除B树T上结点p->pt的关键字kPrintBTree(T);初始条件：树T存在操作结果：中序遍历B树DestroyBTree(T)初始条件：树T存在操作结果：销毁B树}ADTBTree三、存储结构定义#include<stdio.h>#include<stdlib.h>#include<time.h>#defineTRUE1#defineFALSE0#defineOVERFLOW-2#defineOK1#defineERROR0typedefintKeyType;typedefintStatus;typedefstruct{KeyTypekey;chardata;}Record;typedefstructBTNode{intkeynum;//结点中关键字个数，即结点的大小structBTNode*parent;//指向双亲结点KeyTypekey[21];//关键字向量，0号单元未用structBTNode*ptr[21];//子树指针向量Record*recptr[21];//记录指针向量，0号单元未用}BTNode,*BTree;//B树结点和B树的类型typedefstruct{BTNode*pt;//指向找到的结点inti;//1..m，在结点中的关键字序号inttag;//1:查找成功，0:查找失败}restype,*result;//在B树的查找结果类型四、关键算法设计流程图主函数：MAIN();功能：确定B树阶数与初始结点数，提供根本的菜单功能选择函数名：intSearchNode(BTreep,intk);功能：在节点中查找关键字，返回该关键字在节点中的位置。函数名：voidSearchBTree(BTreet,intk,result&SearchBTree);功能：在m阶B树t上查找关键码k，返回(pt,i,tag)。函数名：voidsplit(BTree&q,ints,BTree&ap);功能：将结点q分裂成两个结点，前一半保存，后一半移入新生结点ap。函数名：voidnewroot(BTree&t,BTreep,intx,BTreeap);功能：生成新的根结点。函数名：voidInsert(BTree&q,inti,intx,BTreeap);功能：将关键字ap分别插入到q->key[i+1]和q->ptr[i+1]中。函数名：voidInsertBTree(BTree&t,intk,BTreeq,inti,intm);功能：在B树t上结点*q的key[i]和key[i+1]之间插入关键字k。函数名：voidSuccessor(BTree&p,inti);功能：由后继最下层非终端结点的最小关键字代替结点中关键字key[i]。函数名：voidRemove(BTree&p,inti);功能：从结点p中删除key[i]。函数名：voidRestore(BTree&p,inti,intm,BTree&T);功能：调整B树。函数名：voidDeleteBTree(BTreep,inti,intm,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、在VisualC++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<=m^h-1，因此有h>=logm(N+1);2〕假设让每个结点中的关键字个数到达最少，那么容纳同样多关键字的B树的高度可到达最大，此时有h<=log┌m/2┐((N+1)/2+1)。2、复杂度：每次查找共需访问O(logmN)个结点，由此可知，对存有N个关键字的m阶B树的每次查找，耗时不超过O(logmN)。七、总结和体会本次设计主要在AnyviewCL自由编程平台上进行编程，通过深入学习课本提供的查找与插入算法后，我很轻易地写出了构建的算法，再根据递归的知识完成了B树的中序遍历算法和销毁算法。本次设计的难点在于B树的调整算法，B树在插入的过程中可能发生上溢，此时需要通过分裂结点来处理，在此过程中B树可能出现长高。而在删除的过程中那么可能发生下溢，此时需要分：借左兄弟、借右兄弟、与左兄弟合并、与右兄弟这四种调整方式来处理，并要处理合并后根结点为空的情况，在此过程中B树可能出现高度降低。在该平台的可视化调试功能的帮助严格测试了下各个根本操作的算法设计，改良算法中一些可能出现的错误，保证了代码的正确性。然后将代码移植到VisualC++6.0中，编译并运行后，初始化B树时程序出现异常代码:c0000005，在Dubug模式下找到原因是操作了未经初始化的对象，而代码本身在AnyviewCL自由编程平台上是可以顺利运行的，后来经过对几个关键指针的初始化Bug顺利排除。究其原因可能是AnyviewCL平台在实现可视化的过程已经对所有运用到的指针都进行了初始化。总而言之，在这次设计中我深入理解了B树的各项根本操作，也很好地锻炼了自己的动手能力，收获匪浅。八、程序关键源码//BTreeforVisualC++6.0//By：2023级计算机科学与技术3班3113005867方典禹//包含文件BTree.cpp、Operation.h、BTree.cppDatastructure.h//*******************定义数据类型***********************//BTree.cpp//*******************主函数***********************//Operation.h#include"Datastructure.h"//******************************根本操作函数****************************//intSearchNode(BTreep,intk)//在p->key[1..keynum]找p->key[i]<=k<p->key[i+1]，并返回i{inti=1;while(i<=p->keynum&&k>p->key[i])i++;returni;}voidSearchBTree(BTreet,intk,result&SearchBTree)//在m阶B树t上查找关键码k，返回(pt,i,tag)。//假设查找成功，那么特征值tag=1，指针pt所指结点中第i个关键码等于k；否那么，//特征值tag=0,等于k的关键码记录应插入在指针pt所指结点中第i个和第i+1个关键码间{inti=0,found=0;BTreep=t,q=NULL;//初始，p指向待查结点，q指向p的双亲while(p!=NULL&&0==found){i=SearchNode(p,k);//在p->key[1..keynum]找p->key[i]<=k<p->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;}}voidsplit(BTree&q,ints,BTree&ap)//将结点q分裂成两个结点，前一半保存，后一半移入新生结点ap{inti,j,n=q->keynum;ap=(BTNode*)malloc(sizeof(BTNode));//生成新结点apap->ptr[0]=q->ptr[s];for(i=s+1,j=1;i<=n;i++,j++)//后一半移入ap{ap->key[j]=q->key[i];ap->ptr[j]=q->ptr[i];}ap->keynum=n-s;ap->parent=q->parent;for(i=0;i<=n-s;i++)if(ap->ptr[i])ap->ptr[i]->parent=ap;q->keynum=s-1;//q的前一半保存，修改keynum}voidnewroot(BTree&t,BTreep,intx,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;//新根的双亲是空指针}voidInsert(BTree&q,inti,intx,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,intk,BTreeq,inti,intm)//在B树t上结点*q的key[i]和key[i+1]之间插入关键字k//假设引起结点过大，那么沿双亲链进行必要的结点分裂调整，使T仍是m阶的B树{intx,s;BTreeap;intfinished=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<m)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和apnewroot(t,q,x,ap);//生成含信息(t,x,ap)的新的根结点root}}voidSuccessor(BTree&p,inti)//由后继最下层非终端结点的最小关键字代替结点中关键字key[i]{BTNode*u;u=p->ptr[i];while(NULL!=u->ptr[0])//找出关键字的后继{u=u->ptr[0];}p->key[i]=u->key[1];p=u;}voidRemove(BTree&p,inti)//从结点p中删除key[i]{intj,n=p->keynum;for(j=i;j<n;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--;}voidRestore(BTree&p,inti,intm,BTree&T)//调整B树{intj;BTreeap=p->parent;BTreelc,rc,pr;intfinished=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];}elseif(r==ap->keynum){rc=NULL;lc=ap->ptr[r-1];}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中的子女的父结点为pp->ptr[0]->parent=p;ap->key[r]=lc->key[lc->keynum];//左兄弟上移到父亲位置lc->keynum--;finished=1;break;}elseif(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中的子女的父结点为pp->ptr[p->keynum]->parent=p;ap->key[r]=rc->key[1];//右兄弟上移到父亲位置rc->ptr[0]=rc->ptr[1];for(j=1;j<rc->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<=(m-1)/2))//与左兄弟合并{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<=lc->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<=p->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<=(rc->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<=p->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<=p->keynum;j++)p->ptr[p->keynum+j]->parent=rc;}for(j=r;j<ap->keynum;j++)//将父结点中关键字和指针左移{ap->key[j]=ap->key[j+1];ap->ptr[j]=ap->ptr[j+1];}ap->keynum--;//父结点的关键字个数减1pr=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;elseif(NULL==ap)//假设调整后出现空的根结点，那么删除该根结点，树高减1{pr=T;T=p;//根结点下移free(pr);pr=NULL;finished=1;}p=p->parent;}}voidDeleteBTree(BTreep,inti,intm,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<(m-1)/2)//删除后关键字个数小于〔m-1〕/2Restore(p,i,m,T);//调整B树}}//中序遍历B树voidPrintBTree(BTreet){inti=1;if(NULL!=t){while(i<=t->keynum){PrintBTree(t->ptr[i-1]);printf("%d",t->key[i]);i++;}PrintBTree(t->ptr[i-1]);}}//销毁B树voidDestroyBTree(BTreet){int