数据结构B树(共15页)

1、精选优质文档-倾情为你奉上数据结构课程设计实习报告 题 目：B树的表示及基本操作学 号：姓 名：任 强年 级：2011级学 院：信息技术科学学院专 业：计算机科学与技术完成日期：2011.5.6授课教师：辛运帏1. 题目B树的表示及基本操作（查找、插入、删除及图形化显示）2. 要求a) 参考书中的示例代码，以整数表示每个记录的关键字。为简单起见，每个记录可以只包含一个关键字（即其他的字段可以不定义）。b) 从空树开始，依次输入各关键字，建立相应的B树。c) 并实现B树中关键字的插入及删除。d) 同时将树型显示在屏幕上。全部关键字插入完毕时显示树型，之后每完成一次插入或删除操作后也显示当前的树型

2、。3.程序实现3.1程序运行及编译环境 程序运行及编译环境：windows 7， VC+ 6.03.2程序描述 本程序实现了B树的建立、查找、插入和删除等基本操作。从空树开始，利用键盘键入的关键字建立B树；在此基础上进行插入和删除操作。B树建立好以及完成插入和删除操作后进行B树的打印显示。同时，程序通过必要的提示和功能选择提供人机交互信息。利用B树类的私有函数声明提供了相关操作的封装性。3.3实现功能4321开始建立B树插入关键字删除关键字结束打印B树功能选择输入错误3.3.1子功能模块1 建立B树3.3.1.1 输入项建立B树时，在人机交互的提示下通过键盘输入相关数据：待建B树的阶数m（大于

3、等于3）、要输入的关键字的数目n以及关键字key（以-1为结束标志）（当所输入的关键字数目大于n，只插入前n个关键字建立B树，后面的关键字忽略）。所有要输入的数据均为整型。截图如下：3.3.1.2输出项 根据输入的B树阶数和关键字建立B树，然后按照广义表形式输出B树。见上图。3.3.1.3数据结构的定义3.3.1.3.1全局数据结构 1).B树结点结构体的声明：template<class T>struct B_Node /B树结点类int k; /当前关键字个数T *data; /保存关键字B_Node<T> *b; /保存孩子结点B_Node(int num) k=

4、0;data=new Tnum-1;b=new B_Node<T>*num; 2).B树类声明：template<class T>class B_Treepublic:B_Tree()root=NULL;void Set_order(int num)order=num;B_Node<T>* getRoot()constreturn root;/查找、插入、删除公有函数声明ResultCode Search(T& x)const;ResultCode Insert(T& x);ResultCode Remove(T& x);void P

5、rint(B_Node<T>*);int order;B_Node<T>*root;private:/查找相关的私有函数声明ResultCode Search(B_Node<T>*pc,T&x)const;ResultCode SearchNode(B_Node<T>*pc,T&x,int &pos);/插入相关的私有函数声明ResultCode Insert(B_Node<T>*pc,T&x,T &median,B_Node<T>*& right);void PushIn(

6、B_Node<T>*pc,const T&x,B_Node<T>* right,int pos);void SplitNode(B_Node<T>*pc,const T&x,B_Node<T>*q,int pos,T &median,B_Node<T>*& rHalf);/删除相关的私有函数声明ResultCode Remove(B_Node<T>*pc,T&x);void CopyInPre(B_Node<T>*pc,int pos);void RemoveData(B

7、_Node<T>*pc,int pos);void Restore(B_Node<T>*pc,int pos);void MoveLeft(B_Node<T>*pc,int pos);void MoveRight(B_Node<T>*pc,int pos);void Combine(B_Node<T>*pc,int pos);B树类中函数的声明具有以下特点：查找、插入、删除都是由私有函数实现，并且通过一个公有函数作为外界接口方便函数的调用。这实现了类的封装性。3).函数返回结果ResultCode：枚举类型enum ResultCod

8、eNotPresent,Success,Overflow,Duplicate; 此处的全局数据结构在之后的模板中均有使用，之后不再赘述。3.3.1.3.2 局部数据结构B树的实例化：B_Tree<int> tree;从键盘键入的关键字和关键字数组：int key,array20;3.3.1.4算法及程序说明 本模块通过键盘键入的关键字，反复调用插入操作，建立B树。具体插入操作见子模块3.3.3.3.3.1.5接口设计B树的建立在main函数中进行，通过人机交互键入B树的阶数和关键字，调用插入函数建立B树；下一模块是B树的打印以及插入、删除等操作，即B树的插入、删除以及打印都需要建立

