數(shù)結(jié)-2靜態(tài)鏈和多項(xiàng)式

§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1單鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.3.4靜態(tài)鏈表2.3.4靜態(tài)鏈表用數(shù)組模擬鏈表：#defineMAXSIZE1000typedef

struct{

ElemTypedata;

intcur;//游標(biāo)cursor}SLinkList[MAXSIZE];//存儲(chǔ)池類型SLinkListspace;//定義一個(gè)存儲(chǔ)池space線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)·靜態(tài)鏈表datacur

數(shù)組元素spacedatacurspace

datacur0102121a3102324343a16454856L=5

→53676a21787a508989910911101110a471112111212131213MAXSIZE-10MAXSIZE-10初始化：拉備用鏈

動(dòng)態(tài)鏈靜態(tài)鏈內(nèi)存資源存儲(chǔ)池?cái)?shù)組space中的備用結(jié)點(diǎn)鏈指針p（指針類型）游標(biāo)q（整型）

p->dataspace[q].data

p->nextspace[q].cur內(nèi)部函數(shù)malloc向系統(tǒng)申請(qǐng)結(jié)點(diǎn)自編模擬函數(shù)malloc_sl從備用鏈摘取一個(gè)結(jié)點(diǎn)內(nèi)部函數(shù)free向系統(tǒng)釋放結(jié)點(diǎn)自編模擬函數(shù)free_sl將一個(gè)不用的結(jié)點(diǎn)插入備用鏈space數(shù)組中有兩條鏈：線性表鏈和備用鏈a1a2a3a4a5∧

備用結(jié)點(diǎn)鏈：L線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)·靜態(tài)鏈表線性表鏈：頭結(jié)點(diǎn)的下標(biāo)為0備用鏈的功能：起存儲(chǔ)池的作用當(dāng)線性表需要申請(qǐng)結(jié)點(diǎn)時(shí)，從備用鏈上摘?。划?dāng)線性表釋放結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)添加到備用鏈中。

為了模擬鏈表操作，必須模擬出malloc和free函數(shù)的功能：malloc_sl----從備用鏈上摘下一個(gè)結(jié)點(diǎn)刪除備用鏈中的第一個(gè)結(jié)點(diǎn)free_sl----將不再使用的空閑結(jié)點(diǎn)還給備用鏈用頭插法插入備用鏈插入點(diǎn)和刪除點(diǎn)都在這里線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)·靜態(tài)鏈表備用結(jié)點(diǎn)鏈：教材P33，算法2.15int

malloc_sl(SLinkListspace){//向備用鏈申請(qǐng)結(jié)點(diǎn)----刪除備用鏈中的第一個(gè)結(jié)點(diǎn)//若備用鏈非空返回第一個(gè)結(jié)點(diǎn)的下標(biāo)，否則返回0i=space[0].cur;//獲得備用鏈第一個(gè)結(jié)點(diǎn)的下標(biāo)if(i)space[0].cur=space[i].cur;//修改頭結(jié)點(diǎn)的后繼指針returni;//返回結(jié)點(diǎn)下標(biāo)}

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)·靜態(tài)鏈表教材P33，算法2.15voidfree_sl(SLinkListspace,intk){//將下標(biāo)為k的空閑結(jié)點(diǎn)用頭插法插入備用鏈

space[k].cur=space[0].cur;//修改空閑結(jié)點(diǎn)的后繼space[0].cur=k;//頭結(jié)點(diǎn)的后繼指向空閑結(jié)點(diǎn)}線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)·靜態(tài)鏈表space

datacurspacedatacur0201a3101a324243a163a164848L=5→53L=5→536a216a217a507a50898991191110a4710a41112111212131213MAXSIZE-10MAXSIZE-10例，刪除a4結(jié)點(diǎn)：107p72210例：刪除靜態(tài)鏈表L中第i個(gè)元素statusListDelete_sl(SLinkListspace,intL,inti){//L是頭結(jié)點(diǎn)的游標(biāo)

intp=L,j=1,q;while(space[p].cur&&j<i-1){p=space[p].cur;j++;}//找ai-1if(p==0||j>i-1)returnERROR；//i非法

q=space[p].cur;space[p].cur=space[q].cur;//修改游標(biāo)

free_sl(space,q);returnOK;}

//endListDelete_slspace

datacurspacedatacur0201a3101a32423a163a164848L=5

→53L=5

→536a216a217a507a50898991191110a4710a471112111212131213MAXSIZE-10MAXSIZE-10例，在a4之前插入新結(jié)點(diǎn)：244e10102p在靜態(tài)鏈表L的第i個(gè)元素前插入新結(jié)點(diǎn)estatusListInsert_sl(SLinkListspace,intL,inti,

ElemTypee){

//L是頭結(jié)點(diǎn)的游標(biāo)

intp=L,j=1,s;while(space[p].cur&&j<i-1){p=space[p].cur;j++;}//找ai-1if(p==0||j>i-1)returnERROR；//i非法

s＝malloc_sl(space)if(!s)returnOVERFLOW;space[s].data=e;space[s].cur=space[p].cur;space[p].cur=s;//修改游標(biāo)

returnOK;}

//endListInsert_sl教材P33－34，算法2.17A=(A-B)U(B-A)1、從鍵盤輸入A表的m個(gè)元素，用尾插法建單鏈表，尾指針是r；2、從鍵盤中輸入B表的n個(gè)元素，對(duì)每個(gè)bi檢測(cè)它在A表中是否存在;若存在，刪除A表中等于bi的元素；不存在，將bi插在r指針的后面；第二章線性表§2.1線性表的定義§2.2線性表的順序表示和實(shí)現(xiàn)----順序表§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)§2.4線性表的應(yīng)用舉例----多項(xiàng)式的表示與實(shí)現(xiàn)§2.4一元多項(xiàng)式的表示與運(yùn)算一元多項(xiàng)式：

Pn(x)=p0+p1x+p2x2+...+pn-1xn-1+pnxn可用系數(shù)組成的線性表表示：

P(p0,p1,p2,...,pn-1,pn)這里指數(shù)隱含在元素在線性表中的位序里。稠密多項(xiàng)式：0系數(shù)很少稀疏多項(xiàng)式：0系數(shù)非常多

多項(xiàng)式的基本運(yùn)算：創(chuàng)建多項(xiàng)式CreatePolyn(&P);銷毀多項(xiàng)式DestroyPolyn(&P)打印多項(xiàng)式PrintPolyn(P)求項(xiàng)數(shù)LengthPolyn(P)多項(xiàng)式求和AddPolyn(&Pa,&Pb)多項(xiàng)式求差SubstractPolyn(&Pa,&Pb)多項(xiàng)式求積MultiplyPolyn(&Pa,&Pb)多項(xiàng)式求值CalculatePolyn(P,v)求導(dǎo)函數(shù)differential(&P)求不定積分Quadrature(&P)稠密多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)：順序表：p0p1p2...pi...pn012in這樣表示的多項(xiàng)式除了P=P×Q或R=P×Q運(yùn)算外，其余的運(yùn)算都是很容易實(shí)現(xiàn)的。兩個(gè)稠密多項(xiàng)式求和:P=Pn+QmPp0p1p2...pn-1pn012n-1nQq0q1q2...qm-1qm012n-1nP+Qp0+q0p1+q1p2+q2...pm+qmpm+1pm+2...pn(n>m)012m-1m+1m+2nP+Qp0+q0p1+q1p2+q2...pn+qnqn+1qn+2...qm(n<m)012n-1n+1n+2m稠密多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：這樣表示的多項(xiàng)式R=P×Q也是容易實(shí)現(xiàn)的P=Pn+Qm,m>nP=Pn+Qm,m<nqm∧p0+q0p1+q1pn+qn

