數(shù)據(jù)結(jié)構(gòu)簡明教程（第3版）課件 第2章 線性表(下)

第2章線性表2.1線性表的基本概念2.2順序表2.3單鏈表和循環(huán)單鏈表2.4雙鏈表和循環(huán)雙鏈表2.5線性表的應(yīng)用第2章線性表1/592.4雙鏈表和循環(huán)雙鏈表2.4.1雙鏈表的定義

雙鏈表中用兩個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系。指向其前驅(qū)結(jié)點(diǎn)的指針域prior。指向其后繼結(jié)點(diǎn)的指針域next。2.4雙鏈表和循環(huán)雙鏈表2/59仍假設(shè)數(shù)據(jù)元素的類型為ElemType。雙鏈表的類型聲明如下：typedefstructnode{ElemTypedata; //數(shù)據(jù)域

structnode*prior,*next; //分別指向前驅(qū)結(jié)點(diǎn)

//和后繼結(jié)點(diǎn)的指針}DLinkNode;

//雙鏈表結(jié)點(diǎn)類型2.4雙鏈表和循環(huán)雙鏈表3/59與單鏈表一樣，雙鏈表也分為非循環(huán)雙鏈表（簡稱為雙鏈表）和循環(huán)雙鏈表兩種。除特別指出外，本章所指的雙鏈表均指帶頭結(jié)點(diǎn)的雙鏈表。2.4雙鏈表和循環(huán)雙鏈表4/592.4.2線性表基本運(yùn)算在雙鏈表上的實(shí)現(xiàn)在帶頭結(jié)點(diǎn)的雙鏈表中，通常頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，尾結(jié)點(diǎn)的next域置為NULL。如下圖所示是一個(gè)帶頭結(jié)點(diǎn)的雙鏈表。La1a2an∧…priornext2.4雙鏈表和循環(huán)雙鏈表5/591.雙鏈表基本運(yùn)算算法（1）初始化線性表運(yùn)算算法創(chuàng)建一個(gè)空的雙鏈表，它只有一個(gè)頭結(jié)點(diǎn)，由L指向它，該結(jié)點(diǎn)的next域和prior域均為空，data域未設(shè)定任何值。voidInitList(DLinkNode*&L){L=(DLinkNode*)malloc(sizeof(DLinkNode));

//創(chuàng)建頭結(jié)點(diǎn)LL->prior=L->next=NULL;}2.4雙鏈表和循環(huán)雙鏈表6/59（2）銷毀線性表運(yùn)算算法銷毀一個(gè)雙鏈表中的所有結(jié)點(diǎn)的算法思路與單鏈表的銷毀算法相同。voidDestroyList(DLinkNode*&L){DLinkNode*pre=L,*p=pre->next;

while(p!=NULL)

{ free(pre); pre=p;p=p->next; //pre、p同步后移}

free(pre);}2.4雙鏈表和循環(huán)雙鏈表7/59（3）求線性表長度運(yùn)算算法其設(shè)計(jì)思路與單鏈表的求表長算法完全相同。intGetLength(DLinkNode*L) {inti=0;

DLinkNode*p=L->next; //p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)

while(p!=NULL)

{ i++; //i累加數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù)

p=p->next;

}

returni;}2.4雙鏈表和循環(huán)雙鏈表8/59（4）求線性表中第i個(gè)元素運(yùn)算算法其設(shè)計(jì)思路與單鏈表的求線性表中第i個(gè)元素運(yùn)算算法完全相同。intGetElem(DLinkNode*L,inti,ElemType&e){intj=0;

DLinkNode*p=L; //p指向頭結(jié)點(diǎn)，計(jì)數(shù)器j置為0

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=NULL&&j<i)

{ j++; p=p->next;

}

if(p==NULL)return0; //未找到返回0

else

{ e=p->data; return1; //找到后返回1

}}2.4雙鏈表和循環(huán)雙鏈表9/59（5）按值查找運(yùn)算算法其設(shè)計(jì)思路與單鏈表的按值查找運(yùn)算算法完全相同。intLocate(DLinkNode*L,ElemTypee) {DLinkNode*p=L->next;

inti=1; //p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，i置為其序號(hào)1

while(p!=NULL&&p->data!=e)

{ p=p->next; i++;

}if(p==NULL)return0; //未找到返回0

elsereturni; //找到后返回其序號(hào)}2.4雙鏈表和循環(huán)雙鏈表10/59（6）插入元素運(yùn)算算法先在雙鏈表中查找到第i-1個(gè)結(jié)點(diǎn)，若成功找到該結(jié)點(diǎn)（由p所指向），創(chuàng)建一個(gè)以x為值的新結(jié)點(diǎn)s，將s結(jié)點(diǎn)插入到p之后即可。2.4雙鏈表和循環(huán)雙鏈表11/59在雙鏈表中p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作步驟如下：將結(jié)點(diǎn)s的next域指向結(jié)點(diǎn)p的下一個(gè)結(jié)點(diǎn)（s->next=p->next）。若p不是最后結(jié)點(diǎn)（若p是最后結(jié)點(diǎn)，只插入s作為尾結(jié)點(diǎn)），則將p之后結(jié)點(diǎn)的prior域指向s（p->next->prior=s）。將s的prior域指向p結(jié)點(diǎn)（s->prior=p）。將p的next域指向s（p->next=s）。ps①②④③2.4雙鏈表和循環(huán)雙鏈表12/59intInsElem(DLinkNode*&L,ElemTypex,inti){intj=0;

DLinkNode*p=L,*s;

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=NULL&&j<i-1) //查找第i-1個(gè)結(jié)點(diǎn)p