9、的B树的根作为调用参数。3.3.2子功能模块2 在B树中查找关键字在B树中查找关键字这一环节在本程序中没有提供相应的功能选择，但是B树的插入、删除等操作都需要首先进行查找操作，根据查找结果采取相应操作。所以，在此仍旧把查找作为一个单独的子模块。由于查找隶属于插入和删除操作，相关的输入输出项在插入删除中在解释。这一模块只说明插入的算法及程序说明和接口设计。3.3.2.1算法及程序说明B树中关键字的查找可以看作插入和删除的一部分，即在进行关键字的插入与删除之前首先进行查找操作，根据查找结果采取相应操作。查找由B树类的两个私有函数实现。具体操作如下：首先以待查找关键字作为函数参数调用公有函数接口；在

10、公有函数中调用实际完成查找的函数，函数参数为B树的根和待查关键字，查找返回结果为Success（成功）和NotPresent（失败）；在实际查找函数中进一步调用结点查找函数，在当前结点内查找关键字，查找成功结束，查找失败则通过实际查找函数转向子树。关键代码实现见附录3.6.1 B树的查找运算实现关键代码。3.3.2.2接口设计本模块是插入、删除操作的一部分，所以隶属于插入和删除操作。其实现有一个外在接口公有函数ResultCode Search(T& x)const，通过这个接口调用具体实现查找操作的函数私有函数ResultCode Search(B_Node<T>*pc,

11、T&x)const。而下一模块是插入和删除的具体操作，根据查找的返回结果：Success或者NotPresent。3.3.3子功能模块3在B树中插入关键字3.3.3.1输入项本模块的输入项是通过键盘的功能选择输入待插入的关键字。3.3.3.2输出项在插入相关关键字后，根据插入结果：插入成功则打印插入后的B树；如插入失败（关键字已经在B树中）则显示相应提示信息。具体输入输出显示见下页截图：3.3.3.3算法及程序说明B树的插入运算方法：1）首先在B树中查找给定的关键字元素，如果查找成功，表示所给关键字已经在B树中，插入失败；否则将给定的关键字和一个空指针插入查找失败处。2）插入新的关键字

12、后，若结点未溢出，即结点中的关键字个数未超过order-1，插入运算成功终止。3）若插入关键字后结点溢出，则必须将结点分裂。结点的分裂位置为结点中间的关键字（若关键字为偶数则为前半部分最后一个关键字）。分裂位置之前的元素（关键字和指针）保留在原来的结点中，之后的元素存在新创建的结点中。而分裂位置的关键字插入双亲结点中，新创建的结点作为双亲结点的一个孩子结点。因此，双亲结点中新增一个关键字和一个指针，因此分裂完成后检查双亲结点是否溢出，按照以上两步继续处理双亲结点。4）如果按照3）分裂的是根结点，而根结点没有双亲，所以分裂产生的两个结点以及分裂位置的关键字组成一个新的根结点，B树也相应的增高一层

13、。关键代码实现见附录3.6.2 B树的插入运算实现的关键代码。3.3.3.4接口设计本模块实现插入操作，由B树类中的成员函数实现。首先由主函数以键盘输入的关键字作为函数参数调用B树类的公有函数接口ResultCode Insert(T& x)，然后在公有函数中调用实际实现插入操作的私有成员函数ResultCode Insert(B_Node<T>*pc,T&x,T &median,B_Node<T>*& right)。本模块的下一模块是B树的打印。按照题目要求每次插入新的关键字后均需要打印B树。3.3.4子功能模块4 在B树中删除关键字3

14、.3.4.1输入项本模块的输入项是通过键盘的功能选择输入待删除的关键字。3.3.4.2输出项 在删除相关关键字后，根据删除结果：删除成功则打印删除后的B树；如删除失败（关键字不在B树中）则显示相应提示信息。具体输入输出显示见下页截图：3.3.4.3算法及程序说明B树的删除运算方法：1）首先在B树中查找待删除的关键字，如果查找失败，则删除运算终止。如果查找成功，且待删除的关键字在叶结点中，直接删除该关键字；如果待删除的关键字不在叶结点中，先用其前驱（左子树的最大关键字）替代，然后从叶结点中删除替代关键字。2）如果删除关键字后，当前结点未发生下溢（关键字个数至少为order/2），则删除运算成功终

15、止；否则需对结点进一步处理，首先借元素：如果左兄弟有富余关键字（左兄弟关键字数目大于order/2），则可以向左兄弟接一个关键字；否则，若右兄弟有则向右兄弟借。借关键字是利用旋转操作进行的。3）若删除关键字后，结点下溢且左右兄弟都没有富余关键字（都只有order/2个关键字），则需要进行联合操作。若有左兄弟则与左兄弟联合，否则与右兄弟联合。联合是将两个结点中的元素连同双亲结点中分割两者的元素结合成一个新的结点。联合后，需要将其中一个结点删除。即联合后双亲结点中会少一个关键字和一个孩子结点，可能导致双亲结点下溢。所以检查双亲结点，按照上述两步处理。4）如果由于联合，导致根结点中一个关键字被删除，

