線性表的鏈式存儲結(jié)構(gòu)實驗報告

《線性表的鏈式存儲結(jié)構(gòu)實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法分析實驗名稱：鏈表的實現(xiàn)與應(yīng)用實驗日期：2015.01.30班級:數(shù)媒1401姓名：范業(yè)嘉學(xué)號1030514108—實驗?zāi)康恼莆站€性表的鏈式存儲結(jié)構(gòu)設(shè)訃與基本操作的實現(xiàn)。二、實驗內(nèi)容與要求⑴定義線性表的鏈式存儲表示；⑵基于所設(shè)計的存儲結(jié)構(gòu)實現(xiàn)線性表的基木操作；⑶編寫一個主程序?qū)λ鶎崿F(xiàn)的線性表進行測試；⑷線性表的應(yīng)用：①設(shè)線性表L1和L2分別代表集合A和B,試設(shè)計算法求A和B的并集C,并用線性表L3代表集合C；②(選做)設(shè)線性表L1和L2中的數(shù)據(jù)元素為整數(shù)，且均已按值非遞減有序排列,試設(shè)計算法對L1和L2進行合

2、并，用線性表L3保存合并結(jié)果，要求L3中的數(shù)據(jù)元素也按值非遞減有序排列。⑸設(shè)計一個一元多項式計算器，要求能夠：①輸入并建立多項式；②輸出多項式；③執(zhí)行兩個多項式相加；④執(zhí)行兩個多項式相減；⑤(選做)執(zhí)行兩個多項式相乘。三、數(shù)據(jù)結(jié)構(gòu)設(shè)計1.按所用指針的類型、個數(shù)、方法等的不同，又可分為：線性鏈表(單鏈表)靜態(tài)鏈表循環(huán)鏈表雙向鏈表雙向循壞鏈表2.用一組任意的存儲單元存儲線性表屮數(shù)據(jù)元素，用指針來表示數(shù)據(jù)元素間的邏輯關(guān)系。四、算法設(shè)計1.定義一個鏈表voidcreatlist(Linklist&L,intn){inti;Linklistp,s;L=

3、(Linklist)malloc(sizeof(Lnode));P=L;L->next=NULL;for(i=0;idata);s->next=NULL;p?>next二s;p=s;2.(1)兩個鏈表的合并voidMergelist(Linklist&La,Linklist&Lb,Linklist&Lc){Linklistpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb)

4、{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);}(2)兩個鏈表的并集Linklistunionlist(Linklist&La,Linklist&Lb){Linklistpl,p2,head,q,s;intflag;head=q=(Linklist)malloc(sizeof(Lnode));pl=La->next;while(pl){flag=0;p2

5、=Lb->next;while(p2){if(p1->data==p2->data){flag=l；break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=pl->data;q->next=s;q=s;}pl=pl->next;q->next=Lb->next;returnhead;}1.(1)一元多項式的加法Listaddpoly(Listpa,Listpb)〃一元多項式的加法{intn;Listpc,s,p;pa=pa->next;pb=pb->n

6、ext;pc=(List)malloc(sizeof(structLinklist));pc->next=NULL;p二pc;while(pa!=NULL&&pb!=NULL){if(pa->expn>pb->expn){s=(List)malloc(sizeof(structLinklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;P=S；pa=pa->next;}elseif(pa->expnexpn){s=(List)malloc(sizeof(st

7、ructLinklist));s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p?>next二s;P=S；pb=pb->next;}else{n=pa->coef+pb->coef;if(n!=O){s=(List)malloc(sizeof(structLinklist));s->expn=pa->expn;s->coef=n;s->next=NULL;p?>next=s;P=S；}pb=pb->next;pa=pa->next;}}while(pa!=NULL){s=(List)malloc(

8、sizeof(structLinklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;P