基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】

基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第1頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)實驗基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)

基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第2頁。目錄基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第2頁。TOC\o"1-2"\h\z\u1基于順序存儲結(jié)構(gòu)的線性表實現(xiàn) 21.1問題描述 21.2系統(tǒng)設(shè)計 31.3系統(tǒng)實現(xiàn) 181.4實驗小結(jié) 30附錄A基于順序存儲結(jié)構(gòu)線性表實現(xiàn)的源程序 34

基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第3頁。1基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第3頁。1.1問題描述構(gòu)造順序表，呈現(xiàn)一個簡易菜單的功能演示系統(tǒng)，該演示系統(tǒng)可選擇實現(xiàn)多個線性表管理。需要在主程序中完成函數(shù)調(diào)用以及所需實參值和函數(shù)執(zhí)行結(jié)果的輸出。定義線性表的初始化表、銷毀表、清空表、判定空表、求表長和獲得元素等函數(shù)，并給出適當(dāng)?shù)牟僮魈崾?，并且可選擇以文件的形式進行存儲和加載。依據(jù)最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了線性表的初始化表、銷毀表、清空表、判定空表、求表長和獲得元素等12種基本運算，具體運算功能定義如下。⑴初始化表：函數(shù)名稱是InitaList(L)；初始條件是線性表L不存在已存在；操作結(jié)果是構(gòu)造一個空的線性表。⑵銷毀表：函數(shù)名稱是DestroyList(L)；初始條件是線性表L已存在；操作結(jié)果是銷毀線性表L。⑶清空表：函數(shù)名稱是ClearList(L)；初始條件是線性表L已存在；操作結(jié)果是將L重置為空表。⑷判定空表：函數(shù)名稱是ListEmpty(L)；初始條件是線性表L已存在；操作結(jié)果是若L為空表則返回TRUE,否則返回FALSE。⑸求表長：函數(shù)名稱是ListLength(L)；初始條件是線性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個數(shù)。⑹獲得元素：函數(shù)名稱是GetElem(L,i,e)；初始條件是線性表已存在，1≤i≤ListLength(L)；操作結(jié)果是用e返回L中第i個數(shù)據(jù)元素的值。⑺查找元素：函數(shù)名稱是LocateElem(L,e,compare())；初始條件是線性表已存在；操作結(jié)果是返回L中第1個與e滿足關(guān)系compare（）關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。⑻獲得前驅(qū)：函數(shù)名稱是PriorElem(L,cur_e,pre_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。⑼獲得后繼：函數(shù)名稱是NextElem(L,cur_e,next_e)；初始條件是線性表L基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第4頁。已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第4頁。⑽插入元素：函數(shù)名稱是ListInsert(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)+1；操作結(jié)果是在L的第i個位置之前插入新的數(shù)據(jù)元素e。⑾刪除元素：函數(shù)名稱是ListDelete(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)；操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，用e返回其值。⑿遍歷表：函數(shù)名稱是ListTraverse(L,visit())，初始條件是線性表L已存在；操作結(jié)果是依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。1.1.1實驗?zāi)康?1)加深對線性表的概念、基本運算的理解；(2)熟練掌握線性表的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系；(3)物理結(jié)構(gòu)采用順序表,熟練掌握線性表的基本運算的實現(xiàn)。1.2系統(tǒng)設(shè)計1.2.1系統(tǒng)總體設(shè)計本系統(tǒng)提供一個順序存儲的線性表。菜單可供選擇的操作有：初始化線性表、銷毀表、清空表、判空表，求表長、得到某元素、查找元素、獲得某元素的前驅(qū)、獲得某元素的后繼、插入元素、刪除元素、遍歷線性表。1.2.2有關(guān)常量和類型定義數(shù)據(jù)元素類型的定義：typedefintstatus;typedefintElemType;有關(guān)常量的定義：#defineTRUE1基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第5頁。#defineFALSE0基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第5頁。#defineOK1#defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineMAX_NUM101.2.3算法設(shè)計(1)函數(shù)名稱：InitaList(L)；初始條件：線性表L不存在已存在；操作結(jié)果：是構(gòu)造一個空的線性表；算法思路：先分配存儲空間后，將表長設(shè)為0，再將線性表容量設(shè)為預(yù)定義的初始存儲容量，圖1-1為InitaList(L)函數(shù)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第6頁。圖1-1InitaList(L)流程圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第6頁。(2)函數(shù)名稱：DestroyList(L)；初始條件：線性表L已存在；操作結(jié)果：銷毀線性表L；算法思路：釋放內(nèi)存并將各數(shù)據(jù)設(shè)置為初值，圖1-2為DestroyList(L)的流程圖。圖1-2DestroyList(L)流程圖(3)函數(shù)名稱：ClearList(L)；初始條件：線性表L已存在；操作結(jié)果：將L重置為空表；算法思路：將表長設(shè)為0即可，圖1-3為ClearList(L)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第7頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第7頁。圖1-3ClearList(L)流程圖(4)函數(shù)名稱：ListEmpty(L)；初始條件：線性表L已存在；操作結(jié)果：若L為空表則返回TRUE,否則返回FALSE；算法思路：表長為0則為空表，否則不是空表，圖1-4為ListEmpty(L)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第8頁。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第8頁。圖1-4ListEmpty(L)流程圖(5)函數(shù)名稱：ListLength(L)；初始條件：線性表已存在；操作結(jié)果：返回L中數(shù)據(jù)元素的個數(shù)；算法思路：返回線性表表長的值，圖1-5為ListLength(L)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第9頁。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第9頁。圖1-5ListLength(L)流程圖(6)函數(shù)名稱：GetElem(L,i,e)；初始條件：線性表已存在，1≤i≤ListLength(L)；操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值；算法思路：將線性表中第i個數(shù)據(jù)元素的值賦值給e，圖1-6為GetElem(L,i,e)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第10頁。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第10頁。圖1-6GetElem(L,i,e)流程圖(7)函數(shù)名稱：LocateElem(L,e,compare())；初始條件：線性表已存在；操作結(jié)果：返回線性表中第1個與e相等的數(shù)據(jù)元素的位置，若這樣的數(shù)據(jù)元素不存在，則返回值為0；算法思路：先遍歷順序表，將線性表中的數(shù)據(jù)元素依次與e進行比較，返回該元素的位序，圖1-7為LocateElem(L,e,compare())的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第11頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第11頁。圖1-7LocateElem(L,e,compare())流程圖(8)函數(shù)名稱：PriorElem(L,cur_e,pre_e)；初始條件：線性表L已存在；操作結(jié)果：若cur_e是L的數(shù)據(jù)元素并且不是第一個數(shù)據(jù)元素，用pre_e返回它的前驅(qū)，否則操作失敗。算法思路：首先遍歷該順序表。若找到該結(jié)點，并且該結(jié)點有前驅(qū)元素，則將前驅(qū)元素賦值給pre_e。若未找到該結(jié)點，或者找到該結(jié)點但該結(jié)點不存在前驅(qū)元素，則返回FALSE。圖1-8為PriorElem(L,cur_e,pre_e)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第12頁。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第12頁。圖1-8PriorElem(L,cur_e,pre_e)流程圖(9)函數(shù)名稱：NextElem(L,cur_e,next_e)初始條件：線性表L已存在；操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。算法思路：先遍歷線性表，如果找到該結(jié)點并且該結(jié)點有后繼元素，則將后繼節(jié)點元素賦值給next_e。若未找到該結(jié)點，或者找到該結(jié)點但該結(jié)點不存在后繼元素，則返回FALSE。圖1-9為NextElem(L,cur_e,next_e)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第13頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第13頁。圖1-9NextElem(L,cur_e,next_e)流程圖(10)函數(shù)名稱：ListInsert(L,i,e)初始條件：線性表L已存在且非空，1≤i≤ListLength(L)+1；操作結(jié)果：在L的第i個位置之前插入新的數(shù)據(jù)元素e。算法思路：先遍歷順序表，若線性表L已存在且不為空，輸入的i值不合法，則返回ERROR。若滿足線性表L已存在且L非空，并且i的值合法，則在線性表的第i個位置之前插入新的數(shù)據(jù)元素e，返回OK。圖1-10為ListInsert(L,i,e)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第14頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第14頁。圖1-10ListInsert(L,i,e)流程圖(11)函數(shù)名稱：ListDelete(L,i,e)；初始條件：線性表L已存在且非空，1≤i≤ListLength(L)；操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，用e返回其值；設(shè)計思想：先遍歷順序表，如果線性表L已存在且非空，并且輸入的i值不合法，則返回ERROR。若滿足線性表L已存在且L非空，并且i的值合法，則刪除線性表的第i個位置的數(shù)據(jù)元素，并用e返回其值，返回OK。圖1-11為ListDelete(L,i,e)的流程圖。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第15頁。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第15頁。圖1-11ListDelete(L,i,e)流程圖(12)函數(shù)名稱：ListTrabverse(L)；初始條件：線性表L已存在；操作結(jié)果：依次遍歷L的每個數(shù)據(jù)元素；設(shè)計思想：若線性表L存在，則遍歷元素；否則返回ERROR。圖1-12為ListTrabverse(L)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第16頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第16頁。圖1-12ListTrabverse(L)流程圖(13)函數(shù)名稱：SaveList(L,filename)；初始條件：線性表L已存在；操作結(jié)果：將線性表L保存為文件形式；算法思路：用fwrite保存為文件，圖1-13為SaveList(L,filename)的流程圖?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第17頁。基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第17頁。圖1-13SaveList(L,filename)流程圖(14)函數(shù)名稱：LoadList(L);初始條件：文件filename已存在；操作結(jié)果：將線性表L以文件形式加載讀取;算法思路：用fread將文件讀取順序表，圖1-14為LoadList(L)的流程圖。圖1-14LoadList(L)流程圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第18頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第18頁。1.3系統(tǒng)實現(xiàn)1.3.1程序源代碼見《附錄A基于順序存儲結(jié)構(gòu)線性表實現(xiàn)的源程序》。1.3.2系統(tǒng)測試程序采用簡易界面，如圖1-15所示，挑選ListEmpty,ListLength,GetElem,LocateElem,PriorElem,NextElem,ListInsert,ListDelete,ListTrabverse這些重要功能進行測試。圖1-15程序簡易界面截圖測試用例為：sss{1,2,3,4,5,6,7,8,9},null(空表)以及順序表不存在。(1)ListEmpty測試表1-1ListEmpty測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss界面選4線性表不是空表！線性表不是空表！null界面選4文件為空！文件為空！若表不存在界面選4線性表不存在！線性表不存在！基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第19頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第19頁。圖1-16ListEmpty測試截圖(2)ListLength測試表1-2ListLength測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss界面選5線性表表長為9線性表表長為9null界面選5線性表表長為0線性表表長為0若表不存在界面選5線性表不存在！線性表不存在！圖1-17ListLength測試截圖(3)GetElem測試基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第20頁。表1-3GetElem測試用例表基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第20頁。測試用例輸入理論結(jié)果測試結(jié)果sss界面選6輸入位置3第3個節(jié)點的元素是：3第3個節(jié)點的元素是：3sss界面選6輸入位置12輸入位置錯誤！輸入位置錯誤！若表不存在界面選6線性表不存在！線性表不存在！圖1-18(a)GetElem測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第21頁。圖1-18(b)GetElem測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第21頁。(4)LocateElem測試表1-4LocateElem測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss界面選7輸入元素44元素位于第4個位置4元素位于第4個位置sss界面選7輸入元素20該元素不存在！該元素不存在！若表不存在界面選7線性表不存在！線性表不存在！圖1-19(a)LocateElem測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第22頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第22頁。圖1-19(b)LocateElem測試截圖(5)PriorElem測試表1-5PriorElem測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss界面選8輸入元素2其前驅(qū)元素為：1其前驅(qū)元素為：1sss界面選8輸入元素1其不存在前驅(qū)元素！其不存在前驅(qū)元素！sss界面選8輸入元素13順序表中沒有該元素！順序表中沒有該元素！若表不存在界面選8線性表不存在！線性表不存在！基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第23頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第23頁。圖1-20(a)LocateElem測試截圖圖1-20(b)LocateElem測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第24頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第24頁。圖1-20(c)LocateElem測試截圖(6)NextElem測試表1-6NextElem測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss界面選9輸入元素4其后繼元素為：5其后繼元素為：5sss界面選9輸入元素9其不存在后繼元素其不存在后繼元素sss界面選19輸入元素選14順序表中沒有該元素！順序表中沒有該元素！若表不存在界面選9線性表不存在！線性表不存在！基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第25頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第25頁。圖1-21(a)NextElem測試截圖圖1-21(b)NextElem測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第26頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第26頁。圖1-21(c)NextElem測試截圖(7)ListInsert測試表1-7ListInsert測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss界面選10輸入元素10輸入位置10插入數(shù)據(jù)元素成功！插入數(shù)據(jù)元素成功！sss界面選10輸入元素2插入位置20插入位置不正確！插入數(shù)據(jù)元素失??！插入位置不正確！插入數(shù)據(jù)元素失??！若表不存在界面選10線性表不存在！線性表不存在！基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第27頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第27頁。圖1-22(a)ListInsert測試截圖圖1-22(b)ListInsert測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第28頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第28頁。圖1-22(c)ListInsert測試截圖(8)ListDelete測試表1-8ListDelete測試用例表測試用例輸入理論結(jié)果測試結(jié)果sss選11、輸入1刪除元素成功！刪除元素成功！sss選11、輸入12刪除元素失?。h除元素失??！若表不存在選11線性表不存在！線性表不存在！圖1-23(a)ListDelete測試截圖基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第29頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第29頁。圖1-23(b)ListDelete測試截圖圖1-23(c)ListDelete測試截圖(9)ListTrabverse測試表1-9ListTrabverse測試用例表測試用例程序輸入理論結(jié)果測試結(jié)果sss主界面選12123456789123456789不存在的表主界面選12線性表不存在線性表不存在基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第30頁?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第30頁。圖1-24(a)ListTrabverse測試截圖圖1-24(b)ListTrabverse測試截圖1.4實驗小結(jié)本次實驗主要內(nèi)容是關(guān)于線性表的練習(xí)，由于實驗之前老師已給出基礎(chǔ)框架，只需對實驗中要求的函數(shù)進行補充，這減小了我們的學(xué)習(xí)壓力，更能突出對課程內(nèi)容的考查與訓(xùn)練。本次實驗使我獲益匪淺，加深了我對線性表的理解，也使我發(fā)現(xiàn)了自身很多的不足之處。首先，對C語言這一基本工具掌握不足，不能夠熟練地使用這一語言，從而也導(dǎo)致了實驗內(nèi)容出現(xiàn)bug時無從下手。其次，做實驗之前應(yīng)該好好看書，書上有著插入，刪除等函數(shù)的算法，而自己卻沒看，導(dǎo)致在第一次交予助教基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第31頁。檢查時便出了錯。關(guān)于文件的保存和加載函數(shù)，自己掌握不夠清楚，還要再看看C語言中的第十章文件?；陧樞虼鎯Y(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第31頁。本次實驗鍛煉了我們理論與實踐結(jié)合的能力，更加深了我們對于數(shù)據(jù)結(jié)構(gòu)這門課程的學(xué)習(xí)，從這次實驗中，我學(xué)到了很多。最后，我由衷地感謝老師、助教和同學(xué)在本次實驗中對我的幫助，幫助我解決實驗中遇到的難題，謝謝！