16、而根结点中仅有一个关键字，删除后成为空结点，那么联合后形成的新结点成为新的根结点。这时，B树因此降低一层。关键代码实现见附录3.6.3 B树的删除运算实现的关键代码。3.3.4.4接口设计 本模块实现删除操作，由B树类中的成员函数实现。首先由主函数以键盘输入的关键字作为函数参数调用B树类的公有函数接口ResultCode Remove(T& x)，然后在公有函数中调用实际实现插入操作的私有成员函数ResultCode Remove(B_Node<T>*pc,T&x)。本模块的下一模块是B树的打印。按照题目要求每次删除关键字后均需要打印B树。3.4运行结果 本程序的执

17、行是在人机交互的指导下运行的，运行结果在前面子模块中已经有相应展示。为了更加直观的展示程序的功能以及运行结果，下面在附一份完全的程序运行结果截图。3.5尚未解决的问题本程序没有实现B树的图形化显示输出。由于本学期开始学可视化编程课程，很多知识点学习还不够深入，不能利用API接口完成B树的图形化输入显示。本程序采用的是基本的广义表形式打印B树。3.6附录：程序实现的关键代码3.6.1 B树的查找运算实现的关键代码：/*B树的查找运算实现*/查找操作接口，通过此函数调用查找函数template<class T>ResultCode B_Tree<T>:Search (T &

18、amp;x)constreturn Search(root,x); /调用函数查找相关结点/查找结点操作template<class T>ResultCode B_Tree<T>:Search (B_Node<T>*pc,T &x) constResultCode result=NotPresent;int pos;if(pc!=NULL)result=SearchNode(pc,x,pos); /在当前结点查找关键字，返回查找结果if(result=NotPresent) /如果查找失败，递归调用查找下一个结点result=Search(pc-&g

19、t;bpos,x);else /查找成功则将关键字返回x=pc->datapos;return result;/在结点内查找关键字template<class T>ResultCode B_Tree<T>:SearchNode (B_Node<T>*pc,T &x,int &pos)pos=0;while(pos<pc->k&&x>pc->datapos) /在当前结点范围内遍历，直到待查关键字小于当前关键字或遍历结束pos+;if(pos<pc->k&&x=pc-&g

20、t;datapos) /若在当前结点范围内查找到关键字，返回查找成功信息及关键字位置x=pc->datapos;return Success; else /否则返回查找失败信息return NotPresent;3.6.2 B树的插入运算实现的关键代码：/*B树的插入运算实现*/插入操作接口，通过此函数调用插入运算template<class T,int order>ResultCode B_Tree<T>:Insert (T &x)T median;B_Node<T>*right,*p;ResultCode result=Insert(roo

21、t,x,median,right); /调用插入操作插入关键字并返回插入结果if(result=Overflow) /如果当前B树为空，新建立结点（根结点）p=new B_Node<T>(order);p->k=1;p->data0=median;p->b0=root;p->b1=right;root=p;result=Success;return result;/插入运算的实现template<class T>ResultCode B_Tree<T>:Insert (B_Node<T>*pc,T &x,T &am

22、p;median,B_Node<T>* &right)ResultCode result;int pos;if(pc=NULL) /如果树为空，递归结束median=x;right=NULL;result=Overflow;else /查找当前结点if(SearchNode(pc,x,pos)=Success) /查找关键字是否已经存在于B树中，结点位置和关键字位置都已指向待插入位置result=Duplicate;elseT y;B_Node<T>*q;result=Insert(pc->bpos,x,y,q); /递归调用在待插入位置插入关键字if(r

23、esult=Overflow)if(pc->k<order-1) /如果关键字不会溢出，直接插入关键字PushIn(pc,y,q,pos);result=Success;else /插入关键字后若会发生溢出，则分裂结点SplitNode(pc,y,q,pos,median,right);return result;/在适合位置插入关键字template<class T>void B_Tree<T>:PushIn (B_Node<T>*pc,const T &x,B_Node<T>*right,int pos)for(int i

24、=pc->k;i>pos;i-) /将待插入关键字位置后面的关键字及孩子结点依次往后移位pc->datai=pc->datai-1;pc->bi+1=pc->bi;pc->datapos=x; /插入关键字pc->bpos+1=right; /连接孩子结点pc->k+; /关键字数目加1/分裂结点操作template<class T>void B_Tree<T>:SplitNode (B_Node<T>*pc,const T&x,B_Node<T>*q,int pos,T &m

25、edian,B_Node<T>*& rHalf)rHalf=new B_Node<T>(order);int mid; /记录结点中间位置，将结点分为左右两个部分if(order%2=0)mid=order/2-1;elsemid=order/2;if(pos<=mid) /如果插入关键字的位置在结点左半部分for(int i=mid;i<order-1;i+) /将结点右半部分的关键字及孩子结点复制给新的结点rHalf->datai-mid=pc->datai;rHalf->bi-mid+1=pc->bi+1;pc->

