數(shù)據(jù)結構B樹(共15頁)

1、精選優(yōu)質文檔-傾情為你奉上數(shù)據(jù)結構課程設計實習報告 題 目：B樹的表示及基本操作學 號：姓 名：任 強年 級：2011級學 院：信息技術科學學院專 業(yè)：計算機科學與技術完成日期：2011.5.6授課教師：辛運幃1. 題目B樹的表示及基本操作（查找、插入、刪除及圖形化顯示）2. 要求a) 參考書中的示例代碼，以整數(shù)表示每個記錄的關鍵字。為簡單起見，每個記錄可以只包含一個關鍵字（即其他的字段可以不定義）。b) 從空樹開始，依次輸入各關鍵字，建立相應的B樹。c) 并實現(xiàn)B樹中關鍵字的插入及刪除。d) 同時將樹型顯示在屏幕上。全部關鍵字插入完畢時顯示樹型，之后每完成一次插入或刪除操作后也顯示當前的樹型

2、。3.程序實現(xiàn)3.1程序運行及編譯環(huán)境 程序運行及編譯環(huán)境：windows 7， VC+ 6.03.2程序描述 本程序實現(xiàn)了B樹的建立、查找、插入和刪除等基本操作。從空樹開始，利用鍵盤鍵入的關鍵字建立B樹；在此基礎上進行插入和刪除操作。B樹建立好以及完成插入和刪除操作后進行B樹的打印顯示。同時，程序通過必要的提示和功能選擇提供人機交互信息。利用B樹類的私有函數(shù)聲明提供了相關操作的封裝性。3.3實現(xiàn)功能4321開始建立B樹插入關鍵字刪除關鍵字結束打印B樹功能選擇輸入錯誤3.3.1子功能模塊1 建立B樹3.3.1.1 輸入項建立B樹時，在人機交互的提示下通過鍵盤輸入相關數(shù)據(jù)：待建B樹的階數(shù)m（大于

3、等于3）、要輸入的關鍵字的數(shù)目n以及關鍵字key（以-1為結束標志）（當所輸入的關鍵字數(shù)目大于n，只插入前n個關鍵字建立B樹，后面的關鍵字忽略）。所有要輸入的數(shù)據(jù)均為整型。截圖如下：3.3.1.2輸出項 根據(jù)輸入的B樹階數(shù)和關鍵字建立B樹，然后按照廣義表形式輸出B樹。見上圖。3.3.1.3數(shù)據(jù)結構的定義3.3.1.3.1全局數(shù)據(jù)結構 1).B樹結點結構體的聲明：template<class T>struct B_Node /B樹結點類int k; /當前關鍵字個數(shù)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;/查找、插入、刪除公有函數(shù)聲明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:/查找相關的私有函數(shù)聲明ResultCode Search(B_Node<T>*pc,T&x)const;ResultCode SearchNode(B_Node<T>*pc,T&x,int &pos);/插入相關的私有函數(shù)聲明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);/刪除相關的私有函數(shù)聲明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樹類中函數(shù)的聲明具有以下特點：查找、插入、刪除都是由私有函數(shù)實現(xiàn)，并且通過一個公有函數(shù)作為外界接口方便函數(shù)的調用。這實現(xiàn)了類的封裝性。3).函數(shù)返回結果ResultCode：枚舉類型enum ResultCod

8、eNotPresent,Success,Overflow,Duplicate; 此處的全局數(shù)據(jù)結構在之后的模板中均有使用，之后不再贅述。3.3.1.3.2 局部數(shù)據(jù)結構B樹的實例化：B_Tree<int> tree;從鍵盤鍵入的關鍵字和關鍵字數(shù)組：int key,array20;3.3.1.4算法及程序說明 本模塊通過鍵盤鍵入的關鍵字，反復調用插入操作，建立B樹。具體插入操作見子模塊3.3.3.3.3.1.5接口設計B樹的建立在main函數(shù)中進行，通過人機交互鍵入B樹的階數(shù)和關鍵字，調用插入函數(shù)建立B樹；下一模塊是B樹的打印以及插入、刪除等操作，即B樹的插入、刪除以及打印都需要建立

