B-樹課程設(shè)計

1、-作者xxxx-日期xxxxB-樹課程設(shè)計【精品文檔】課程設(shè)計成果 學(xué)院: 計算機工程學(xué)院 班 級: 學(xué)生姓名: 學(xué) 號: 設(shè)計地點（單位） 設(shè)計題目: B-樹 完成日期： 年 月 日 指導(dǎo)教師評語: 成績(五級記分制): 教師簽名: 目 錄1 需求分析11.1 系統(tǒng)目標11.2 主體功能11.3 開發(fā)環(huán)境12概要設(shè)計12.1 功能模塊劃分12.2 系統(tǒng)流程圖23 詳細設(shè)計33.1 數(shù)據(jù)結(jié)構(gòu)33.2 模塊設(shè)計44 測試7測試數(shù)據(jù)7測試結(jié)果75 總結(jié)10參考文獻11附錄 源程序代碼12【精品文檔】1 需求分析1.1 系統(tǒng)目標完成B-樹的創(chuàng)建、查找、插入和刪除。1.2 主體功能B-Trees是一類

2、滿足特殊條件的M路查找樹，它滿足如下兩個條件的M路查找樹：1.所有葉節(jié)點的高度相同。2.除根之外的所有節(jié)點都是半滿的，即該節(jié)點包含M/2或更多的值。3.樹中每個節(jié)點都至多有M棵樹。4.所有的葉子節(jié)點都出現(xiàn)在同一層，并且不帶信息。5.所有的非終端節(jié)點中包含下列信息：(n,A0,K1,A1,K2,A2K3,A3.Kn,An)其中：Ki為關(guān)鍵字，且KiKi+1;Ai為指向自樹的指針，且Ai-1所指子樹中所有的節(jié)點的關(guān)鍵字均小于Ki,An所指子樹中所有節(jié)點的關(guān)鍵字均大于Kn，n為關(guān)鍵字的個數(shù)。1.設(shè)計并實現(xiàn)B-Trees數(shù)據(jù)結(jié)構(gòu)，包含其上的基本操作，如節(jié)點的插入和刪除等。2.實現(xiàn)在B-trees樹上的

3、查找操作。3.設(shè)計良好的運行界面，能夠?qū)崿F(xiàn)重復(fù)的操作。 1.3 開發(fā)環(huán)境開發(fā)系統(tǒng)：Windows 系統(tǒng)，處理器要求最低奔騰處理器，內(nèi)存32m，建議在i5處理器，128m內(nèi)存配置下調(diào)試。編譯集成軟件：Devc+開發(fā)軟件。Devc+是一個強大的C/C+軟件開發(fā)工具，操作簡單，使用非常廣泛，稱為很多程序員的首選開發(fā)工具。2概要設(shè)計 2.1 功能模塊劃分主函數(shù)即main()函數(shù)，主要實現(xiàn)B-Trees的建立，建立一棵滿足要求的4節(jié)B-Trres樹。菜單介紹函數(shù)即meau（）函數(shù)，主要包括介紹各個功能的實現(xiàn)途徑，并給操作者提供個操作界面。插入元素函數(shù)即insertbtree(b)函數(shù)，主要有用戶通過界面

4、輸入要插入的元素，首先判斷要插入的元素是否已在B-Trees中，若不在則插入之。刪除函數(shù)即deletetree(b)函數(shù)，首先判斷要刪除的元素是否在B-Trees中若在該B-Trees中則刪除。查找函數(shù)即searchbtree(b)函數(shù)，由用戶通過界面輸入一個元素，查找該元素是否在該B-Trees中，若在就輸出它在節(jié)點的位置。圖2.1 主函數(shù)流程圖2.2 系統(tǒng)流程圖圖2.2 主程序流程圖B-樹的主程序流程如圖所示圖2.3 主程序流程圖3 詳細設(shè)計3.1 數(shù)據(jù)結(jié)構(gòu)B-樹的數(shù)據(jù)類型：typedef struct BTNode int keynum; /結(jié)點中關(guān)鍵字的個數(shù)，即結(jié)點的大小 struct

