華中科技大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

律中科於夫掌課程實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)專業(yè)班級(jí)：學(xué)號(hào)：姓名：指導(dǎo)教師：報(bào)告日期：2015年11月20日計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院目錄TOC\o"1-5"\h\z\o"CurrentDocument"1基于順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本運(yùn)算 1\o"CurrentDocument"問(wèn)題描述 1\o"CurrentDocument"順序表演示系統(tǒng)設(shè)計(jì) 3\o"CurrentDocument"系統(tǒng)總體設(shè)計(jì) 3\o"CurrentDocument"有關(guān)常量和類型定義 3\o"CurrentDocument"算法設(shè)計(jì) 3\o"CurrentDocument"順序表演示系統(tǒng)實(shí)現(xiàn)與測(cè)試 8\o"CurrentDocument"系統(tǒng)實(shí)現(xiàn) 8\o"CurrentDocument"系統(tǒng)測(cè)試 18\o"CurrentDocument"實(shí)驗(yàn)小結(jié) 20\o"CurrentDocument"2基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本運(yùn)算 20\o"CurrentDocument"問(wèn)題描述 20\o"CurrentDocument"單鏈表演示系統(tǒng)設(shè)計(jì) 21系統(tǒng)總體設(shè)計(jì) 21\o"CurrentDocument"算法設(shè)計(jì) 22\o"CurrentDocument"單鏈表演示系統(tǒng)實(shí)現(xiàn)與測(cè)試 24\o"CurrentDocument"系統(tǒng)實(shí)現(xiàn) 24\o"CurrentDocument"系統(tǒng)測(cè)試 36\o"CurrentDocument"實(shí)驗(yàn)小結(jié) 37\o"CurrentDocument"3基于順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧的基本運(yùn)算 38\o"CurrentDocument"1順序棧實(shí)驗(yàn) 38\o"CurrentDocument"問(wèn)題描述 38\o"CurrentDocument"順序棧設(shè)計(jì) 38順序棧實(shí)現(xiàn)與測(cè)試 44\o"CurrentDocument"3.2表達(dá)式求值實(shí)驗(yàn) 55\o"CurrentDocument"問(wèn)題描述 55\o"CurrentDocument"算法設(shè)計(jì)部分 55實(shí)現(xiàn)與測(cè)試部分 56\o"CurrentDocument"3實(shí)驗(yàn)小結(jié) 57\o"CurrentDocument"4基于循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列的基本運(yùn)算 58\o"CurrentDocument"1問(wèn)題描述 58\o"CurrentDocument"2隊(duì)列基本操作算法設(shè)計(jì)： 58\o"CurrentDocument"3實(shí)驗(yàn)小結(jié) 66\o"CurrentDocument"5基于二叉鏈表實(shí)現(xiàn)二叉樹的基本運(yùn)算 67\o"CurrentDocument"1實(shí)驗(yàn)內(nèi)容與要求 67\o"CurrentDocument"5.2程序概要設(shè)計(jì) 67\o"CurrentDocument"5.3數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) 68\o"CurrentDocument"5.4程序清單與測(cè)試 70\o"CurrentDocument"5.5實(shí)驗(yàn)總結(jié)與評(píng)價(jià) 83\o"CurrentDocument"6基于鄰接表實(shí)現(xiàn)圖的基本運(yùn)算 84\o"CurrentDocument"6.1實(shí)驗(yàn)內(nèi)容與要求 84\o"CurrentDocument"6.2程序概要設(shè)計(jì) 84\o"CurrentDocument"6.3數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) 85\o"CurrentDocument"6.4程序清單與測(cè)試 87\o"CurrentDocument"6.5實(shí)驗(yàn)總結(jié)與評(píng)價(jià) 109\o"CurrentDocument"參考文獻(xiàn) 1091基于順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本運(yùn)算1.1問(wèn)題描述敘述實(shí)驗(yàn)中線性表的物理結(jié)構(gòu)形式，如何用物理結(jié)構(gòu)表示數(shù)據(jù)元素間的邏輯關(guān)系，可用圖的方式直觀表示物理結(jié)構(gòu)，如圖1-1所示。圖1-1順序表物理結(jié)構(gòu)示意圖實(shí)驗(yàn)耍完成的順序表算法：InitaList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表。DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。ClearList(&L)初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，貝IJ返回TRUE,否則返回FALSE。ListLength(L)初始條件：線性表已存在。操作結(jié)果：返回L中數(shù)據(jù)元素的個(gè)數(shù)。GetElem(L,i,&e)初始條件：線性表已存在，IWiWListLength(L)。操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值。LocateElem(L,e,compare())初始條件：線性表已存在。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。PriorElem(L,cur_e,&pre_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。NextElem(L,cur_e,&next_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。ListInsert(&L,i,e)初始條件：線性表L已存在且非空，l〈i《ListLength(L)+l。操作結(jié)果：在L的第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L的長(zhǎng)度加1ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，IWiWListLength(L)。操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，用e返回其值，L的長(zhǎng)度減1.ListTraverse(L,visit())初始條件：線性表L已存在。操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。。一旦調(diào)用失敗，則操作失敗。ReadList(&L)操作結(jié)果：讀取線性表SaveList(L)操作結(jié)果：保存線性表實(shí)驗(yàn)?zāi)繕?biāo)：構(gòu)造成具有功能菜單的系統(tǒng)完成線性表基本操作。通過(guò)實(shí)驗(yàn)達(dá)到：(1)加深對(duì)線性表的概念、基本運(yùn)算的理解：(2)熟練掌握線性表的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系；(3)物理結(jié)構(gòu)采用順序表，熟練掌握線性表的基本運(yùn)算的實(shí)現(xiàn)。順序表演示系統(tǒng)設(shè)計(jì)系統(tǒng)總體設(shè)計(jì)系統(tǒng)的總體架構(gòu)：界面上采用簡(jiǎn)易菜單，通過(guò)switch函數(shù)進(jìn)行功能的選擇，進(jìn)入相關(guān)功能函數(shù)執(zhí)行相關(guān)操作。有關(guān)常量和類型定義typedefintElemType;//數(shù)據(jù)元素類型定義#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{〃順序表(順序結(jié)構(gòu))的定義ElemType*elem;intlength;intlistsize;}SqList;算法設(shè)計(jì)InitaList(&L)設(shè)計(jì)：分配存儲(chǔ)空間，并將length值設(shè)為0,listsize值設(shè)為預(yù)定義的初始存儲(chǔ)容量。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)DestroyList(&L)設(shè)計(jì)：釋放內(nèi)存，并讓ele指向NULL,表長(zhǎng)及存儲(chǔ)容量置為0。復(fù)雜度：時(shí)間復(fù)雜度T(n)=0(1)空間復(fù)雜度S(n)=0(1)ClearList(&L)設(shè)計(jì)：將表長(zhǎng)設(shè)為0。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=0(1)ListEmpty(L)設(shè)計(jì)：讀取表長(zhǎng)length的值，為0則返回TRUE,否則FALSE。復(fù)雜度：時(shí)間復(fù)雜度T(n)=0(1)空間復(fù)雜度S(n)=O(l)ListLength(L)設(shè)計(jì)：返回L.length的值。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)GetElem(L,i,&e)設(shè)計(jì)：將L.elem[i-1]的值賦給e,并返回OK復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)LocateElem(L,e,compare())設(shè)計(jì)：遍歷順序表，將與給定元素e滿足關(guān)系compare的元素的位序返回。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)PriorElem(L,cur_e,&pre_e)設(shè)計(jì)：從頭遍歷，若當(dāng)前節(jié)點(diǎn)后繼值為cur_e,則將當(dāng)前結(jié)點(diǎn)的元素賦給pre_e,returnOK。若未找至則返回FALSE。流程圖如下所示：復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l) 4 NextElem(L,cur_e,&next_e)設(shè)計(jì)：從頭遍歷，若當(dāng)前節(jié)點(diǎn)值為cur_e且非表尾，則將后繼結(jié)點(diǎn)的元素賦給pre_e,returnOK,若未找到，則返回FALSE。流程圖如下：復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)

