B-樹(shù)課程設(shè)計(jì)

1、課程設(shè)計(jì)成果 學(xué)院: 計(jì)算機(jī)工程學(xué)院 班 級(jí): 學(xué)生姓名: 學(xué) 號(hào): 設(shè)計(jì)地點(diǎn)（單位） 設(shè)計(jì)題目: B-樹(shù) 完成日期： 年 月 日 指導(dǎo)教師評(píng)語(yǔ): 成績(jī)(五級(jí)記分制): 教師簽名: 目 錄1 需求分析11.1 系統(tǒng)目標(biāo)11.2 主體功能11.3 開(kāi)發(fā)環(huán)境12概要設(shè)計(jì)12.1 功能模塊劃分12.2 系統(tǒng)流程圖23 詳細(xì)設(shè)計(jì)33.1 數(shù)據(jù)結(jié)構(gòu)33.2 模塊設(shè)計(jì)44 測(cè)試74.1測(cè)試數(shù)據(jù)74.2測(cè)試結(jié)果75 總結(jié)10參考文獻(xiàn)11附錄 源程序代碼121 需求分析1.1 系統(tǒng)目標(biāo)完成B-樹(shù)的創(chuàng)建、查找、插入和刪除。1.2 主體功能B-Trees是一類滿足特殊條件的M路查找樹(shù)，它滿足如下兩個(gè)條件的M路查找

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

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

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

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

6、 4.4442插入，插入元素在B-樹(shù)中圖 4.5561刪除，刪除元素在B-樹(shù)中圖 4.6651刪除，刪除元素不在B-樹(shù)中圖 4.74.2測(cè)試結(jié)果界面主菜單運(yùn)行結(jié)果如圖4.1所示。圖4.1 主界面運(yùn)行查詢B-樹(shù)中元素運(yùn)行結(jié)果分兩種可能一是要查元素在B-樹(shù)中，另一種是不在。要查元素在B-樹(shù)中的運(yùn)行結(jié)果如圖4.2所示。圖4.2 查找B-樹(shù)已有元素要查不在元素在B-樹(shù)中的運(yùn)行結(jié)果如圖4.3所示。圖4.3 查找B-樹(shù)中沒(méi)有元素插入B-樹(shù)中元素運(yùn)行結(jié)果分兩種可能一是要查元素在B-樹(shù)中，另一種是不在。要插入的元素在B-樹(shù)中的運(yùn)行結(jié)果如圖4.4所示。圖4.4 插入B-樹(shù)已有元素要插入的元素不在B-樹(shù)中的運(yùn)行結(jié)

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

8、的工作。幸好，有很多資料可以在網(wǎng)路上搜到。所以課程設(shè)計(jì)的第一天，我們搜集了很多關(guān)于B-樹(shù)的資料，包括幾種不同思路的程序代碼，以及程序流程。然后我們的工作就變成：盡量看懂并整理這些代碼，然后再其基礎(chǔ)上篩選需要的功能，按照自己的意愿來(lái)修改與完善。在操作界面的人性化上，我倒盡可能的做得很完善，無(wú)論從美觀角度還是方便清楚操作，都實(shí)行了非常人性化的方式。因?yàn)橥ǔＧ宄绦虻娜?，知道怎么操作以及該輸入什么，而不清楚的人卻有很大可能在細(xì)節(jié)方面輸入錯(cuò)誤導(dǎo)致程序運(yùn)行失敗，或是根本不知道應(yīng)該怎么輸入。所以，盡可能的人性化的設(shè)計(jì)是非常有必要的，讓不懂程序的人也可以正確的操作運(yùn)行。在調(diào)試程序的過(guò)程中，遇到了許多常識(shí)性的

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

10、及上機(jī)指導(dǎo)，中國(guó)水利水電出版社，2014年.4譚浩強(qiáng)編.C語(yǔ)言設(shè)計(jì).清華大學(xué)出版社，2011年. 20附錄 源程序代碼#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define m 4 /B-樹(shù)的階，設(shè)定為4 #define max 32767 typedef struct BTNode int keynum; /結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，即結(jié)點(diǎn)的大小 struct BTNode *parent; /指向雙親指針int keym+1; /關(guān)鍵字向量struct BTNode *ptrm+1; /子

