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