B樹(shù)課程設(shè)計(jì)報(bào)告

1、課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告 課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目：B-樹(shù)算法的應(yīng)用 院（系）： 專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： I 目目 錄錄 1 需求分析需求分析.1 1.1 課程設(shè)計(jì)的內(nèi)容.1 1.2 B-樹(shù)的描述.1 2 概要設(shè)計(jì)概要設(shè)計(jì).2 2.1 總體設(shè)計(jì)思想 .2 2.2 局部模塊構(gòu)想 .2 2.2.1 查找關(guān)鍵字.2 2.2.2 將關(guān)鍵字插入結(jié)點(diǎn)，分裂結(jié)點(diǎn)，建立新的結(jié)點(diǎn)，建立 B-樹(shù).2 2.2.3 搜索指定結(jié)點(diǎn)，新建文件.2 3 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì).4 3.1 主函數(shù)設(shè)計(jì) .4 3.1.1 設(shè)計(jì)思想.4 3.1.

2、2 主流程圖.5 3.2 函數(shù)設(shè)計(jì).5 3.3 存儲(chǔ)結(jié)構(gòu).6 3.4 函數(shù)流程圖.7 4 運(yùn)行調(diào)試運(yùn)行調(diào)試.17 4.1 調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法.17 4.2 運(yùn)行結(jié)果 .17 4.3 結(jié)論分析 .18 參考文獻(xiàn)參考文獻(xiàn).19 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.20 1 1 需求分析 1.1 課程設(shè)計(jì)的內(nèi)容課程設(shè)計(jì)的內(nèi)容 編寫(xiě)算法能將學(xué)生信息保存到文件中，能夠?yàn)閷W(xué)生信息建立 B-樹(shù)索引， 并能夠利用 B-樹(shù)索引查找到指定學(xué)生的信息。建立 B-樹(shù)索引使用學(xué)號(hào)為關(guān) 鍵字。 （ B-樹(shù)中只含有學(xué)號(hào)和該記錄在文件中的位置信息） 要求： 1.1.B-樹(shù)的階可以選擇，要求給出一個(gè)

3、完整班的學(xué)生信息。 2.參考相應(yīng)資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。 3.3交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。 1.2 B-樹(shù)的描述樹(shù)的描述 B-樹(shù)是一種平衡的多路查找樹(shù)，它在文件系統(tǒng)中很有用。在此先介紹樹(shù)的 結(jié)構(gòu)。一棵 m 階的 B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M足下列特性的 m 叉樹(shù)： （1） 樹(shù)中每個(gè)結(jié)點(diǎn)至多有 m 棵子樹(shù)； （2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)； （3）除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)； （4） 所有非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù) （n,A0，K1,A1,K2,A2,Kn,An） 其中：Ki(i=1,n)為關(guān)鍵字，且 KiKi+1(i=1,n-1);Ai(i=0,n) 為指向