11、樹(shù)指針向量BTNode,*BTree; /定義B-樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)int data20=3,24,45,27,53,90,50,61,70,100,12,37,85,105,108,113,121,124,138,135; BTree T,R,R1; int rag; BTree searchtree(int k) /查找建樹(shù)時(shí)要插入元素的位置 int j; BTree p1,q1; p1=T; while(p1) for(j=1;j<m;j+) if(p1->keyj>k) break; q1=p1;p1=p1->ptrj-1; rag=j-1; return q1; v

12、oid search(BTree p2,int a) int j; for(j=1;j<m;j+) if(p2->keyj>a) break; rag=j-1; void zimeau() /介紹菜單 printf("ttn"); printf("tt菜單簡(jiǎn)介n"); printf("ttn"); printf("tt1.查詢結(jié)點(diǎn)信息n"); printf("tt2.插入新的結(jié)點(diǎn)n"); printf("tt3.刪除結(jié)點(diǎn)n"); printf("t

13、t4.退出n"); printf("ttn"); int searchbtree(int k) /查詢要查元素在樹(shù)中，若樹(shù)中有該元素則打印否則打印說(shuō)明無(wú) int i,found=0; BTree p; p=T; while(!found)&&(p->ptr0!=NULL) for(i=1;i<m;i+) if(k<=p->keyi) break; if(p->keyi=k) found=1; else p=p->ptri-1; if(p->ptr0=NULL) for(i=1;i<m;i+) if(k

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

15、置while(!finished) if(q->keynum=0) /當(dāng)要插入的元素所在結(jié)點(diǎn)是根節(jié)點(diǎn),且為新申請(qǐng)的根結(jié)點(diǎn) 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)/當(dāng)要插入的元素所在結(jié)點(diǎn)是中間的結(jié)點(diǎn)x for(j=3;j>rag;j-) q->keyj+1=q->keyj;q->ptrj+1=q->ptrj; q->ptr

16、j+1=R;R->parent=q;q->keyj+1=x;q->keynum+; else /當(dāng)插入的元素所在結(jié)點(diǎn)是最下層的結(jié)點(diǎn)時(shí) for(j=3;j>rag;j-) q->keyj+1=q->keyj; q->keyj+1=x;q->keynum+; finished=0; if(q->keynum<m) /當(dāng)插入節(jié)點(diǎn)后，結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)小于m時(shí),插入新的元素完成finished=1; else /當(dāng)插入新的結(jié)點(diǎn)后，結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)不小于m時(shí)將結(jié)點(diǎn)分裂 s=m/2+1;x=q->keys;q->keys=max;q->

17、;keynum=s-1; R=(BTNode*)malloc(sizeof(BTNode); /新申請(qǐng)一個(gè)結(jié)點(diǎn)來(lái)存放分裂的另一部分?jǐn)?shù)據(jù)R->key1=q->keys+1; for(j=2;j<=m;j+) R->keyj=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); /新申請(qǐng)一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)T=

18、q=R1; q->keynum=0;q->parent=NULL; for(j=1;j<=m;j+) q->keyj=max; for(j=0;j<=m;j+) q->ptrj=NULL; else search(q,x); /在一個(gè)結(jié)點(diǎn)中查找要插入元素的位置 void deletetree1(BTree q,int j) /當(dāng)要?jiǎng)h除的節(jié)點(diǎn)是終端結(jié)點(diǎn),j是要?jiǎng)h除元素是節(jié)點(diǎn)的地幾個(gè)元素 int i,h; BTree p,q0,q1; p=q->parent; for(h=0;h<m;h+) if(p->ptrh=q) break; if(h=

19、0) q1=p->ptrh+1; else q0=p->ptrh-1;q1=p->ptrh+1; if(q->keynum>=m/2) /當(dāng)節(jié)點(diǎn)的數(shù)目不小于m/2 for(i=j;i<m;i+) q->keyi=q->keyi+1; else if(q->keynum<m/2)&&(q0->keynum>=2|q1->keynum>=2) /當(dāng)結(jié)點(diǎn)的數(shù)目少于m/2但其左兄弟或右兄弟的結(jié)點(diǎn)數(shù)目大于時(shí) if(q1->keynum>=m/2) /右兄弟時(shí) q->keyj=p->