(10)ListInsert(&L,i,e)設(shè)計(jì)：先判斷i值是否符合要求，不符返回ERROR。i值合法，則檢查空間大小，若空間不夠，增加存儲(chǔ)容量。然后將插入位置及之后的元素右移，最后插入e,表長(zhǎng)加".流程圖如下所示：復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)(1l)ListDelete(&L,i,&e)設(shè)計(jì)：先判斷i值是否符合要求，不符返回ERROR。i值合法，則將被刪除元素的值賦給e,然后將被刪除元素之后的元素左移，最后表長(zhǎng)減流程圖如下所示：Y+找到刪除位置&(L-Xlem[i-1D；將被刪除元素的值賦給e用循環(huán)將刪除位置之后的元素前移復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)(12)ListTraverse(L,visit())設(shè)計(jì)：遍歷順序表，對(duì)每個(gè)元素調(diào)用函數(shù)指針visit所指向的函數(shù)，若調(diào)用失敗則提示操作失敗。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)(13)ReadList(&L)設(shè)計(jì)：若原L已存在，銷毀，新建，再要求用戶輸入讀取文件名，然后使用fread函數(shù)進(jìn)行文件的讀取。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)(14)SaveList(L)設(shè)計(jì)：讓用戶輸入所要保存到的文件名，然后使用fwrite函數(shù)將順序表保存入文件中。復(fù)雜度：時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)順序表演示系統(tǒng)實(shí)現(xiàn)與測(cè)試1-3.1系統(tǒng)實(shí)現(xiàn)編程環(huán)境：WIN10下使用Dev—C++進(jìn)行編譯調(diào)試，語(yǔ)言選擇C語(yǔ)言。各函數(shù)間調(diào)用關(guān)系：主函數(shù)通過(guò)switch調(diào)用各功能函數(shù)，各函數(shù)間除ReadList調(diào)用DestroyList和InitList外，各自相互獨(dú)立。程序源代碼：#include<stdio.h>#include<stdlib.h>〃函數(shù)結(jié)果狀態(tài)代碼defineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASTABLE-1defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;//數(shù)據(jù)元素類型定義typedefintElemType;defineLISTJNIT_SIZE100defineLISTINCREMENT10typedefstruct{〃順序表(順序結(jié)構(gòu))的定義ElemType*elem;intlength;intlistsize;JSqList;StatusInitList(SqList*L);StatusDestroyList(SqList*L);StatusClearList(SqList*L);StatusListEmpty(SqListL);intListLength(SqListL);StatusGetElem(SqListL,inti,ElemType*e);intLocateElem(SqListL,ElemTypee,Status(*compare)(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);StatusListTraverse(SqListL,Status(*visit)(ElemTypea));StatusReadList(SqList*L);StatusSaveList(SqListL);StatusCompare(ElemTypea,ElemTypeb);StatusVisit(ElemTypea);/*函數(shù)名稱：IntiaList輸入?yún)?shù)：線性表L地址返回值：Status函數(shù)功能：構(gòu)造一個(gè)空的線性表。/StatusInitList(SqList*L){L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem)(exit(OVERFLOW);)L->length=O;L->listsize=LISTJN1T_SIZE;returnOK;函數(shù)名稱：DestroyList輸入?yún)?shù)：線性表L地址返回值：Status函數(shù)功能：構(gòu)造一個(gè)空的線性表。/StatusDestroyList(SqList函數(shù)名稱：ListEmpty*輸入?yún)?shù)：線性表L函數(shù)名稱：ListEmpty*輸入?yún)?shù)：線性表L*返回值：Status*函數(shù)功能：若L為空表，則返回TRUE,否則返回FALSE。*/free(L->elem);L->elem=NULL;L->length=0;L->listsize=O;returnOK;函數(shù)名稱：ClearList輸入?yún)?shù)：線性表L地址返回值：Status函數(shù)功能：將L重置為空表。刊StatusClearList(SqList*L)(L->length=0;returnOK;StatusListEmpty(SqListL)(if(L.length==0)(returnTRUE;)else(returnFALSE;函數(shù)名稱：ListLength輸入?yún)?shù)：線性表L返回值：Status函數(shù)功能：返回L中數(shù)據(jù)元素的個(gè)數(shù)。刊intListLength(SqListL)(returnL.length;*e=L.elem[i-1];returnOK;函數(shù)名稱：LocateElem輸入?yún)?shù)：線性表L,用于比較的元素e,指向用于比較的函數(shù)的函數(shù)指針compare返回值：ini函數(shù)功能：返回L中第1個(gè)與e滿足關(guān)系compare()關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。為intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))(inti;for(i=1;i<=L.length;i++)(if((*compare)(L.elem[i-l],e)){return(i);})return0;函數(shù)名稱：PriorEIem輸入?yún)?shù)：線性表L,我的元素cur_e,用于返回其前驅(qū)的元素pre_e的地址返回值：Status函數(shù)功能：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。刊StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e)inti;for(i=0;i<(L.length-1);i++)if(L.elem[i+l]==cur_e)(*pre_e=L.elem[i];returnOK;))returnERROR;函數(shù)名稱：NextElem輸入?yún)?shù)：線性表L,查找的元素cur_e,用于返回其后繼的元素nexl_e的地址*返回值：Status函數(shù)功能：若cuje是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。*/StatusNextElem(SqListL,ElemTypecur_e,ElemType函數(shù)名稱:Listinsert*輸入?yún)?shù)：線性表函數(shù)名稱:Listinsert*輸入?yún)?shù)：線性表L地址，插入位置i,插入元素e*返回值：Status*函數(shù)功能：在L的第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L的長(zhǎng)度加1inti;for(i=O;i<(L.length-l);i++)(if(L.elem[i]==cur_e){*next_e=L.elem[i+1];returnOK;})returnERROR;}

