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

1、課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱(chēng)： 數(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)教師：1 需求分析 11.1 課程設(shè)計(jì)的內(nèi)容11.2 B-樹(shù)的描述12 概要設(shè)計(jì) 22.1 總體設(shè)計(jì)思想 22.2 局部模塊構(gòu)想 22.2.1 查找關(guān)鍵字 22.2.2 將關(guān)鍵字插入結(jié)點(diǎn)，分裂結(jié)點(diǎn)，建立新的結(jié)點(diǎn)，建立B-樹(shù)22.2.3 搜索指定結(jié)點(diǎn)，新建文件23 詳細(xì)設(shè)計(jì) 43.1 主函數(shù)設(shè)計(jì)43.1.1 設(shè)計(jì)思想 43.1.2 主流程圖 53.2 函數(shù)設(shè)計(jì) 53.3 存儲(chǔ)結(jié)構(gòu) 63.4 函數(shù)流程圖 74 運(yùn)行調(diào)試 174.1 調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法 174

2、.2 運(yùn)行結(jié)果 174.3 結(jié)論分析 18參考文獻(xiàn) 19附錄（關(guān)鍵部分程序清單） 201 需求分析1.1 課程設(shè)計(jì)的內(nèi)容編寫(xiě)算法能將學(xué)生信息保存到文件中，能夠?yàn)閷W(xué)生信息建立B-樹(shù)索弓I,并能夠利用B-樹(shù)索引查找到指定學(xué)生的信息。建立B-樹(shù)索引使用學(xué)號(hào) 為關(guān)鍵字。 ( B- 樹(shù)中只含有學(xué)號(hào)和該記錄在文件中的位置信息)要求：1. 1.B-樹(shù)的階可以選擇，要求給出一個(gè)完整班的學(xué)生信息。2. 參考相應(yīng)資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。3. 3交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。1.2 B- 樹(shù)的描述B-樹(shù)是一種平衡的多路查找樹(shù)，它在文件系統(tǒng)中很有用。在此先介紹樹(shù)的 結(jié)構(gòu)。一棵m階的B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M(mǎn)足下列特

3、性的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)鍵字，且 Ki<Ki+1(i=1,n-1);Ai(i=0,n)為指向子樹(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<=n<=m-1) 為關(guān)鍵字的個(gè)數(shù)(或n+1 為子樹(shù)個(gè)數(shù)) 。( 5) 所有的葉子結(jié)點(diǎn)都

4、出現(xiàn)在同一層次上，并且不帶信息(可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)實(shí)際上這些結(jié)點(diǎn)根本不存在，指向這些結(jié)點(diǎn)的指針為空) 。2 概要設(shè)計(jì)2.1 總體設(shè)計(jì)思想首先將學(xué)生信息從鍵盤(pán)鍵入存到指定的文件中，在此每當(dāng)輸入一個(gè)學(xué)生的信息，對(duì)應(yīng)學(xué)生信息的學(xué)號(hào)將作為B-樹(shù)的關(guān)鍵字，連同一起的該記錄在文件中的信 息這兩部分作為結(jié)點(diǎn)插入到 B-樹(shù)中，插入的過(guò)程也就是建立B-樹(shù)的過(guò)程，其中B-樹(shù)的階m在開(kāi)始的時(shí)候已經(jīng)確定了，當(dāng)結(jié)點(diǎn)中的關(guān)鍵字的個(gè)數(shù)大于m-1時(shí)就開(kāi)始分裂，并生成新的結(jié)點(diǎn)，按此規(guī)律即能建立好B-樹(shù)，程序運(yùn)行時(shí)只須輸入任意學(xué)生的學(xué)號(hào)，然后屏幕上將顯示此學(xué)號(hào)對(duì)應(yīng)的學(xué)生的全部信息，由此即完成課程設(shè)計(jì)要求。2.2