4、子樹(shù)根結(jié)點(diǎn)的指針，且指針 Ai-1 所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均 小于 Ki(i=1,n),An 所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均大于 Kn,n(m/2 -1=nnum 否 開(kāi)始 是 否 返回i-1 k小于p-keyi i加1 結(jié)束 是 圖 3-4 SearchNode()函數(shù)流程圖 實(shí)現(xiàn)過(guò)程：如圖 2.1.2(a)所示，SearchNode()函數(shù)代入的參數(shù)是指向關(guān)鍵字可 能所在節(jié)點(diǎn)的指針 p 和關(guān)鍵字 k，從該節(jié)點(diǎn)的第一個(gè)關(guān)鍵字找起，依次將要查找 的關(guān)鍵字與節(jié)點(diǎn)中的關(guān)鍵字比較，返回結(jié)果是所給關(guān)鍵字應(yīng)該在節(jié)點(diǎn)中的位置。 3.4.3 B-樹(shù)查找函數(shù)樹(shù)查找函數(shù) 函數(shù)名稱(chēng)：SearchBTree()

5、功能：從 B-樹(shù)的根節(jié)點(diǎn)開(kāi)始查找，查找所給關(guān)鍵字在該 B-樹(shù)中的節(jié)點(diǎn)位置 以及在所在節(jié)點(diǎn)中的位置，該函數(shù)返回結(jié)果為 Result 類(lèi)型，result.i表示關(guān)鍵字 在節(jié)點(diǎn)中應(yīng)該插入的位置，result.pt 表示關(guān)鍵字應(yīng)該所在的節(jié)點(diǎn)，result.tag表 示是否能夠在 B-樹(shù)中查找到該關(guān)鍵字。 10 賦初值：found=0；i=1 p不為空且found=0 否 開(kāi)始 是 調(diào)用函數(shù)SearchNode，查找應(yīng) 該插入的節(jié)點(diǎn)p以及插入位置i 否 賦值：result.pt=p; result.i=i;result.tag=1; found=1 賦值：result.pt=q; result.i=i;

6、result.tag=0; 結(jié)束 是 圖 3-5 SearchBTree()函數(shù)流程圖 實(shí)現(xiàn)過(guò)程：如圖 2.1.2(b)所示，代入 B-樹(shù)的根節(jié)點(diǎn)指針和要查找的關(guān)鍵字， 從根節(jié)點(diǎn)開(kāi)始，對(duì)每個(gè)節(jié)點(diǎn)使用 SearchNode()函數(shù)，查找所給關(guān)鍵字所在的節(jié)點(diǎn) 以及在該節(jié)點(diǎn)中的位置，如果該關(guān)鍵字已經(jīng)存在于 B-樹(shù)中，則返回關(guān)鍵字所在節(jié) 點(diǎn)、以及所在序號(hào)以及查找到的標(biāo)志；如果不存在，則返回應(yīng)該插入的節(jié)點(diǎn)指針、 在節(jié)點(diǎn)中的序號(hào)以及沒(méi)有找到的標(biāo)志。 3.4.4 節(jié)點(diǎn)插入函數(shù)節(jié)點(diǎn)插入函數(shù) 函數(shù)名：Insert() 函數(shù)功能：將所給關(guān)鍵字插入到正確節(jié)點(diǎn)的正確位置 11 j減1 結(jié)束 j大于i 賦初值：j=q-

7、keynum 否 開(kāi)始 q-keyj后移，q-ptrj后移 是 ap=NULL 否 否 賦值：ap-parent=q 賦值q-keyi+1=x;q-ptri+1=ap; q-num加1 圖 3-6 Insert()函數(shù)流程圖 實(shí)現(xiàn)過(guò)程：如圖 2.1.2(c)所示，代入指向所給關(guān)鍵字應(yīng)該插入節(jié)點(diǎn)的指針、所 給關(guān)鍵字、關(guān)鍵字應(yīng)該插入的位置，然后再將該關(guān)鍵字插入到節(jié)點(diǎn)的正確位置上， 節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)加 1，返回指向該節(jié)點(diǎn)的指針 q。 3.4.5 節(jié)點(diǎn)分裂函數(shù)節(jié)點(diǎn)分裂函數(shù) 函數(shù)名：split() 12 函數(shù)功能：當(dāng)節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)不符合要求時(shí)，進(jìn)行節(jié)點(diǎn)分裂 賦初值：ap-ptr0=q-ptrs; 結(jié)束