{ j++; p=p->next;

}

if(p==NULL)return0; //未找到返回0

else

{ s=(DLinkNode*)malloc(sizeof(DLinkNode)); s->data=x; //創(chuàng)建一個(gè)存放元素x的新結(jié)點(diǎn)

s->next=p->next; //對應(yīng)插入操作的步驟①

if(p->next!=NULL) //對應(yīng)插入操作的步驟②

p->next->prior=s; s->prior=p; //對應(yīng)插入操作的步驟③

p->next=s; //對應(yīng)插入操作的步驟④

return1; //插入運(yùn)算成功,返回1

}}2.4雙鏈表和循環(huán)雙鏈表13/59在雙鏈表中也可以通過一個(gè)結(jié)點(diǎn)找到其前驅(qū)結(jié)點(diǎn)，所以插入操作也可以改為：在雙鏈表中找到第i個(gè)結(jié)點(diǎn)p，然后在p結(jié)點(diǎn)之前插入新結(jié)點(diǎn)。2.4雙鏈表和循環(huán)雙鏈表14/59（7）刪除結(jié)點(diǎn)運(yùn)算算法先在雙鏈表中查找到第i個(gè)結(jié)點(diǎn)，若成功找到該結(jié)點(diǎn)（由p所指向），通過前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針域改變來刪除p結(jié)點(diǎn)。2.4雙鏈表和循環(huán)雙鏈表15/59在雙鏈表中刪除p結(jié)點(diǎn)（其前驅(qū)結(jié)點(diǎn)為pre）的操作：

若p不是尾結(jié)點(diǎn)，則將其后繼結(jié)點(diǎn)的prior域指向pre結(jié)點(diǎn):

p->next->prior=pre將pre結(jié)點(diǎn)的next域改為指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn): pre->next=p->nextprep①②2.4雙鏈表和循環(huán)雙鏈表16/59intDelElem(DLinkNode*&L,inti) //刪除結(jié)點(diǎn){intj=0;

DLinkNode*p=L,*pre;

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=NULL&&j<i) //查找第i個(gè)結(jié)點(diǎn)p

{ j++; p=p->next;

}

if(p==NULL)return0; //未找到第i個(gè)結(jié)點(diǎn)時(shí)返回0