26、k=mid; /修改当前结点的关键字数目rHalf->k=order-1-mid; /新结点的关键字数目PushIn(pc,x,q,pos); /在带插入位置插入关键字else /如果插入关键字的位置在右半部分mid+;for(int i=mid;i<order-1;i+) /复制结点右半部分rHalf->datai-mid=pc->datai;rHalf->bi-mid+1=pc->bi+1;pc->k=mid;rHalf->k=order-1-mid;PushIn(rHalf,x,q,pos-mid);median=pc->datapc

27、->k-1;rHalf->b0=pc->bpc->k; /为新结点的第一个孩子结点赋值pc->k-; 3.6.3 B树的删除运算实现的关键代码：/*B树的删除运算实现*/删除操作接口template<class T>ResultCode B_Tree<T>:Remove (T &x)ResultCode result;result=Remove(root,x); /调用删除操作if(root!=NULL&&root->k=0) /根为空B_Node<T>*p=root;root=root->b

28、0; /原根剩下唯一孩子结点成为新根delete p;return result; /删除原根/删除运算的实现template<class T>ResultCode B_Tree<T>:Remove (B_Node<T>*pc,T &x)ResultCode result;int pos;if(pc=NULL) /如果当前树为空，返回删除失败result=NotPresent;else /查找当前结点if(SearchNode(pc,x,pos)=Success) /找到关键字result=Success;if(pc->bpos!=NULL)

29、/如果关键字不在叶结点CopyInPre(pc,pos); /将待删除关键字与其左子树最大关键字（前驱）交换后删除Remove(pc->bpos,pc->datapos);else /待删除关键字在叶结点则直接移除关键字RemoveData(pc,pos);else /若未找到关键字，则到下一个结点中查找result=Remove(pc->bpos,x);if(pc->bpos!=NULL) /考查删除关键字后的结点if(pc->bpos->k<(order-1)/2) /若结点下溢Restore(pc,pos);return result;/将待删除

30、关键字与其左子树最大关键字（前驱）交换template<class T>void B_Tree<T>:CopyInPre (B_Node<T>*pc,int pos)B_Node<T>*leaf=pc->bpos;while(leaf->bleaf->k!=NULL)leaf=leaf->bleaf->k;pc->datapos=leaf->dataleaf->k-1;/从结点中删除指定关键字template<class T>void B_Tree<T>:RemoveData

31、 (B_Node<T>*pc,int pos)for(int i=pos;i<pc->k-1;i+) /将待删除关键字后的关键字依次前移一位pc->datai=pc->datai+1;pc->k-; /当前关键字数目减1/删除后结点下溢，恢复操作template<class T>void B_Tree<T>:Restore (B_Node<T>*pc,int pos)if(pos=pc->k) /当前结点是双亲的最右边孩子结点if(pc->bpos-1->k>(order-1)/2) /若左兄

32、弟有多余关键字，向左兄弟借MoveRight(pc,pos-1);elseCombine(pc,pos); /否则与左兄弟联合else if(pos=0) /当前结点是双亲的最左边孩子结点if(pc->b1->k>(order-1)/2) /若右兄弟有多余关键字，向右兄弟借MoveLeft(pc,1);elseCombine(pc,1); /否则与右兄弟联合else /当前结点不是双亲的两端孩子结点if(pc->bpos-1->k>(order-1)/2) /向左兄弟借MoveRight(pc,pos-1);else if(pc->bpos+1->

33、;k>(order-1)/2) /向右兄弟借MoveLeft(pc,pos+1);elseCombine(pc,pos); /与左兄弟联合/向右兄弟借关键字操作template<class T>void B_Tree<T>:MoveLeft (B_Node<T>*pc,int pos)B_Node<T>*left=pc->bpos-1,*right=pc->bpos;left->dataleft->k=pc->datapos-1; /双亲的分割元素移到左兄弟的最右边left->b+left->k=right->b0; /右兄弟的最左边子树移到左兄弟的最右边pc->datapos-1=right->data0; /右兄弟的最左元素移到双亲中right->k-; /右兄弟结点元素个数减1