8、將q節(jié)點(diǎn)中序號(hào)大于s的關(guān)鍵 字和指針插入到新建節(jié)點(diǎn)ap 開(kāi)始 賦值：ap-keynum=q-keynum-s; ap-parent=q-parent; 賦值：q-keyq-keynum=0;q-keynum=s-1; 返回ap 將ap中子樹(shù)指針父節(jié)點(diǎn)指向ap 圖 3-7 split()函數(shù)流程圖 實(shí)現(xiàn)過(guò)程：如圖 2.1.2(d)所示，該函數(shù)帶入的參數(shù)是指向要產(chǎn)生分裂的節(jié)點(diǎn)的 指針 q、節(jié)點(diǎn)最小子樹(shù)個(gè)數(shù) s 以及空指針 ap，首先給 ap 分配 BTree 類(lèi)型的空間， 然后再將 q 中序號(hào)大于 s 的關(guān)鍵字插入到 ap 節(jié)點(diǎn)中，同時(shí)紙箱子樹(shù)的指針也插入 到 ap 中，然后再分別計(jì)算 q 和 a

9、p 中的關(guān)鍵字個(gè)數(shù)，對(duì) q 和 ap 進(jìn)行處理。最后返 回 ap 指針。 3.4.6 節(jié)點(diǎn)建立函數(shù)節(jié)點(diǎn)建立函數(shù) 13 函數(shù)名：NewRoot() 函數(shù)功能：建立新的節(jié)點(diǎn)，并且返回指向該節(jié)點(diǎn)的指針。 結(jié)束 是 給T分配空間 開(kāi)始 返回T 是 賦值：p-parent=T 賦值：T-parent=NULL p！=NULL 否 否 賦值：T-keynum=1; T-ptr0=p; T-ptr1=ap; T-key1=x; ap！=NULL 賦值：ap-parent=T 圖 3-8 NewRoot()函數(shù)流程圖 實(shí)現(xiàn)過(guò)程：如圖 2.1.2(e)所示，該函數(shù)的代入?yún)?shù)是根節(jié)點(diǎn) T、指向子樹(shù)的指 針 p 和

10、 ap 以及關(guān)鍵字 x，創(chuàng)建這個(gè)新節(jié)點(diǎn)，需要將關(guān)鍵字插入到該節(jié)點(diǎn)序號(hào) 1 的 位置上，0 號(hào)和 1 號(hào)的子樹(shù)指針?lè)謩e指向空。如果 p 和 ap 不為空，則它們的父節(jié) 點(diǎn)指向 T 節(jié)點(diǎn)。該函數(shù)最后返回的是指針 T。 3.4.7 B-樹(shù)建立函數(shù)樹(shù)建立函數(shù) 14 函數(shù)名：InsertBTree() 函數(shù)功能：從空樹(shù)開(kāi)始建立 B-樹(shù)，返回的是 B-樹(shù)的根指針。 賦值：x=K; ap=NULL; finished=needNewRoot=0; 調(diào)用函數(shù)Insert，將返回值賦給q 結(jié)束 是 是 否 否 q為空 開(kāi)始 返回T Finshed=0且 needNewRoot=0 是 q-numptri-1;

11、ikeynum 是 是 kptri-1！=NULL 否 賦值：p=p-ptri-1; 調(diào)用函數(shù)found，將返回值賦給i p-ptri-1！=NULL 否 圖 3-10 found()函數(shù)流程圖 16 函數(shù)功能：查找指指定關(guān)鍵字，查找成功則返回在所在節(jié)點(diǎn)的序號(hào)，否則返 回-1。 實(shí)現(xiàn)過(guò)程：如圖 2.1.2(g)所示，該函數(shù)代入?yún)?shù)是 B-樹(shù)根節(jié)點(diǎn)指針 t 以及關(guān) 鍵字 k，從根節(jié)點(diǎn)開(kāi)始查找，如果查找到返回 i 值否則返回-1，在查找過(guò)程中低軌 調(diào)用函數(shù) found()進(jìn)行查找。 3.4.9 文件隨機(jī)讀寫(xiě)輸出函數(shù)文件隨機(jī)讀寫(xiě)輸出函數(shù) 函數(shù)名：fseek() 功能：將位置指針按需要移動(dòng)到任意位置，