5、 BTNode *parent; /指向雙親指針int keym+1; /關(guān)鍵字向量struct BTNode *ptrm+1; /子樹指針向量BTNode 模塊設(shè)計B-樹插入新元素模塊如圖3.2所示。圖3.2 B-樹插入元素函數(shù)流程圖B-樹刪除元素模塊如圖3.3所示。圖3.3 B-樹刪除元素函數(shù)流程圖B-樹查找模塊如圖3.4所示。圖3.4 B-樹查找元素模塊流程圖B-樹查找模塊如圖3.4所示。圖 B-樹查找元素模塊流程圖4 測試圖表 4-1序號數(shù)據(jù)內(nèi)容說明顯示截圖13查找，要查元素在B-樹中25查找，要查元素不在B-樹中332插入，插入元素不在B樹中442插入，插入元素在B-樹中561刪除，

6、刪除元素在B-樹中651刪除，刪除元素不在B-樹中界面主菜單運行結(jié)果如圖4.1所示。圖4.1 主界面運行查詢B-樹中元素運行結(jié)果分兩種可能一是要查元素在B-樹中，另一種是不在。要查元素在B-樹中的運行結(jié)果如圖4.2所示。圖4.2 查找B-樹已有元素要查不在元素在B-樹中的運行結(jié)果如圖4.3所示。圖4.3 查找B-樹中沒有元素插入B-樹中元素運行結(jié)果分兩種可能一是要查元素在B-樹中，另一種是不在。要插入的元素在B-樹中的運行結(jié)果如圖4.4所示。圖4.4 插入B-樹已有元素要插入的元素不在B-樹中的運行結(jié)果如圖4.5所示。圖4.5 插入B-樹中沒有元素插入B-樹中元素運行結(jié)果分兩種可能一是要查元素

7、在B-樹中，另一種是不在。要刪除的元素在B-樹中的運行結(jié)果如圖4.6所示。圖4.6 刪除B-樹中已有元素要刪除的元素不在B-樹中的運行結(jié)果如圖4.7所示。圖4.7 刪除B-樹中沒有元素退出B-樹中元素的運行結(jié)果如圖4.8所示。圖4.8 退出運行主界面5 總結(jié)歷時兩周的課程設(shè)計終于結(jié)束了，對于課程設(shè)計：首先，關(guān)于程序方面，我發(fā)現(xiàn)即使對設(shè)計思路有了眉目，知道了所要用到的B-樹的一些知識，但是要把這些寫成函數(shù)代碼，其實還是一件非常不容易的事情。再加上要完善設(shè)計思路，構(gòu)造整個程序框架在內(nèi)，都是一件工作量非常大的工作。幸好，有很多資料可以在網(wǎng)路上搜到。所以課程設(shè)計的第一天，我們搜集了很多關(guān)于B-樹的資料

8、，包括幾種不同思路的程序代碼，以及程序流程。然后我們的工作就變成：盡量看懂并整理這些代碼，然后再其基礎(chǔ)上篩選需要的功能，按照自己的意愿來修改與完善。在操作界面的人性化上，我倒盡可能的做得很完善，無論從美觀角度還是方便清楚操作，都實行了非常人性化的方式。因為通常清楚程序的人，知道怎么操作以及該輸入什么，而不清楚的人卻有很大可能在細節(jié)方面輸入錯誤導(dǎo)致程序運行失敗，或是根本不知道應(yīng)該怎么輸入。所以，盡可能的人性化的設(shè)計是非常有必要的，讓不懂程序的人也可以正確的操作運行。在調(diào)試程序的過程中，遇到了許多常識性的問題，通過不斷的調(diào)試、改進，最終使程序能夠運行，并且得到正確的運行結(jié)果。在這個過程中，能夠不斷

9、地發(fā)現(xiàn)問題，并且自己獨立的去解決多遇到的問題，這是課程設(shè)計過程中所不可缺少的精神。 最后，做再次一下總結(jié)。程序方面仍有為解決的問題，希望即便課設(shè)之后也可以努力將問題解決掉。然后B-樹的算法中，有些知道怎么做卻很難清楚回答出來的問題，希望可以再好好的查找一下相關(guān)資料，將知識系統(tǒng)化、理論化、規(guī)范化。參考文獻1顧澤元，劉文強編.數(shù)據(jù)結(jié)構(gòu).北京：北京航空航天大學(xué)出版社，2011年. 2李素若，陳萬華，游明坤編.數(shù)據(jù)結(jié)構(gòu)（C語言描述），中國水利水電出版社，2014年.3李素若，陳萬華，游明坤編.數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及上機指導(dǎo)，中國水利水電出版社，2014年.4譚浩強編.C語言設(shè)計.清華大學(xué)出版社，2011年

