數(shù)據(jù)結(jié)構(gòu)實習(xí)報告二叉樹

數(shù)據(jù)結(jié)構(gòu)第二次作業(yè)實習(xí)報告1110685數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

實習(xí)報告題目：B樹的建立，插入與刪除學(xué)號：1110685姓名：李建男年級：大二學(xué)院：信息技術(shù)科學(xué)學(xué)院專業(yè)：計算機科學(xué)與技術(shù)專業(yè)完成日期：2013.5.12授課教師：辛運帷

題目B樹的表示及基本操作的實現(xiàn)。1．掌握B樹的存貯結(jié)構(gòu)。2．實現(xiàn)B樹中關(guān)鍵字值的插入及刪除操作。3．練習(xí)屏幕圖形化的顯示。2.要求參考書中的示例代碼，以整數(shù)表示每個記錄的關(guān)鍵字。為簡單起見，每個記錄可以只包含一個關(guān)鍵字（即其他的字段可以不定義）。從空樹開始，依次輸入各關(guān)鍵字，建立相應(yīng)的B樹。并實現(xiàn)B樹中關(guān)鍵字的插入及刪除。同時將樹型顯示在屏幕上。全部關(guān)鍵字插入完畢時顯示樹型，之后每完成一次插入或刪除操作后也顯示當前的樹型。假設(shè)B樹中不存在重復(fù)的關(guān)鍵字。程序運行時，當要輸入數(shù)據(jù)時必須在屏幕上給出輸入的格式要求（中英文均可）。當有輸出顯示時，也需要將輸出的內(nèi)容做必要的解釋。3.程序?qū)崿F(xiàn)3.1程序運行及編譯環(huán)境VisualStudio20123.2程序描述該程序支持用戶進行以下三種操作：新建B樹：從鍵盤輸入新建B樹的階數(shù)和關(guān)鍵字個數(shù)，新建B樹。插入關(guān)鍵字：既支持單個關(guān)鍵字的插入，也支持多個關(guān)鍵字的插入。（重復(fù)插入時給出信息提示）刪除關(guān)鍵字：既支持單個關(guān)鍵字的刪除，也支持多個關(guān)鍵字的刪除。（樹中沒有該關(guān)鍵字時給出信息提示）特別說明：程序編寫時參考了《算法導(dǎo)論》中的內(nèi)容，對B樹的規(guī)定與老師課上所講略有出入，采用了如下規(guī)則：對m階B樹：關(guān)鍵字個數(shù)：Least：m-1；Most：2*m-1孩子個數(shù)：Least：m；Most：2*m3.3實現(xiàn)功能介紹該程序應(yīng)具有的功能，可采用IPO圖（即輸入一處理一輸出圖）的形式。說明：如果該程序只有單一功能時可以直接描述其輸入項、輸出項等等各個部分，否則按照各個子功能模塊分別介紹。3.3.1子功能模塊1——新建B樹&插入關(guān)鍵字說明：因新建和插入用到的算法相同，故合并為一個模塊根據(jù)用戶輸入的B樹階數(shù)，關(guān)鍵字個數(shù)及關(guān)鍵字，新建B樹。用戶：用戶：輸入B樹階數(shù)degree，待輸入關(guān)鍵字個數(shù)key_num。根據(jù)根據(jù)degree，初始化B樹：MyBTreeBTree（degree）；用戶：依次輸入關(guān)鍵字用戶：依次輸入關(guān)鍵字（超出關(guān)鍵字個數(shù)的忽略掉）調(diào)用調(diào)用Insert函數(shù)，將輸入的關(guān)鍵字依次插入到B樹中，完成B樹的創(chuàng)建。3.3.1.1輸入項輸入項一：B樹階數(shù)degree和帶插入關(guān)鍵字個數(shù)key_num名稱：B樹階數(shù)標識：degree數(shù)據(jù)類型：int有效范圍：整型變量輸入方式：用戶從鍵盤輸入名稱：待插入關(guān)鍵字個數(shù)標識：key_num數(shù)據(jù)類型：int有效范圍：整型變量輸入方式：用戶從鍵盤輸入輸入項二：名稱：關(guān)鍵字標識：key數(shù)據(jù)類型：int有效范圍：整型變量存儲方式：動態(tài)數(shù)組newint[key_num]輸入方式：用戶從鍵盤輸入3.3.1.2輸出項輸出為B樹樹形，采用兩種輸出方式：屏幕圖形化輸出（采用MFC實現(xiàn)）；層遍歷輸出所有關(guān)鍵字、具體輸出方式同子模塊1，不再贅述。3.3.1.3數(shù)據(jù)結(jié)構(gòu)的定義3.3.1全局數(shù)據(jù)結(jié)構(gòu)函數(shù)bool*erase(intkey)——用來實現(xiàn)B樹關(guān)鍵字的插入3.3.2局部數(shù)據(jù)結(jié)構(gòu)函數(shù)voidsplite_child(node*pnode,inti)——用來實現(xiàn)當結(jié)點滿時結(jié)點的分裂3.3.1.4算法及程序說明采取的算法：樹的創(chuàng)建：B樹類classb_trees。包含兩個私有數(shù)據(jù)變量：結(jié)點類node*root，和表示樹階數(shù)的變量intdegree。node類包含三個成員變量——關(guān)鍵字隊列deque<int>keys、指向孩子的指針隊列deque<node*>children、判斷是否是葉節(jié)點的布爾變量boolleaf。B樹的構(gòu)造函數(shù)如下：explicitb_trees(intdeg=10):root(newnode),degree(deg){};用戶從鍵盤輸入degree后，用degree初始化b樹。結(jié)點定義代碼：關(guān)鍵字的插入：在B樹中插入關(guān)鍵字：沿樹下降查找新關(guān)鍵字的插入位置時，分裂沿途遇到的每個滿結(jié)點。B樹中結(jié)點的分裂：調(diào)用函數(shù)voidsplite_child(node*pnode,inti)。表示分裂pnode結(jié)點下標為i的子結(jié)點。滿根的分裂：讓原根成為一個新根的孩子，再調(diào)用splite_child（root，0）分裂原根。滿非根結(jié)點的分裂：分裂過程如下：動態(tài)分配一個新結(jié)點new_node新結(jié)點的leaf與待分裂結(jié)點的leaf具有相同的真值迭代：將原結(jié)點下標為degree到最大下標的所有關(guān)鍵字插入到新結(jié)點的關(guān)鍵字隊列中將原結(jié)點中下標為degree-1的關(guān)鍵字提升到父節(jié)點pnode下標為i的關(guān)鍵字處刪除原結(jié)點中下標為degree-1到最大下標的關(guān)鍵字判斷：待分裂結(jié)點是否為葉節(jié)點：若不是：迭代：將原結(jié)點中下標為degree到最大下標的孩子結(jié)點插入到新結(jié)點的孩子隊列中；刪除原結(jié)點中對應(yīng)孩子結(jié)點新結(jié)點成為原結(jié)點第i+1個孩子結(jié)點。對B樹用單程下行遍歷樹方式插入關(guān)鍵字：判斷跟是否為滿根。若是，分裂根，樹高加1；遞歸沿樹下降查找合適的插入位置，與滿結(jié)點即分裂，直至查找到葉節(jié)點；將關(guān)鍵字插入到葉結(jié)點的合適位置。樹的打印屏幕圖形化輸出：函數(shù)voidprint_B_tree(node*current,CDC*pDC,CPointpoint,intedge)Current->當前待打印結(jié)點；pDC->繪圖封裝類對象，用于在客戶區(qū)繪制圖形；point->當前結(jié)點關(guān)鍵字矩形的中間位置；edge->point與屏幕邊界的距離設(shè)置靜態(tài)全局變量staticone_sqare=25,表示一個矩形的邊長點temp記錄首個關(guān)鍵字矩形左上角的位置迭代，從temp依次打印關(guān)鍵字矩形和關(guān)鍵字迭代，打印current的孩子結(jié)點。判斷孩子指針是否為空：若不為空:計算孩子結(jié)點關(guān)鍵字矩形的中間位置subtemp，計算孩子結(jié)點與屏幕邊界的距離startpoint畫線，連接指針矩形與孩子結(jié)點的中間位置遞歸調(diào)用print_B_tree（current->children[i]，pDC，subtemp，startpoint）按層打?。憾x隊列，根節(jié)點入隊列迭代（判斷條件：隊列非空）首元素出隊列；打印該結(jié)點所有關(guān)鍵字；該節(jié)點所有孩子結(jié)點入隊列3.3.1.5接口設(shè)計1、用戶輸入樹階數(shù)degree和待輸入關(guān)鍵字樹key_num，定義B樹類成員bTree，用degree初始化bTree2、用戶輸入關(guān)鍵字，調(diào)用insert函數(shù)建3.3.2子功能模塊2——刪除關(guān)鍵字用戶：輸入命令（用戶：輸入命令（d->單關(guān)鍵字刪除；md->多關(guān)鍵字刪除：關(guān)鍵字間用“，”分隔，“#”記錄結(jié)束）調(diào)用調(diào)用Erase函數(shù)，將輸入的關(guān)鍵字依次從B樹中刪除。若輸入關(guān)鍵字樹中不存在，彈出錯誤信息提示。3.3.1.1輸入項輸入項一：刪除命令（“d”or“md”）名稱：刪除命令標識：str數(shù)據(jù)類型：string有效范圍：z字符串變量變量輸入方式：用戶從鍵盤輸入輸入項二：待刪除關(guān)鍵字名稱：待刪除關(guān)鍵字標識：val數(shù)據(jù)類型：int有效范圍：整型變量輸入方式：用戶從鍵盤輸入3.3.1.2輸出項輸出為B樹樹形，采用兩種輸出方式：屏幕圖形化輸出（采用MFC實現(xiàn)）；層遍歷輸出所有關(guān)鍵字名稱：B樹結(jié)點標識：btree->node數(shù)據(jù)類型：int有效范圍：整型變量輸出方式1：同插入操作，不再贅述。3.3.2.3數(shù)據(jù)結(jié)構(gòu)的定義3.3.1全局數(shù)據(jù)結(jié)構(gòu)函數(shù)node*insert(intkey)——用來實現(xiàn)B樹關(guān)鍵字的插入3.3.2局部數(shù)據(jù)結(jié)構(gòu)函數(shù)node*grow_keys(node*pnode,inti)——用來實現(xiàn)關(guān)鍵字的擴展函數(shù)node*merge_node(node*pnode,inti)——用來實現(xiàn)結(jié)點的合并函數(shù)node*inter_erase(node*pnode,inti)——用來實現(xiàn)內(nèi)結(jié)點關(guān)鍵字的刪除3.3.2.4算法及程序說明采取的算法：關(guān)鍵字的刪除算法：a)遞歸找到待刪除關(guān)鍵字所在的結(jié)點；（判斷條件：結(jié)點不是葉節(jié)點）b)在下溯過程中，如果當前節(jié)點的孩子結(jié)點關(guān)鍵個數(shù)達下界，調(diào)用grow_keys函數(shù)，拓展該節(jié)點；c)找到關(guān)鍵字所在結(jié)點后，判斷結(jié)點是否為葉節(jié)點，若不是，調(diào)用inter_erase函數(shù)，刪除內(nèi)結(jié)點中關(guān)鍵字d)若關(guān)鍵字所在結(jié)點為葉節(jié)點，直接從葉節(jié)點中刪除結(jié)點擴展算法：函數(shù)node*merge_node(node*pnode,inti)表示擴展結(jié)點pnode位置為i的孩子結(jié)點判斷：如果孩子結(jié)點的左兄弟有富余關(guān)鍵字，向左兄弟借：將父節(jié)點pnode位置為i的關(guān)鍵字插入到待擴展結(jié)點的首元素位置左兄弟最后一個元素出隊列，插入到父節(jié)點中位置i若孩子結(jié)點不是葉節(jié)點，將左兄弟最后一個孩子掛接到擴展結(jié)點的第一個孩子的位置若左兄弟沒有富余元素，向右兄弟借，算法同上若左右兄弟都沒有富余元素，合并兩結(jié)點結(jié)點合并算法:node*merge_node(node*pnode,inti),表示合并pnode中下標為i的關(guān)鍵字的左右兩結(jié)點新建結(jié)點，存儲左孩子將pnode下標為i的關(guān)鍵字下降到新建結(jié)點中將右孩子所有關(guān)鍵字插入到新建結(jié)點后面如果左右孩子不是葉結(jié)點，將右孩子指針掛接到新建結(jié)點后將下標為i的關(guān)鍵字從父節(jié)點中刪除將下標為i+1的孩子從父節(jié)點中刪除判斷：若父節(jié)點為根節(jié)點，且下降后父節(jié)點為空，刪除根節(jié)點，并將合并后結(jié)點作為新的根節(jié)點內(nèi)結(jié)點關(guān)鍵字刪除算法：函數(shù)node*inter_erase(node*pnode,inti)表示刪除結(jié)點pnode中下標為i的關(guān)鍵字若左孩子關(guān)鍵字富余，遞歸下降到左孩子，左孩子的最后一個關(guān)鍵字代替父節(jié)點的待刪除關(guān)鍵字若左孩子沒有富余，下降到右孩子左右孩子關(guān)鍵字都不富余，合并i的左右結(jié)點，合并后待刪除節(jié)點在合并結(jié)點的正中間刪除合并結(jié)點中下標為degree-1的關(guān)鍵字3.4運行結(jié)果1、按層打印結(jié)果A）功能一——新建B樹按層打印的結(jié)點對所建樹的信息說明按層打印的結(jié)點對所建樹的信息說明B)功能二——插入關(guān)鍵字多關(guān)鍵字輸入單關(guān)鍵字輸入輸入格式說明多關(guān)鍵字輸入單關(guān)鍵字輸入輸入格式說明重復(fù)插入時會出現(xiàn)錯誤信息提示，如下：重復(fù)插入時的錯誤信息提示重復(fù)插入時的錯誤信息提示C）功能三——刪除關(guān)鍵字單關(guān)鍵字刪除多關(guān)鍵字刪除單關(guān)鍵字刪除多關(guān)鍵字刪除刪除不存在關(guān)鍵字時錯誤信息提示：刪除不存在關(guān)鍵字時錯誤信息提示刪除不存在關(guān)鍵字時錯誤信息提示2、屏幕圖形化輸出：1)功能一——新建B樹a)單擊菜單上的“B樹”菜單項->新建B樹B）出現(xiàn)如下對話框輸入階數(shù)和關(guān)鍵字個數(shù)，點擊確定；若B樹已創(chuàng)建過，會出現(xiàn)如下提示信息C）以包含10個關(guān)鍵字的2階B樹為例