5、局部模塊構(gòu)想2.2.1 查找關(guān)鍵字分別從結(jié)點(diǎn)中，B-樹(shù)中查找關(guān)鍵字K,因?yàn)橐虢?shù)，就要插入結(jié)點(diǎn)，插入結(jié)點(diǎn)要先檢驗(yàn)一下此時(shí)樹(shù)中有沒(méi)有次結(jié)點(diǎn)， int SearchNode(BTree p,int k) 函數(shù) 和 Result SearchBTree(BTree t,int k) 函數(shù)實(shí)現(xiàn)了查找功能。2.2.2 將關(guān)鍵字插入結(jié)點(diǎn)，分裂結(jié)點(diǎn)，建立新的結(jié)點(diǎn)，建立 B-樹(shù) 在將關(guān)鍵字插入結(jié)點(diǎn)時(shí)，由于階樹(shù)m經(jīng)決定了，當(dāng)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于m-1 時(shí)就要分裂此結(jié)點(diǎn)，第 m/2 個(gè)結(jié)點(diǎn)被提升到上一結(jié)點(diǎn)，與此同時(shí)原結(jié)點(diǎn)中關(guān) 鍵字前面的關(guān)鍵字還繼續(xù)在此結(jié)點(diǎn)中，關(guān)鍵字之后的關(guān)鍵字需要存儲(chǔ)到新生成的結(jié)點(diǎn)中，這樣逐

6、個(gè)結(jié)點(diǎn)才能順利插入到B-樹(shù)中。即此時(shí)的B-樹(shù)已經(jīng)建立好了。2.2.3 搜索指定結(jié)點(diǎn)，新建文件B-樹(shù)索引過(guò)程就是搜索指定關(guān)鍵字的過(guò)程，從根結(jié)點(diǎn)開(kāi)始，向子樹(shù)結(jié)點(diǎn)中的 關(guān)鍵字查找， 當(dāng)查找時(shí)即返回此時(shí)文件指針fp 當(dāng)前位置， 假如查找失敗， 就繼續(xù)查找，直到找到根結(jié)點(diǎn)為止，倘若還沒(méi)查找到就返回沒(méi)有找到。我們需要把學(xué)生的相關(guān)信息從鍵盤(pán)輸入到指定文件中，其中包括學(xué)生的姓名，學(xué)號(hào)和家庭地址等信息，在利用文件中的 fseek 函數(shù)，使文件指針指向?qū)W生的相應(yīng)信息位置，定義為整型，與結(jié)點(diǎn)中學(xué)生信息在文件中的位置信息相對(duì)應(yīng)，運(yùn)行時(shí)只需要輸入學(xué)生學(xué)號(hào)，屏幕上會(huì)顯示相應(yīng)的學(xué)生完整信息，此時(shí)索引過(guò)程完成。3 詳細(xì)設(shè)計(jì)3

7、.1 主函數(shù)設(shè)計(jì)3.1.1 設(shè)計(jì)思想B-樹(shù)算法的實(shí)現(xiàn)，首先應(yīng)該建立一個(gè)m階的B-樹(shù)(在本算法中m設(shè)為5)。在 建立B-樹(shù)過(guò)程中，首先輸入一個(gè)關(guān)鍵字學(xué)生學(xué)號(hào)序列(為方便起見(jiàn)本算法使用整 數(shù)序列，關(guān)鍵字個(gè)數(shù)設(shè)定為10) ，將這個(gè)整數(shù)序列存入數(shù)組中，然后從空樹(shù)開(kāi)始，依次將關(guān)鍵字插入B-樹(shù)中，建立一個(gè)m階的B-樹(shù)。(在輸入學(xué)生信息的同時(shí)只是 將學(xué)生學(xué)號(hào)作為關(guān)鍵字存入文件中)建樹(shù)過(guò)程中，每插入一個(gè)關(guān)鍵字，首先應(yīng)該判斷出這個(gè)關(guān)鍵字在B-樹(shù)中應(yīng)該插入的位置，需要調(diào)用 SearchBTree()和SearchNode()兩個(gè)函數(shù)共同配合完成；然后調(diào)用InsertBTree() 和Insert() 函數(shù)進(jìn)行插入

