數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二鏈表

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二1、實(shí)驗(yàn)?zāi)康?熟練掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義及基本操作?理解循環(huán)鏈表和雙鏈表的特點(diǎn)和基本運(yùn)算2、實(shí)驗(yàn)內(nèi)容：建立單鏈表，完成鏈表（帶表頭結(jié)點(diǎn)）的基本操作：建立鏈表、插入、刪除、查找、輸出、求前驅(qū)、求后繼、兩個(gè)有序鏈表的合并操作。其他基本操作還有銷毀鏈表、將鏈表置為空表、求鏈表的長(zhǎng)度、獲取某位置結(jié)點(diǎn)的內(nèi)容、搜索結(jié)點(diǎn)。1．問(wèn)題描述：利用線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),設(shè)計(jì)一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠?qū)捂湵磉M(jìn)行如下操作：初始化一個(gè)帶表頭結(jié)點(diǎn)的空鏈表；創(chuàng)建一個(gè)單鏈表是從無(wú)到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相互鏈接的關(guān)系。又分為逆位序（插在表頭）輸入n個(gè)元素的值和正位序（插在表尾）輸入n個(gè)元素的值；插入結(jié)點(diǎn)可以根據(jù)給定位置進(jìn)行插入（位置插入），也可以根據(jù)結(jié)點(diǎn)的值插入到已知的鏈表中（值插入），且保持結(jié)點(diǎn)的數(shù)據(jù)按原來(lái)的遞增次序排列，形成有序鏈表。刪除結(jié)點(diǎn)可以根據(jù)給定位置進(jìn)行刪除（位置刪除），也可以把鏈表中查找結(jié)點(diǎn)的值為搜索對(duì)象的結(jié)點(diǎn)全部刪除（值刪除）；輸出單鏈表的內(nèi)容是將鏈表中各結(jié)點(diǎn)的數(shù)據(jù)依次顯示，直到鏈表尾結(jié)點(diǎn)；求前驅(qū)結(jié)點(diǎn)是根據(jù)給定結(jié)點(diǎn)的值，在單鏈表中搜索其當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)值為給定的值，將當(dāng)前結(jié)點(diǎn)返回；求后繼結(jié)點(diǎn)是根據(jù)給定結(jié)點(diǎn)的值，在單鏈表中搜索其當(dāng)前結(jié)點(diǎn)的值為給定的值，將后繼結(jié)點(diǎn)返回；兩個(gè)有序鏈表的合并是分別將兩個(gè)單鏈表的結(jié)點(diǎn)依次插入到第3個(gè)單鏈表中，繼續(xù)保持結(jié)點(diǎn)有序；編寫(xiě)主程序，實(shí)現(xiàn)對(duì)各不同的算法調(diào)用。其它的操作算法描述略。2．實(shí)現(xiàn)要求：對(duì)鏈表的各項(xiàng)操作一定要編寫(xiě)成為C（C++）語(yǔ)言函數(shù)，組合成模塊化的形式，還要針對(duì)每個(gè)算法的實(shí)現(xiàn)從時(shí)間復(fù)雜度和空間復(fù)雜度上進(jìn)行評(píng)價(jià)?！俺跏蓟惴ā钡牟僮鹘Y(jié)果：構(gòu)造一個(gè)空的線性表L,產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)；“建立鏈表算法”初始條件：空鏈存在；操作結(jié)果：選擇逆位序或正位序的方法，建立一個(gè)單鏈表，并且返回完成的結(jié)果；“鏈表（位置）插入算法”初始條件：已知單鏈表L存在；操作結(jié)果：在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e；“鏈表(位置)刪除算法”初始條件：已知單鏈表L存在；操作結(jié)果：在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素,并由e返回其值；“輸出算法”初始條件：鏈表L已存在；操作結(jié)果：依次輸出鏈表的各個(gè)結(jié)點(diǎn)的值；“求前驅(qū)算法”初始條件:線性表L已存在；操作結(jié)果：若cur_e是L的數(shù)據(jù)元素,且不是第一個(gè)，則用pre_e返回它的前驅(qū)；“求后繼算法”初始條件:線性表L已存在；操作結(jié)果：若cur_e是L的數(shù)據(jù)元素,且不是最后一個(gè),則用next_e返回它的后繼；“兩個(gè)有序鏈表的合并算法”初始條件：線性表單鏈線性表La和Lb的元素按值非遞減排列；操作結(jié)果:歸并La和Lb得到新的單鏈表。3、實(shí)驗(yàn)指導(dǎo)1．根據(jù)一個(gè)完整的C語(yǔ)言組成，將實(shí)驗(yàn)內(nèi)容組合成如上所述的三個(gè)組成部分，功能清晰明了，其常量定義和常用系統(tǒng)函數(shù)原型聲明的文件“pubuse.h”代碼復(fù)用，不需另行建立。2?建立一個(gè)單鏈表類型定義的頭文件，如取名為：1inklistDef.h，以后凡使用該文件定義的類型，就只需使用包含語(yǔ)句#inc1ude“l(fā)inklistDef.h”即可。關(guān)于實(shí)驗(yàn)內(nèi)容要完成的操作，一般都以獨(dú)立的算法出現(xiàn)，建立一個(gè)單鏈表的基本算法文件，將各種不同算法組合在一個(gè)文件之中，存儲(chǔ)為一個(gè)頭文件如取名為：linklistAlgo.h,后凡涉及到要使用本文件中的單鏈表算法，一定要在你的文件的前面加上一條#inc1ude“l(fā)inklistAlgo.h”即可，實(shí)現(xiàn)的算法函數(shù)，女口ListInit_Link、ListInsert_Link、ListDelete_Link、ListTraverse_Link、PriorE1em_Link、NextE1em_Link、GetE1em_Link、MergeList_Link等；還應(yīng)包含一個(gè)main函數(shù)，作為整個(gè)程序的執(zhí)行入口處，定義測(cè)試的數(shù)據(jù)，完成各種算法的調(diào)用執(zhí)行，對(duì)算法的執(zhí)行過(guò)程和結(jié)果進(jìn)行判斷和輸出控制，存儲(chǔ)為一個(gè)源文件(如取名為1ink1istUse.cpp)。4、基本實(shí)驗(yàn)的參考程序文件1ink1istDef.h是線性表的單鏈表存儲(chǔ)結(jié)構(gòu)的定義structLNode{E1emTypedata；structLNode*next；}；typedefstructLNode*LinkList； /*另一種定義LinkList的方法*/文件1ink1istA1go.h是單鏈表的基本算法描述/*以下的算法均是針對(duì)帶表頭結(jié)點(diǎn)的單鏈表*/StatusListInit_Link(LinkList&L){/*操作結(jié)果：構(gòu)造一個(gè)空的線性表L*/L=(LinkList)ma11oc(sizeof(structLNode))； /*產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn)*/if(!L)/*存儲(chǔ)分配失敗*/exit(OVERFLOW)；L->next=NULL；/*指針域?yàn)榭?/returnOK；}StatusListDestroy_Link(LinkListL){/*初始條件：線性表L已存在。*//*操作結(jié)果：銷毀線性表L*/LinkListq；while(L){q=L->next；free(L)；L=q；}returnOK；}StatusListClear_Link(LinkListL)/*不改變L*/{/*初始條件：線性表L已存在。*//*操作結(jié)果：將L重置為空表*/LinkListp,q；p=L->next；/*p指向第一個(gè)結(jié)點(diǎn)*/while(p)/*沒(méi)到表尾*/{q=p->next；free(p)；p=q；}L->next=NULL；/*頭結(jié)點(diǎn)指針域?yàn)榭?/returnOK；}StatusListEmpty_Link(LinkListL){/*初始條件：線性表L已存在。*//*操作結(jié)果：若L為空表，則返回TRUE,否則返回FALSE*/if(L->next)/*非空*/returnFALSE；elsereturnTRUE；}intListLength_Link(LinkListL){/*初始條件：線性表L已存在。*//*操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)*/inti=0；LinkListp=L->next；/*p指向第一個(gè)結(jié)點(diǎn)*/while(p)/*沒(méi)到表尾*/{i++；p=p->next；}returni；}StatusGetElem_Link(LinkListL,inti,ElemType&e)/*算法2.8*/{/*初始條件:L為帶頭結(jié)點(diǎn)的單鏈表的頭指針*//*操作結(jié)果：當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK,否則返回ERROR*/intj=1；/*j為計(jì)數(shù)器*/LinkListp=L->next；/*p指向第一個(gè)結(jié)點(diǎn)*/while(p&&j<i)/*順指針向后查找,直到p指向第i個(gè)元素或p為空*/{p=p->next；j++；}if(!p||j>i)/*第i個(gè)元素不存在*/returnERROR；e=p->data；/*取第i個(gè)元素*/returnOK；}intLocateElem_Link(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/*初始條件：線性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0)*//*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。*//*若這樣的數(shù)據(jù)元素不存在,則返回值為0*/inti=0；LinkListp=L->next；while(p){i++；if(compare(p->data,e))/*找到這樣的數(shù)據(jù)元素*/returni；p=p->next；}return0；}StatusListInsert_Link(LinkListL,inti,ElemTypee)/*算法2.9，不改變L*/{/*在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e*/intj=0；LinkListp=L,s；while(p&&j<i-1)/*尋找第i-1個(gè)結(jié)點(diǎn)*/{p=p->next；j++；}if(!p||j>i-1)/*i小于1或者大于表長(zhǎng)*/returnERROR；s=(LinkList)malloc(sizeof(structLNode))；/*生成新結(jié)點(diǎn)*/s->data=e；/*插入L中*/s->next=p->next；p->next=s；returnOK；}StatusListDelete_Link(LinkListL,inti,ElemType&e)/*算法2.10,不改變L*/{/*在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素,并由e返回其值*/intj=0；LinkListp=L,q；while(p->next&&j<i-1)/*尋找第i個(gè)結(jié)點(diǎn),并令p指向其前趨*/{p=p->next；j++；}if(!p->next||j>i-1)/*刪除位置不合理*/returnERROR；q=p->next；/*刪除并釋放結(jié)點(diǎn)*/p->next=q->next；e=q->data；free(q)；returnOK；}StatusListTraverse_Link(LinkListL){/*初始條件：線性表L已存在*//*操作結(jié)果:依次對(duì)L的每個(gè)數(shù)據(jù)元素的值進(jìn)行輸出*/LinkListp=L->next；while(p){printf("%d",p->data)；p=p->next；}printf("\n")；returnOK；}voidCreateList_Link(LinkList&L,intn)/*算法2.11*/{/*逆位序(插在表頭)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表L*/inti；LinkListp；L=(LinkList)malloc(sizeof(structLNode))；L->next=NULL；/*先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表*/printf(”請(qǐng)輸入％d個(gè)數(shù)據(jù)\n",n)；for(i=n；i>0；--i){p=(LinkList)malloc(sizeof(structLNode))； /*生成新結(jié)點(diǎn)*/scanf("%d",&p->data)； /*輸入元素值*/p->next=L->next； /*插入到表頭*/L->next=p；}}voidCreateList2_Link(LinkList&L,intn){/*正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表*/inti；LinkListp,q；L=(LinkList)malloc(sizeof(structLNode))； /*生成頭結(jié)點(diǎn)*/L->next=NULL；q=L；printf(”請(qǐng)輸入％d個(gè)數(shù)據(jù)\n",n)；for(i=1；i<=n；i++){p=(LinkList)malloc(sizeof(structLNode))；scanf("%d",&p->data)；q->next=p；q=q->next；}p->next=NULL；}StatusPriorElem_Link(LinkListL,ElemTypecur_e,ElemType&pre_e){/*初始條件:線性表L已存在*//*操作結(jié)果:若cur_e是L的數(shù)據(jù)元素,且不是第一個(gè),則用pre_e返回它的前驅(qū),*//*返回OK；否則操作失敗,pre_e無(wú)定義，返回INFEASIBLE*/………(將函數(shù)補(bǔ)充完整)LinkListq,p=L->next； /*p指向第一個(gè)結(jié)點(diǎn)*/while(p->next)/*p所指結(jié)點(diǎn)有后繼*/{q=p-〉next； /*q為p的后繼*/if(q->data==cur_e){pre_e=p-〉data；returnOK；}p=q； /*p向后移*/}returnINFEASIBLE；}}StatusNextElem_Link(LinkListL,ElemTypecur_e,ElemType&next_e){/*初始條件：線性表L已存在*//*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，*//*返回OK；否則操作失敗，next_e無(wú)定義，返回INFEASIBLE*/………(將函數(shù)補(bǔ)充完整)LinkListp=L-〉next； /*p指向第一個(gè)結(jié)點(diǎn)*/while(p-〉next)/*p所指結(jié)點(diǎn)有后繼*/{if(p-〉data==cur_e){next_e=p-〉next-〉data；returnOK；}p=p-〉next；}returnINFEASIBLE；}}voidMergeList_Link(LinkList&La,LinkList&Lb,LinkList&Lc)/*算法2.12為擴(kuò)展實(shí)驗(yàn)的內(nèi)容*/{/*已知單鏈線性表La和Lb的元素按值非遞減排列。*//*歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列*/………(將函數(shù)補(bǔ)充完整)LinkListpa=La-〉next,pb=Lb-〉next,pc；Lc二pc二La； /*用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)*/while(pa&&pb)if(pa-〉data<=pb-〉data){pc-〉next=pa；pc=pa；pa=pa-〉next；}else{pc->next=pb；pc=pb；pb=pb->next；}pc->next=pa?pa:pb；/*插入剩余段*/free(Lb)； /*釋放Lb的頭結(jié)點(diǎn)*/Lb=NULL；}}3.將測(cè)試數(shù)據(jù)和主函數(shù)新定義一個(gè)文件，如取名為:linlistUse.cpp./*linlistUse.cpp主要實(shí)現(xiàn)算法2.9、2.10、2.11、2.12的程序*/#include"pubuse.h"typedefintElemType；#include"linklistDef.h"#include"linklistAlgo.h"voidmain(){intn=5；LinkListLa，Lb，Lc；inti；ElemTypee；printf(”按非遞減順序,”)；CreateList2_Link(La，n)； /*正位序輸入n個(gè)元素的值，建立一個(gè)單鏈表*/printf("La=")； /*輸出鏈表La的內(nèi)容*/ListTraverse_Link(La)；printf(”按非遞增順序,")；CreateList_Link(Lb,n)； /*逆位序輸入n個(gè)元素的值*/printf("Lb=")； /*輸出鏈表Lb的內(nèi)容*/ListTraverse_Link(Lb)；MergeList_Link(La,Lb,Lc)； /*按非遞減順序歸并La和Lb,得到新表Lc*/printf("Lc=")； /*輸出鏈表Lc的內(nèi)容*/ListTraverse_Link(Lc)；/*算法2.9的測(cè)試*/printf("\nenterinsertlocationandvalue:")；scanf("%d%d",&i,&e)；ListInsert_Link(Lc,i,e)；/*在Lc鏈表中第i個(gè)結(jié)點(diǎn)處插入一個(gè)新的結(jié)點(diǎn)，其值為e；*/printf("Lc=")； /*輸出鏈表Lc的內(nèi)容*/ListTraverse_Link(Lc)；/*算法2.10的測(cè)試*/printf("\nenterdeletdlocati