12、實(shí)現(xiàn)隨即讀寫(xiě)功能。 結(jié)束 是 開(kāi)始 否 索引過(guò)程是否結(jié)束 fseek(fp,i*sizeof( struct student),0)_函數(shù) 輸出相應(yīng)學(xué)生信 息 輸入待查找學(xué)生 信息對(duì)應(yīng)的學(xué)號(hào) 圖 3-11 fseek()函數(shù)流程圖 實(shí)現(xiàn)過(guò)程: 需要查找學(xué)生相關(guān)信息時(shí)，只需輸入對(duì)應(yīng)的學(xué)生學(xué)號(hào)，利用 fseek()函數(shù)，將文件指針指到相應(yīng)內(nèi)存處，將所有該學(xué)生信息全部顯示出來(lái)，完 成索引過(guò)程。 17 4 運(yùn)行調(diào)試 4.1 調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法 在調(diào)試程序的過(guò)程中，遇到的問(wèn)題有多種，但是集中表現(xiàn)為語(yǔ)句錯(cuò)誤、邏輯 錯(cuò)誤、參數(shù)未定義等方面。針對(duì)該算法中的這些問(wèn)題，進(jìn)

13、行了具體分析，找到了 正確的解決辦法。 4.1.1 語(yǔ)句錯(cuò)誤語(yǔ)句錯(cuò)誤 問(wèn)題：missing ; before ；括號(hào)匹配不正確 分析：這種問(wèn)題在編譯時(shí)最容易體現(xiàn)出來(lái)，因?yàn)槿绻霈F(xiàn)這種錯(cuò)誤，系統(tǒng)會(huì) 進(jìn)行提示。產(chǎn)生這種問(wèn)題的原因是輸入代碼時(shí)疏忽，或是代入?yún)?shù)的類(lèi)型與定義 類(lèi)型布匹配。如：定義 BTree 類(lèi)型的指針 p，引用的是 struct BTNode *parent; int keym+1; struct BTNode *ptrm+1; int locationm+1; BTNode,*BTree; typedef struct BTNode *pt; 21 int i; int tag;

14、Result; struct student int num; char name10; int score; stdn; int an,bn; /在結(jié)點(diǎn)中查找關(guān)鍵字 int SearchNode(BTree p,int k) int i=1; while(ikeynum) if(kkeyi) return i-1; else if(k=p-keyi) return -1; else i+; 22 return i-1; /在 B 樹(shù)中查找關(guān)鍵字 k Result SearchBTree(BTree t,int k)/t 為 B 樹(shù)根節(jié)點(diǎn) BTree p=t,q=NULL; int found