8、，插入完成后，應(yīng)該看該節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)是否小于B-樹(shù)的階數(shù)m,當(dāng)節(jié)點(diǎn)中插入的關(guān)鍵字個(gè)數(shù)不符合要求時(shí)，應(yīng)該考慮節(jié)點(diǎn)分裂的情況(根節(jié)點(diǎn)和子 樹(shù)節(jié)點(diǎn)的情況都應(yīng)該考慮到，如果有節(jié)點(diǎn)分裂的情況，應(yīng)該進(jìn)行節(jié)點(diǎn)分裂，可以建立一個(gè) split() 函數(shù)來(lái)實(shí)現(xiàn)這個(gè)功能；如果需要建立新的根節(jié)點(diǎn)，需要建立一個(gè)NewRoot()函數(shù)來(lái)完成這個(gè)功能。B-樹(shù)建立成功后，返回指向該 B-樹(shù)根節(jié)點(diǎn)的 指針。該算法要求具有查找任一指定學(xué)生信息的功能，可以輸入任意一個(gè)學(xué)生的學(xué)號(hào)，在B-樹(shù)中查找該關(guān)鍵字，看該關(guān)鍵字是否存在在該 B-樹(shù)，如果存在，則返回 該關(guān)鍵字對(duì)應(yīng)的學(xué)生完整信息，否則查找不成功，則該學(xué)號(hào)所對(duì)應(yīng)的關(guān)鍵字不在該B-樹(shù)

9、中，以上即完成B-樹(shù)索引過(guò)程。3.1.2 主流程圖(結(jié)束)圖3-1主函數(shù)流程圖3.2 函數(shù)設(shè)計(jì)在該算法中，設(shè)計(jì)了一個(gè) main()主函數(shù)和10個(gè)子函數(shù)，通過(guò)主函數(shù)調(diào)用子 函數(shù)、子函數(shù)相互調(diào)用，完成設(shè)計(jì)要求的B-樹(shù)的建立、在B-樹(shù)中查找指定節(jié)點(diǎn)(該 算法中查找具體的關(guān)鍵字位置)、B-樹(shù)的遍歷以及輸出遍歷序列等功能。3.2.1 函數(shù)在該算法中涉及到的各個(gè)函數(shù)的中文和英文名稱(chēng)分別為：主函數(shù)main()、節(jié)點(diǎn)查找函數(shù)SearchNode()、B-樹(shù)查找函數(shù)SearchBTree()、節(jié)點(diǎn)插入函數(shù)Inset()、 節(jié)點(diǎn)分裂函數(shù)split()、節(jié)點(diǎn)建立函數(shù)NewRoot()、B-樹(shù)插入函數(shù)InsertBT

10、ree()、 查找函數(shù)found()、中序遍歷輸出函數(shù) PrintBTree()、文件寫(xiě)函數(shù)savestud ()、 文件讀取函數(shù)readstud ()。3.2.2函數(shù)調(diào)用關(guān)系圖3.2.2 函數(shù)調(diào)用關(guān)系說(shuō)明主函數(shù)里面包含四個(gè)函數(shù)，即主函數(shù)中需調(diào)用四個(gè)函數(shù)分別為 SearchBTree()、InsertBTree() 、found()、PrintBTree();執(zhí)行 SearchBTree() 函數(shù)時(shí)需調(diào)用 SearchNode()函數(shù)；執(zhí)行InsertBTree() 函數(shù)時(shí)，需要調(diào)用 SearchNode()、NewRoot()、Insert() 以及 split() 函數(shù)；執(zhí)行 found(

11、)函數(shù)時(shí)， 要用到遞歸調(diào)用found()函數(shù)；執(zhí)行 PrintBTree()函數(shù)時(shí)，也要用到遞歸調(diào)用 PrintBTree()函數(shù)。3.3 存儲(chǔ)結(jié)構(gòu)在該設(shè)計(jì)的算法中，定義B-樹(shù)中節(jié)點(diǎn)類(lèi)型、B-樹(shù)類(lèi)型以及查找結(jié)果類(lèi)型如下#define m 3/B-typedef struct BTNodeint keynum;/struct BTNode *parent; /int keym+1;/樹(shù)的階，暫定為3節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)指向雙親節(jié)點(diǎn)關(guān)鍵字向量，0號(hào)單元未用struct BTNode *ptrm+1; /BTNode,*BTree;/B-typedef structBTNode *pt;/int i;/

12、int tag;/1Result;/B-3.4 函數(shù)流程圖子樹(shù)指針向量樹(shù)節(jié)點(diǎn)和B-樹(shù)的類(lèi)型指向找到的節(jié)點(diǎn)在節(jié)點(diǎn)中的關(guān)鍵字序號(hào)：查找成功，0：查找失敗樹(shù)的查找結(jié)果類(lèi)型在這部分中，將每個(gè)函數(shù)分別用流程圖表示出來(lái)，并且將每個(gè)函數(shù)的功能以及實(shí)現(xiàn)過(guò)程詳細(xì)的表述出來(lái)，使得能夠更加清晰、有條理體現(xiàn)出該算法。3.4.1 函數(shù)調(diào)用關(guān)系說(shuō)明函數(shù)名： main()函數(shù)功能：輸入關(guān)鍵字序列，調(diào)用 B-樹(shù)建立函數(shù)、查找函數(shù)、遍歷輸出函數(shù)實(shí)現(xiàn)過(guò)程：如圖 2.1.1 所示，輸入一個(gè)關(guān)鍵字序列，存儲(chǔ)到數(shù)組中。對(duì)于數(shù)組中每個(gè)學(xué)號(hào)關(guān)鍵字，首先調(diào)用函數(shù)SearchBTree() ，找出該關(guān)鍵字應(yīng)該插入的位置，然后調(diào)用函數(shù)Inser

13、tBTree(),將關(guān)鍵字依次插入B-樹(shù)中，插入完成后，返 回指向B-樹(shù)的根節(jié)點(diǎn)指針。然后按照要求輸入要查找的學(xué)號(hào)關(guān)鍵字，調(diào)用found() 函數(shù)進(jìn)行查找， 返回查找結(jié)果 (可進(jìn)行循環(huán)輸入查找) 。 并將查找的學(xué)號(hào)所對(duì)應(yīng)的學(xué)生完整信息輸出在屏幕上。完成索引過(guò)程。開(kāi)始圖3-3主函數(shù)流程圖3.4.2 節(jié)點(diǎn)查找函數(shù)函數(shù)名：SearchNode()功能：在節(jié)點(diǎn)中查找關(guān)鍵字，返回該關(guān)鍵字在節(jié)點(diǎn)中的位置圖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)鍵字找起，依次將要查 找