......Ppn∧p0+q0p1+q1pm+qm

......Pp0p1p2pn∧

P...稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)：

P105(x)=-2+x7+x23-x88+x105一般表示為：

Pn(x)=p1xe1+p2xe2+...+pmxem用線性表表示時(shí),每個(gè)元素都是二元組(系數(shù),指數(shù)):

Pn

=((p1,e1),(p2,e2),...,(pm,em))

按ei的升序排列。P85(x)=-2+6x7+3x23–x68+7x85coefexp0-2016723233-168478556順序結(jié)構(gòu)：coefexpnext系數(shù)指數(shù)后繼鏈?zhǔn)浇Y(jié)構(gòu)：67-20785∧-168323P多項(xiàng)式異地求和

P85(x)=-2+6x7+3x23-x68+7x85

Q97(x)=4x3-8x23-7x85-9x91+7x97PcoefexpQcoefexpRcoefexp000111222333444555666ijk

-20

43

67

-523

-168

-991

797此算法類似兩個(gè)有序表的歸并。若是就地求和，有插入和刪除操作

-20

323

-168

785

67

43

-785

-991

797

-823多項(xiàng)式就地求和

P85(x)=-2+6x7+3x23+x68+5x85

P=P+Q

Q97(x)=4x3-8x23-x68-9x91+7x97方法一：將Q表中的結(jié)點(diǎn)插入P表的適當(dāng)位置P67-20785∧168323-82343597∧-991-168Qprepq指針p、q指示當(dāng)前結(jié)點(diǎn)。P表中pre是p的直接前驅(qū)。當(dāng)p和q都非空時(shí),分別對(duì)下列三種情況做不同的處理：p->exp<q->exp:pre和p右移一次；p->exp>q->exp:將q所指的結(jié)點(diǎn)插在p之前,q右移一次p->exp==q->exp:x=p->coef+q->coef

如果x=0,刪p,刪q;p和q分別右移一次如果x≠0,ｐ->coef=x,刪q。pre、p、q右移-82343597∧-991-168Q67-20785∧168323P-20Pprepqp->exp<q->exp:pre和p右移p->exp>q->exp:將q所指的結(jié)點(diǎn)插在p之前,q右移597∧-991-16843-823Q-2067785∧-1683234367785∧168323Pp->exp<q->exp:pre和p右移-20Pprepq597∧-991-16843-823Q-2067785∧-1683234367785∧168323Pp->exp==q->exp:x=p->coef+q->coef≠0,p->coef=x,

刪qpre、p、q右移-20Pprepq597∧-991-16843-823Q-2067785∧168323P-5-20Pprepq597∧-99143168Q-2067785∧-523-168Pp->exp==q->exp:p->coef+q->coef==0,

刪p,刪q;p和q右移-20Pprepq597∧-99143