else

{ pre=p->prior; //pre指向被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

if(p->next!=NULL) //從單鏈表中刪除p結(jié)點(diǎn)

p->next->prior=pre; pre->next=p->next; free(p); //釋放其空間

return1;

}}2.4雙鏈表和循環(huán)雙鏈表17/59（8）輸出線性表運(yùn)算算法其設(shè)計(jì)思路與單鏈表的輸出元素值運(yùn)算算法完全相同。voidDispList(DLinkNode*L){DLinkNode*p=L->next;

while(p!=NULL)

{ printf("%d",p->data); p=p->next;

}

printf("\n");}2.4雙鏈表和循環(huán)雙鏈表18/592.整體創(chuàng)建雙鏈表的算法（1）頭插法建表從一個(gè)空雙鏈表（含有一個(gè)L指向的頭結(jié)點(diǎn)）開始。讀取數(shù)組a（含有n個(gè)元素）中的一個(gè)元素，生成一個(gè)新結(jié)點(diǎn)s，將讀取的數(shù)據(jù)元素存放到新結(jié)點(diǎn)的數(shù)據(jù)域中。然后將新結(jié)點(diǎn)s插入到當(dāng)前鏈表的表頭上。再讀取數(shù)組a的下一個(gè)元素，采用相同的操作建立新結(jié)點(diǎn)s并插入到雙鏈表L中，直到數(shù)組a中所有元素讀完為止。2.4雙鏈表和循環(huán)雙鏈表19/59voidCreateListF(DLinkNode*&L,ElemTypea[],intn){DLinkNode*s;inti;

L=(DLinkNode*)malloc(sizeof(DLinkNode));

//創(chuàng)建頭結(jié)點(diǎn)

L->next=NULL;

for(i=0;i<n;i++){s=(DLinkNode*)malloc(sizeof(DLinkNode));//創(chuàng)建新結(jié)點(diǎn)

s->data=a[i];

s->next=L->next; //將s插入到頭結(jié)點(diǎn)之后

s->prior=L;

if(L->next!=NULL) //若s不是作為尾結(jié)點(diǎn)插入

L->next->prior=s;

L->next=s;

}}2.4雙鏈表和循環(huán)雙鏈表20/59（2）尾插法建表從一個(gè)空雙鏈表（含有一個(gè)L指向的頭結(jié)點(diǎn)）開始。讀取數(shù)組a（含有n個(gè)元素）中的一個(gè)元素，生成一個(gè)新結(jié)點(diǎn)s，將讀取的數(shù)據(jù)元素存放到新結(jié)點(diǎn)的數(shù)據(jù)域中。然后將新結(jié)點(diǎn)s插入到當(dāng)前鏈表的表尾上。再讀取數(shù)組a的下一個(gè)元素，采用相同的操作建立新結(jié)點(diǎn)s并插入到雙鏈表L中，直到數(shù)組a中所有元素讀完為止。2.4雙鏈表和循環(huán)雙鏈表21/59voidCreateListR(DLinkNode*&L,ElemTypea[],intn){DLinkNode*s,*tc;inti;

L=(DLinkNode*)malloc(sizeof(DLinkNode));//創(chuàng)建頭結(jié)點(diǎn)

tc=L; //tc始終指向尾結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)

for(i=0;i<n;i++)

{ s=(DLinkNode*)malloc(sizeof(DLinkNode));//創(chuàng)建新結(jié)點(diǎn)

s->data=a[i]; tc->next=s; //將s插入tc之后

s->prior=tc; tc=s;

}

tc->next=NULL; //尾結(jié)點(diǎn)next域置為NULL}2.4雙鏈表和循環(huán)雙鏈表22/59

【例2.22】假設(shè)一個(gè)整數(shù)序列用雙鏈表L存儲(chǔ)，設(shè)計(jì)一個(gè)算法刪除其中最大值的結(jié)點(diǎn)。2.4雙鏈表2.4.3雙鏈表的算法設(shè)計(jì)示例

用p遍歷雙鏈表L，用maxp保存找到的第一個(gè)最大值的結(jié)點(diǎn)（初值為p）。最后通過其前驅(qū)結(jié)點(diǎn)pre和后繼結(jié)點(diǎn)post刪除maxp結(jié)點(diǎn)并釋放其空間。23/59void

Delmax(DLinkNode*&L){DLinkNode*p=L->next,*maxp=p,*pre,*post;

while(p!=NULL) //查找第一個(gè)最大值的結(jié)點(diǎn)maxp

{if(p->data>maxp->data)

maxp=p;

p=p->next;

}

pre=maxp->prior; //指向被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

post=maxp->next; //指向被刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)

pre->next=post; //刪除maxp結(jié)點(diǎn)

if(post!=NULL)post->prior=pre;

free(maxp); //釋放其空間}2.4雙鏈表和循環(huán)雙鏈表24/59

【例2.18】設(shè)有一個(gè)雙鏈表L，設(shè)計(jì)一個(gè)算法查找第一個(gè)元素值為x的結(jié)點(diǎn)，將其與后繼結(jié)點(diǎn)進(jìn)行交換。2.4雙鏈表和循環(huán)雙鏈表

先找到第一個(gè)元素值為x的結(jié)點(diǎn)p，q指向其后繼結(jié)點(diǎn)。先刪除p結(jié)點(diǎn)，將p結(jié)點(diǎn)插入到q結(jié)點(diǎn)之后。25/59intSwap(DLinkNode*L,ElemTypex){DLinkNode*p=L->next,*q;

while(p!=NULL&&p->data!=x)p=p->next;

if(p==NULL) //未找到值為x的結(jié)點(diǎn)return0; //返回0

else

{q=p->next; //q指向p的后繼結(jié)點(diǎn)

if(q!=NULL)

{p->prior->next=q; //先刪除p結(jié)點(diǎn)

q->prior=p->prior;

p->next=q->next; //將p結(jié)點(diǎn)插入到q結(jié)點(diǎn)之后

if(q->next!=NULL) //若q結(jié)點(diǎn)存在后繼結(jié)點(diǎn)

q->next->prior=p;

q->next=p;

p->prior=q;

return1;}

elsereturn0; //表示值為x的結(jié)點(diǎn)是尾結(jié)點(diǎn)

}}2.4雙鏈表和循環(huán)雙鏈表26/592.4.4循環(huán)雙鏈表與循環(huán)單鏈表一樣，也可以使用循環(huán)雙鏈表。循環(huán)雙鏈表的結(jié)點(diǎn)類型與雙鏈表的結(jié)點(diǎn)類型相同，也采用前面聲明的DLinkNode類型。2.4雙鏈表和循環(huán)雙鏈表27/59一個(gè)帶頭結(jié)點(diǎn)的有n個(gè)結(jié)點(diǎn)的循環(huán)雙鏈表。表中尾結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的prior域指向尾結(jié)點(diǎn)，整個(gè)鏈表形成兩個(gè)環(huán)。在循環(huán)雙鏈表中，從任一結(jié)點(diǎn)出發(fā)都可以找到表中其他結(jié)點(diǎn)。特點(diǎn)：La1a2an…2.4雙鏈表和循環(huán)雙鏈表28/59（1）初始化線性表運(yùn)算算法創(chuàng)建一個(gè)空的循環(huán)雙鏈表，它只有一個(gè)頭結(jié)點(diǎn)，由L指向它，該結(jié)點(diǎn)的next域和prior域均指向該頭結(jié)點(diǎn)，data域未設(shè)定任何值。voidInitList(DLinkNode*&L){L=(DLinkNode*)malloc(sizeof(DLinkNode));

L->prior=L->next=L;}循環(huán)雙鏈表基本運(yùn)算算法2.4雙鏈表和循環(huán)雙鏈表29/59（2）銷毀線性表運(yùn)算算法銷毀一個(gè)循環(huán)雙鏈表中的所有結(jié)點(diǎn)的算法思路與循環(huán)單鏈表的銷毀算法相同。voidDestroyList(DLinkNode*&L){DLinkNode*pre=L,*p=pre->next;while(p!=L)

{ free(pre); pre=p;p=p->next; //pre、p同步后移

}

free(pre);}2.4雙鏈表和循環(huán)雙鏈表30/59（3）求線性表長度運(yùn)算算法其設(shè)計(jì)思路與循環(huán)單鏈表的求表長算法完全相同。intGetLength(DLinkNode*L) //求表長運(yùn)算{inti=0;

DLinkNode*p=L->next;

while(p!=L)

{ i++; p=p->next;

}

returni;}2.4雙鏈表和循環(huán)雙鏈表31/59（4）求線性表中第i個(gè)元素運(yùn)算算法其設(shè)計(jì)思路與循環(huán)單鏈表中求線性表中第i個(gè)元素運(yùn)算算法完全相同。intGetElem(DLinkNode*L,inti,ElemType&e){intj=1;

DLinkNode*p=L->next; //p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，j置為1

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=L&&j<i)

{ j++; p=p->next;

}

if(p==L)return0; //未找到返回0

else

{ e=p->data; return1;

//找到后返回1

}}2.4雙鏈表和循環(huán)雙鏈表32/59（5）按值查找運(yùn)算算法其設(shè)計(jì)思路與循環(huán)單鏈表中按值查找運(yùn)算算法完全相同。intLocate(DLinkNode*L,ElemTypex) {inti=1;

DLinkNode*p=L->next;

while(p!=L&&p->data!=x) //從第1個(gè)結(jié)點(diǎn)開始查找data域?yàn)閤的結(jié)點(diǎn)

{ p=p->next; i++;

}

if(p==L)return0;

elsereturni;}2.4雙鏈表和循環(huán)雙鏈表33/59（6）插入元素運(yùn)算算法先在循環(huán)雙鏈表L中查找第i個(gè)結(jié)點(diǎn)p及其前驅(qū)結(jié)點(diǎn)pre，用j記錄p結(jié)點(diǎn)的序號(hào)。當(dāng)p==L且i>j+1時(shí)表示i參數(shù)錯(cuò)誤（如循環(huán)雙鏈表中只有3個(gè)結(jié)點(diǎn)，當(dāng)i>4時(shí)出現(xiàn)這種錯(cuò)誤）。當(dāng)成功找到pre結(jié)點(diǎn)后，創(chuàng)建data域?yàn)閤的結(jié)點(diǎn)s。在pre結(jié)點(diǎn)之后插入s結(jié)點(diǎn)。2.4雙鏈表和循環(huán)雙鏈表34/59intInsElem(DLinkNode*&L,ElemTypex,inti) {intj=0;

DLinkNode*pre=L,*p=pre->next,*s;

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=L&&j<i-1) //查找第i個(gè)結(jié)點(diǎn)p和其前驅(qū)結(jié)點(diǎn)pre