10、. 附錄 源程序代碼#include #include #include #define m 4 /B-樹的階，設(shè)定為4 #define max 32767 typedef struct BTNode int keynum; /結(jié)點中關(guān)鍵字的個數(shù)，即結(jié)點的大小 struct BTNode *parent; /指向雙親指針int keym+1; /關(guān)鍵字向量struct BTNode *ptrm+1; /子樹指針向量BTNode,*BTree; /定義B-樹的節(jié)點結(jié)構(gòu)int data20=3,24,45,27,53,90,50,61,70,100,12,37,85,105,108,113,121

11、,124,138,135; BTree T,R,R1; int rag; BTree searchtree(int k) /查找建樹時要插入元素的位置 int j; BTree p1,q1; p1=T; while(p1) for(j=1;jkeyjk) break; q1=p1;p1=p1-ptrj-1; rag=j-1; return q1; void search(BTree p2,int a) int j; for(j=1;jkeyja) break; rag=j-1; void zimeau() /介紹菜單 printf(ttn); printf(tt菜單簡介n); printf(t

12、tn); printf(tt1.查詢結(jié)點信息n); printf(tt2.插入新的結(jié)點n); printf(tt3.刪除結(jié)點n); printf(tt4.退出n); printf(ttn); int searchbtree(int k) /查詢要查元素在樹中，若樹中有該元素則打印否則打印說明無 int i,found=0; BTree p; p=T; while(!found)&(p-ptr0!=NULL) for(i=1;im;i+) if(kkeyi) break; if(p-keyi=k) found=1; else p=p-ptri-1; if(p-ptr0=NULL) for(i=1

13、;im;i+) if(kkeyi) break; if(p-keyi=k) found=1; if(found=0) printf(tt此元素不在該B-樹中n); else printf(tt此元素元素在該B-樹中n); printf(tt該元素是B-樹中結(jié)點的第%d元素n,i); return found; void insertbtree(int x) /插入元素函數(shù) int j,finished,s; BTree q,p; finished=0; q=searchtree(x); /查找要插入元素在B-樹中的位置while(!finished) if(q-keynum=0) /當要插入的

14、元素所在結(jié)點是根節(jié)點,且為新申請的根結(jié)點 q-ptr0=p;q-ptr1=R;q-key1=x; q-keynum+;p-parent=q;R-parent=q; else if(q-keynum!=0)&(q-ptr0!=NULL)/當要插入的元素所在結(jié)點是中間的結(jié)點x for(j=3;jrag;j-) q-keyj+1=q-keyj;q-ptrj+1=q-ptrj; q-ptrj+1=R;R-parent=q;q-keyj+1=x;q-keynum+; else /當插入的元素所在結(jié)點是最下層的結(jié)點時 for(j=3;jrag;j-) q-keyj+1=q-keyj; q-keyj+1=x

