廣工數(shù)據(jù)結(jié)構(gòu)實驗設(shè)計報告-B樹（難度1.4

1、 數(shù)據(jù)結(jié)構(gòu)設(shè)計性實驗報告 課程名稱 數(shù)據(jù)結(jié)構(gòu)實驗 題目名稱 B樹（難度1.4） 學(xué)生學(xué)院 計算機學(xué)院 專業(yè)班級 學(xué) 號 姓 名 指導(dǎo)教師 黃劍鋒 2015年 06 月25日B樹抽象數(shù)據(jù)類型實現(xiàn)一、設(shè)計簡介本次設(shè)計在AnyviewCL自由編程平臺上實現(xiàn)了B樹的6種基本操作，并根據(jù)這個基本操作設(shè)計了友好的交際界面，操作簡單易懂，并在AnyviewCL自由編程平臺上可視化測試B樹各個基本操作，保證了各基本的操作算法的正確性。經(jīng)在AnyviewCL自由編程平臺嚴(yán)格測試后，將本設(shè)計移植到Visual C+ 6.0平臺生成可運行程序，并進行各個基本操作的測試，保證了程序運行的穩(wěn)定性。其中數(shù)據(jù)來源為一組在0

2、1000內(nèi)的int型隨機數(shù)，但數(shù)據(jù)由typedef int KeyType定義，若需要改變數(shù)據(jù)類型，只需要將int替換成所需的數(shù)據(jù)類型即可。二、抽象數(shù)據(jù)類型定義及各種基本操作的描述ADT BTree數(shù)據(jù)對象：D是具有相同特征的數(shù)據(jù)元素集合。數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹；（1）樹中每個結(jié)點最多含有m棵子樹；（2）若根結(jié)點不是葉子結(jié)點，則至少有2個子樹；（3）除根結(jié)點之外的所有非終端結(jié)點至少有m/2棵子樹；（4）每個非終端結(jié)點中包含信息：（n，A0，K1，A1，K2，A2，Kn，An）。其中：1）Ki（1=i=n）為關(guān)鍵字，且關(guān)鍵字按升序排序；2）指針Ai（0=i=n）指向子樹的根結(jié)點，Ai-

3、1指向子樹中所有結(jié)點的關(guān)鍵字均小于Ki，且大于Ki-1；3）關(guān)鍵字的個數(shù)n必須滿足：m/2-1=n pt, p - i, m);初始條件：樹T存在，p - pt指向T中某個結(jié)點操作結(jié)果：在B樹T上結(jié)點p - pt的keyi和keyi+1之間插入關(guān)鍵字k DeleteBTree(p - pt, p - i, m, T);初始條件：樹T存在，p - pt指向T中某個結(jié)點操作結(jié)果：刪除B樹T上結(jié)點p - pt的關(guān)鍵字kPrintBTree(T);初始條件：樹T存在操作結(jié)果：中序遍歷B樹DestroyBTree(T)初始條件：樹T存在操作結(jié)果：銷毀B樹ADT BTree三、存儲結(jié)構(gòu)定義#include

4、#include#include #define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int KeyType;typedef int Status;typedef struct KeyType key; char data;Record;typedef struct BTNode int keynum; / 結(jié)點中關(guān)鍵字個數(shù)，即結(jié)點的大小 struct BTNode *parent; / 指向雙親結(jié)點 KeyType key21; / 關(guān)鍵字向量，0號單元未用 struct BTN

5、ode *ptr21; / 子樹指針向量 Record *recptr21; / 記錄指針向量，0號單元未用BTNode, *BTree; / B樹結(jié)點和B樹的類型typedef struct BTNode *pt; / 指向找到的結(jié)點 int i; / 1.m，在結(jié)點中的關(guān)鍵字序號 int tag; / 1:查找成功，0:查找失敗restype,*result; / 在B樹的查找結(jié)果類型四、關(guān)鍵算法設(shè)計流程圖主函數(shù)：MAIN();功能：確定B樹階數(shù)與初始結(jié)點數(shù)，提供基本的菜單功能選擇 函數(shù)名：int SearchNode(BTree p, int k);功能：在節(jié)點中查找關(guān)鍵字，返回該關(guān)鍵字