{ j++; pre=p;p=p->next; //pre、p同步后移一個(gè)結(jié)點(diǎn)

}

if(p==L&&i>j+1)return0;//參數(shù)i>n+1時(shí)錯(cuò)誤返回0

else

//成功查找到p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)pre

{ s=(DLinkNode*)malloc(sizeof(DLinkNode)); s->data=x; //創(chuàng)建新結(jié)點(diǎn)s用于存放元素x pre->next->prior=s; //將s結(jié)點(diǎn)插入到pre結(jié)點(diǎn)之后

s->next=pre->next; pre->next=s; s->prior=pre; return1; //插入運(yùn)算成功,返回1

}}2.4雙鏈表和循環(huán)雙鏈表35/59（7）刪除元素運(yùn)算算法

先在循環(huán)雙鏈表L中查找第i個(gè)結(jié)點(diǎn)p，若成功找到后通過其前驅(qū)結(jié)點(diǎn)pre將p結(jié)點(diǎn)刪除。2.4雙鏈表和循環(huán)雙鏈表36/59intDelElem(DLinkNode*&L,inti)//刪除結(jié)點(diǎn)算法{intj=1;

DLinkNode*p=L->next,*pre;

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

if(L->next==L)return0; //空循環(huán)雙鏈表不能刪除，返回0