基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第32頁。附錄A基于順序存儲結(jié)構(gòu)線性表實現(xiàn)的源程序基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第32頁。/*LinearTableOnSequenceStructure*/#include<stdio.h>#include<malloc.h>#include<stdlib.h>/*ontextbook*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2#defineMAX_NUM10typedefintstatus;typedefintElemType;//數(shù)據(jù)元素類型定義/*ontextbook*/#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{//順序表（順序結(jié)構(gòu)）的定義 ElemType*elem; intlength; intlistsize;}SqList;FILE*fp;/*ontextbook*/statusIntiaList(SqList&L);statusDestroyList(SqList&L);statusClearList(SqList&L);statusListEmpty(SqListL);intListLength(SqListL);statusGetElem(SqListL,inti,ElemType*e);statusLocateElem(SqListL,ElemTypee,status(*compare)(ElemType,ElemType));statuscompare(ElemTypea,ElemTypeb);statusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e);statusNextElem(SqListL,ElemTypecur_e,ElemType*next_e);statusListInsert(SqList&L,inti,ElemTypee);statusListDelete(SqList*L,inti,ElemType*e);基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第33頁。statusListTrabverse(SqListL);基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第33頁。statusSaveList(SqListL,char*filename);statusLoadList(SqList*L,char*filename);/**/intmain(void){charfilename[40];intop=1;inti;inti_num=1;SqListL[MAX_NUM];for(i=0;i<MAX_NUM;i++){L[i].elem=NULL;L[i].listsize=0;L[i].length=0;}//上面的for循環(huán)是用來生成存儲空間為空的線性表ElemTypee,cur_e,pre_e,next_e;while(op){/***利用最簡單的printf來制作簡易的菜單，可供選擇；*簡潔美觀的菜單有助于平復(fù)測試時的心情!!!*/ system("cls"); //用于清屏printf("\n\n"); printf("\t\t\tMenuforLinearTableOnSequenceStructure\n"); printf("可在%d個順序表進行多表操作，初始化請先操作功能15,默認在第一個表上操作\n",MAX_NUM); printf("\n"); printf("**\t\t\t1.IntiaList7.LocateElem\t\t\t**\n"); printf("**\t\t\t2.DestroyList8.PriorElem\t\t\t**\n"); printf("**\t\t\t3.ClearList9.NextElem\t\t\t**\n"); printf("**\t\t\t4.ListEmpty10.ListInsert\t\t\t**\n"); printf("**\t\t\t5.ListLength11.ListDelete\t\t\t**\n"); printf("**\t\t\t6.GetElem12.ListTrabverse\t\t\t**\n"); printf("**\t\t\t13.SaveList 14.LoadList\t\t\t**\n"); printf("**\t\t\t0.Exit制作時間：2018.11.13\t\t\t**\n"); printf("**\t\t\t15.ChooseList(請先進行此選項以選擇在哪個表上進行操作)\n"); printf("**\t\t\t本實驗已有文件sss，可通過函數(shù)14進行加載\n"); printf("王明明\n");基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第34頁。 printf("請選擇你的操作[0--15]:\n");基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第34頁。 scanf("%d",&op);//選擇op的值,用于switchswitch(op){ case1://第一種情況是初始化線性表 if(IntiaList(L[i_num])==OK){printf("請輸入要保存的線性表名稱\n");scanf("%s",filename);printf("線性表創(chuàng)建成功\n");} elseprintf("線性表創(chuàng)建失??！\n"); getchar();getchar(); break; case2: //第二種情況是用來銷毀線性表 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;} if(DestroyList(L[i_num])==OK){printf("銷毀線性表成功!\n");}elseprintf("銷毀線性表失敗！\n"); getchar();getchar(); break; case3: //用于重置線性表 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}if(ClearList(L[i_num])==OK){printf("線性表重置成功！\n");}基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第35頁。elseprintf("線性表重置失??！\n");基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第35頁。 getchar();getchar(); break; case4: //判斷是否為空 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}if(ListEmpty(L[i_num])==TRUE){printf("文件為空！\n");}elseprintf("線性表不是空表！\n"); getchar();getchar(); break; case5: //得到線性表長度 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}printf("線性表表長為%d\n",ListLength(L[i_num])); getchar();getchar(); break; case6: //得到某個元素 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}printf("請輸入要取結(jié)點的位置：\n"); scanf("%d",&i); if(GetElem(L[i_num],i,&e)==OK) printf("第%d個結(jié)點的元素是：%d\n",i,e);基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第36頁。 elseprintf("輸入位置錯誤！\n");基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第36頁。 getchar();getchar(); break; case7: //確定元素位置，容易出錯 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}printf("請輸入數(shù)據(jù)元素值：\n"); scanf("%d",&e); if(i=LocateElem(L[i_num],e,compare)) printf("%d元素位于第%d個位置！\n",e,i); elseprintf("該元素不存在!\n"); getchar();getchar(); break; case8: //求出前驅(qū)結(jié)點 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;} printf("請輸入數(shù)據(jù)元素：\n"); scanf("%d",&cur_e); PriorElem(L[i_num],cur_e,&pre_e); if(PriorElem(L[i_num],cur_e,&pre_e)==OK) printf("其前驅(qū)元素為：%d\n",pre_e); elseif(PriorElem(L[i_num],cur_e,&pre_e)==OVERFLOW) printf("順序表中沒有該元素！\n"); elseprintf("其不存在前驅(qū)元素！\n"); getchar();getchar(); break; case9: //求出后置節(jié)點 if(L[i_num].elem==NULL){printf("線性表不存在!\n");基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第37頁。getchar();getchar();基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第37頁。break;}printf("請輸入數(shù)據(jù)元素：\n"); scanf("%d",&cur_e); if(NextElem(L[i_num],cur_e,&next_e)==OK) printf("其后繼元素為：%d\n",next_e); elseif(NextElem(L[i_num],cur_e,&pre_e)==FALSE) printf("其不存在后繼元素！\n"); else{printf("順序表中沒有該元素！\n");} getchar();getchar(); break; case10: //插入元素 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;} printf("請輸入您要插入的數(shù)據(jù)元素：\n"); scanf("%d",&e); printf("請輸入您要插入的數(shù)據(jù)元素的位置：\n"); scanf("%d",&i); if(ListInsert(L[i_num],i,e)==OK) printf("插入數(shù)據(jù)元素成功！\n"); else printf("插入數(shù)據(jù)元素失敗！\n"); getchar();getchar(); break; case11: //刪除元素 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;} printf("請輸入您要刪除的數(shù)據(jù)元素的位置：\n"); scanf("%d",&i); if(ListDelete(&L[i_num],i,&e)==OK)基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第38頁。 printf("刪除數(shù)據(jù)元素成功！\n");基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第38頁。 else printf("刪除數(shù)據(jù)元素失??！\n"); getchar();getchar(); break; case12: //遍歷線性表中的元素 if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}if(!ListTrabverse(L[i_num]))printf("線性表是空表！\n"); getchar();getchar(); break;case13://保存文件if(L[i_num].elem==NULL){printf("線性表不存在!\n");getchar();getchar();break;}if(SaveList(L[i_num],filename)==OK) printf("文件保存成功\n文件名為%s\n",filename);break;case14://加載文件，需要輸入需要加載的名稱printf("請輸入要加載的文件名:\n"); scanf("%s",filename); if(LoadList(&L[i_num],filename)==OK){printf("文件加載成功\n"); }break;case15://選擇在哪個表進行操作printf("請輸入要在第幾個表操作:\n");printf("*只支持在%d個順序表上操作*\n",MAX_NUM);基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第39頁。 scanf("%d",&i_num);基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第39頁。 printf("正在對第%d個表進行操作\n",i_num); if((i_num<1)||(i_num>10)) { printf("請選擇正確范圍！\n"); i_num=1; } getchar();getchar(); break;break; case0://退出菜單，退出整個程序break; }//endofswitch}//endofwhileprintf("歡迎下次再使用本辣雞系統(tǒng)!\n");}//endofmain()/*ontextbook*//****************************************************************函數(shù)名稱：IntiaList*函數(shù)功能：構(gòu)造一個空的線性表*注釋：初始條件是線性表L不存在已存在；操作結(jié)果是構(gòu)造一個空的線性表。*返回值類型：status類型****************************************************************/statusIntiaList(SqList&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//如果空間不足，創(chuàng)建失敗 L.length=0;L.listsize=LIST_INIT_SIZE; returnOK;}/****************************************************************函數(shù)名稱：DestoryList*函數(shù)功能：銷毀線性表*注釋：初始條件是線性表L已存在；操作結(jié)果是銷毀線性表L*返回值類型：status類型****************************************************************/statusDestroyList(SqList&L){ if(L.elem) free(L.elem); L.elem=NULL;基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第40頁。 L.length=0;基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第40頁。 L.listsize=0; returnOK;}/****************************************************************函數(shù)名稱：ClearList*函數(shù)功能：重置順序表*注釋：初始條件是線性表L已存在；操作結(jié)果是將L重置為空表。*返回值類型：status類型****************************************************************/statusClearList(SqList&L){L.length=0;returnOK;}/****************************************************************函數(shù)名稱：ListEmpty*函數(shù)功能：判斷線性表是否為空*注釋：初始條件是線性表L已存在；操作結(jié)果是若L為空表則返回TRUE,否則返回FALSE。*返回值類型：status類型****************************************************************/statusListEmpty(SqListL){if(L.length==0){returnTRUE;}returnFALSE;}/****************************************************************函數(shù)名稱：ListLength*函數(shù)功能：求線性表的表長*注釋：初始條件是線性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個數(shù)。*返回值類型：int類型****************************************************************/intListLength(SqListL)基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第41頁。{基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第41頁。returnL.length;}/****************************************************************函數(shù)名稱：GetElem*函數(shù)功能：得到某一個元素的值*注釋：初始條件是線性表已存在，1≤i≤ListLength(L)；操作結(jié)果是用e返回L中第i個數(shù)據(jù)元素的值*返回值類型：status類型****************************************************************/statusGetElem(SqListL,inti,ElemType*e){if(i<1||i>L.length){returnERROR;}*e=L.elem[i-1];//將得到的元素賦值給ereturnOK;}/****************************************************************函數(shù)名稱：LocateElem*函數(shù)功能：查找元素*注釋：初始條件是線性表已存在；操作結(jié)果是返回L中第1個與e滿足關(guān)系compare（）關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。*返回值類型：status類型****************************************************************/statusLocateElem(SqListL,ElemTypee,status(*compare)(ElemType,ElemType)){inti;for(i=0;i<L.length;i++){if(compare(L.elem[i],e))return++i;}return0;}基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第42頁。/***************************************************************基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第42頁。*函數(shù)名稱：compare*函數(shù)功能：比較大小，服務(wù)于LocateList函數(shù)*注釋：輸入兩個ElemType類型的值*返回值類型：status類型****************************************************************/statuscompare(ElemTypea,ElemTypeb){ if(a==b) returnTRUE; elsereturnFALSE;}/****************************************************************函數(shù)名稱：PriorElem*函數(shù)功能：求元素的前驅(qū)*注釋：初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。*返回值類型：status類型****************************************************************/statusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e){inti;for(i=0;i<L.length;i++){if(L.elem[i]==cur_e&&i==0){returnERROR;}elseif(L.elem[i]==cur_e){*pre_e=L.elem[i-1];returnOK;}}returnOVERFLOW;}/****************************************************************函數(shù)名稱：NextElem*函數(shù)功能：求后繼節(jié)點基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第43頁。*輸入輸出：初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個，基于順序存儲結(jié)構(gòu)的線性表實現(xiàn)【數(shù)據(jù)結(jié)構(gòu)實驗】全文共46頁，當(dāng)前為第43頁。則用next_e返回它的后繼，否則操作失敗，next_e無定義。*返回值類型：status類型****************************************************************/statusNextElem(SqListL,ElemTypecur_e,ElemType*next_e){inti;for(i=0;i<(L.length-1);i++){if(L.elem[i]==cur_e){*next_e=L.elem[i+1];returnOK;}}if(i==L.length-1&&(L.elem[i]!=cur_e))returnOVERFLOW;elsereturnFALSE;}/****************************************************************函數(shù)名稱：ListInsert*函數(shù)功能：插入元素*注釋：初始條件是線性表L已存在且非空，1≤i≤ListLength(L)+1；*操作結(jié)果是在L的第i個位置之前插入新的數(shù)據(jù)元素e*返回值類型：status類型****************************************************************/statusListInsert(SqList&L,inti,ElemTypee){int*p,*q,*newbase;if(i<1||i>L.length+1){printf("插入位置不正確!\n");returnERROR;}if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(