9、的B樹的根作為調用參數(shù)。3.3.2子功能模塊2 在B樹中查找關鍵字在B樹中查找關鍵字這一環(huán)節(jié)在本程序中沒有提供相應的功能選擇，但是B樹的插入、刪除等操作都需要首先進行查找操作，根據(jù)查找結果采取相應操作。所以，在此仍舊把查找作為一個單獨的子模塊。由于查找隸屬于插入和刪除操作，相關的輸入輸出項在插入刪除中在解釋。這一模塊只說明插入的算法及程序說明和接口設計。3.3.2.1算法及程序說明B樹中關鍵字的查找可以看作插入和刪除的一部分，即在進行關鍵字的插入與刪除之前首先進行查找操作，根據(jù)查找結果采取相應操作。查找由B樹類的兩個私有函數(shù)實現(xiàn)。具體操作如下：首先以待查找關鍵字作為函數(shù)參數(shù)調用公有函數(shù)接口；在

10、公有函數(shù)中調用實際完成查找的函數(shù)，函數(shù)參數(shù)為B樹的根和待查關鍵字，查找返回結果為Success（成功）和NotPresent（失?。辉趯嶋H查找函數(shù)中進一步調用結點查找函數(shù)，在當前結點內(nèi)查找關鍵字，查找成功結束，查找失敗則通過實際查找函數(shù)轉向子樹。關鍵代碼實現(xiàn)見附錄3.6.1 B樹的查找運算實現(xiàn)關鍵代碼。3.3.2.2接口設計本模塊是插入、刪除操作的一部分，所以隸屬于插入和刪除操作。其實現(xiàn)有一個外在接口公有函數(shù)ResultCode Search(T& x)const，通過這個接口調用具體實現(xiàn)查找操作的函數(shù)私有函數(shù)ResultCode Search(B_Node<T>*pc,

11、T&x)const。而下一模塊是插入和刪除的具體操作，根據(jù)查找的返回結果：Success或者NotPresent。3.3.3子功能模塊3在B樹中插入關鍵字3.3.3.1輸入項本模塊的輸入項是通過鍵盤的功能選擇輸入待插入的關鍵字。3.3.3.2輸出項在插入相關關鍵字后，根據(jù)插入結果：插入成功則打印插入后的B樹；如插入失?。P鍵字已經(jīng)在B樹中）則顯示相應提示信息。具體輸入輸出顯示見下頁截圖：3.3.3.3算法及程序說明B樹的插入運算方法：1）首先在B樹中查找給定的關鍵字元素，如果查找成功，表示所給關鍵字已經(jīng)在B樹中，插入失??；否則將給定的關鍵字和一個空指針插入查找失敗處。2）插入新的關鍵字

12、后，若結點未溢出，即結點中的關鍵字個數(shù)未超過order-1，插入運算成功終止。3）若插入關鍵字后結點溢出，則必須將結點分裂。結點的分裂位置為結點中間的關鍵字（若關鍵字為偶數(shù)則為前半部分最后一個關鍵字）。分裂位置之前的元素（關鍵字和指針）保留在原來的結點中，之后的元素存在新創(chuàng)建的結點中。而分裂位置的關鍵字插入雙親結點中，新創(chuàng)建的結點作為雙親結點的一個孩子結點。因此，雙親結點中新增一個關鍵字和一個指針，因此分裂完成后檢查雙親結點是否溢出，按照以上兩步繼續(xù)處理雙親結點。4）如果按照3）分裂的是根結點，而根結點沒有雙親，所以分裂產(chǎn)生的兩個結點以及分裂位置的關鍵字組成一個新的根結點，B樹也相應的增高一層

13、。關鍵代碼實現(xiàn)見附錄3.6.2 B樹的插入運算實現(xiàn)的關鍵代碼。3.3.3.4接口設計本模塊實現(xiàn)插入操作，由B樹類中的成員函數(shù)實現(xiàn)。首先由主函數(shù)以鍵盤輸入的關鍵字作為函數(shù)參數(shù)調用B樹類的公有函數(shù)接口ResultCode Insert(T& x)，然后在公有函數(shù)中調用實際實現(xiàn)插入操作的私有成員函數(shù)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輸出項 在刪除相關關鍵字后，根據(jù)刪除結果：刪除成功則打印刪除后的B樹；如刪除失敗（關鍵字不在B樹中）則顯示相應提示信息。具體輸入輸出顯示見下頁截圖：3.3.4.3算法及程序說明B樹的刪除運算方法：1）首先在B樹中查找待刪除的關鍵字，如果查找失敗，則刪除運算終止。如果查找成功，且待刪除的關鍵字在葉結點中，直接刪除該關鍵字；如果待刪除的關鍵字不在葉結點中，先用其前驅（左子樹的最大關鍵字）替代，然后從葉結點中刪除替代關鍵字。2）如果刪除關鍵字后，當前結點未發(fā)生下溢（關鍵字個數(shù)至少為order/2），則刪除運算成功終