while(p!=L&&j<i) //查找第i個(gè)結(jié)點(diǎn)p

{ j++; p=p->next;

}

if(p==L)return0; //未找到第i個(gè)結(jié)點(diǎn)返回0

else

{ pre=p->prior; //pre指向被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

p->next->prior=pre; pre->next=p->next; free(p); //釋放其空間

return1;

}}2.4雙鏈表和循環(huán)雙鏈表37/59（8）輸出線性表運(yùn)算算法其設(shè)計(jì)思路與循環(huán)單鏈表的輸出元素值運(yùn)算算法完全相同。voidDispList(DLinkNode*L){DLinkNode*p=L->next;

while(p!=L)

{ printf("%d",p->data); p=p->next;

}

printf("\n");}2.4雙鏈表和循環(huán)雙鏈表38/59

【例2.24】設(shè)計(jì)一個(gè)算法將帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L的所有結(jié)點(diǎn)逆置。2.4.5循環(huán)雙鏈表的算法設(shè)計(jì)示例2.4雙鏈表和循環(huán)雙鏈表

先建立一個(gè)空的循環(huán)雙鏈表L，用p遍歷余下的數(shù)據(jù)結(jié)點(diǎn)，依次將p結(jié)點(diǎn)采用頭插法插入到L中。39/59voidReverse(DLinkNode*&L){DLinkNode*p=L->next,*q;

L->next=L->prior=L; //構(gòu)造一個(gè)空的循環(huán)雙鏈表

while(p!=L)

{ q=p->next; p->next=L->next; //將p結(jié)點(diǎn)插入到表頭

L->next->prior=p; L->next=p; p->prior=L; p=q;

}}2.4雙鏈表和循環(huán)雙鏈表40/59