*/StatusListInsert(SqList函數(shù)名稱：ListDelete*輸入?yún)?shù)：線性表L函數(shù)名稱：ListDelete*輸入?yún)?shù)：線性表L地址，刪除位置i,用于返回其值的元素e的地址*返回值:Statusif(i<1||i>L->length+l)//i值不合法(returnERROR;)if(L->length>=L->listsize)〃當(dāng)前存儲(chǔ)空間已滿，增加分配((L->listsize+ElemType*(L->listsize+newbase=(ElemType*)realloc(L->elem,LISTINCREMENT)*sizeof(ElemType));if(!newbase)(exit(OVERFLOW);〃存儲(chǔ)分配失敗)L->elem=newbase; //新基址L->listsize+=LISTINCREMENT;〃增力□存儲(chǔ)容量)ElemType*p,*q;q=&(L->elem[i-l]);//q為插入位置for(p=&(L->elem[L->length-1]);p>=q;—p)(*(p+l)=*p; 〃插入位置及之后的元素右移)*q=e; 〃插入e++L->length; 〃表長(zhǎng)增加1returnOK;*函數(shù)功能：刪除L的第i個(gè)數(shù)據(jù)元素，用e返回其值，L的長(zhǎng)度減1.*/StatusListDelete(SqList*L,inti,ElemType*e)(ElemType*p,*q;if(i<1||i>L->length)//i值不合法(returnERROR;)p=&(L->elem[i-l])://p為被刪元素位置*e=*p; 〃被刪除元素的值賦給eq=L->elem+L->length-1;//表尾元素的位置for(++p;p<=q;++p) 〃被刪除元素之后的元素左移(*(p-l)=*p;)--L->length;〃表長(zhǎng)減1returnOK;函數(shù)名稱：ListTraverse輸入?yún)?shù)：線性表L,指向調(diào)用函數(shù)的函數(shù)指針visit返回值：Status函數(shù)功能：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。。!StatusListTraverse(SqListL,Status(*visit)(ElemTypea))(inti;printf("\n allelements \nn);for(i=0;i<L.length;i++)(if(!(*visit)(L.elem[i]))printf("操作失??！)))printf("\n end \nn);returnL.length;函數(shù)名稱：ReadList輸入?yún)?shù)：線性表L返回值：Status*函數(shù)功能：讀取線性表。*/StatusReadList(SqList*L)(if((*L).elem!=NULL)(DestroyList(L);)InitList(L);FILE*fp;charfilename[30];printf(”請(qǐng)輸入讀取文件名：H);scanf(H%sn,&filename);if((fp=fopen(filename,nrH))==NULL)(printfC文件打開失敗!\n*');returnERROR;)while(fread(&(L->elem[L->length]),sizeof(ElemType),1,fp))L->length++;fclose(fp);returnOK;函數(shù)名稱：SaveList輸入?yún)?shù)：線性表L返回值：Status函數(shù)功能：保存線性表。刊StatusSaveList(SqListL)(FILE*fp;charfilename[30];printf(”請(qǐng)輸入保存文件名：”)；scanf(,'%s',,&filename);〃寫文件的方法if((fp=fopen(filename,"w"))==NULL)(printf("文件打開失敗\n”)；returnERROR;)fwrite(L.elem,sizeof(ElemType),L.length,fp);fclose(fp);returnOK;函數(shù)名稱：Compare輸入?yún)?shù)：ElemTypea,ElemTypeb返回值：Status函數(shù)功能：判斷a,b是否滿足關(guān)系列StatusCompare(ElemTypea,ElemTypeb)(if(a==b)returnTRUE;)else(returnFALSE;函數(shù)名稱：Visit輸入?yún)?shù)：ElemTypea返回值：Status函數(shù)功能：輸出a/StatusVisit(ElemTypea)(printf(M%d”,a);returnOK;)1.3.2系統(tǒng)測(cè)試使用預(yù)先保存的測(cè)試用例挑選LocateElem,NextElem,Listinsert,ListDelete>ListTraverse進(jìn)行測(cè)試。使用的測(cè)試用例：Testi(表含5,12,0,44,94),Test2(空表)。(1)LocateElem測(cè)試：表1.3.2-1LocateElem算法測(cè)試用例表測(cè)試用例程序輸入理論結(jié)果運(yùn)行結(jié)果Testi.主界面選擇7進(jìn)入函數(shù).按提示輸入所要比較的函數(shù)（本程序比較函數(shù)設(shè)為兩數(shù)相等返回TRUE,故提示語(yǔ)為輸入要搜尋的函數(shù)），輸入12輸出“第二個(gè)元素符合條件”.輸出“第二個(gè)元素符合條件”，符合預(yù)期。.主界面選擇7進(jìn)入函數(shù).輸入100提示“未找到符合條件的元素”輸出“未找到符合條件的元素”，符合預(yù)期。Test2.主界面選擇7進(jìn)入函數(shù).輸入100提示“未找到符合條件的元素”輸出“未找到符合條件的元素”，符合預(yù)期。無(wú)1.主界面選擇7進(jìn)入函數(shù)提示“線性表不存輸出“線性表不存在！