6、在節(jié)點中的位置。函數(shù)名：void SearchBTree(BTree t, int k, result &SearchBTree);功能：在m階B樹t上查找關(guān)鍵碼k，返回(pt,i,tag)。函數(shù)名：void split(BTree &q, int s, BTree &ap);功能：將結(jié)點q分裂成兩個結(jié)點，前一半保留，后一半移入新生結(jié)點ap。函數(shù)名：void newroot(BTree &t, BTree p, int x, BTree ap);功能：生成新的根結(jié)點。函數(shù)名：void Insert(BTree &q, int i, int x, BTree ap);功能：將關(guān)鍵字ap分別插入到

7、q-keyi+1和q-ptri+1中。函數(shù)名：void InsertBTree(BTree &t, int k, BTree q, int i, int m);功能：在B樹t上結(jié)點*q的keyi和keyi+1之間插入關(guān)鍵字k。函數(shù)名：void Successor(BTree &p, int i);功能：由后繼最下層非終端結(jié)點的最小關(guān)鍵字代替結(jié)點中關(guān)鍵字keyi。函數(shù)名：void Remove(BTree &p, int i);功能：從結(jié)點p中刪除keyi。函數(shù)名：void Restore(BTree &p, int i, int m, BTree &T);功能：調(diào)整B樹。函數(shù)名：void De

8、leteBTree(BTree p, int i, int m, BTree &T);功能：刪除B樹T上結(jié)點p的關(guān)鍵字k。五、 程序測試1、AnyviewCL自由編程平臺上測試結(jié)果1）3階B樹的測試：此時B樹的結(jié)構(gòu)為：進行查找操作： 進行插入操作：插入后B樹的結(jié)構(gòu)為：進行刪除操作（直接刪除關(guān)鍵字）：刪除關(guān)鍵字618后B樹的結(jié)構(gòu)為：此時對B樹進行打印操作：繼續(xù)進行刪除操作：（刪后結(jié)點與左兄弟合并）刪除關(guān)鍵字798后B樹的結(jié)構(gòu)為：繼續(xù)進行刪除操作：（直接刪除關(guān)鍵字）刪除關(guān)鍵字796后B樹的結(jié)構(gòu)為：繼續(xù)進行刪除操作：（刪后結(jié)點與右兄弟合并、父節(jié)點與左兄弟合并）刪除關(guān)鍵字580后B樹的結(jié)構(gòu)為：繼續(xù)進行

9、刪除操作：（刪后結(jié)點與左兄弟合并、父節(jié)點與右兄弟合并，樹的高度減1）刪除關(guān)鍵字281后B樹的結(jié)構(gòu)為：進行B樹的銷毀：此時AnyviewCL的演示區(qū)情況為：2）5階B樹的測試：初始化B樹的結(jié)構(gòu)后，B樹的結(jié)構(gòu)為： 進行插入操作：插入關(guān)鍵字580后B樹的結(jié)構(gòu)為：進行刪除操作：（刪后結(jié)點與右兄弟合并）刪除關(guān)鍵字21后B樹的結(jié)構(gòu)為：繼續(xù)進行刪除操作：（尋找后繼結(jié)點并與之交換，刪后向左兄弟借關(guān)鍵字）刪除關(guān)鍵字596后B樹的結(jié)構(gòu)為： 進行打印B樹操作：2、在Visual C+ 6.0平臺測試： B樹設(shè)置界面：進行B樹初始話操作：進行打印B樹操作：進行查找操作：進行插入操作： 插入關(guān)鍵字588后的B樹結(jié)構(gòu)為：

10、進行刪除操作：刪除關(guān)鍵字532后的B樹結(jié)構(gòu)為：進行銷毀B樹操作：銷毀后B樹為空，無法打?。和顺龀绦虿僮鳎毫?、思考與小結(jié)1、B樹的高度：若N=1，則對任意一棵包含N個關(guān)鍵字、高度為h、階數(shù)為m的B樹：1）因為B樹中每個結(jié)點最多有m棵子樹，m-1個關(guān)鍵字，所以在一棵高度為h的m階B樹中的關(guān)鍵字個數(shù)應(yīng)滿足：N=logm(N+1);2）若讓每個結(jié)點中的關(guān)鍵字個數(shù)達(dá)到最少，則容納同樣多關(guān)鍵字的B樹的高度可達(dá)到最大，此時有hkey1.keynum找p-keyi=kkeyi+1，并返回i int i = 1; while(i keynum & k p-keyi) i+; return i;void Sear