14、的關(guān)鍵字與節(jié)點(diǎn)中的關(guān)鍵字比較，返回結(jié)果是所給關(guān)鍵字應(yīng)該在節(jié)點(diǎn)中的位置。3.4.3 B-樹(shù)查找函數(shù)函數(shù)名稱(chēng)：SearchBTree()功能：從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)鍵字實(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)中的位置，如果

15、該關(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ù)函數(shù)名：Insert()函數(shù)功能：將所給關(guān)鍵字插入到正確節(jié)點(diǎn)的正確位置L開(kāi)始'：賦初值：j=q->keynumjo_j 大于 i 二是q->keyj后移，q->ptrj后移j減11 J賦 值 q->keyi+1=x;q->ptri+1=ap一工一五ap=NULL 丁巨賦值：ap->parent=qq->nunmj 口 1結(jié)束：；圖3-6 Insert()函數(shù)流程圖實(shí)

16、現(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ù)函數(shù)名:split()函數(shù)功能：當(dāng)節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)不符合要求時(shí)，進(jìn)行節(jié)點(diǎn)分裂賦初值:ap->ptr0=q->ptrs;將q節(jié)點(diǎn)中序號(hào)大刪關(guān)鍵 字和指針插入到新建廊點(diǎn)賦值:ap->keynum=q->keynum-s;ap->parent=q->parent;將a葉子樹(shù)指專(zhuān)t父節(jié)點(diǎn)指向賦值：q->keyq->keynum=0;q-&g