在！請(qǐng)先創(chuàng)建！”請(qǐng)先創(chuàng)建！”，符合。(2)NextElem測(cè)試:表1.3.2-2NextElem算法測(cè)試用例表測(cè)試用例程序輸入理論結(jié)果運(yùn)行結(jié)果Testi.主界面選擇9進(jìn)入函數(shù).輸入12輸出“該元素后繼為0”。輸出“該元素后繼為0”，符合預(yù)期。1.主界面選擇9進(jìn)入函數(shù)2輸入100提示“未找到”輸出“未找到”，符合預(yù)期。.主界面選擇9進(jìn)入函數(shù).輸入94提示“未找到”輸出“未找到”，符合預(yù)期。Test21.主界面選擇9進(jìn)入函數(shù)2輸入12提示“未找到”輸出“未找到”，符合預(yù)期。無(wú)1.主界面選擇9進(jìn)入函數(shù)提示“線性表不存在！請(qǐng)先創(chuàng)建！”輸出“線性表不存在！請(qǐng)先創(chuàng)建！”，符合。(3)Lisllnsert測(cè)試:表1.3.2-3Listinsert算法測(cè)試用例表測(cè)試用例程序輸入理論結(jié)果運(yùn)行結(jié)果Testi.主界面選擇10進(jìn)入函數(shù).根據(jù)提示輸入位置，輸入1.根據(jù)提示輸入新元素，輸入10提示插入成功使用Traverse函數(shù),得 到 友10,5,12,0,44,94輸出“插入成功！”使用Traverse函數(shù)，輸出“1051204494”，符合預(yù)期。1.主界面選擇10進(jìn)入函數(shù)2輸入63.輸入10提示插入成功使用Traverse函數(shù),得 到 表5,12,0,44,94,10輸出''插入成功！”使用Traverse函數(shù)，輸出“5120449410”，符合預(yù)期。.主界面選擇10進(jìn)入函數(shù).輸入7.輸入10i值不符要求，提示插入失敗輸出''插入失?。≌?qǐng)檢查i值”，符合預(yù)期。1.主界面選擇10進(jìn)入函數(shù)2輸入03.輸入10i值不符要求，提示插入失敗輸出“插入失敗！請(qǐng)檢查i值”，符合預(yù)期。Test21.主界面選擇10進(jìn)入函數(shù)2輸入13.輸入10提示插入成功使用Traverse函數(shù)，得到表10輸出''插入成功！”使用Traverse函數(shù)，輸出“10”,符合預(yù)期。1.主界面選擇10進(jìn)入函數(shù)2輸入23.輸入10i值不符要求，提示插入失敗輸出“插入失??！請(qǐng)檢查i值”，符合預(yù)期。1.主界面選擇10進(jìn)入函數(shù)2輸入03.輸入10＞值不符要求，提示插入失敗輸出''插入失??！請(qǐng)檢查i值”，符合預(yù)期。無(wú)1.主界面選擇10進(jìn)入函數(shù)提示“線性表不存輸出“線性表不存在！

