數(shù)據(jù)結(jié)構(gòu)課件第二章線性表4講

2023/11/22計算機(jī)科學(xué)與技術(shù)教研室1/12第二章線性表線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)(2)及應(yīng)用

1、單鏈表的合并

2、循環(huán)鏈表

3、雙向鏈表

4、單鏈表應(yīng)用舉例

第4講2023/11/22計算機(jī)科學(xué)與技術(shù)教研室2/12算法評價兩個有序鏈表并為一個有序鏈表算法思想：需設(shè)立3個指針pa、pb和pc，其中pa和pb分別指向La表和Lb表中當(dāng)前待比較插入的結(jié)點(diǎn)，而pc指向Lc表中當(dāng)前最后一個結(jié)點(diǎn)，若pa->data≤pb->data，則將pa所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后，否則將pb所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后。T(n)=O(La.length+Lb.length)2023/11/22計算機(jī)科學(xué)與技術(shù)教研室3/12voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈線性表La和Lb元素按值非遞減排列。//歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(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)}//MergeList_L合并2023/11/22計算機(jī)科學(xué)與技術(shù)教研室4/12循環(huán)鏈表(circularlinkedlist)循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next=NULL循環(huán)鏈表p或p->next=Hhh空表2023/11/22計算機(jī)科學(xué)與技術(shù)教研室5/12雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點(diǎn)結(jié)點(diǎn)定義typedefstructDuLNode{ElemTypedata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;priordatanextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;2023/11/22計算機(jī)科學(xué)與技術(shù)教研室6/12bcaPvoiddel_dulist(DuLNode*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}刪除算法描述算法評價：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;2023/11/22計算機(jī)科學(xué)與技術(shù)教研室7/12voidins_dulist(DuLNode*p,intx){DuLNode*s;s=(DuLNode*)malloc(sizeof(DuLNode));s->data=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法評價：T(n)=O(1)xSbaP插入2023/11/22計算機(jī)科學(xué)與技術(shù)教研室8/122.4線性表的應(yīng)用舉例一元多項式的表示及相加一元多項式的表示：可用線性表P表示但對S(x)這樣的多項式浪費(fèi)空間一般其中用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表2023/11/22計算機(jī)科學(xué)與技術(shù)教研室9/12單鏈表的結(jié)點(diǎn)定義typedefstructnode{intcoef,exp;structnode*next;}JD;coefexpnextx=x+7(((x-17x+)x87)=97)xxx+522117))3xBAxCxx+9228(xxB+=1785(A+++=-1A703198517^-1B81227-98^-1C70111227517^一元多項式相加2023/11/22計算機(jī)科學(xué)與技術(shù)教研室10/12設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)比較p->exp與q->expp->exp<q->exp:p結(jié)點(diǎn)是和多項式中的一項p后移,q不動p->exp>q->exp:q結(jié)點(diǎn)是和多項式中的一項將q插在p之前,q后移,p不動p->exp=q->exp:系數(shù)相加0：從A表中刪去p,釋放p,q，p,q后移

0：修改p系數(shù)域,

釋放q，p,q后移直到p或q為NULL若q==NULL，結(jié)束若p==NULL，將B中剩余部分連到A上即可運(yùn)算規(guī)則2023/11/22計算機(jī)科學(xué)與技術(shù)教研室11/12q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^算法描述2023/11/22計算機(jī)科學(xué)與技術(shù)教研室12/12voidadd_poly(LNode*pa,LNode*pb){LNode*p,*q,*u,*pre;intx;p=pa->next;q=pb->next;pre=pa;while((p!=NULL)&&((q!=NULL)){if(p->exp<q->exp){pre=p;p=p->next;}elseif(p->exp==q->exp){x=p->coef+q->coef;if(x!=0){p->coef=x;pre=p;}else{pre->next=p->next;free(p);}p=pre->next;