17、t;keynum=s-1;結(jié)束圖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和ap中的關(guān)鍵字個(gè)數(shù)，對(duì)q和ap進(jìn)行處理。最后返 回ap指針。3.4.6 節(jié)點(diǎn)建立函數(shù)函數(shù)名：NewRoot()函數(shù)功能：建立新的節(jié)點(diǎn)，并且返回指向該節(jié)點(diǎn)的指針。:開(kāi)始,；圖3-8 NewRoot()函數(shù)流程圖實(shí)現(xiàn)過(guò)程：如圖2.1.2(e)所示，該函數(shù)的代入?yún)?shù)是根節(jié)點(diǎn)T、指向

18、子樹(shù)的指針p和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ù)最后返回的是指針 T3.4.7 B-樹(shù)建立函數(shù)函數(shù)名：InsertBTree()函數(shù)功能：從空樹(shù)開(kāi)始建立 B-樹(shù)，返回的是B-樹(shù)的根指針實(shí)現(xiàn)過(guò)程：如圖2.1.2 所示，該函數(shù)代入?yún)?shù)是根節(jié)點(diǎn) T、要插入到的節(jié) 點(diǎn)q、要插入的關(guān)鍵字可以及在節(jié)點(diǎn)中應(yīng)該插入的位置序號(hào)i。該函數(shù)從根節(jié)點(diǎn)開(kāi)始建立B-樹(shù)，當(dāng)根節(jié)點(diǎn)為空時(shí)，需要建立新的根節(jié)點(diǎn)并且插入關(guān)鍵字；如果根節(jié) 點(diǎn)不為空，則直接插入即可，但是插入完成后，要考慮是否有節(jié)點(diǎn)分裂的情

19、況產(chǎn)生，入伏哦需要進(jìn)行節(jié)點(diǎn)分裂，則要調(diào)用 split()函數(shù)分裂節(jié)點(diǎn)(根節(jié)點(diǎn)分裂以 及子樹(shù)節(jié)點(diǎn)分裂的情況都考慮到)重新進(jìn)行分裂插入。函數(shù)最后返回指向B-樹(shù)根節(jié)點(diǎn)的指針T。3.4.8 查找函數(shù)函數(shù)名：found()函數(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ù)函數(shù)名：fseek()功能:將位置指針按需要移動(dòng)到任意位置，實(shí)現(xiàn)隨即讀寫(xiě)功能開(kāi)始)輸入待查找學(xué)

20、生 信息對(duì)應(yīng)的學(xué)號(hào)fseek(fp,i*sizeof(structstudent),0)_輸出相應(yīng)學(xué) 4信 息圖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ò)程。4 運(yùn)行調(diào)試4.1 調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法在調(diào)試程序的過(guò)程中，遇到的問(wèn)題有多種，但是集中表現(xiàn)為語(yǔ)句錯(cuò)誤、邏輯錯(cuò)誤、參數(shù)未定義等方面。針對(duì)該算法中的這些問(wèn)題，進(jìn)行了具體分析，找到了 正確的解決辦法。4.1.1 語(yǔ)句錯(cuò)誤問(wèn)題： missing '' before '&#

