【正文】 while時(shí)首先會(huì)詢問(wèn)用戶對(duì)哪個(gè)線性表進(jìn)行操作，直至退出演示系統(tǒng)之前一直對(duì)指定線性表進(jìn)行操作。 //當(dāng)前分配的存儲(chǔ)容量(以 sizeof(ElemType)為單位) }SqList。 演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線性表管理。附錄 A 提供了簡(jiǎn)易菜單的框架。⑾刪除元素：函數(shù)名稱是ListDelete(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)；操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，用e返回其值。⑺查找元素：函數(shù)名稱是LocateElem(L,e,pare())；初始條件是線性表已存在；操作結(jié)果是返回L中第1個(gè)與e滿足關(guān)系pare（）關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。⑶清空表：函數(shù)名稱是ClearList(L)；初始條件是線性表L已存在；操作結(jié)果是將L重置為空表。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示。定義了線性表的初始化表、銷毀表、清空表、判定空表、求表長(zhǎng)和獲得元素等基本運(yùn)算對(duì)應(yīng)的函數(shù)，并給出適當(dāng)?shù)牟僮魈崾撅@示，可選擇以文件的形式進(jìn)行存儲(chǔ)和加載，即將生成的線性表存入到相應(yīng)的文件中，也可以從文件中獲取線性表進(jìn)行操作。線性表的存儲(chǔ)結(jié)構(gòu)分為線性存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。⑷判定空表：函數(shù)名稱是ListEmpty(L)；初始條件是線性表L已存在；操作結(jié)果是若L為空表則返回TRUE,否則返回FALSE。⑻獲得前驅(qū)：函數(shù)名稱是PriorElem(L,cur_e,pre_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。⑿遍歷表：函數(shù)名稱是ListTraverse(L,visit())，初始條件是線性表L已存在；操作結(jié)果是依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。 演示系統(tǒng)可選擇實(shí)現(xiàn)線性表的文件形式保存。 系統(tǒng)設(shè)計(jì)黑體4號(hào)加粗， 數(shù)據(jù)物理結(jié)構(gòu)線性表的數(shù)據(jù)物理結(jié)構(gòu)如下： typedef struct { //順序表（順序結(jié)構(gòu)）的定義 ElemType *elem。 要實(shí)現(xiàn)同時(shí)對(duì)多個(gè)線性表管理，只需要定義一個(gè)結(jié)構(gòu)數(shù)組即可。演示系統(tǒng)結(jié)構(gòu)如圖11. 運(yùn)算算法思想與設(shè)計(jì) 線性表運(yùn)算算法思想與設(shè)計(jì)如下：1. 初始化線性表思想：將線性表初始化過(guò)程寫成函數(shù)，其中傳入函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)型變量L的引用，在函數(shù)中，首先使用malloc函數(shù)分配LISTSIZE大小的連續(xù)內(nèi)存空間，由于線性表的長(zhǎng)度為0，即完成了線性表的初始化。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。8. 獲得后繼算法思想：將獲得后繼寫成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類型變量以及特定數(shù)據(jù)元素的值。在函數(shù)中，首先判斷插入位置的合法性，即是否在線性表中合適的位置，其次還要判斷當(dāng)前存儲(chǔ)空間是否已滿，如果滿了的話要malloc函數(shù)重新分配空間，插入元素時(shí)從該位置起到最后一個(gè)元素從后開始以此往后移一個(gè)單元。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。 頭文件及預(yù)定義常量說(shuō)明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。圖14 系統(tǒng)演示1，進(jìn)入菜單演示界面，如圖15所示。圖17 系統(tǒng)演示4 測(cè)試計(jì)劃測(cè)試功能及序號(hào)輸入要管理的線性表序號(hào)輸入函數(shù)的參數(shù)（具體元素）預(yù)計(jì)輸出此時(shí)線性表的狀態(tài)1無(wú)線性表初始化成功分配了連續(xù)的物理存儲(chǔ)空間，表長(zhǎng)度為0，表尺寸為空間大小1無(wú)線性表刪除成功線性表連續(xù)物理空間被釋放， 1無(wú)線性表清空成功線性表的物理空間保留，但表長(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無(wú)輸出線性表非空同上1無(wú)輸出線性表的長(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所示。圖111 判斷線性表非空的測(cè)試結(jié)果，求線性表的長(zhǎng)度，測(cè)試結(jié)果如圖112所示。115 查找元素的后繼數(shù)據(jù)元素，刪除第三個(gè)數(shù)據(jù)元素，測(cè)試結(jié)果如圖116所示。圖119 遍歷輸出線性表中元素的測(cè)試結(jié)果 實(shí)驗(yàn)小結(jié)黑體4號(hào)加粗， 經(jīng)過(guò)本次試驗(yàn)，我充分了解到了線性表的物理結(jié)構(gòu)，并且通過(guò)切身的體會(huì)熟練掌握了線性表的基本操作，提高了自己寫有關(guān)線性表的代碼的能力，尤其是在寫的過(guò)程中遇到了許多困難，在多次尋求同學(xué)的幫助下終于解決了。”引用符號(hào)的理解，加強(qiáng)了其與“*”的區(qū)別，“amp。要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)，其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾尽＃?） 若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}）是一棵符合本定義的二叉樹，稱為根的右子樹。⑷清空二叉樹：函數(shù)名稱是ClearBiTree (T)；初始條件是二叉樹T存在； 操作結(jié)果是將二叉樹T清空。⑻獲得結(jié)點(diǎn)：函數(shù)名稱是Value(T,e)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的值。⑾獲得左孩子結(jié)點(diǎn)：函數(shù)名稱是LeftChild(T,e)；初始條件是二叉樹T存在，e是T中某個(gè)節(jié)點(diǎn)；操作結(jié)果是返回e的左孩子結(jié)點(diǎn)指針。⒀獲得左兄弟結(jié)點(diǎn)：函數(shù)名稱是LeftSibling(T,e)；初始條件是二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的左兄弟結(jié)點(diǎn)指針。⒂插入子樹：函數(shù)名稱是InsertChild(T,p,LR,c)；初始條件是二叉樹T存在，p指向T中的某個(gè)結(jié)點(diǎn)，LR為0或1，,非空二叉樹c與T不相交且右子樹為空；操作結(jié)果是根據(jù)LR為0或者1，插入c為T中p所指結(jié)點(diǎn)的左或右子樹，p 所指結(jié)點(diǎn)的原有左子樹或右子樹則為c的右子樹。⒅中序遍歷：函數(shù)名稱是InOrderTraverse(T,Visit))；初始條件是二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是中序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。其中，在主函數(shù)中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾尽?struct BiTNode *lchild, *rchild。Op初始化為1，以便第一次能進(jìn)入循環(huán)。 銷毀二叉樹算法思想：將二叉樹的銷毀過(guò)程寫成函數(shù)，函數(shù)的參數(shù)是指向二叉樹根結(jié)點(diǎn)的結(jié)構(gòu)類型指針T，采取遞歸的方式先銷毀二叉樹的左子樹，在銷毀二叉樹的右子樹，最后用free函數(shù)釋放掉根結(jié)點(diǎn)對(duì)應(yīng)的內(nèi)存空間。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。 結(jié)點(diǎn)賦值的算法思想是：將結(jié)點(diǎn)賦值寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針，主函數(shù)中輸入的關(guān)鍵字，根據(jù)關(guān)鍵字獲取到根結(jié)點(diǎn)，并對(duì)根結(jié)點(diǎn)賦值，思想同8，不在贅述。1 獲得左兄弟結(jié)點(diǎn)的算法思想是：將獲得左孩子結(jié)點(diǎn)寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針，如果頭指針為空，返回NULL；否則，如果二叉樹的根結(jié)點(diǎn)的右孩子關(guān)鍵字與給定關(guān)鍵字一致，返回根結(jié)點(diǎn)的左孩子。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。1 獲得右孩子結(jié)點(diǎn)的算法思想是：算法思想同上。1 刪除子樹的算法思想是：將刪除子樹寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，特定結(jié)點(diǎn)的指針，根據(jù)指向特定結(jié)點(diǎn)的指針找到給結(jié)點(diǎn)并將其左右孩子指針域置為空，對(duì)應(yīng)的還應(yīng)該在這之前調(diào)用DESTROY函數(shù)將其左子樹或右子樹銷毀。經(jīng)分許，該算法的時(shí)間復(fù)雜度為O(n)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。 頭文件及預(yù)定義常量說(shuō)明頭文件 include include include 預(yù)定義常量（1）函數(shù)結(jié)果狀態(tài)宏定義 define TRUE 1define FALSE 0define OK 1define ERROR 0define OVERFLOW 2（2）類型表達(dá)式 typedef int status。圖22 演示系統(tǒng)操作圖1~20，會(huì)執(zhí)行序號(hào)所對(duì)應(yīng)的操作。圖26 二叉樹創(chuàng)建，根據(jù)其前序遍歷、中序遍歷、后續(xù)遍歷的結(jié)果是否與預(yù)期一致判斷結(jié)構(gòu)是否正確。圖29 后序遍歷二叉樹的測(cè)試結(jié)果，層序遍歷二叉樹，測(cè)試結(jié)果如圖210所示。圖212 求二叉樹深度測(cè)試結(jié)果，求二叉樹的根結(jié)點(diǎn)，測(cè)試結(jié)果如圖213所示。圖216 查找左孩子的測(cè)試結(jié)果1，測(cè)試關(guān)鍵字為F的結(jié)點(diǎn)的左孩子，測(cè)試結(jié)果如圖217所示。圖220 查找結(jié)點(diǎn)的左兄弟測(cè)試結(jié)果2，在原二叉樹的基礎(chǔ)上插入子樹，測(cè)試結(jié)果如圖221所示。，刪除關(guān)鍵字為E的結(jié)點(diǎn)的右子樹，即I結(jié)點(diǎn)，測(cè)試結(jié)果如圖225所示。圖230 驗(yàn)證二叉樹為空 實(shí)驗(yàn)小結(jié)黑體4號(hào)加粗，通過(guò)本次實(shí)驗(yàn)，熟悉了二叉樹的基本操作，學(xué)會(huì)了用二叉樹去解決一些問(wèn)題，學(xué)習(xí)中的主要收獲為以下幾點(diǎn)： 加深了對(duì)二叉樹的概念和邏輯結(jié)構(gòu)的理解。 規(guī)范了報(bào)告撰寫能力。typedef struct { ElemType * elem。status Initlist(SqList amp。 = LIST_INIT_SIZE。 = NULL。 } return ERROR。 return OK。L) { if ( == 0) return TRUE。 else e = [i 1]。 j = 1。pre_e) { int j。 j != 1) { pre_e = [j 2]。next_e) { int j。 j != ) { next_e = [j]。L, int i, ElemType e) { ElemType *newbase, *p, *q。 = newbase。 for (p = amp。 *q = e。L, int i, ElemType amp。 p = amp。 pq。}status ListTrabverse(SqList L) { int i。 i++) printf(%d , [i])。 int i。 i = 1。 return OK。 char filename[30]。 return FALSE。 fclose(stream)。 while (t) { printf(請(qǐng)輸入對(duì)哪一個(gè)線性表進(jìn)行操作199，輸入0退出！\n)。 system(cls)。 int next_e。 printf(\n\n)。 printf( 2. DestroyList 9. NextElem\n)。 printf( 6. GetElem 13. SaveData\n)。 printf( 請(qǐng)選擇你的操作[0~12]:\n)。 else printf(線性表創(chuàng)建失?。n)。 case 2: //printf(\nDestroyList功能待實(shí)現(xiàn)！\n)。 getchar()。 else printf(線性表清空失??！\n)。 case 4: //printf(\nListEmpty功能待實(shí)現(xiàn)！\n)。 getchar()。 getchar()。 scanf(%d, amp。 else printf(L中線性表中第%d個(gè)數(shù)據(jù)元素的值為%d!\n, i, e)。 case 7: printf(請(qǐng)輸入需定位的數(shù)據(jù)元素的值！\n)。 i = LocateElem(L[t], e)。 getchar()。cur)。 getchar()。 scanf(%d, amp。 else printf(數(shù)據(jù)元素%d的后繼數(shù)據(jù)元素為%d!\n, cur, next_e)。 case 10: printf(請(qǐng)輸入插入新的數(shù)據(jù)元素位置以及數(shù)據(jù)元素值！\n)。 if (ListInsert(L[t], i, e) =