【正文】 容()程序規(guī)范()報(bào)告內(nèi)容()報(bào)告規(guī)范()考勤（8分）逾期扣分合 計(jì)(100分)得分附錄A 基于順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表實(shí)現(xiàn)的源程序黑體小2加粗居中，另起頁(yè)include include include define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASTABLE 1define OVERFLOW 2define LIST_INIT_SIZE 100define LISTINCREMENT 10typedef int status。 通過(guò)遞歸算法的編寫(xiě)加深了對(duì)遞歸的認(rèn)識(shí)和理解。，刪除二叉樹(shù)，此時(shí)銷(xiāo)毀二叉樹(shù)的存儲(chǔ)空間，頭指針置為空，測(cè)試結(jié)果如圖229所示。通過(guò)遍歷新生成的二叉樹(shù)驗(yàn)證其結(jié)構(gòu)正確性。圖218 查找結(jié)點(diǎn)的雙親結(jié)點(diǎn)，查找關(guān)鍵字為E的結(jié)點(diǎn)的左兄弟，查找結(jié)果如圖219所示。圖214 求二叉樹(shù)指定結(jié)點(diǎn)的值測(cè)試結(jié)果，將關(guān)鍵字為E的結(jié)點(diǎn)值改為9，測(cè)試結(jié)果如圖215所示。，判斷二叉樹(shù)是否為空樹(shù)，測(cè)試結(jié)果如圖211所示。圖27 先序遍歷二叉樹(shù)的測(cè)試結(jié)果，中序遍歷二叉樹(shù)，并執(zhí)行PRINT操作，測(cè)試結(jié)果如圖28所示。圖23 演示系統(tǒng)操作圖3 測(cè)試計(jì)劃測(cè)試功能及序號(hào)輸入函數(shù)的參數(shù)預(yù)計(jì)輸出此時(shí)二叉樹(shù)的狀態(tài)無(wú)二叉樹(shù)創(chuàng)建成功二叉樹(shù)根結(jié)點(diǎn)指針置為空，未分配具體的存儲(chǔ)空間無(wú)二叉樹(shù)銷(xiāo)毀失敗二叉樹(shù)頭指針置為空，對(duì)應(yīng)的存儲(chǔ)空間被釋放依次輸入關(guān)鍵字及其對(duì)應(yīng)值：A1 B9 D7 E0H1I2C9F6G2J0二叉樹(shù)創(chuàng)建成功按照輸入關(guān)鍵字的先序序列創(chuàng)建二叉樹(shù)，每個(gè)結(jié)點(diǎn)賦值無(wú)二叉樹(shù)清空成功二叉樹(shù)根結(jié)點(diǎn)保留，但其左右指針域置為空無(wú)二叉樹(shù)不為空同上3無(wú)二叉樹(shù)的深度為4同上3無(wú)二叉樹(shù)的根結(jié)點(diǎn)關(guān)鍵字為A同上3輸入關(guān)鍵字為D輸出關(guān)鍵字為D的結(jié)點(diǎn)值為7同上3輸入關(guān)鍵字E輸入關(guān)鍵字為E的結(jié)點(diǎn)的值改為9輸出關(guān)鍵字為E的結(jié)點(diǎn)的值已改為9同上3輸入查找關(guān)鍵字為I的結(jié)點(diǎn)輸出關(guān)鍵字為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)為E同上3(測(cè)試1)輸入查找關(guān)鍵字為E的結(jié)點(diǎn)輸出關(guān)鍵字為E的結(jié)點(diǎn)的左孩子為H同上3（測(cè)試2）輸入查找關(guān)鍵字為F的結(jié)點(diǎn)輸出關(guān)鍵字為F的左孩子不存在，查找失敗同上3（測(cè)試1）輸入查找關(guān)鍵字為B的結(jié)點(diǎn)輸出關(guān)鍵字為B的結(jié)點(diǎn)右孩子為E同上3（測(cè)試2）輸入查找關(guān)鍵字為F的結(jié)點(diǎn)輸出關(guān)鍵字為F的右孩子不存在，操作失敗同上3（測(cè)試1）輸入查找關(guān)鍵字為G的結(jié)點(diǎn)輸出關(guān)鍵字為G的結(jié)點(diǎn)左孩子為F同上3（測(cè)試2）輸入查找關(guān)鍵字為B的結(jié)點(diǎn)輸出關(guān)鍵字為B的結(jié)點(diǎn)左孩子不存在，操作失敗同上3輸入LR值為0，輸入查找關(guān)鍵字為J，新生成右子樹(shù)為空的二叉樹(shù)輸入：M1N2K3（字母后為該關(guān)鍵字結(jié)點(diǎn)的值）輸出二叉樹(shù)插入成功在原二叉樹(shù)的基礎(chǔ)上，將新生成二叉樹(shù)作為關(guān)鍵字為J的結(jié)點(diǎn)的左子樹(shù)，J的左子樹(shù)作為新生成二叉樹(shù)的右子樹(shù)輸入查找關(guān)鍵字為E的結(jié)點(diǎn)，輸入LR值為1輸出二叉樹(shù)刪除成功在上一基礎(chǔ)上，將原二叉樹(shù)的E結(jié)點(diǎn)的右子樹(shù)刪除無(wú)輸出先序遍歷序列：ABDEHICFGJ同上3無(wú)輸出中序遍歷序列：DBHEIAFCGJ同上3無(wú)輸出后續(xù)遍歷序列：DHIEBFJGCA同上3無(wú)輸出層序遍歷序列：ABCDEFGHIJ同上3表21 測(cè)試計(jì)劃圖24 按以上測(cè)試用例生成的原始二叉樹(shù) 測(cè)試，測(cè)試結(jié)果如圖25所示。typedef BiTree QElemType。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。1 前序遍歷的算法思想是：將前序遍歷寫(xiě)成函數(shù)，函數(shù)的形參是二叉樹(shù)的頭指針，首先訪(fǎng)問(wèn)根結(jié)點(diǎn)，并對(duì)其執(zhí)行遍歷操作，操作成功后采取遞歸的方式遍歷根結(jié)點(diǎn)的左子樹(shù)，返回值為OK時(shí)繼續(xù)遍歷其右子樹(shù)，最終遍歷完成。1 插入子樹(shù)的算法思想是：將插入子樹(shù)寫(xiě)成函數(shù)，函數(shù)的形參是二叉樹(shù)的頭指針T，指向特定二叉樹(shù)結(jié)點(diǎn)的指針p（在主函數(shù)中要求輸入關(guān)鍵字，通過(guò)FIND函數(shù)找到插入點(diǎn)位置并將其值記錄），再調(diào)用CreateBiTNode函數(shù)創(chuàng)建根結(jié)點(diǎn)c的右子樹(shù)為空的二叉樹(shù)，插入的過(guò)程即將P所指向結(jié)點(diǎn)的左子樹(shù)或者右子樹(shù)根結(jié)點(diǎn)指針賦值給c的右孩子指針域，而c賦值給p所指結(jié)點(diǎn)的左指針域或者右指針域。如果根結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字一致，且其左孩子存在，則返回其左孩子關(guān)鍵字，否則遞歸調(diào)用原函數(shù)分別將根結(jié)點(diǎn)的左右子樹(shù)根結(jié)點(diǎn)指針作為形參，若返回值非空則返回該值。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。 獲得雙親結(jié)點(diǎn)的算法思想是：將獲得雙親結(jié)點(diǎn)寫(xiě)成函數(shù)，函數(shù)的參數(shù)是二叉樹(shù)的頭指針，若頭指針為空，則返回空；否則，如果頭指針左孩子或右孩子不為空且關(guān)鍵字與給定關(guān)鍵字相同，返回根結(jié)點(diǎn)，如果不同，采取遞歸的方式調(diào)用原函數(shù)，傳入的參數(shù)分別為根結(jié)點(diǎn)的左右子樹(shù)的根結(jié)點(diǎn)?；蛘卟扇》沁f歸的方式，即使用堆棧來(lái)存儲(chǔ)根結(jié)點(diǎn)的信息，先將根結(jié)點(diǎn)入棧，在循環(huán)中彈出棧頂元素，比較關(guān)鍵字，在分別將其右子樹(shù)和左子樹(shù)的根結(jié)點(diǎn)入棧。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。 創(chuàng)建二叉樹(shù)算法思想：將二叉樹(shù)的創(chuàng)建過(guò)程寫(xiě)成函數(shù)，函數(shù)的參數(shù)是指向二叉樹(shù)根結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型指針T，按照先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值，如果第一個(gè)字符為，則T為空二叉樹(shù)。圖21 系統(tǒng)設(shè)計(jì)結(jié)構(gòu)圖 運(yùn)算算法思想與設(shè)計(jì) 二叉樹(shù)運(yùn)算算法思想與設(shè)計(jì)如下： 初始化二叉樹(shù)算法思想：將初始化二叉樹(shù)過(guò)程寫(xiě)成函數(shù)，函數(shù)的參數(shù)是主函數(shù)中所定義的結(jié)構(gòu)類(lèi)型指針T（參數(shù)傳遞為引用方式，即取別名），T所指向的是二叉樹(shù)的根結(jié)點(diǎn)，將T賦值為NULL即完成了二叉樹(shù)的初始化。}BiTNode,*BiTree。演示系統(tǒng)可選擇實(shí)現(xiàn)線(xiàn)性表的文件形式保存，演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線(xiàn)性表的管理。⒇按層遍歷：函數(shù)名稱(chēng)是LevelOrderTraverse(T,Visit))；初始條件是二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是層序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。 操作結(jié)果是根據(jù)LR為0或者1，刪除c為T(mén)中p所指結(jié)點(diǎn)的左或右子樹(shù)。⒁獲得右兄弟結(jié)點(diǎn)：函數(shù)名稱(chēng)是RightSibling(T,e)；初始條件是二叉樹(shù)T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右兄弟結(jié)點(diǎn)指針。⑿獲得右孩子結(jié)點(diǎn)：函數(shù)名稱(chēng)是RightChild(T,e)；初始條件是二叉樹(shù)T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右孩子結(jié)點(diǎn)指針。e,value)；初始條件是二叉樹(shù)T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是結(jié)點(diǎn)e賦值為value。⑹求二叉樹(shù)深度：函數(shù)名稱(chēng)是BiTreeDepth(T)；初始條件是二叉樹(shù)T存在；操作結(jié)果是返回T的深度。⑵銷(xiāo)毀二叉：樹(shù)函數(shù)名稱(chēng)是DestroyBiTree(T)；初始條件是二叉樹(shù)T已存在；操作結(jié)果是銷(xiāo)毀二叉樹(shù)T。 邏輯結(jié)構(gòu)與基本運(yùn)算 抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的定義如下：ADT BinaryTree { 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合?！狈?hào)。并且我還加深了對(duì)線(xiàn)性表的存在與空的區(qū)別。圖117 保存線(xiàn)性表測(cè)試結(jié)果，在執(zhí)行功能14，加載線(xiàn)性表，測(cè)試結(jié)果如圖118所示。圖113 查找數(shù)據(jù)元素的測(cè)試結(jié)果，確定值為4的數(shù)據(jù)元素前驅(qū)數(shù)據(jù)元素，測(cè)試結(jié)果如圖114所示。圖19 刪除線(xiàn)性表的操作結(jié)果，往線(xiàn)性表中添加數(shù)據(jù)元素1,2,3,4,5，測(cè)試結(jié)果如圖110所示。如圖16所示。 系統(tǒng)演示操作。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。該算法的程序流程圖如圖13所示。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。圖12 線(xiàn)性表查找算法流程圖7. 獲得前驅(qū)算法思想：將獲得前驅(qū)過(guò)程寫(xiě)成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類(lèi)型變量以及特定數(shù)據(jù)元素的值，接受前驅(qū)的變量作為另一個(gè)參數(shù)，首先調(diào)用獲得元素的函數(shù)判斷該線(xiàn)性表中特定數(shù)據(jù)元素的位序，首先判斷不為1，否則的話(huà)返回FALSE，[j2]。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。經(jīng)分許，該算法的時(shí)間復(fù)雜度為O(1)。2. 銷(xiāo)毀線(xiàn)性表思想：將銷(xiāo)毀線(xiàn)性表的過(guò)程寫(xiě)成函數(shù)，其中傳入函數(shù)是主函數(shù)中定義的結(jié)構(gòu)性變量L。進(jìn)入循環(huán)后系統(tǒng)首先顯示功能菜單，然后用戶(hù)輸入選擇014，其中114分別代表線(xiàn)性表的一個(gè)基本運(yùn)算，在主函數(shù)中通過(guò)SWITCH語(yǔ)句對(duì)應(yīng)到相應(yīng)的函數(shù)功能，執(zhí)行完該功能后BREAK跳出SWITCH語(yǔ)句，繼續(xù)執(zhí)行while循環(huán)，直至用戶(hù)輸入0退出當(dāng)前演示系統(tǒng)。 //線(xiàn)性表的長(zhǎng)度 int listsize。附錄 B 提供了文件存取的方法。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。⑽插入元素：函數(shù)名稱(chēng)是ListInsert(L,i,e)；初始條件是線(xiàn)性表L已存在且非空，1≤i≤ListLength(L)+1；操作結(jié)果是在L的第i個(gè)位置之前插入新的數(shù)據(jù)元素e。⑹獲得元素：函數(shù)名稱(chēng)是GetElem(L,i,e)；初始條件是線(xiàn)性表已存在，1≤i≤ListLength(L)；操作結(jié)果是用e返回L中第i個(gè)數(shù)據(jù)元素的值。⑵銷(xiāo)毀表：函數(shù)名稱(chēng)是DestroyList(L)；初始條件是線(xiàn)性表L已存在；操作結(jié)果是銷(xiāo)毀線(xiàn)性表L。線(xiàn)性表中元素的個(gè)數(shù)n定義為線(xiàn)性表的長(zhǎng)度，n=0時(shí)成為空表。課 程 實(shí) 驗(yàn) 報(bào) 告課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 專(zhuān)業(yè)班級(jí)： 信息安全201502 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： 報(bào)告日期： 2016年 10月 28 日 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院華中科技大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告目 1基于順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表實(shí)現(xiàn) 1 1 1 1 12 基于二叉鏈表的二叉樹(shù)實(shí)現(xiàn) 2 2 2 2 2指導(dǎo)教師評(píng)定意見(jiàn) 3附錄A 基于順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表實(shí)現(xiàn)的源程序 4附錄B 基于二叉鏈表二叉樹(shù)實(shí)現(xiàn)的源程序 5章為宋體小4號(hào)加粗，其余宋體小4號(hào)，,段落前后0行華中科技大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1 基于順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表實(shí)現(xiàn)黑體小2加粗，居中， 問(wèn)題描述黑體4號(hào)加粗，采用順序表的物理結(jié)構(gòu)，構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。 線(xiàn)性表的基本概念線(xiàn)性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，即n個(gè)數(shù)據(jù)元素的有限序列。 邏輯結(jié)構(gòu)與基本運(yùn)算線(xiàn)性表的數(shù)據(jù)邏輯結(jié)構(gòu)定義如下: ADT List｛ 數(shù)據(jù)對(duì)象：D=｛ai|ai∈ElemSet，i=1，2，……，n，n≥0｝ 數(shù)據(jù)關(guān)系：R1=｛ ai1，ai | ai1，ai∈D，i=2，……，n｝ ｝ 依據(jù)最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了包括線(xiàn)性表的初始化表、加載表、保存表、銷(xiāo)毀表、清空表、判定空表、求表長(zhǎng)、獲得元素、查找元素、獲得前驅(qū)、獲得后繼、插入元素、刪除元素、遍歷表 14 個(gè)基本運(yùn)算，要求分別定義函數(shù)來(lái)實(shí)現(xiàn)上述功能，具體功能運(yùn)算如下：⑴初始化表：函數(shù)名稱(chēng)是InitaList(L)；初始條件是線(xiàn)性表L不存在已存在；操作結(jié)果是構(gòu)造一個(gè)空的線(xiàn)性表。⑸求表長(zhǎng)：函數(shù)名稱(chēng)是ListLength(L)；初始條件是線(xiàn)性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個(gè)數(shù)。⑼獲得后繼：函數(shù)名稱(chēng)是NextElem(L,cur_e,next_e)；初始條件是線(xiàn)性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。 演示系統(tǒng)與數(shù)據(jù)文件要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，①需要設(shè)計(jì)文件數(shù)據(jù)記錄格式，以高效保存線(xiàn)性表數(shù)據(jù)邏輯結(jié)構(gòu)(D,{R})的完整信息；②需要設(shè)計(jì)線(xiàn)性表文件保存和加載操作合理模式。 //定義整型指針，為存儲(chǔ)空間基址 int length。 演示系統(tǒng) 將菜單演示和用戶(hù)選擇寫(xiě)入到while循環(huán)中，用OP獲取用戶(hù)的選擇，OP初始化為1，以便第一次能進(jìn)入循環(huán)。經(jīng)分析，算法的時(shí)間復(fù)雜度為O(1)。3. 清空線(xiàn)性表的思想：將清空表的過(guò)程寫(xiě)成函數(shù)，其中將主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)參數(shù)，在函數(shù)中，由于清空操作并不釋放內(nèi)存空間，故只需將線(xiàn)性表的長(zhǎng)度置為0即可。5. 獲得元素的算法思想：將獲得線(xiàn)性表元素寫(xiě)成函數(shù)，其中函數(shù)的參數(shù)是結(jié)構(gòu)型變量L以及數(shù)據(jù)元素的序號(hào)i，由于采取的是線(xiàn)性存儲(chǔ)結(jié)構(gòu)，[i1]來(lái)獲取元素，當(dāng)然，在這之前需要判斷合法性。查找算法的流程圖如圖12所示。首先判斷是否為最后一個(gè)元素，如果不是則直接返回其后一個(gè)元素，否則的話(huà)返回FALSE，同樣該算法需要調(diào)用獲得元素的函數(shù)來(lái)確定該特定元素在線(xiàn)性表中的次序。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。11. 遍歷線(xiàn)性表算法思想：將遍歷線(xiàn)性表寫(xiě)成一個(gè)函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)類(lèi)型變量，直接用一個(gè)循環(huán)來(lái)對(duì)線(xiàn)性表中的每一個(gè)元素進(jìn)行操作。typedef int ElemType。