【例2.25】有一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L，其結(jié)點(diǎn)data域值為整數(shù)，設(shè)計(jì)一個(gè)算法，判斷其所有元素是否對稱。

如果從前向后讀和從后向前讀得到的數(shù)據(jù)序列相同，表示是對稱的；否則不是對稱的。

2.4雙鏈表和循環(huán)雙鏈表41/59

先讓p指向第一個(gè)結(jié)點(diǎn)，q指向尾結(jié)點(diǎn)，當(dāng)兩者所指結(jié)點(diǎn)值不等時(shí)返回0，否則p后移一個(gè)結(jié)點(diǎn)，q前移一個(gè)結(jié)點(diǎn)，依次比較下去，直到p->next==q或p==q。循環(huán)結(jié)束后返回1。abbapq對稱情況1：結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)abapq對稱情況2：結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)2.4雙鏈表和循環(huán)雙鏈表42/59intSymmetric(DLinkNode*L){intflag=1;DLinkNode*p=L->next,*q=L->prior;while(flag==1) //flag為1時(shí)循環(huán){if(p->data!=q->data) //對應(yīng)結(jié)點(diǎn)值不同時(shí)退出循環(huán)flag=0;else{if(p==q||p->next==q)break; //是對稱的情況p=p->next; //從前向后移動(dòng)q=q->prior; //從后向前移動(dòng)}}returnflag;}2.4雙鏈表和循環(huán)雙鏈表43/592.5線性表的應(yīng)用2.5.1設(shè)計(jì)線性表應(yīng)用程序的一般步驟當(dāng)通過分析確定了求解問題中數(shù)據(jù)邏輯結(jié)構(gòu)為線性關(guān)系時(shí)，設(shè)計(jì)線性表應(yīng)用程序的一般步驟如下：

（1）根據(jù)求解功能的特點(diǎn)設(shè)計(jì)相應(yīng)的存儲(chǔ)結(jié)構(gòu)。（2）設(shè)計(jì)相應(yīng)的基本運(yùn)算算法。（3）設(shè)計(jì)求解問題的主程序。2.5線性表的應(yīng)用44/59兩類存儲(chǔ)結(jié)構(gòu)特點(diǎn)的比較特點(diǎn)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)（1）無須為表示線性表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間，存儲(chǔ)密度大。（2）具有隨機(jī)存儲(chǔ)特性。（1）由于采用結(jié)點(diǎn)的動(dòng)態(tài)分配方式，具有良好的適應(yīng)性。（2）插入和刪除操作只需修改相關(guān)指針域，不需要移動(dòng)大量元素。缺點(diǎn)（1）插入和刪除操作需要移動(dòng)大量元素。（2）如果采用靜態(tài)數(shù)組存儲(chǔ)線性表元素，其空間大小分配難以掌握，大大了會(huì)浪費(fèi)空間，分小了易發(fā)生上溢出；如果采用動(dòng)態(tài)數(shù)組存儲(chǔ)線性表元素，其算法設(shè)計(jì)比較復(fù)雜。（1）為表示線性表中元素之間的邏輯關(guān)系而需要增加額外的存儲(chǔ)空間（指針域），存儲(chǔ)密度小。（2）不具有隨機(jī)存儲(chǔ)特性。2.5線性表的應(yīng)用45/592.5.2線性表應(yīng)用示例假設(shè)一個(gè)多項(xiàng)式形式為，其中ei（1≤i≤m）為整數(shù)類型的指數(shù)，ci（1≤i≤m）為實(shí)數(shù)類型的系數(shù)。為了簡便，假設(shè)每個(gè)多項(xiàng)式按指數(shù)遞減排列，并且沒有相同指數(shù)的多項(xiàng)式項(xiàng)。編寫求兩個(gè)多項(xiàng)式相加的程序。例如：兩個(gè)多項(xiàng)式分別為：