15、=0; int i=0; Result result; while(p if(i=-1) result.pt=p; result.i=i; result.tag=1; return result; while(p-ptri) 23 p=p-ptri; i=SearchNode(p,k); if(i0 else q=p; p=p-ptri; if(found) result.pt=p; result.i=i; result.tag=1; else result.pt=q; 24 result.i=i; result.tag=0; return result; /將關(guān)鍵字插入節(jié)點(diǎn) BTree In

16、sert(BTree q,int i,int x,BTree ap,int l) / insert the key X between the keyi and keyi+1 / at the pointer node q int j; for(j=q-keynum;ji;j-) q-keyj+1=q-keyj; q- location j+1=q- location j; q-ptrj+1=q-ptrj; q-keyi+1=x; q-ptri+1=ap; q- location i+1=l; if(ap) 25 ap-parent=q; q-keynum+; return q; /分裂節(jié)點(diǎn)

17、BTree split(BTree q,int s,BTree ap) /move keys+1.m,p-ptrs.m int the new pointer *ap int i,j; ap=(BTree)malloc(sizeof(BTNode); ap-ptr0=q-ptrs; for(i=s+1,j=1;ikeynum;i+,j+) ap-keyj=q-keyi; ap-ptrj=q-ptri; ap- location j=q- location i; ap-keynum=q-keynum-s; ap-parent=q-parent; for(i=0;ikeynum-s;i+) if(

18、ap-ptri) 26 ap-ptri-parent=ap; q-keyq-keynum=0; q- location q-keynum=0; q-keynum=s-1; return ap; /建立新的節(jié)點(diǎn) BTree NewRoot(BTree T,BTree p,int x,BTree ap,int z) T=(BTree)malloc(sizeof(BTNode); T-keynum=1; T-ptr0=p; T-ptr1=ap; T-key1=x; T- location 1=z; if(p) p-parent=T; if(ap) ap-parent=T; T-parent=NULL

19、; return T; 27 /建立 B-樹(shù) BTree InsertBTree(BTree T,int K,BTree q,int i,int l) / 在 m 階 B 樹(shù) T 上結(jié)點(diǎn)*q 的 keyi與 keyi+1之間插入關(guān)鍵字 K。 / 若引起結(jié)點(diǎn)過(guò)大，則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整，使 T 仍是 m 階 B 樹(shù)。 BTree ap; int finished, needNewRoot, s; int x; if(!q) / T 是空樹(shù)(參數(shù) q 初值為 NULL) T=NewRoot(T,NULL,K,NULL,l); / 生成僅含關(guān)鍵字 K 的根結(jié)點(diǎn)*T else x=K; ap

20、=NULL; finished=needNewRoot=0; while(!needNewRoot / 將 x 和 ap 分別插入到 q-keyi+1和 q- ptri+1 if(q-keynumkeys+1.m, q-ptrs.m和 / q- location s+1.m移入新結(jié)點(diǎn)*ap s=(m+1)/2; ap=split(q,s,ap); x=q-keys; l=q- location s; q-locations=0; q-keys=0; if(q-parent) / 在雙親結(jié)點(diǎn)*q 中查找 x 的插入位置 q=q-parent; i=SearchNode(q, x); else n

21、eedNewRoot=1; / else / while if(needNewRoot) / 根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)*q 和*ap T=NewRoot(T,q,x,ap,l); / 生成新根結(jié)點(diǎn)*T,q 和 ap 為子樹(shù)指針 return T; / InsertBTree 29 int found(BTree MT,int k) /查找關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)位置 int i; BTree p=MT; while(p!=NULL) i=1; while(kp-keyi if(k=p-keyi) return p- location i; else if(kp-keyi) p=p-ptri; else

22、if(kkeyi) p=p-ptri-1; return -1; void savestud(FILE *fout) /存 儲(chǔ)信息 30 int i; if (fout=fopen(E:xuesheng.txt,wb)=NULL) printf(can not open filen); exit(0); for(i=0;in;i+) scanf(%d%s%d, ai=stdi.num; bi=i; fwrite( fclose(fout); void readstud(FILE *fin,int j) /讀取 信息的 int i; fin=fopen(E:xuesheng.txt,rb); f

23、seek(fin,sizeof(struct student),0); fseek(fin,-sizeof(struct student),1); 31 for(i=1;i=j;i+) fseek(fin,sizeof(struct student),1); fread( printf(學(xué)號(hào) 姓名 成績(jī)n); printf(%-6d%-10s%6dn,std0.num,,std0.score); fclose(fin); /中序遍歷 B 樹(shù) void PrintBTree(BTree t) if(t) int i=1; while(ikeynum) PrintBTree(t-

24、ptri-1); printf(%dn,t-keyi); i+; 32 PrintBTree(t-ptri-1); void main() FILE *f1; BTree root=NULL; Result result; int i,x,arrayn; int en,h; printf(輸入學(xué)生信息n); savestud(f1); for(i=0;in;i+) arrayi=ai; ei=bi; for(i=0;in;i+) result=SearchBTree(root,arrayi); /尋找關(guān)鍵字在 B 樹(shù)中應(yīng)該 插入的位置 root=InsertBTree(root,arrayi,resul