21、39; ；括號(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,引用的是&p,則會(huì)出現(xiàn)、'' 匹配有誤，解決該問(wèn)題，根據(jù)提示找到該符號(hào)的地方，進(jìn)行改正即可。4.1.2 邏輯錯(cuò)誤問(wèn)題：函數(shù)不能調(diào)用或賦值語(yǔ)句不能分析：這種問(wèn)題在執(zhí)行程序時(shí)出現(xiàn)，表現(xiàn)為執(zhí)行到一半會(huì)出錯(cuò)。通常這種問(wèn)題是由于編寫(xiě)算法算判斷語(yǔ)句不完善造成的，通常解決辦法是單步調(diào)試，找到出 錯(cuò)的地方，即算法執(zhí)行停止的地方，修改錯(cuò)誤的邏輯語(yǔ)句。4.2 運(yùn)行結(jié)果該設(shè)計(jì)最終要求實(shí)現(xiàn)B-

22、樹(shù)算法，根據(jù)該算法設(shè)定的參數(shù)，輸入事先指定好的 學(xué)生信息，按先后順序從鍵盤(pán)輸入到文件中，此時(shí)B-樹(shù)已經(jīng)建立好了，索引時(shí)只需輸入任意一個(gè)學(xué)生的學(xué)號(hào)，就可以得到該學(xué)生完整信息的運(yùn)行結(jié)果： 學(xué)生信息包括學(xué)生的姓名，學(xué)號(hào)，成績(jī)等。例如：輸入的是：Zhao 1 78Qian 2 56Sun 3 87Li 4 34Zhou 5 67Wu 6 64Zheng 7 39Wang 8 79Feng 9 68Chen 10 86程序會(huì)自動(dòng)以學(xué)號(hào)為關(guān)鍵字建立好B-樹(shù),請(qǐng)輸入要查找的學(xué)生信息的學(xué)號(hào)：例如：輸入5；則輸出：Zhou 5 67當(dāng)輸入 0 的時(shí)候停止索引，過(guò)程結(jié)束！4.3 結(jié)論分析在該算法中，實(shí)現(xiàn)了建立一個(gè)

23、m階的B-樹(shù)，返回指向建好的B-樹(shù)根節(jié)點(diǎn)的指 針，并且能夠查找指定的學(xué)號(hào)關(guān)鍵字，若查找成功，則返回該關(guān)鍵字所在學(xué)生的相關(guān)信息，否則查找不成。在調(diào)試程序的過(guò)程中，遇到了許多常識(shí)性的問(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ò)程中所不可缺少的精神。參考文獻(xiàn)1 .數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+的述），殷人昆等，清華大學(xué)出版社。2 . 算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo) ，寧正元等，清華大學(xué)出版社。3 . 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn) 徐孝凱 編著 ，清華大學(xué)出版社。4 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu) （C 語(yǔ)

24、言版 ） M . 北京：清華大學(xué)出版社， 2006.5 呂國(guó)英 . 算法設(shè)計(jì)與分析 M . 北京：清華大學(xué)出版社，2006.6 徐寶文，李志.C程序設(shè)計(jì)語(yǔ)言MC .北京：機(jī)械工業(yè)出版社，2004.7 夏克儉 . 數(shù)據(jù)結(jié)構(gòu)+算法M . 北京：國(guó)防工業(yè)出版社， 2001.8 李春葆，曾慧，張植民. 數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典M . 北京：清華大學(xué)出版社， 2002.附 錄（關(guān)鍵部分程序清單）/B- 樹(shù)算法的應(yīng)用#include "stdio.h"#include "math.h"#include "malloc.h"#include "

25、;stdlib.h"#include "fstream.h"#define m 5#define n 10typedef struct BTNodeint keynum;struct BTNode *parent;int keym+1;struct BTNode *ptrm+1;int locationm+1;BTNode,*BTree;typedef structBTNode *pt;int i;int tag;Result;struct student int num;char name10;int score;stdn;int an,bn;/ 在結(jié)點(diǎn)中查找關(guān)

