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

整理為word格式整理為word格式整理為word格式課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：B-樹算法的應(yīng)用院（系）：專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：學(xué)號(hào)：姓名：指導(dǎo)教師：整理為word格式整理為word格式整理為word格式目錄1需求分析 11.1課程設(shè)計(jì)的內(nèi)容 11.2B-樹的描述 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-樹 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運(yùn)行結(jié)果 174.3結(jié)論分析 18參考文獻(xiàn) 19附錄（關(guān)鍵部分程序清單） 20整理為word格式整理為word格式整理為word格式1需求分析1.1課程設(shè)計(jì)的內(nèi)容編寫算法能將學(xué)生信息保存到文件中，能夠?yàn)閷W(xué)生信息建立B-樹索引，并能夠利用B-樹索引查找到指定學(xué)生的信息。建立B-樹索引使用學(xué)號(hào)為關(guān)鍵字。（B-樹中只含有學(xué)號(hào)和該記錄在文件中的位置信息）要求：1.B-樹的階可以選擇，要求給出一個(gè)完整班的學(xué)生信息。參考相應(yīng)資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。3．交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。1.2B-樹的描述B-樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。在此先介紹樹的結(jié)構(gòu)。一棵m階的B-樹，或?yàn)榭諛?，或?yàn)闈M足下列特性的m叉樹：樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；除根之外的所有非終端結(jié)點(diǎn)至少有[m/2]棵子樹；（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)為指向子樹根結(jié)點(diǎn)的指針，且指針Ai-1所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki(i=1,…,n),An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn,n([m/2]-1<=n<=m-1)為關(guān)鍵字的個(gè)數(shù)（或n+1為子樹個(gè)數(shù)）。（5）所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)實(shí)際上這些結(jié)點(diǎn)根本不存在，指向這些結(jié)點(diǎn)的指針為空）。整理為word格式整理為word格式整理為word格式2概要設(shè)計(jì)2.1總體設(shè)計(jì)思想首先將學(xué)生信息從鍵盤鍵入存到指定的文件中，在此每當(dāng)輸入一個(gè)學(xué)生的信息，對(duì)應(yīng)學(xué)生信息的學(xué)號(hào)將作為B-樹的關(guān)鍵字，連同一起的該記錄在文件中的信息這兩部分作為結(jié)點(diǎn)插入到B-樹中，插入的過(guò)程也就是建立B-樹的過(guò)程，其中B-樹的階m在開始的時(shí)候已經(jīng)確定了，當(dāng)結(jié)點(diǎn)中的關(guān)鍵字的個(gè)數(shù)大于m-1時(shí)就開始分裂，并生成新的結(jié)點(diǎn)，按此規(guī)律即能建立好B-樹，程序運(yùn)行時(shí)只須輸入任意學(xué)生的學(xué)號(hào)，然后屏幕上將顯示此學(xué)號(hào)對(duì)應(yīng)的學(xué)生的全部信息，由此即完成課程設(shè)計(jì)要求。2.2局部模塊構(gòu)想2.2.分別從結(jié)點(diǎn)中，B-樹中查找關(guān)鍵字K，因?yàn)橐虢?，就要插入結(jié)點(diǎn)，插入結(jié)點(diǎn)要先檢驗(yàn)一下此時(shí)樹中有沒(méi)有次結(jié)點(diǎn)，intSearchNode(BTreep,intk)函數(shù)和ResultSearchBTree(BTreet,intk)函數(shù)實(shí)現(xiàn)了查找功能。2.2.2將關(guān)鍵字插入結(jié)點(diǎn)，分裂結(jié)點(diǎn)，建立新的結(jié)點(diǎn)在將關(guān)鍵字插入結(jié)點(diǎn)時(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)中，這樣逐個(gè)結(jié)點(diǎn)才能順利插入到B-樹中。即此時(shí)的B-樹已經(jīng)建立好了。2.2.3搜索指定結(jié)點(diǎn)，新建文件B-樹索引過(guò)程就是搜索指定關(guān)鍵字的過(guò)程，從根結(jié)點(diǎn)開始，向子樹結(jié)點(diǎn)中的關(guān)鍵字查找，當(dāng)查找時(shí)即返回此時(shí)文件指針fp當(dāng)前位置，假如查找失敗，就繼續(xù)查找，直到找到根結(jié)點(diǎn)為止，倘若還沒(méi)查找到就返回沒(méi)有找到。我們需要把學(xué)生的相關(guā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é)生完整信息，整理為word格式整理為word格式整理為word格式此時(shí)索引過(guò)程完成。整理為word格式整理為word格式整理為word格式3詳細(xì)設(shè)計(jì)3.1主函數(shù)設(shè)計(jì)3.1.1設(shè)計(jì)思想B-樹算法的實(shí)現(xiàn)，首先應(yīng)該建立一個(gè)m階的B-樹（在本算法中m設(shè)為5）。在建立B-樹過(guò)程中，首先輸入一個(gè)關(guān)鍵字學(xué)生學(xué)號(hào)序列（為方便起見本算法使用整數(shù)序列，關(guān)鍵字個(gè)數(shù)設(shè)定為10），將這個(gè)整數(shù)序列存入數(shù)組中，然后從空樹開始，依次將關(guān)鍵字插入B-樹中，建立一個(gè)m階的B-樹。（在輸入學(xué)生信息的同時(shí)只是將學(xué)生學(xué)號(hào)作為關(guān)鍵字存入文件中）建樹過(guò)程中，每插入一個(gè)關(guān)鍵字，首先應(yīng)該判斷出這個(gè)關(guān)鍵字在B-樹中應(yīng)該插入的位置，需要調(diào)用SearchBTree()和SearchNode()兩個(gè)函數(shù)共同配合完成；然后調(diào)用InsertBTree()和Insert()函數(shù)進(jìn)行插入，插入完成后，應(yīng)該看該節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)是否小于B-樹的階數(shù)m，當(dāng)節(jié)點(diǎn)中插入的關(guān)鍵字個(gè)數(shù)不符合要求時(shí)，應(yīng)該考慮節(jié)點(diǎn)分裂的情況（根節(jié)點(diǎn)和子樹節(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-樹建立成功后，返回指向該B-樹根節(jié)點(diǎn)的指針。該算法要求具有查找任一指定學(xué)生信息的功能，可以輸入任意一個(gè)學(xué)生的學(xué)號(hào)，在B-樹中查找該關(guān)鍵字，看該關(guān)鍵字是否存在在該B-樹，如果存在，則返回該關(guān)鍵字對(duì)應(yīng)的學(xué)生完整信息，否則查找不成功，則該學(xué)號(hào)所對(duì)應(yīng)的關(guān)鍵字不在該B-樹中，以上即完成B-樹索引過(guò)程。整理為word格式整理為word格式整理為word格式3.1.2主流程圖圖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-樹的建立、在B-樹中查找指定節(jié)點(diǎn)（該算法中查找具體的關(guān)鍵字位置）、B-樹的遍歷以及輸出遍歷序列等功能。3.2.1在該算法中涉及到的各個(gè)函數(shù)的中文和英文名稱分別為：主函數(shù)main()、節(jié)點(diǎn)查找函數(shù)SearchNode()、B-樹查找函數(shù)SearchBTree()、節(jié)點(diǎn)插入函數(shù)Inset()、節(jié)點(diǎn)分裂函數(shù)split()、節(jié)點(diǎn)建立函數(shù)NewRoot()、B-樹插入函數(shù)InsertBTree()、查找函數(shù)found()、中序遍歷輸出函數(shù)PrintBTree()、文件寫函數(shù)savestud（）、文件讀取函數(shù)readstud（）。整理為word格式整理為word格式整理為word格式3.2.2Readstud()函數(shù)Savestud()函數(shù)圖3-2函數(shù)調(diào)用模塊圖Readstud()函數(shù)Savestud()函數(shù)3.2.1主函數(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()函數(shù)時(shí)，要用到遞歸調(diào)用found()函數(shù)；執(zhí)行PrintBTree()函數(shù)時(shí)，也要用到遞歸調(diào)用PrintBTree()函數(shù)。3.3存儲(chǔ)結(jié)構(gòu)在該設(shè)計(jì)的算法中，定義B-樹中節(jié)點(diǎn)類型、B-樹類型以及查找結(jié)果類型如下：#definem3//B-樹的階，暫定為3typedefstructBTNode{intkeynum;//節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)structBTNode*parent;//指向雙親節(jié)點(diǎn)整理為word格式整理為word格式整理為word格式intkey[m+1];//關(guān)鍵字向量，0號(hào)單元未用structBTNode*ptr[m+1];//子樹指針向量}BTNode,*BTree;//B-樹節(jié)點(diǎn)和B-樹的類型typedefstruct{BTNode*pt;//指向找到的節(jié)點(diǎn)inti;//在節(jié)點(diǎn)中的關(guān)鍵字序號(hào)inttag;//1：查找成功，0：查找失敗}Result;//B-樹的查找結(jié)果類型3.4函數(shù)流程圖在這部分中，將每個(gè)函數(shù)分別用流程圖表示出來(lái)，并且將每個(gè)函數(shù)的功能以及實(shí)現(xiàn)過(guò)程詳細(xì)的表述出來(lái)，使得能夠更加清晰、有條理體現(xiàn)出該算法。3.4.1函數(shù)名：main()函數(shù)功能：輸入關(guān)鍵字序列，調(diào)用B-樹建立函數(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ù)InsertBTree(),將關(guān)鍵字依次插入B-樹中，插入完成后，返回指向B-樹的根節(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ò)程。整理為word格式整理為word格式整理為word格式圖3-3主函數(shù)流程圖3.4.2函數(shù)名：SearchNode()功能：在節(jié)點(diǎn)中查找關(guān)鍵字，返回該關(guān)鍵字在節(jié)點(diǎn)中的位置整理為word格式整理為word格式整理為word格式圖3-4SearchNode()函數(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函數(shù)名稱：SearchBTree()功能：從B-樹的根節(jié)點(diǎn)開始查找，查找所給關(guān)鍵字在該B-樹中的節(jié)點(diǎn)位置以及在所在節(jié)點(diǎn)中的位置，該函數(shù)返回結(jié)果為Result類型，result.i表示關(guān)鍵字在節(jié)點(diǎn)中應(yīng)該插入的位置，result.pt表示關(guān)鍵字應(yīng)該所在的節(jié)點(diǎn)，result.tag表示是否能夠在B-樹中查找到該關(guān)鍵字。整理為word格式整理為word格式整理為word格式圖3-5SearchBTree()函數(shù)流程圖實(shí)現(xiàn)過(guò)程：如圖2.1.2(b)所示，代入B-樹的根節(jié)點(diǎn)指針和要查找的關(guān)鍵字，從根節(jié)點(diǎn)開始，對(duì)每個(gè)節(jié)點(diǎn)使用SearchNode()函數(shù)，查找所給關(guān)鍵字所在的節(jié)點(diǎn)以及在該節(jié)點(diǎn)中的位置，如果該關(guān)鍵字已經(jīng)存在于B-樹中，則返回關(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函數(shù)名：Insert()函數(shù)功能：將所給關(guān)鍵字插入到正確節(jié)點(diǎn)的正確位置整理為word格式整理為word格式整理為word格式圖3-6Insert()函數(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函數(shù)名：split()整理為word格式整理為word格式整理為word格式函數(shù)功能：當(dāng)節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)不符合要求時(shí)，進(jìn)行節(jié)點(diǎn)分裂圖3-7split()函數(shù)流程圖實(shí)現(xiàn)過(guò)程：如圖2.1.2(d)所示，該函數(shù)帶入的參數(shù)是指向要產(chǎn)生分裂的節(jié)點(diǎn)的指針q、節(jié)點(diǎn)最小子樹個(gè)數(shù)s以及空指針ap，首先給ap分配BTree類型的空間，然后再將q中序號(hào)大于s的關(guān)鍵字插入到ap節(jié)點(diǎn)中，同時(shí)紙箱子樹的指針也插入到ap中，然后再分別計(jì)算q和ap中的關(guān)鍵字個(gè)數(shù)，對(duì)q和ap進(jìn)行處理。最后返回ap指針。3.4.6整理為word格式整理為word格式整理為word格式函數(shù)名：NewRoot()函數(shù)功能：建立新的節(jié)點(diǎn)，并且返回指向該節(jié)點(diǎn)的指針。圖3-8NewRoot()函數(shù)流程圖實(shí)現(xiàn)過(guò)程：如圖2.1.2(e)所示，該函數(shù)的代入?yún)?shù)是根節(jié)點(diǎn)T、指向子樹的指針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)的子樹指針?lè)謩e指向空。如果p和ap不為空，則它們的父節(jié)點(diǎn)指向T節(jié)點(diǎn)。該函數(shù)最后返回的是指針T。3.4.7整理為word格式整理為word格式整理為word格式函數(shù)名：InsertBTree()函數(shù)功能：從空樹開始建立B-樹，返回的是B-樹的根指針。圖3-9InsertBTree()函數(shù)流程圖實(shí)現(xiàn)過(guò)程：如圖2.1.2(f)所示，該函數(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)開始建立B-樹，當(dāng)根節(jié)點(diǎn)為空時(shí)，需要建立新的根節(jié)點(diǎn)并且插入關(guān)鍵字；如果根節(jié)點(diǎn)不為空，則直接插入即可，但是插入完成后，要考慮是否有節(jié)點(diǎn)分裂的情況產(chǎn)生，入伏哦需要進(jìn)行節(jié)點(diǎn)分裂，則要調(diào)用split()函數(shù)分裂節(jié)點(diǎn)（根節(jié)點(diǎn)分裂以及子樹節(jié)點(diǎn)分裂的情況都考慮到）重新進(jìn)行分裂插入。函數(shù)最后返回指向B-樹根節(jié)點(diǎn)的指針T。整理為word格式整理為word格式整理為word格式3.4.8函數(shù)名：found()圖3-10found()函數(shù)流程圖整理為word格式整理為word格式整理為word格式函數(shù)功能：查找指指定關(guān)鍵字，查找成功則返回在所在節(jié)點(diǎn)的序號(hào)，否則返回-1。實(shí)現(xiàn)過(guò)程：如圖2.1.2(g)所示，該函數(shù)代入?yún)?shù)是B-樹根節(jié)點(diǎn)指針t以及關(guān)鍵字k，從根節(jié)點(diǎn)開始查找，如果查找到返回i值否則返回-1，在查找過(guò)程中低軌調(diào)用函數(shù)found()進(jìn)行查找。3.4.9函數(shù)名：fseek()功能：將位置指針按需要移動(dòng)到任意位置，實(shí)現(xiàn)隨即讀寫功能。圖3-11fseek()函數(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ò)程。整理為word格式整理為word格式整理為word格式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問(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ù)的類型與定義類型布匹配。如：定義BTree類型的指針p，引用的是&p,則會(huì)出現(xiàn)’{‘、’}’匹配有誤，解決該問(wèn)題，根據(jù)提示找到該符號(hào)的地方，進(jìn)行改正即可。4.1.2邏輯問(wèn)題：函數(shù)不能調(diào)用或賦值語(yǔ)句不能分析：這種問(wèn)題在執(zhí)行程序時(shí)出現(xiàn)，表現(xiàn)為執(zhí)行到一半會(huì)出錯(cuò)。通常這種問(wèn)題是由于編寫算法算判斷語(yǔ)句不完善造成的，通常解決辦法是單步調(diào)試，找到出錯(cuò)的地方，即算法執(zhí)行停止的地方，修改錯(cuò)誤的邏輯語(yǔ)句。4.2運(yùn)行結(jié)果該設(shè)計(jì)最終要求實(shí)現(xiàn)B-樹算法，根據(jù)該算法設(shè)定的參數(shù)，輸入事先指定好的學(xué)生信息，按先后順序從鍵盤輸入到文件中，此時(shí)B-樹已經(jīng)建立好了，索引時(shí)只需輸入任意一個(gè)學(xué)生的學(xué)號(hào)，就可以得到該學(xué)生完整信息的運(yùn)行結(jié)果：學(xué)生信息包括學(xué)生的姓名，學(xué)號(hào)，成績(jī)等。例如：輸入的是：Zhao178整理為word格式整理為word格式整理為word格式Qian256Sun387Li434Zhou567Wu664Zheng739Wang879Feng968Chen1086程序會(huì)自動(dòng)以學(xué)號(hào)為關(guān)鍵字建立好B-樹，請(qǐng)輸入要查找的學(xué)生信息的學(xué)號(hào)：例如：輸入5；則輸出：Zhou567當(dāng)輸入0的時(shí)候停止索引，過(guò)程結(jié)束！4.3結(jié)論分析在該算法中，實(shí)現(xiàn)了建立一個(gè)m階的B-樹，返回指向建好的B-樹根節(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ò)程中所不可缺少的精神。整理為word格式整理為word格式整理為word格式參考文獻(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ǔ)言版)［M］.北京：清華大學(xué)出版社，2006.[5]呂國(guó)英.算法設(shè)計(jì)與分析［M］.北京：清華大學(xué)出版社，2006.[6]徐寶文，李志.C程序設(shè)計(jì)語(yǔ)言［M］.北京：機(jī)械工業(yè)出版社，2004.[7]夏克儉.數(shù)據(jù)結(jié)構(gòu)+算法［M］.北京：國(guó)防工業(yè)出版社，2001.[8]李春葆，曾慧，張植民.數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典［M］.北京：清華大學(xué)出版社，2002.整理為word格式整理為word格式整理為word格式附錄（關(guān)鍵部分程序清單）//B-樹算法的應(yīng)用#include"stdio.h"#include"math.h"#include"malloc.h"#include"stdlib.h"#include"fstream.h"#definem5#definen10typedefstructBTNode{intkeynum;structBTNode*parent;intkey[m+1];structBTNode*ptr[m+1]; intlocation[m+1];}BTNode,*BTree;typedefstruct{BTNode*pt;整理為word格式整理為word格式整理為word格式inti;inttag;}Result;structstudent{intnum; charname[10]; intscore;}std[n];inta[n],b[n];//在結(jié)點(diǎn)中查找關(guān)鍵字intSearchNode(BTreep,intk){inti=1;while(i<=p->keynum){if(k<p->key[i])returni-1;else if(k==p->key[i]) return-1;elsei++;整理為word格式整理為word格式整理為word格式}returni-1;}//在B樹中查找關(guān)鍵字kResultSearchBTree(BTreet,intk)//t為B樹根節(jié)點(diǎn){BTreep=t,q=NULL;intfound=0;inti=0;Resultresult;while(p&&!found){i=SearchNode(p,k); if(i==-1) { result.pt=p; result.i=i; result.tag=1; returnresult; } while(p->ptr[i])整理為word格式整理為word格式整理為word格式 { p=p->ptr[i]; i=SearchNode(p,k); }if(i>0&&p->key[i]==k)found=1;else{q=p;p=p->ptr[i];}}if(found){result.pt=p;result.i=i;result.tag=1;}else{result.pt=q;整理為word格式整理為word格式整理為word格式result.i=i;result.tag=0;}returnresult;}//將關(guān)鍵字插入節(jié)點(diǎn)BTreeInsert(BTreeq,inti,intx,BTreeap,intl){//insertthekeyXbetweenthekey[i]andkey[i+1]//atthepointernodeqintj;for(j=q->keynum;j>i;j--){q->key[j+1]=q->key[j];q->location[j+1]=q->location[j];q->ptr[j+1]=q->ptr[j];}q->key[i+1]=x;q->ptr[i+1]=ap;q->location[i+1]=l;if(ap)整理為word格式整理為word格式整理為word格式 ap->parent=q;q->keynum++;returnq;}//分裂節(jié)點(diǎn)BTreesplit(BTreeq,ints,BTreeap){//movekey[s+1...m],p->ptr[s...m]intthenewpointer*apinti,j;ap=(BTree)malloc(sizeof(BTNode));ap->ptr[0]=q->ptr[s];for(i=s+1,j=1;i<=q->keynum;i++,j++){ap->key[j]=q->key[i];ap->ptr[j]=q->ptr[i];ap->location[j]=q->location[i];}ap->keynum=q->keynum-s;ap->parent=q->parent;for(i=0;i<=q->keynum-s;i++) if(ap->ptr[i])整理為word格式整理為word格式整理為word格式 ap->ptr[i]->parent=ap; q->key[q->keynum]=0; q->location[q->keynum]=0; q->keynum=s-1; returnap;}//建立新的節(jié)點(diǎn)BTreeNewRoot(BTreeT,BTreep,intx,BTreeap,intz){T=(BTree)malloc(sizeof(BTNode));T->keynum=1;T->ptr[0]=p;T->ptr[1]=ap;T->key[1]=x;T->location[1]=z;if(p) p->parent=T;if(ap) ap->parent=T;T->parent=NULL;returnT;整理為word格式整理為word格式整理為word格式}//建立B-樹BTreeInsertBTree(BTreeT,intK,BTreeq,inti,intl){//在m階B樹T上結(jié)點(diǎn)*q的key[i]與key[i+1]之間插入關(guān)鍵字K。//若引起結(jié)點(diǎn)過(guò)大，則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整，使T仍是m階B樹。BTreeap;intfinished,needNewRoot,s;intx;if(!q)//T是空樹(參數(shù)q初值為NULL)T=NewRoot(T,NULL,K,NULL,l);//生成僅含關(guān)鍵字K的根結(jié)點(diǎn)*Telse{x=K;ap=NULL;finished=needNewRoot=0;while(!needNewRoot&&!finished) {q=Insert(q,i,x,ap,l);//將x和ap分別插入到q->key[i+1]和q->ptr[i+1]if(q->keynum<m) finished=1;//插入完成else {//分裂結(jié)點(diǎn)*q整理為word格式整理為word格式整理為word格式//將q->key[s+1..m],q->ptr[s..m]和//q->location[s+1..m]移入新結(jié)點(diǎn)*aps=(m+1)/2; ap=split(q,s,ap); x=q->key[s]; l=q->location[s]; q->location[s]=0; q->key[s]=0;if(q->parent) {//在雙親結(jié)點(diǎn)*q中查找x的插入位置q=q->parent; i=SearchNode(q,x); } elseneedNewRoot=1;}//else}//whileif(needNewRoot)//根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)*q和*apT=NewRoot(T,q,x,ap,l);//生成新根結(jié)點(diǎn)*T,q和ap為子樹指針}returnT;}//InsertBTree整理為word格式整理為word格式整理為word格式intfound(BTreeMT,intk)//查找關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)位置{ inti;BTreep=MT; while(p!=NULL) { i=1; while(k>p->key[i]&&i<p->keynum) i++; if(k==p->key[i]) returnp->location[i]; elseif(k>p->key[i]) p=p->ptr[i]; elseif(k<p->key[i]) p=p->ptr[i-1]; } return-1;}voidsavestud(FILE*fout)//存儲(chǔ)信息整理為word格式整理為word格式整理為word格式{ inti; if((fout=fopen("E:\\xuesheng.txt","wb"))==NULL) { printf("cannotopenfile\n"); exit(0); } for(i=0;i<n;i++) { scanf("%d%s%d",&std[i].num,std[i].name,&std[i].score); a[i]=std[i].num; b[i]=i; fwrite(&std[i],sizeof(structstudent),1,fout); } fclose(fout);}voidreadstud(FILE*fin,intj)//讀取信息的{inti; fin=fopen("E:\\xuesheng.txt","rb"); fseek(fin,sizeof(structstudent),0); fseek(fin,-sizeof(structstudent),1);整理為word格式整理為word格式整理為word格式 for(i=1;i<=j;i++) { fseek(fin,sizeof(structstudent),1); } fread(&std[0],sizeof(structstudent),1,fin); printf("學(xué)號(hào)姓名成績(jī)\n"); printf("%-6d%-10s%6d\n",std[0].num,std[0].name,std[0].score); fclose(fin);}/