在！請(qǐng)先創(chuàng)建！”請(qǐng)先創(chuàng)建！”，符合。(4)ListDelete測(cè)試：(與上類似，故簡(jiǎn)化)表1.3.2-4ListDelete算法測(cè)試用例表測(cè)試用例程序輸入理論結(jié)果運(yùn)行結(jié)果Testi.主界面選擇11進(jìn)入函數(shù).根據(jù)提示輸入位置，輸入1提示插入成功使用Traverse函數(shù)，得到表12,0,44,94輸出“插入成功！”使用Traverse函數(shù)，輸出“1204494”，符合預(yù)期。1.主界面選擇10進(jìn)入函數(shù)2.輸入0i值不符要求，提示插入失敗輸出“插入失?。≌?qǐng)檢查i值”，符合預(yù)期。(5)ListTraverse測(cè)試：表132-5ListTraverse算法測(cè)試用例表測(cè)試用例程序輸入理論結(jié)果運(yùn)行結(jié)果Testi主界面選擇12進(jìn)入函數(shù)得到表5,12,0,44,94輸出“51204494”，符合預(yù)期。Test2主界面選擇12進(jìn)入函數(shù)提示線性表為空輸出“線性表是空表”，符合預(yù)期。無(wú)主界面選擇12進(jìn)入函數(shù)提示“線性表不存在！請(qǐng)先創(chuàng)建！”輸出“線性表不存在！請(qǐng)先創(chuàng)建！”，符合。1.4實(shí)驗(yàn)小結(jié)本次實(shí)驗(yàn)加深了對(duì)線性表的概念、基本運(yùn)算的理解，掌握了線性表的基本運(yùn)算的實(shí)現(xiàn)。熟練了線性表的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系。今后的學(xué)習(xí)過(guò)程中應(yīng)當(dāng)多從數(shù)據(jù)結(jié)構(gòu)的角度分析如何進(jìn)行數(shù)據(jù)的處理、存儲(chǔ)以方便問(wèn)題的解決，并要勤加練習(xí)達(dá)到熟能生巧的地步。2基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本運(yùn)算問(wèn)題描述掌握基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，實(shí)現(xiàn)線性表的基本的、常見(jiàn)的運(yùn)算2.2單鏈表演示系統(tǒng)設(shè)計(jì)系統(tǒng)總體設(shè)計(jì)一共有17個(gè)基本函數(shù)，具體功能如下InitSqList(SqList*L)操作結(jié)果：創(chuàng)建鏈?zhǔn)奖斫M。InitList(LinkList*L)操作結(jié)果：構(gòu)造一個(gè)空的鏈?zhǔn)奖鞤estroyList(LinkList*L)初始條件：鏈?zhǔn)奖鞮已存在。操作結(jié)果：銷毀鏈?zhǔn)奖鞮。ClearList(LinkList*L)初始條件：鏈?zhǔn)奖鞮已存在。操作結(jié)果：將L重:置為空鏈?zhǔn)奖?。ListEmpty(LinkList*L)初始條件：鏈?zhǔn)奖鞮已存在。操作結(jié)果：若L為空鏈?zhǔn)奖?，則返回TRUE,否則返回FALSE.ListLength(LinkList*L)初始條件：鏈?zhǔn)奖硪汛嬖?。操作結(jié)果：返回L中數(shù)據(jù)元素的個(gè)數(shù)。GetElem(LinkListL,inti,ElemType*e)初始條件：?jiǎn)捂湵硪汛嬖冢琹〈i〈ListLength(L)。操作結(jié)果：用e返回L中第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素值.LocateElem(LinkListL,ElemTypee,Status(*compare)(ElemTypea,ElemTypeb))初始條件：鏈?zhǔn)奖硪汛嬖凇２僮鹘Y(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值。PriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)初始條件：?jiǎn)捂湵鞮已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。NextElem(LinkListL,ElemTypecur_e,ElemType*next_e)初始條件：?jiǎn)捂湵鞮已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后-一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。ListInsert(LinkList*L,inti,ElemTypee)初始條件：鏈?zhǔn)奖鞮已存在且非空，1Wi〈ListLength(L)+l。操作結(jié)果：在L的第i個(gè)結(jié)點(diǎn)之前插入新數(shù)據(jù)元素e的結(jié)點(diǎn)。ListDelete(LinkList*L,inti,ElemType*e)初始條件：鏈?zhǔn)奖鞮已存在且非空，iWiWListLength(L)。操作結(jié)果：刪除L第i個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)，用e返回其結(jié)點(diǎn)數(shù)據(jù)元素的值。ListTraverse(LinkListL,Status(*visit)(ElemTypea)初始條件：鏈?zhǔn)奖鞮已存在。操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。。一旦調(diào)用失敗，則操作失敗。ChooseList(LinkList*L,chars[],SqListLO)初始條件：鏈?zhǔn)奖鞮已存在操作結(jié)果：選取已有鏈?zhǔn)奖斫M中的一組鏈?zhǔn)奖鞤eleteList(LinkList*L,chars[],SqListLO)初始條件：鏈?zhǔn)奖鞮存在操作結(jié)果：刪除鏈?zhǔn)奖鞮ReadList(SqList*L)初始條件：文件夾中保存有鏈?zhǔn)奖聿僮鹘Y(jié)果：成功讀取鏈?zhǔn)奖鞮SaveList(SqListL)初始條件：已創(chuàng)建鏈?zhǔn)奖鞮操作結(jié)果：將鏈?zhǔn)奖鞮保存在創(chuàng)建的文件夾中2.2.3算法設(shè)計(jì)InitSqList(SqList*L)創(chuàng)建鏈表組，參數(shù)為各個(gè)鏈?zhǔn)奖淼谋眍^指針地址，從而實(shí)現(xiàn)多個(gè)鏈?zhǔn)奖淼墓餐芾?。?fù)雜度：時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)InitList(LinkList*L)創(chuàng)建空鏈?zhǔn)奖鞮分三步：1.分配空間2.將數(shù)據(jù)域初始化為零3.將指針域初始化為0。時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)DestroyList(LinkList*L)銷毀鏈?zhǔn)奖矸?步：1.將上一個(gè)鏈?zhǔn)奖砼c下一個(gè)鏈?zhǔn)奖磉B接2.釋放鏈?zhǔn)奖頃r(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)ClearList(LinkList*L)將鏈?zhǔn)奖碇每眨柔尫沛準(zhǔn)奖淼拇鎯?chǔ)空間，再將上一個(gè)與下一個(gè)鏈?zhǔn)奖磉B接，最后將自身指針域置空處理，由此達(dá)到重置為空表的目的。時(shí)間復(fù)雜度T(n)=O(l)空間復(fù)雜度S(n)=O(l)ListEmpty(LinkList*L)判斷鏈?zhǔn)奖硎欠駷榭?。時(shí)間復(fù)雜度T(n)=0(n)空間復(fù)雜度S(n)=O(l)ListLength(LinkList*L)遍歷鏈表，利用計(jì)數(shù)器i統(tǒng)計(jì)鏈表元素個(gè)數(shù)。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)GetElem(LinkListL,inti,ElemType*e)利用結(jié)點(diǎn)P遍歷鏈?zhǔn)奖鞮,再利用計(jì)數(shù)器j來(lái)判斷是否到達(dá)所需位置i,如果到達(dá)，則返回該處元素，達(dá)到函數(shù)目的。時(shí)間復(fù)雜度T(n)=0(n)空間復(fù)雜度S(n)=O(l)LocateElem(LinkListL,ElemTypee,Status(*compare)(ElemTypea,Elemiypeb))利用p指針遍歷鏈表，再運(yùn)用compare函數(shù)進(jìn)行比較，如果在遍歷過(guò)程中找到元素e則返回此時(shí)計(jì)數(shù)器i,就是該元素在鏈表中的位置，由此實(shí)現(xiàn)函數(shù)功能。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)PriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)參數(shù)為鏈表頭指針L,查找的元素cur_e,用于返回其前驅(qū)的元素pre_e的地址,Status成功則返回OK,未找到返回ERROR,若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。時(shí)間復(fù)雜度T(n)=0(n)空間復(fù)雜度S(n)=O(l)NextElem(LinkListL,ElemTypecur_e,ElemType*next_e)參數(shù)為鏈表頭指針L,Status成功則返回OK,未找到返回ERROR,若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用next_e返回它的后驅(qū)，否則操作失敗，next_e無(wú)定義。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)ListInsert(LinkList*L,inti.ElemTypee)輸入?yún)?shù)：鏈表頭指針地址&L,插入位置i,插入元素e,在L的第i個(gè)結(jié)點(diǎn)之前插入新數(shù)據(jù)元素e的結(jié)點(diǎn)。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)ListDelete(LinkList*L,inti,ElemType*e)鏈表頭指針L,刪除位置i,用于返回其值的元素e的地址，刪除L第i個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)，用e返回其結(jié)點(diǎn)數(shù)據(jù)元素的值。時(shí)間復(fù)雜度T(n)=0(n)空間復(fù)雜度S(n)=O(l)ListTraverse(LinkListL,Status(*visit)(ElemTypea)鏈表頭指針L,指向調(diào)用函數(shù)的函數(shù)指針visit,依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visitOo一旦調(diào)用失敗，則操作失敗。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)ChooseList(LinkList*L,chars[],SqListLO)單鏈表頭指針地址，選擇的單鏈表名s,用于管理單鏈表的順序表L0,選擇指定單鏈表。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)DeleteList(LinkList*L,chars[],SqListLO)單鏈表頭指針地址，選擇的單鏈表名s,用于管理單鏈表的順序表L0,刪除指定單鏈表。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)ReadList(SqList*L)讀取鏈?zhǔn)奖?。時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)SaveList(SqListL)保存鏈?zhǔn)奖頃r(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(l)2.3單鏈表演示系統(tǒng)實(shí)現(xiàn)與測(cè)試2.3.1系統(tǒng)實(shí)現(xiàn)程序源代碼：#include<stdio.h>#include<stdlib.h> 24 #include<string.h>defineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASTABLE-1defineOVERFLOW-2typedefintStatus; //status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintElemType; 〃數(shù)據(jù)元素類型定義#defineLISTJNIT_SIZE100〃線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10〃線性表存儲(chǔ)空間的分配增量typedefstructLnode{ElemTypedata;structLnode*next;JLNode,*LinkList;typedefstruct(charname[20];LinkListTopLnode;}Top;typedefstruct{Top*elem;intlength;intlistsize;ISqList;〃線性表的單鏈表存儲(chǔ)結(jié)構(gòu)〃單鏈表的數(shù)據(jù)域〃單鏈表的指針域StatusInitSqList(SqList*L);〃創(chuàng)建鏈?zhǔn)奖斫MStatusInitList(LinkList*L);//構(gòu)造一個(gè)空的鏈?zhǔn)奖鞸tatusDestroyList(LinkList*L);〃銷毀線性表LStatusClearList(LinkList*L); 〃將L重置為空表StatusListEmpty(LinkListL); 〃若L為空表，則返回1,否則返回0intListLength(LinkListL); 〃返回L中數(shù)據(jù)元素的個(gè)數(shù)StatusGetElem(LinkListL,inti,ElemType*e);〃用e返回L中第i個(gè)數(shù)據(jù)元素的值intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemTypea,ElemTypeb));StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e); /*若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義*/StatusNextElem(LinkListL,ElemTypecur_e,ElemType*next_e); /*若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回的后繼，否則操作失敗，next”無(wú)定義刃/*在L的第/*在L的第i個(gè)位置/*刪除L的第i個(gè)數(shù)/*依次對(duì)L的每個(gè)之前插入新的數(shù)據(jù)元素e,L的長(zhǎng)度加1*/StatusListDelete(LinkList*L,inti,ElemType*e);據(jù)元素，用e返回其值，L的長(zhǎng)度減1*/StatusListTraverse(LinkListL,Status(*visit)(ElemTypea));數(shù)據(jù)元素調(diào)用函數(shù)visit。。一旦調(diào)用失敗，則操作失敗等〃選取已有鏈表中一個(gè)鏈?zhǔn)奖怼▌h除一個(gè)鏈?zhǔn)奖怼ㄗx取鏈?zhǔn)奖怼ū４骀準(zhǔn)奖怼ㄟx取已有鏈表中一個(gè)鏈?zhǔn)奖怼▌h除一個(gè)鏈?zhǔn)奖怼ㄗx取鏈?zhǔn)奖怼ū４骀準(zhǔn)奖鞸tatusDeleteList(LinkList*L,chars[],SqListLO);StatusReadList(SqList*L);StatusSaveList(SqListL);StatusVisit(ElemTypea);StatusCompare(ElemTypea,ElemTypeb);StatusInitSqList(SqList*L) 〃參數(shù)：管理各單鏈表的順序表頭指針地址(L->elem=(Top*)malloc(LISTJNIT^SIZE*sizeof(Top));if(!L->elem)(exit(OVERFLOW);)L->length=O; 〃空表長(zhǎng)度為0L->Iistsize=LIST_INIT_SIZE; //初始存儲(chǔ)容量StatusInitList(LinkList*L)returnOK;〃StatusInitList(LinkList*L)*L=(LinkList)malloc(sizeof(LNode));if(*L==NULL)(exit(OVERFLOW);)(*L)->data=0;//空表長(zhǎng)度為o(*L)->next=NULL;returnOK;1〃將指針域初始化為0StatusDestroyList(LinkList*L)LinkListp,q;p=*L;〃p指向頭結(jié)點(diǎn)while(p)i〃遍歷沒(méi)到表尾tq=p->next;free(p);〃將上一個(gè)鏈?zhǔn)奖砼c下一個(gè)鏈?zhǔn)奖磉B接p=q；}*L=NULL;returnOK;)StatusClearList(LinkList*L)LinkListp,q;p=(*L)->next;while(p)(〃p指向第一個(gè)結(jié)點(diǎn)//遍歷沒(méi)到表尾q=p->next;free(p);〃將上一個(gè)與下一個(gè)鏈?zhǔn)奖磉B接p=q；(*L)->next=NULL;〃頭結(jié)點(diǎn)指針域?yàn)榭誶eturnOK;StatusListEmpty(LinkListL)〃判斷鏈?zhǔn)奖硎欠駷榭読f(L->next)(returnFALSE;)else(returnTRUE;))intListLength(LinkListL)(inti=0;LinkListp=L->next;while(p)//p指向第一個(gè)結(jié)點(diǎn)〃當(dāng)p沒(méi)到表尾i++；p=p->next;)returni;)StatusGetElem(LinkListLJnti,ElemType*e)intj=1;LinkListp;p=L->next;while(p&&j<i)//j為計(jì)數(shù)器〃聲明一結(jié)點(diǎn)p〃讓p指向鏈表L的第一個(gè)結(jié)點(diǎn)〃p不為空或者計(jì)數(shù)器j還沒(méi)有等于i時(shí)，循環(huán)繼續(xù)

p=p->next; 〃讓p指向下一個(gè)結(jié)點(diǎn)++j；)if(!pllj>i)(returnERROR; 〃第i個(gè)元素不存在]*e=p->data; 〃用e取第i個(gè)元素returnOK;IintLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemTypea,ElemTypeb))(inti=0;LinkListp=L->next; //p初始為頭指針while(p)(i++；if((*compare)(p->data,e))//找到這樣的數(shù)據(jù)元素(returni;)p=p->next;)return0;}StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)(LinkListp=L->next;)if(p->next==NULL)while(p->next!=NULL&&p->next->data!=cur_e)(p=)if(p->next==NULL)〃未找到對(duì)應(yīng)元素的前驅(qū)returnERROR;!*pre_e=p->data;returnOK;}StatusNextElem(LinkListL,ElemTypecur_e,ElemType*next_e)(LinkListp=L->next;while(p->next!=NULL&&p->data!=cur_e){p=p->next;)if(p->next==NULL) 〃到最后一個(gè)仍未找到(returnERROR;}*next_e=p->next->data;returnOK;)StatusListInsert(LinkList*L,inti,ElemTypee)(intj=1;LinkListp,new;P=*L;while(p&&j<i) 〃尋找第i個(gè)結(jié)點(diǎn)(p=p->next;++j；)if(!p||j>i) 〃第i個(gè)元素不存在returnERROR;)new=(LinkList)malloc(sizeof(LNode));〃生成新結(jié)點(diǎn)if(new==NULL)(exit(OVERFLOW);}new->data=e;new->next=p->next; 〃將p的后繼結(jié)點(diǎn)賦值給new的后繼p->next=new; 〃將new賦值給p的后繼returnOK;)StatusCompare(ElemTypea,ElemTypeb)(if(a==b)(returnTRUE;)else(returnFALSE;StatusVisit(ElemTypea)(printf(H%d\a);returnOK;StatusListDelete(LinkList*L,inti,ElemType*e)intj=1;LinkListp,q;p=*L;while(p->next&&j<i)〃尋找第i個(gè)元素p=p->next;++j；?1if(!(p->next)||j>i)〃第i個(gè)元素不存在(returnERROR;)q=p->next;p->next=q->next;〃將q的后繼賦值給p的后繼*e=q->data;〃將q結(jié)點(diǎn)中的數(shù)據(jù)給efree(q);〃釋放內(nèi)存returnOK;)StatusListTraverse(LinkListL,Status(*visit)(ElemTypea))(LinkListp=L->next;if(lp)(returnERROR;Iprintf(H\n allelements \nn);while(p)(if(!(*visit)(p->data))(printf("操作失??！");)p=p->next;}printf(H\n end \nn);returnOK;StatusChooseList(LinkList*L,chars[],SqListLO)(inti;for(i=0;i<LO.length;i++)(if(strcmp(LO.elem[i].name,s)==0)(*L=L0.elem[i].TopLnode;returnOK;))returnERROR;)StatusDeleteList(LinkList*L,chars[],SqListLO)(inti,j;for(i=0;i<LO.length;i++)(if(strcmp(LO.elem[i].name,s)==0)(〃若當(dāng)前單鏈表為刪除的鏈表，將單鏈表置空if(*L=LO.elem[i].TopLnode){ClearList(L);I//刪除位置之后的單鏈表前移for(j=i;j<LO.length-1;j++){LO.elem[j].TopLnode=L0.elem[j+1].TopLnode;strcpy(LO.elem[j].name,LO.elem|j+1J.name);LO.elem[jl.TopLnode=NULL;strcpy(LO.elem[j].name,“無(wú)")；LO.length—;returnOK;})returnERROR;)StatusReadList(SqList*L)(inti,num;InitSqList(L);FILE*fp;charfilename[30];printfC請(qǐng)輸入讀取文件名：”)；scanf(,'%s,\&filename);if((fp=fopen(filename,nrn))==NULL)(printf("文件打開失??！\n")；returnERROR;}while(fread(L->elem[L->length].name,sizeof(char),20,fp))(LinkListI=(LinkList)malloc(sizeof(LNode));L->elem[L->length].TopLnode=I;fread(&num,sizeof(int),1,fp);fbr(i=0;i<=num;i++)(fread(&l->data,sizeof(ElemType),1,fp);l->next=(i!=num)?(LinkList)malloc(sizeof(LNode)):NULL;1=l->next;}L->length++;fclose(fp);returnOK;}StatusSaveList(SqListL) 〃保存線性表(inti;FILE*fp;charfilename[30];primfC請(qǐng)輸入保存文件名：”)；scanf("%s”,&filename);〃寫文件的方法if((fp=fopen(filename,0w"))==NULL)(printf("文件打開失敗\n")；returnERROR;}for(i=0;i<L.length;i++)(intnum;fwrite(L.elem[i].name,sizeof(char),20,fp);LinkList1=L.elem[i].TopLnode;num=ListLength(l);fwrite(&num,sizeof(int),1,fp);intj;fbr(j=0;j<=num;j++)(fwrite(l,sizeof(臼emType),1,fp);1=l->next;})fclose(fp);returnOK;) 35 2.3.2系統(tǒng)測(cè)試測(cè)試用例程序輸入理論結(jié)果運(yùn)行結(jié)果1.文件名M文件和S文件當(dāng)退出系統(tǒng)時(shí)會(huì)將數(shù)據(jù)儲(chǔ)存在建立的文件中文件夾中出現(xiàn)M文件和S文件2.創(chuàng)建鏈?zhǔn)奖鞮1、L2、L3LI,L2儲(chǔ)存在M文件中，L3儲(chǔ)存在S文件中當(dāng)執(zhí)行13,：讀取文件夾M時(shí)，再選取其中鏈?zhǔn)奖鞮1即可成功選取成功選取鏈?zhǔn)奖鞮13.向鏈?zhǔn)奖鞮1輸入數(shù)據(jù)操作序號(hào)10,依次輸入位置及元素：135,7輸出L1中元素時(shí)成功輸出135,7成功輸出1,3574.返回鏈?zhǔn)奖鞮1中第三個(gè)元素操作序號(hào)6,再輸入位置3屏幕顯示輸出5成功輸出55.判斷鏈?zhǔn)奖鞮1是否為空操作序號(hào)4L1不為空測(cè)試成功6.返回鏈?zhǔn)奖鞮1中數(shù)據(jù)8的序號(hào)操作序號(hào)7,再輸入元素58在鏈?zhǔn)奖鞮1中序號(hào)為3測(cè)試成功7.求鏈?zhǔn)奖鞮1中元素8的前一個(gè)元素操作序號(hào)8,再輸入元素5返回元素5的前一個(gè)元素3測(cè)試成功8.求鏈?zhǔn)奖鞮1中元素8的后一個(gè)元素操作序號(hào)9,再輸入元素5返回元素5的后一個(gè)元素7測(cè)試成功9.:鏈?zhǔn)奖鞮1中插入第5個(gè)位置64操作序號(hào)10,再輸入位置5以及元素64插入成功，以及輸出鏈?zhǔn)奖鞮1的元素時(shí)也會(huì)出現(xiàn)64測(cè)試成功10.刪除線鏈?zhǔn)奖鞮中第5個(gè)元素64操作序號(hào)11,再輸入位置5刪除成功，以及輸出鏈?zhǔn)奖鞮1的元素時(shí)64消失測(cè)試成功11.選取鏈?zhǔn)奖鞮2進(jìn)行操作操作序號(hào)15,再輸入鏈?zhǔn)奖砻QL2后續(xù)操作即可為鏈?zhǔn)奖鞮2進(jìn)行操作測(cè)試成功2.4實(shí)驗(yàn)小結(jié)相對(duì)第一次上機(jī)感覺(jué)這次的內(nèi)容要復(fù)雜一些，對(duì)鏈表的操作要比對(duì)數(shù)組的操作更具難度,剛開始不知道怎么入手，問(wèn)過(guò)同學(xué)后才知道該怎么對(duì)多個(gè)鏈表同時(shí)進(jìn)行操作，遇到很多不懂的又翻看課本，最終都找到解決辦法，總之這次上機(jī)還是獲益匪淺的，學(xué)會(huì)用鏈?zhǔn)浇Y(jié)構(gòu)對(duì)線性表進(jìn)行運(yùn)算等操作，但自己的編程能力確實(shí)還有待加強(qiáng)，學(xué)得還不夠深入，使得每次上機(jī)都變得困難重重。以后要努力改進(jìn)，爭(zhēng)取做得更好。3基于順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧的基本運(yùn)算3.1順序棧實(shí)驗(yàn)3.1.1問(wèn)題描述完成棧的創(chuàng)建等基本操作，通過(guò)棧進(jìn)行簡(jiǎn)單的個(gè)位數(shù)的四則運(yùn)算。實(shí)驗(yàn)?zāi)康模?1)加深對(duì)棧的概念、基本運(yùn)算的理解；(2)熟練掌握棧的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系；(3)熟練掌握順序棧的基本運(yùn)算的實(shí)現(xiàn)；(4)通過(guò)棧的應(yīng)用體會(huì)其用途。(5)通過(guò)棧實(shí)現(xiàn)簡(jiǎn)單的個(gè)位數(shù)的四則運(yùn)算棧的簡(jiǎn)介：棧是一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)(最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái))。棧具有記憶作用，對(duì)棧的插入與刪除操作中，不需要改變棧底指針。棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top),另一端為棧底(base)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧(PUSH),刪除則稱為退棧(POP)。棧也稱為后進(jìn)先出表。3.1.2順序棧設(shè)計(jì)InitStack(ftS)操作結(jié)果：構(gòu)造一個(gè)空棧S。函數(shù)代碼：statusInitStack(SqStack*S){〃構(gòu)造一個(gè)空棧SS->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S->base){printf("初始化棧失敗”)；exit(OVERFLOW);}〃存儲(chǔ)分配失敗S->top=S->base;S->stacksize=STACK_INITSIZE;returnOK;}//InitStackDestroyStack(&S)初始條件：棧S存在。操作結(jié)果：棧S被銷毀，不在存在。函數(shù)代碼：statusDestroyStack(SqStack*S){〃銷毀棧S,S不再存在free(S->base)；〃釋放棧底指針S->base=NULL;〃棧底指針指向空。代表?xiàng)２淮嬖赟->top=NULL;〃棧頂指針也指向空S->stacksize=O;〃銷毀棧時(shí)把棧的長(zhǎng)度改為0returnOK;ClearStack(&S)初始條件：棧S存在。操作結(jié)果：將s清成空棧。函數(shù)代碼：statusClearStack(SqStack*S){〃把S置為空棧S->top=S->base;returnOK;)StackEmpty(S)初始條件：棧S存在。操作結(jié)果：若S為空棧，則返回值為TRUE；否則為FALSE。函數(shù)代碼：statusStackEmpty(SqStack*S){〃若棧S為空棧，則返回TURE,否則返回FALSEif(S->top==S->base)returnTRUE;elsereturnFALSE;開始返回FALSE開始返回FALSE返回TURE結(jié)束4(1StackLength(S)初始條件：棧S存在。操作結(jié)果：返回棧S的元素個(gè)數(shù)。函數(shù)代碼：statusStackLength(SqStack*S){〃返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度returnS->top-S->base;(6)(6)GetTop(S,&e)初始條件：棧S存在并且非空。操作結(jié)果：將棧頂元素拷貝到若S為空棧，則結(jié)束拷貝。函數(shù)代碼：statusGetTop(SqStackS,SElemType*e){〃若棧不為空，則用e返回S的棧頂元素，并返回OK,否則返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1)"/選取棧頂元素ereturnOK;取棧頂元素e=*(S.top-l)結(jié)束取棧頂元素e=*(S.top-l)結(jié)束Push(&S,e)初始條件：棧S存在。若S已滿，則發(fā)生溢出。若不能解決溢出，重新分配空間失敗,則插入失敗。操作結(jié)果：插入元素e為新的棧頂元素。函數(shù)代碼：statusPush(SqStack*S,SElemTypee){〃插入元素e為新的棧頂元素if(S->top-S->base>=S->stacksize){〃棧滿，追加存儲(chǔ)空間S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S->base)exit(OVERFLOW);〃存儲(chǔ)分配失敗S->top=S->base+STACKINCREMENT;*S->top++=e;returnOK;}//PushPop(&S,&e)初始條件：棧S存在并且非空。操作結(jié)果：刪除棧S的棧頂元素，并送入e。若S為空棧，發(fā)生“下溢"(underflow)：

為空棧時(shí)，表示某項(xiàng)任務(wù)已完成。函數(shù)代碼：statusPop(SqStack*S){//若棧不空，則刪除S的棧頂元素，返回其值，否則返回ERRORif(S->top—S->base)returnERROR;return(*—S->top);}//PopStackTravserse(S,visit())初始條件：棧S存在。操作結(jié)果：從棧底到棧頂依次對(duì)棧S中的元素使用函數(shù)visit進(jìn)行訪問(wèn)。函數(shù)代碼：intStackTravserse(SqStackS,int(*visit)(SElemType)){//從棧底到棧頂依次對(duì)棧中的每個(gè)元素調(diào)用函數(shù)visit。。一旦visit。失敗，則操作失敗while(S.top>S.base)

visit(*S.base++);returnOK;3.1.2順序棧實(shí)現(xiàn)與測(cè)試1,實(shí)現(xiàn)部分#include<stdio.h>#include<stdlib.h>#include<string.h>/*函數(shù)結(jié)果狀態(tài)代碼刃#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2typedefintStatus; //status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintSElemType; 〃數(shù)據(jù)元素類型定義#defineSTACK_INIT_SIZE100〃存儲(chǔ)空間的初始分配量#defineSTACKINCREMENT10〃存儲(chǔ)空間的分配增量typedefstruct{SElemType*base;SElemType*top;intstacksize;JSqStack;StatusInitStack(SqStack*S);〃構(gòu)造一個(gè)空棧SStatusDestroyStack(SqStack*S);〃銷毀棧s,s不再存在StatusClearStack(SqStack*S);〃把S置為空棧StatusStackEmpty(SqStackS);〃若棧S為空棧，貝lj返回TRUE,否則返回errorintStackLength(SqStackS);〃返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度StatusGetTop(SqStackS,SElemType*e);〃若棧不空，則用e返回S的棧頂元素，并返回OK,否則返回errorStatusPush(SqStack*S,SElemTypee);〃插入元素e為新的棧頂元素StatusPop(SqStack*S,SEIemType*e);〃若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK,否則返回errorStatusStackTraverse(SqStackS,Status(*visit)());〃從棧底到棧頂依次對(duì)棧中每個(gè)元素調(diào)用函數(shù)visit。。一旦visit。失敗，則操作失敗StatusReadStack(SqStack*S);〃讀取棧操作StatusSaveStack(SqStackS);〃保存棧操作StatusVisit(SElemTypea);〃顯示aStatusIn(charc,charop[]);〃判斷輸入的某個(gè)字符是否是運(yùn)算符charPrecede(chara,charb);〃比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)intOperate(inta,chartheta,intb);intEvaluateExpression();StatusInitStack(SqStack*S){〃構(gòu)造一個(gè)空棧S->base=(SElemType*)malloc(STACKJNIT_SIZE*sizeof(SElemType));if(!S->base)exit(OVERFLOW); //存儲(chǔ)分配失敗S->top=S->base;S->stacksize=STACKJNIT_SIZE;returnOK;}//InitStackStatusDestroyStack(SqStack*S){S->top=NULL;S->stacksize=0;free(S->base);returnOK;}//DestroyStackStatusClearStack(SqStack*S){S->top=S->base;returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;intStackLength(SqStackS){return(S.top-S.base);}StatusGetTop(SqStackS,SElemType*e){〃若棧不空，則用e返回S的棧頂元素，并返回0K,否則返回errorif(S.top==S.base)returnERROR;*e=*(S.top-1);returnOK;}//GetTopStatusPush(SqStack*S,SElemTypee){〃插入e為新的棧頂元素if(S->top-S->base>=S->stacksize){〃棧滿，追加存儲(chǔ)空間S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S->base)exit(OVERFLOW); 〃存儲(chǔ)分配失敗S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;)*S->top++=e;returnOK;}//PushStatusPop(SqStack*S,SElemType*e)(〃若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK,否則返回ERRORif(S->top==S->base)returnERROR;*e=*-S->top;returnOK;}//PopStatusStackTraverse(SqStackS,Status(*visit)(SElemTypea)){while(S.top>S.base){visit(*S.ba