26、鍵字int SearchNode(BTree p,int k)int i=1;while(i<=p->keynum)if(k<p->keyi)return i-1;elseif(k=p->keyi)return -1;else i+;return i-1;/在B樹(shù)中查找關(guān)鍵字k為 B 樹(shù)根節(jié)點(diǎn)Result SearchBTree(BTree t,int k)/tBTree p=t,q=NULL;int found=0;int i=0;Result result;while(p&&!found)i=SearchNode(p,k);if(i=-1)re

27、sult.pt=p;result.i=i;result.tag=1;return result;while(p->ptri)p=p->ptri;i=SearchNode(p,k);if(i>0&&p->keyi=k)found=1;elseq=p;p=p->ptri;if(found)result.pt=p;result.i=i;result.tag=1;elseresult.pt=q;result.i=i;result.tag=0;return result;/ 將關(guān)鍵字插入節(jié)點(diǎn)BTree Insert(BTree q,int i,int x,B

28、Tree ap,int l)/ insert the key X between the keyi and keyi+1/ at the pointer node qint j;for(j=q->keynum;j>i;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;ap->parent=q;q->keynum+;return q;/ 分裂

29、節(jié)點(diǎn)BTree split(BTree q,int s,BTree ap)/move keys+1.m,p->ptrs.m int the new pointer *apint i,j;ap=(BTree)malloc(sizeof(BTNode);ap->ptr0=q->ptrs;for(i=s+1,j=1;i<=q->keynum;i+,j+)ap->keyj=q->keyi;ap->ptrj=q->ptri;ap-> location j=q-> location i;ap->keynum=q->keynum-

30、s;ap->parent=q->parent;for(i=0;i<=q->keynum-s;i+)if(ap->ptri)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=

31、p;T->ptr1=ap;T->key1=x;T-> location 1=z;if(p)p->parent=T;if(ap)ap->parent=T;T->parent=NULL;return T;/建立B-樹(shù)BTree InsertBTree(BTree T,int K,BTree q,int i,int l)/ 在m階B權(quán)t 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(!

32、q)/ T是空樹(shù)(參數(shù)q初值為NULL)T=NewRoot(T,NULL,K,NULL,l); / 生成僅含關(guān)鍵字K 的根結(jié)點(diǎn) *Telsex=K; ap=NULL; finished=needNewRoot=0;while(!needNewRoot&&!finished)q=Insert(q,i,x,ap,l);/ 將 x 和 ap 分 別 插入 到 q->keyi+1 和q->ptri+1if(q->keynum< m)finished = 1; / 插入完成else/將 q->keys+1.m, q->ptrs.m/ q-> lo

33、cation s+1.m移入新結(jié)點(diǎn) *aps=(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 needNewRoot=1; / else / whileif(needNewRoot) /根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)*q和*apT=NewRoot(T,q,x,ap,l); /生成新根結(jié)點(diǎn) *T,q 和 ap 為子樹(shù)指針ret

34、urn T; / InsertBTreeint found(BTree MT,int k)查找關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)位置/int i;BTree p=MT;while(p!=NULL)i=1;while(k>p->keyi&&i<p->keynum)i+;if(k=p->keyi)return p-> location i;else if(k>p->keyi)p=p->ptri;else if(k<p->keyi)p=p->ptri-1;return -1;void savestud(FILE *fout)信

35、息/存儲(chǔ)int i;if (fout=fopen("E:xuesheng.txt","wb")=NULL)printf("can not open filen");exit(0);for(i=0;i<n;i+)scanf("%d%s%d",&stdi.num,,&stdi.score);ai=stdi.num;bi=i;fwrite(&stdi,sizeof(struct student),1,fout);fclose(fout);讀取void readstud(FI

36、LE *fin,int j)/信息的 int i;fin=fopen("E:xuesheng.txt","rb");fseek(fin,sizeof(struct student),0);fseek(fin,-sizeof(struct student),1);for(i=1;i<=j;i+)fseek(fin,sizeof(struct student),1);fread(&std0,sizeof(struct student),1,fin);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(i<=t->keyn