20、keyh;p->keyh=q1->key0; for(i=0;i<m;i+) q1->keyi=q1->keyi+1; q1->keynum-; else /左兄弟時(shí) q->keyj=p->keyh;p->keyh=q0->keyq0->keynum; q0->keyq0->keynum=q0->keyq0->keynum+1;q0->keynum-; else /當(dāng)結(jié)點(diǎn)的數(shù)目少于m/2且其左兄弟和右兄弟的結(jié)點(diǎn)數(shù)目小于時(shí) if(h=0) /當(dāng)該節(jié)點(diǎn)只有有兄弟時(shí) q->key1=p->ke

21、y1;q->key2=q1->key1;q->keynum=2;free(q1); for(i=1;i<m;i+) p->keyi=p->keyi+1;p->keyi=p->keyi+1; p->keynum-; else /當(dāng)該節(jié)點(diǎn)有左兄弟時(shí) q->key1=p->keyh;q->key2=q0->key1;q->keynum=2;free(q0); for(i=1;i<m;i+) p->keyi=p->keyi+1; p->ptri=p->ptri+1; p->keynu

22、m-; void deletetree2(BTree q,int j) /要插入節(jié)點(diǎn)是非終端結(jié)點(diǎn) BTree p; p=q; while(q->ptr0)/找終端結(jié)點(diǎn)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é)點(diǎn)的位置 for

23、(i=1;i<m;i+) if(k<=p->keyi) break; if(p->keyi=k) found=1; else p=p->ptri-1; if(p->ptr0=NULL) for(i=1;i<m;i+) if(k<=p->keyi) /找到要插入節(jié)點(diǎn)的位置break; if(p->ptr0=NULL) deletetree1(p,i); /當(dāng)要?jiǎng)h除元素是終端結(jié)點(diǎn)else deletetree2(p,i); /當(dāng)插入節(jié)點(diǎn)不是終端結(jié)點(diǎn) int searchbtree1(int k) /查詢要?jiǎng)h除元素是否在樹(shù)中int i,fo

24、und=0; BTree p; p=T; while(!found)&&(p->ptr0!=NULL) for(i=1;i<m;i+) if(k<=p->keyi) break; if(p->keyi=k)found=1; else p=p->ptri-1; if(p->ptr0=NULL) for(i=1;i<m;i+) if(k<=p->keyi) break; if(p->keyi=k) found=1; /返回值，1代表該元素在B-樹(shù)中可以刪除否則無(wú)法刪除return found; int rumeau(

25、) /提供給讀者自己的選擇 int c; printf("tttt請(qǐng)輸入您的選擇："); scanf("%d",&c); return c; void meau() /菜單選項(xiàng)函數(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,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3); do zimeau(); printf("tt%c %c %c

26、%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請(qǐng)輸入要查找的元素:"); scanf("%d",&b); rate=searchbtree(b); /在B-樹(shù)中查找元素函數(shù)break; case 2:system("cls"

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

28、 scanf("%d",&b); rate=searchbtree1(b); if(rate=0) printf("tt由于該元素不在此B-樹(shù)中，故無(wú)法刪除n"); else printf("tt該元素在此B-樹(shù)中，可刪除n"); deletetree(b); /刪除B-樹(shù)中的元素調(diào)用函數(shù) break; while(a!=4); void main() int x,i,finished,s,j; BTree q,p; system("color 1B"); /背景顏色顯示函數(shù)T=(BTNode*)mallo

29、c(sizeof(BTNode);T->keynum=0; for(i=0;i<3;i+) T->keyi+1=datai;T->keynum+; T->key4=max; for(i=0;i<5;i+) T->ptri=NULL; T->parent=NULL; for(i=3;i<20;i+) x=datai;finished=0;q=searchtree(x); /查找要插入元素在B-樹(shù)中的位置while(!finished) if(q->keynum=0) /當(dāng)要插入的元素所在結(jié)點(diǎn)是根節(jié)點(diǎn),且為新申請(qǐng)的根結(jié)點(diǎn) q->ptr0=p;q->ptr1=R; q->key1=x;q->keynum+;p->parent=q;R->parent=q; else if(q->keynum!=0)&&(q-