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