15、;q-keynum+; finished=0; if(q-keynumkeys;q-keys=max;q-keynum=s-1; R=(BTNode*)malloc(sizeof(BTNode); /新申請一個結(jié)點來存放分裂的另一部分數(shù)據(jù)R-key1=q-keys+1; for(j=2;jkeyj=max;R-ptrj=NULL; R-ptr0=q-ptrs;R-ptr1=q-ptrs+1; R-keynum=1;q-keys+1=max;p=q;q=q-parent; if(!q) R1=(BTNode*)malloc(sizeof(BTNode); /新申請一個節(jié)點作為根節(jié)點T=q=R1;

16、 q-keynum=0;q-parent=NULL; for(j=1;jkeyj=max; for(j=0;jptrj=NULL; else search(q,x); /在一個結(jié)點中查找要插入元素的位置 void deletetree1(BTree q,int j) /當要刪除的節(jié)點是終端結(jié)點,j是要刪除元素是節(jié)點的地幾個元素 int i,h; BTree p,q0,q1; p=q-parent; for(h=0;hptrh=q) break; if(h=0) q1=p-ptrh+1; else q0=p-ptrh-1;q1=p-ptrh+1; if(q-keynum=m/2) /當節(jié)點的數(shù)目

17、不小于m/2 for(i=j;ikeyi=q-keyi+1; else if(q-keynumkeynum=2|q1-keynum=2) /當結(jié)點的數(shù)目少于m/2但其左兄弟或右兄弟的結(jié)點數(shù)目大于時 if(q1-keynum=m/2) /右兄弟時 q-keyj=p-keyh;p-keyh=q1-key0; for(i=0;ikeyi=q1-keyi+1; q1-keynum-; else /左兄弟時 q-keyj=p-keyh;p-keyh=q0-keyq0-keynum; q0-keyq0-keynum=q0-keyq0-keynum+1;q0-keynum-; else /當結(jié)點的數(shù)目少于m

18、/2且其左兄弟和右兄弟的結(jié)點數(shù)目小于時 if(h=0) /當該節(jié)點只有有兄弟時 q-key1=p-key1;q-key2=q1-key1;q-keynum=2;free(q1); for(i=1;ikeyi=p-keyi+1;p-keyi=p-keyi+1; p-keynum-; else /當該節(jié)點有左兄弟時 q-key1=p-keyh;q-key2=q0-key1;q-keynum=2;free(q0); for(i=1;ikeyi=p-keyi+1; p-ptri=p-ptri+1; p-keynum-; void deletetree2(BTree q,int j) /要插入節(jié)點是非終

19、端結(jié)點 BTree p; p=q; while(q-ptr0)/找終端結(jié)點q=q-ptrj; if(q-ptr0!=NULL) q=q-ptr0; q=q-parent;p-keyj=q-key1; deletetree1(q,1); void deletetree(int k) int i,found=0; BTree p; p=T; while(!found)&(p-ptr0!=NULL) /找到要插入節(jié)點的位置 for(i=1;im;i+) if(kkeyi) break; if(p-keyi=k) found=1; else p=p-ptri-1; if(p-ptr0=NULL) fo

20、r(i=1;im;i+) if(kkeyi) /找到要插入節(jié)點的位置break; if(p-ptr0=NULL) deletetree1(p,i); /當要刪除元素是終端結(jié)點else deletetree2(p,i); /當插入節(jié)點不是終端結(jié)點 int searchbtree1(int k) /查詢要刪除元素是否在樹中int i,found=0; BTree p; p=T; while(!found)&(p-ptr0!=NULL) for(i=1;im;i+) if(kkeyi) break; if(p-keyi=k)found=1; else p=p-ptri-1; if(p-ptr0=NU

21、LL) for(i=1;im;i+) if(kkeyi) break; if(p-keyi=k) found=1; /返回值，1代表該元素在B-樹中可以刪除否則無法刪除return found; int rumeau() /提供給讀者自己的選擇 int c; printf(tttt請輸入您的選擇：); scanf(%d,&c); return c; void meau() /菜單選項函數(shù) int a,b,rate; printf(tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn,3,3,3,3,3,3,3,

22、3,3,3,3,3,3,3,3,3,3,3,3,3,3,3); do zimeau(); printf(tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3); a=rumeau(); /子菜單switch(a) case 1:system(cls); printf(tt請輸入要查找的元素:); scanf(%d,&b); rate=searchbtree(b); /在B-樹中查找元素函數(shù)break; case 2:syst

23、em(cls); printf(tt請輸入要插入的元素:); scanf(%d,&b); rate=searchbtree(b); /查詢要插入的元素是否在該B-樹中if(rate=0) printf(tt該元素不在此B-樹中，故可插入之); insertbtree(b); /插入新元素函數(shù) else printf(tt該元素已在B-樹中，不需要再插入n); break; case 3:system(cls); printf(tt請輸入要刪除的元素:); scanf(%d,&b); rate=searchbtree1(b); if(rate=0) printf(tt由于該元素不在此B-樹中，故

24、無法刪除n); else printf(tt該元素在此B-樹中，可刪除n); deletetree(b); /刪除B-樹中的元素調(diào)用函數(shù) break; while(a!=4); void main() int x,i,finished,s,j; BTree q,p; system(color 1B); /背景顏色顯示函數(shù)T=(BTNode*)malloc(sizeof(BTNode);T-keynum=0; for(i=0;ikeyi+1=datai;T-keynum+; T-key4=max; for(i=0;iptri=NULL; T-parent=NULL; for(i=3;ikeynum=0