【正文】 函數(shù)名稱是RightChild(T,e)；初始條件是二叉樹T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右孩子結(jié)點(diǎn)指針。⑾獲得左孩子結(jié)點(diǎn)：函數(shù)名稱是LeftChild(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。⑻獲得結(jié)點(diǎn)：函數(shù)名稱是Value(T,e)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的值。⑹求二叉樹深度：函數(shù)名稱是BiTreeDepth(T)；初始條件是二叉樹T存在；操作結(jié)果是返回T的深度。⑷清空二叉樹：函數(shù)名稱是ClearBiTree (T)；初始條件是二叉樹T存在； 操作結(jié)果是將二叉樹T清空。⑵銷毀二叉：樹函數(shù)名稱是DestroyBiTree(T)；初始條件是二叉樹T已存在；操作結(jié)果是銷毀二叉樹T。（3） 若D1≠Φ，則D1中存在唯一的元素X1，root,X1∈H，且存在D1上的關(guān)系H1包含于H；若Dr≠Φ,則Dr中存在唯一的元素Xr，root,Xr∈H,且存在Dr上的關(guān)系屬于H；（4） （D，{H1}）是一棵符合本定義的二叉樹，稱為根的左子樹，（Dr，{Hr}）是一棵符合本定義的二叉樹，稱為根的右子樹。 邏輯結(jié)構(gòu)與基本運(yùn)算 抽象數(shù)據(jù)類型二叉樹的定義如下：ADT BinaryTree { 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)，其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾尽！狈?hào)?！币梅?hào)的理解，加強(qiáng)了其與“*”的區(qū)別，“amp。并且我還加深了對(duì)線性表的存在與空的區(qū)別。圖119 遍歷輸出線性表中元素的測(cè)試結(jié)果 實(shí)驗(yàn)小結(jié)黑體4號(hào)加粗， 經(jīng)過本次試驗(yàn)，我充分了解到了線性表的物理結(jié)構(gòu)，并且通過切身的體會(huì)熟練掌握了線性表的基本操作，提高了自己寫有關(guān)線性表的代碼的能力，尤其是在寫的過程中遇到了許多困難，在多次尋求同學(xué)的幫助下終于解決了。圖117 保存線性表測(cè)試結(jié)果，在執(zhí)行功能14，加載線性表，測(cè)試結(jié)果如圖118所示。115 查找元素的后繼數(shù)據(jù)元素，刪除第三個(gè)數(shù)據(jù)元素，測(cè)試結(jié)果如圖116所示。圖113 查找數(shù)據(jù)元素的測(cè)試結(jié)果，確定值為4的數(shù)據(jù)元素前驅(qū)數(shù)據(jù)元素，測(cè)試結(jié)果如圖114所示。圖111 判斷線性表非空的測(cè)試結(jié)果，求線性表的長(zhǎng)度，測(cè)試結(jié)果如圖112所示。圖19 刪除線性表的操作結(jié)果，往線性表中添加數(shù)據(jù)元素1,2,3,4,5，測(cè)試結(jié)果如圖110所示。圖17 系統(tǒng)演示4 測(cè)試計(jì)劃測(cè)試功能及序號(hào)輸入要管理的線性表序號(hào)輸入函數(shù)的參數(shù)（具體元素）預(yù)計(jì)輸出此時(shí)線性表的狀態(tài)1無線性表初始化成功分配了連續(xù)的物理存儲(chǔ)空間，表長(zhǎng)度為0，表尺寸為空間大小1無線性表刪除成功線性表連續(xù)物理空間被釋放， 1無線性表清空成功線性表的物理空間保留，但表長(zhǎng)置為0.(多次調(diào)用)1輸入1：1，2：2，3：3，4：4，5：5線性表創(chuàng)建成功創(chuàng)建了一個(gè)線性表，序列為：1，2，3，4，51無輸出線性表非空同上1無輸出線性表的長(zhǎng)度為5同上1輸入數(shù)據(jù)元素的位序?yàn)?輸出線性表的第三個(gè)元素為3同上1輸入數(shù)據(jù)元素的值為4輸出4的前面一個(gè)元素是3同上1輸入數(shù)據(jù)元素的值為2輸出2的后面一個(gè)元素是3同上1輸入數(shù)據(jù)元素的置為3輸出元素刪除成功重新生成了一新的線性表，序列為12451輸入數(shù)據(jù)元素的值為4輸出4是線性表中的第三個(gè)數(shù)據(jù)元素同上1輸出文件保存成功同上1輸出文件加載成功同上 測(cè)試，進(jìn)入菜單演示界面，執(zhí)行功能1，初始化線性表，測(cè)試結(jié)果如圖18所示。如圖16所示。圖14 系統(tǒng)演示1，進(jìn)入菜單演示界面，如圖15所示。 系統(tǒng)演示操作。 頭文件及預(yù)定義常量說明include include include define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASTABLE 1define OVERFLOW 2define LIST_INIT_SIZE 100define LISTINCREMENT 10 typedef int status。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。該算法的程序流程圖如圖13所示。在函數(shù)中，首先判斷插入位置的合法性，即是否在線性表中合適的位置，其次還要判斷當(dāng)前存儲(chǔ)空間是否已滿，如果滿了的話要malloc函數(shù)重新分配空間，插入元素時(shí)從該位置起到最后一個(gè)元素從后開始以此往后移一個(gè)單元。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。8. 獲得后繼算法思想：將獲得后繼寫成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類型變量以及特定數(shù)據(jù)元素的值。圖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（n）。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。經(jīng)分許，該算法的時(shí)間復(fù)雜度為O(1)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。2. 銷毀線性表思想：將銷毀線性表的過程寫成函數(shù)，其中傳入函數(shù)是主函數(shù)中定義的結(jié)構(gòu)性變量L。演示系統(tǒng)結(jié)構(gòu)如圖11. 運(yùn)算算法思想與設(shè)計(jì) 線性表運(yùn)算算法思想與設(shè)計(jì)如下：1. 初始化線性表思想：將線性表初始化過程寫成函數(shù)，其中傳入函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)型變量L的引用，在函數(shù)中，首先使用malloc函數(shù)分配LISTSIZE大小的連續(xù)內(nèi)存空間，由于線性表的長(zhǎng)度為0，即完成了線性表的初始化。進(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)。 要實(shí)現(xiàn)同時(shí)對(duì)多個(gè)線性表管理，只需要定義一個(gè)結(jié)構(gòu)數(shù)組即可。 //線性表的長(zhǎng)度 int listsize。 系統(tǒng)設(shè)計(jì)黑體4號(hào)加粗， 數(shù)據(jù)物理結(jié)構(gòu)線性表的數(shù)據(jù)物理結(jié)構(gòu)如下： typedef struct { //順序表（順序結(jié)構(gòu)）的定義 ElemType *elem。附錄 B 提供了文件存取的方法。 演示系統(tǒng)可選擇實(shí)現(xiàn)線性表的文件形式保存。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。⑿遍歷表：函數(shù)名稱是ListTraverse(L,visit())，初始條件是線性表L已存在；操作結(jié)果是依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。⑽插入元素：函數(shù)名稱是ListInsert(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)+1；操作結(jié)果是在L的第i個(gè)位置之前插入新的數(shù)據(jù)元素e。⑻獲得前驅(qū)：函數(shù)名稱是PriorElem(L,cur_e,pre_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。⑹獲得元素：函數(shù)名稱是GetElem(L,i,e)；初始條件是線性表已存在，1≤i≤ListLength(L)；操作結(jié)果是用e返回L中第i個(gè)數(shù)據(jù)元素的值。⑷判定空表：函數(shù)名稱是ListEmpty(L)；初始條件是線性表L已存在；操作結(jié)果是若L為空表則返回TRUE,否則返回FALSE。⑵銷毀表：函數(shù)名稱是DestroyList(L)；初始條件是線性表L已存在；操作結(jié)果是銷毀線性表L。線性表的存儲(chǔ)結(jié)構(gòu)分為線性存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。線性表中元素的個(gè)數(shù)n定義為線性表的長(zhǎng)度，n=0時(shí)成為空表。定義了線性表的初始化表、銷毀表、清空表、判定空表、求表長(zhǎng)和獲得元素等基本運(yùn)算對(duì)應(yīng)的函數(shù)，并給出適當(dāng)?shù)牟僮魈崾撅@示，可選擇以文件的形式進(jìn)行存儲(chǔ)和加載，即將生成的線性表存入到相應(yīng)的文件中，也可以從文件中獲取線性表進(jìn)行操作。課 程 實(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)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示。 線性表的基本概念線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，即n個(gè)數(shù)據(jù)元素的有限序列。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(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è)空的線性表。⑶清空表：函數(shù)名稱是ClearList(L)；初始條件是線性表L已存在；操作結(jié)果是將L重置為空表。⑸求表長(zhǎng)：函數(shù)名稱是ListLength(L)；初始條件是線性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個(gè)數(shù)。⑺查找元素：函數(shù)名稱是LocateElem(L,e,pare())；初始條件是線性表已存在；操作結(jié)果是返回L中第1個(gè)與e滿足關(guān)系pare（）關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。⑼獲得后繼：函數(shù)名稱是NextElem(L,cur_e,next_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義。⑾刪除元素：函數(shù)名稱是ListDelete(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)；操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，用e返回其值。 演示系統(tǒng)與數(shù)據(jù)文件要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。附錄 A 提供了簡(jiǎn)易菜單的框架。其中，①需要設(shè)計(jì)文件數(shù)據(jù)記錄格式，以高效保存線性表數(shù)據(jù)邏輯結(jié)構(gòu)(D,{R})的完整信息；②需要設(shè)計(jì)線性表文件保存和加載操作合理模式。 演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線性表管理。 //定義整型指針，為存儲(chǔ)空間基址 int length。 //當(dāng)前分配的存儲(chǔ)容量(以 sizeof(ElemType)為單位) }SqList。 演示系統(tǒng) 將菜單演示和用戶選擇寫入到while循環(huán)中，用OP獲取用戶的選擇，OP初始化為1，以便第一次能進(jìn)入循環(huán)。在第一次進(jìn)入循環(huán)while時(shí)首先會(huì)詢問用戶對(duì)哪個(gè)線性表進(jìn)行操作，直至退出演示系統(tǒng)之前一直對(duì)指定線性表進(jìn)行操作。經(jīng)分析，算法的時(shí)間復(fù)雜度為O(1)。在函數(shù)中，,。3. 清空線性表的思想：將清空表的過程寫成函數(shù)，其中將主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)參數(shù)，在函數(shù)中，由于清空操作并不釋放內(nèi)存空間，故只需將線性表的長(zhǎng)度置為0即可。4. 求線性表表長(zhǎng)的思想：將求表長(zhǎng)過程寫成函數(shù)，其中主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)的參數(shù)，在函數(shù)中。5. 獲得元素的算法思想：將獲得線性表元素寫成函數(shù)，其中函數(shù)的參數(shù)是結(jié)構(gòu)型變量L以及數(shù)據(jù)元素的序號(hào)i，由于采取的是線性存儲(chǔ)結(jié)構(gòu)，[i1]來獲取元素，當(dāng)然，在這之前需要判斷合法性。6. 查找元素的算法思想：將查找線性表特定值的數(shù)據(jù)元素寫成函數(shù)，其中函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)類型變量L以及查找的數(shù)據(jù)元素的值，通過循環(huán)對(duì)線性表中的每一個(gè)元素與給定值比較看是否相等，如果相等就返回該元素的次序。查找算法的流程圖如圖12所示。經(jīng)分析，