15、止；否則需對結點進一步處理，首先借元素：如果左兄弟有富余關鍵字（左兄弟關鍵字數(shù)目大于order/2），則可以向左兄弟接一個關鍵字；否則，若右兄弟有則向右兄弟借。借關鍵字是利用旋轉操作進行的。3）若刪除關鍵字后，結點下溢且左右兄弟都沒有富余關鍵字（都只有order/2個關鍵字），則需要進行聯(lián)合操作。若有左兄弟則與左兄弟聯(lián)合，否則與右兄弟聯(lián)合。聯(lián)合是將兩個結點中的元素連同雙親結點中分割兩者的元素結合成一個新的結點。聯(lián)合后，需要將其中一個結點刪除。即聯(lián)合后雙親結點中會少一個關鍵字和一個孩子結點，可能導致雙親結點下溢。所以檢查雙親結點，按照上述兩步處理。4）如果由于聯(lián)合，導致根結點中一個關鍵字被刪除，

16、而根結點中僅有一個關鍵字，刪除后成為空結點，那么聯(lián)合后形成的新結點成為新的根結點。這時，B樹因此降低一層。關鍵代碼實現(xiàn)見附錄3.6.3 B樹的刪除運算實現(xiàn)的關鍵代碼。3.3.4.4接口設計 本模塊實現(xiàn)刪除操作，由B樹類中的成員函數(shù)實現(xiàn)。首先由主函數(shù)以鍵盤輸入的關鍵字作為函數(shù)參數(shù)調用B樹類的公有函數(shù)接口ResultCode Remove(T& x)，然后在公有函數(shù)中調用實際實現(xiàn)插入操作的私有成員函數(shù)ResultCode Remove(B_Node<T>*pc,T&x)。本模塊的下一模塊是B樹的打印。按照題目要求每次刪除關鍵字后均需要打印B樹。3.4運行結果 本程序的執(zhí)

17、行是在人機交互的指導下運行的，運行結果在前面子模塊中已經(jīng)有相應展示。為了更加直觀的展示程序的功能以及運行結果，下面在附一份完全的程序運行結果截圖。3.5尚未解決的問題本程序沒有實現(xiàn)B樹的圖形化顯示輸出。由于本學期開始學可視化編程課程，很多知識點學習還不夠深入，不能利用API接口完成B樹的圖形化輸入顯示。本程序采用的是基本的廣義表形式打印B樹。3.6附錄：程序實現(xiàn)的關鍵代碼3.6.1 B樹的查找運算實現(xiàn)的關鍵代碼：/*B樹的查找運算實現(xiàn)*/查找操作接口，通過此函數(shù)調用查找函數(shù)template<class T>ResultCode B_Tree<T>:Search (T &

18、amp;x)constreturn Search(root,x); /調用函數(shù)查找相關結點/查找結點操作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;/在結點內(nèi)查找關鍵字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) /在當前結點范圍內(nèi)遍歷，直到待查關鍵字小于當前關鍵字或遍歷結束pos+;if(pos<pc->k&&x=pc-&g

20、t;datapos) /若在當前結點范圍內(nèi)查找到關鍵字，返回查找成功信息及關鍵字位置x=pc->datapos;return Success; else /否則返回查找失敗信息return NotPresent;3.6.2 B樹的插入運算實現(xiàn)的關鍵代碼：/*B樹的插入運算實現(xiàn)*/插入操作接口，通過此函數(shù)調用插入運算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;/插入運算的實現(xiàn)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) /查找關鍵字是否已經(jīng)存在于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 /插入關鍵字后若會發(fā)生溢出，則分裂結點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+; /關鍵字數(shù)目加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; /修改當前結點的關鍵字數(shù)目rHalf->k=order-1-mid; /新結點的關鍵字數(shù)目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樹的刪除運算實現(xiàn)的關鍵代碼：/*B樹的刪除運算實現(xiàn)*/刪除操作接口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; /刪除原根/刪除運算的實現(xiàn)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-; /當前關鍵字數(shù)目減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); /否則與左兄弟聯(lián)合else if(pos=0) /當前結點是雙親的最左邊孩子結點if(pc->b1->k>(order-1)/2) /若右兄弟有多余關鍵字，向右兄弟借MoveLeft(pc,1);elseCombine(pc,1); /否則與右兄弟聯(lián)合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); /與左兄弟聯(lián)合/向右兄弟借關鍵字操作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-; /右兄弟結點元素個數(shù)減1