p(x)=3.2x5+2x3-6x+10，q(x)=1.8x5-2.5x4-2x3+x2+6x-5，則相加后的結(jié)果為：

r(x)=p(x)+q(x)=5x5-2.5x4+x2+5。1.問題描述2.5線性表的應(yīng)用46/59一個(gè)多項(xiàng)式由多個(gè)（1≤i≤m）多項(xiàng)式項(xiàng)組成，這些多項(xiàng)式項(xiàng)之間構(gòu)成一種線性關(guān)系，所以一個(gè)多項(xiàng)式可以看成是由多個(gè)多項(xiàng)式項(xiàng)元素構(gòu)成的線性表。線性表可以采用順序表和各種鏈表存儲(chǔ)，由于本例中每個(gè)多項(xiàng)式的項(xiàng)數(shù)難以確定，所以采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。每個(gè)多項(xiàng)式項(xiàng)采用以下結(jié)點(diǎn)類型進(jìn)行存儲(chǔ)：coefexpnext2.設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)2.5線性表的應(yīng)用47/59

coef數(shù)據(jù)域存放系數(shù)ci；expn數(shù)據(jù)域存放指數(shù)ei；next域是一個(gè)鏈域，指向下一個(gè)結(jié)點(diǎn)。這樣的單鏈表結(jié)點(diǎn)的類型聲明如下：typedefstructnode{floatcoef;

//系數(shù)

intexp;

//指數(shù)

structnode*next;

//指向下一個(gè)結(jié)點(diǎn)的指針}PolyNode;2.5線性表的應(yīng)用48/59例如，前面的兩個(gè)多項(xiàng)式p(x)、q(x)的存儲(chǔ)結(jié)構(gòu)如下圖所示。

p(x)=3.2x5+2x3-6x+103.252.03-6.0110.00∧p1.85-2.54-2.031.02-5.00∧6.01q(x)=1.8x5-2.5x4-2x3+x2+6x-5q2.5線性表的應(yīng)用49/593.設(shè)計(jì)基本運(yùn)算算法（1）建立多項(xiàng)式單鏈表由數(shù)組a指定系數(shù)，數(shù)組b指定指數(shù)，共有n個(gè)多項(xiàng)式項(xiàng)(a[0],b[0])，(a[1],b[1])，…，(a[n-1],b[n-1])構(gòu)成一個(gè)多項(xiàng)式，其中指數(shù)按遞減排列。2.5線性表的應(yīng)用50/59voidCreateListR(PolyNode*&L,doublea[],intb[],intn){PolyNode*s,*tc;

inti;

L=(PolyNode*)malloc(sizeof(PolyNode));

tc=L; //tc始終指向終端結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)

for(i=0;i<n;i++)

{ s=(PolyNode*)malloc(sizeof(PolyNode)); s->coef=a[i]; s->exp=b[i]; tc->next=s; //將s插入tc之后

tc=s;

}

tc->next=NULL; //尾結(jié)點(diǎn)next域置為NULL}2.5線性表的應(yīng)用51/59（2）銷毀多項(xiàng)式單鏈表voidDestroyList(PolyNode*&L){PolyNode*pre=L,*p=pre->next;

while(p!=NULL)

{ free(pre); pre=p;p=p->next;

}

free(pre);}2.5線性表的應(yīng)用52/59（3）輸出多項(xiàng)式單鏈表voidDispPoly(PolyNode*L){PolyNode*p=L->next;

while(p!=NULL)

{ printf("(%gx^%d)",p->coef,p->exp); p=p->next;

}

printf("\n");}2.5線性表的應(yīng)用53/59（4）兩個(gè)有序多項(xiàng)式單鏈表相加運(yùn)算對于ha和hb兩個(gè)有序多項(xiàng)式單鏈表，采用二路歸并實(shí)現(xiàn)多項(xiàng)式相加運(yùn)算（產(chǎn)生有序單鏈表hc）的過程如下：2.5線性表的應(yīng)用54/59pa指向ha的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，pb指向hb的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)；創(chuàng)建hc的頭結(jié)點(diǎn)，尾結(jié)點(diǎn)指針tc指向該頭結(jié)點(diǎn)；while(pa、pb均不為空){if(pa->exp>pb->exp)由pa結(jié)點(diǎn)復(fù)制建立一個(gè)新結(jié)點(diǎn)s，將結(jié)點(diǎn)s鏈到hc末尾，pa后移一個(gè)結(jié)點(diǎn)；elseif(pa->exp<pb->exp)

由pb結(jié)點(diǎn)復(fù)制建立一個(gè)新結(jié)點(diǎn)s，將結(jié)點(diǎn)s鏈到hc末尾，pb后移一個(gè)結(jié)點(diǎn)；

else //兩結(jié)點(diǎn)的指數(shù)相同求兩結(jié)點(diǎn)的系數(shù)和c，若不為0，新建一個(gè)結(jié)點(diǎn)s，其coef域?yàn)閏，

將結(jié)點(diǎn)s鏈到hc末尾，pa、pb均后移一個(gè)結(jié)點(diǎn)。}此時(shí)pa、pb中至少有一個(gè)為空，將另一個(gè)未掃描完的結(jié)點(diǎn)逐一復(fù)制并鏈接到hc末尾；置hc尾結(jié)點(diǎn)next域?yàn)榭铡?.5線性表的應(yīng)用55/59voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc){PolyNode*pa=ha->next,*pb=hb->next,*s,*tc;

doublec;

hc=(PolyNode*)malloc(sizeof(PolyNode));

tc=hc;

while(pa!=NULL&&pb!=NULL)

{if(pa->exp>pb->exp)

{s=(PolyNode*)malloc(sizeof(PolyNode));

s->exp=pa->exp;s->coef=pa->coef;

tc->next=s;tc=s;

p