11、chBTree(BTree t, int k, result &SearchBTree)/ 在m階B樹t上查找關(guān)鍵碼k，返回(pt,i,tag)。/ 若查找成功，則特征值tag=1，指針pt所指結(jié)點中第i個關(guān)鍵碼等于k；否則，/ 特征值tag=0,等于k的關(guān)鍵碼記錄應(yīng)插入在指針pt所指結(jié)點中第i個和第i+1個關(guān)鍵碼間 int i = 0, found = 0; BTree p = t, q = NULL; / 初始，p指向待查結(jié)點，q指向p的雙親 while(p != NULL & 0 = found) i = SearchNode(p, k); / 在p-key1.keynum找p-keyi

12、=kkeyi+1 if(i0 & p-keyi = k) found = 1; / 找到待查關(guān)鍵字 else q = p; p = p-ptri-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; void split(BTree &q, int s, BTree &ap)/ 將結(jié)點q分裂

13、成兩個結(jié)點，前一半保留，后一半移入新生結(jié)點ap int i, j, n = q - keynum; ap = (BTNode*)malloc(sizeof(BTNode); / 生成新結(jié)點ap ap - ptr0 = q - ptrs; for(i = s + 1, j = 1; i keyj = q - keyi; ap - ptrj = q - ptri; ap - keynum = n - s; ap - parent = q - parent; for(i = 0; i ptri) ap - ptri - parent = ap; q - keynum = s - 1; / q的前一半

14、保留，修改keynumvoid newroot(BTree &t, BTree p, int x, BTree ap)/ 生成新的根結(jié)點 t = (BTNode*)malloc(sizeof(BTNode); t - keynum = 1; t - ptr0 = p; t - ptr1 = ap; t - key1 = x; if(p!=NULL) p - parent = t; if(ap!=NULL) ap - parent = t; t - parent = NULL; / 新根的雙親是空指針void Insert(BTree &q, int i, int x, BTree ap) in

15、t j,n = q - keynum; for(j = n; j = i; j-) q - keyj+1 = q - keyj; q - ptrj+1 = q - ptrj; q - keyi = x; q - ptri = ap; if(ap!=NULL) ap - parent = q; q - keynum+;void InsertBTree(BTree &t, int k, BTree q, int i, int m)/ 在B樹t上結(jié)點*q的keyi和keyi+1之間插入關(guān)鍵字k/ 若引起結(jié)點過大，則沿雙親鏈進行必要的結(jié)點分裂調(diào)整，使T仍是m階的B樹 int x, s; BTree a

16、p; int finished = 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-keyi+1和q-ptri+1 if(q-keynum keys; if(q - parent) q = q - parent; i = SearchNode(q, x); / 在雙親結(jié)點*q中查找x的插入位置 else neednewroot = 1;

17、if(1 = neednewroot) / t是空樹或者根結(jié)點已分裂為結(jié)點q和ap newroot(t, q, x, ap); / 生成含信息(t,x,ap)的新的根結(jié)點root void Successor(BTree &p, int i)/由后繼最下層非終端結(jié)點的最小關(guān)鍵字代替結(jié)點中關(guān)鍵字keyi BTNode *u; u = p - ptri; while(NULL != u - ptr0) /找出關(guān)鍵字的后繼 u = u - ptr0; p - keyi = u - key1; p = u;void Remove(BTree &p, int i)/從結(jié)點p中刪除keyi int j,n

18、 = p - keynum; for(j = i; j keyj = p - keyj+1; p - ptrj = p - ptrj+1; /free(p - ptrn); /p - ptrn = NULL; p - keynum - ;void Restore(BTree &p, int i, int m, BTree &T)/調(diào)整B樹 int j; BTree ap = p - parent; BTree lc, rc, pr; int finished = 0, r = 0; while(0 = finished) r = 0; while(ap - ptrr != p) /確定p在ap

19、子樹的位置 r+; if(r = 0) r+; lc = NULL; rc = ap - ptrr; else if(r = ap - keynum) rc = NULL; lc = ap - ptrr-1; else lc = ap - ptrr-1; rc = ap - ptrr+1; if(r 0 & lc != NULL & (lc - keynum (m - 1) / 2) /向左兄弟借關(guān)鍵字 p - keynum +; for(j = p - keynum; j 1; j-) /結(jié)點關(guān)鍵字右移 p - keyj = p - keyj-1; p - ptrj = p - ptrj-1

20、; p - key1 = ap - keyr; /父親插入到結(jié)點 p - ptr1 = p - ptr0; p - ptr0 = lc - ptrlc - keynum; if(NULL != p - ptr0) /修改p中的子女的父結(jié)點為p p - ptr0 - parent = p; ap - keyr = lc - keylc - keynum; /左兄弟上移到父親位置 lc - keynum -; finished = 1; break; else if(ap - keynum r & rc != NULL & (rc - keynum (m - 1) / 2) /向右兄弟借關(guān)鍵字 p

21、 - keynum +; p - keyp - keynum = ap - keyr; /父親插入到結(jié)點 p - ptrp - keynum = rc - ptr0; if(NULL != p - ptrp - keynum) /修改p中的子女的父結(jié)點為p p - ptrp - keynum - parent = p; ap - keyr = rc - key1; /右兄弟上移到父親位置 rc - ptr0 = rc - ptr1; for(j = 1; j keynum; j+) /右兄弟結(jié)點關(guān)鍵字左移 rc - keyj = rc - keyj+1; rc - ptrj = rc - pt

22、rj+1; rc - keynum -; finished = 1; break; r = 0; while(ap - ptrr != p) /重新確定p在ap子樹的位置 r+; if(r 0 & (ap - ptrr-1 - keynum ptrr - 1; p - keynum +; for(j = p - keynum; j 1; j- ) /將p結(jié)點關(guān)鍵字和指針右移1位 p - keyj = p - keyj-1; p - ptrj = p - ptrj-1; p - key1 = ap - keyr; /父結(jié)點的關(guān)鍵字與p合并 p - ptr1 = p - ptr0; /從左兄弟右移

23、一個指針 ap - ptrr+1 = lc; for(j = 1; j keynum + p - keynum; j+) /將結(jié)點p中關(guān)鍵字和指針移到p左兄弟中 lc-keylc - keynum + j = p - keyj; lc-ptrlc - keynum + j = p - ptrj; if(p - ptr0) /修改p中的子女的父結(jié)點為lc for(j = 1; j keynum; j+) p - ptrp - keynum + j - parent = lc; lc - keynum = lc - keynum + p - keynum; /合并后關(guān)鍵字的個數(shù) ap - keyn

24、um-; pr = p; free(pr); /釋放p結(jié)點空間 pr = NULL; p = lc; else /與右兄弟合并 rc = ap - ptrr + 1; if(r = 0) r +; p - keynum +; p - keyp - keynum = ap - keyr; /父結(jié)點的關(guān)鍵字與p合并 p - ptrp - keynum = rc - ptr0; /從右兄弟左移一個指針 rc - keynum = p - keynum + rc - keynum; /合并后關(guān)鍵字的個數(shù) ap - ptrr-1 = rc; for(j = 1; j keynum - p - keynu

25、m); j+) /將p右兄弟關(guān)鍵字和指針右移 rc-keyp - keynum + j = rc - keyj; rc-ptrp - keynum + j = rc - ptrj; for(j = 1; j keynum; j+) /將結(jié)點p中關(guān)鍵字和指針移到p右兄弟中 rc-keyj = p - keyj; rc-ptrj = p - ptrj; rc-ptr0 = p - ptr0; if(p - ptr0) /修改p中的子女的父結(jié)點為rc for(j = 1; j keynum; j+) p - ptrp - keynum + j - parent = rc; for(j = r; j

26、keynum; j+) /將父結(jié)點中關(guān)鍵字和指針左移 ap - keyj = ap - keyj + 1; ap - ptrj = ap - ptrj + 1; ap - keynum-; /父結(jié)點的關(guān)鍵字個數(shù)減1 pr = p; free(pr); /釋放p結(jié)點空間 pr = NULL; p = rc; ap = ap - parent; if(p - parent - keynum = (m-1)/2 | (NULL = ap & p - parent - keynum 0) finished = 1; else if(NULL = ap) /若調(diào)整后出現(xiàn)空的根結(jié)點，則刪除該根結(jié)點，樹高減

27、1 pr = T; T = p; /根結(jié)點下移 free(pr); pr = NULL; finished = 1; p = p - parent; void DeleteBTree(BTree p, int i, int m, BTree &T)/ 刪除B樹T上結(jié)點p的關(guān)鍵字k if(p-ptri-1!=NULL) / 若不是最下層非終端結(jié)點 Successor(p, i); / 由后繼最下層非終端結(jié)點的最小關(guān)鍵字代替它 DeleteBTree(p, 1, m, T); / 變成刪除最下層非終端結(jié)點中的最小關(guān)鍵字 else / 若是最下層非終端結(jié)點 Remove(p, i); / 從結(jié)點p中刪除keyi if(p-keynum (m-1)/2) / 刪除后關(guān)鍵字個數(shù)小于（m-1）/2 Restore(p, i, m