數據結構第二章線性表課件

一、單鏈表二、結點和單鏈表的C語言描述三、線性表的操作在單鏈表中的實現四、一個帶頭結點的單鏈表類型五、其它形式的鏈表六、有序表類型2.3線性表的鏈式表示和實現一、單鏈表二、結點和單鏈表的C語言描述三、線性表的操作在1一、單鏈表用一組任意的存儲單元存儲線性表中的數據元素（這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。為了表示每個元素ai與其直接后繼元素ai+1之間的邏輯關系，對元素ai來說，除了存儲元素本身的信息之外，還需存儲一個指針信息，它指示直接后繼元素的存儲位置。這兩部分信息組成數據元素ai的存儲映象，稱為結點。datanext結點

數據域指針域一、單鏈表用一組任意的存儲單元存儲線性表中的2以元素(數據元素的映象)

+指針(指示后繼元素存儲位置)=結點

(表示數據元素或數據元素的映象)以“結點的序列”表示線性表（每個結點中只包含一個指針域）

稱作單鏈表以元素(數據元素的映象)以“結點的序列”表3線性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的線性鏈表存儲結構：

存儲地址數據域指針域1LI43

7QIAN1313SUN119WANGNull25WU3731ZHAO737ZHENG1943ZHOU25頭指針H31線性表頭指針H314線性鏈表的邏輯狀態(tài)ZHAOQIANSUNLIZHOUWUZHENGWANG∧H

用線性鏈表表示線性表時，數據元素之間的邏輯關系是由結點中的指針來指示的，邏輯上相鄰的兩元素其物理位置不要求緊鄰。通常把鏈表畫成用箭頭相連接的結點的序列，結點之間的箭頭表示鏈域中的指針。由此可見，單鏈表可由頭指針唯一確定。線性鏈表的邏輯狀態(tài)ZHAOQIANSUNLIZHOUWUZH5以線性表中第一個數據元素a1的存儲地址作為線性表的地址，稱作線性表的頭指針。當線性表為空時，頭指針為空。頭結點

a1a2…...an^頭指針頭指針

有時為了操作方便，在第一個結點之前虛加一個“頭結點”，頭結點的指針域指向第一個結點的存儲位置；以指向頭結點的指針為鏈表的頭指針?？罩羔樉€性表為空表時，頭結點的指針域為空以線性表中第一個數據元素a1的存儲地址作為線性表的6

TypedefstructLNode{ElemTypedata;//數據域

structLnode*next;//指針域}LNode,*LinkList;

二、結點和單鏈表的C語言描述LinkListL；

//

L為單鏈表的頭指針

ai=p

->data;ai+1=p

->next->dataaiai+1ai+2PTypedefstructLNode{二、結7三、單鏈表操作的實現GetElem(L,i,&e)

//取第i個數據元素ListInsert(&L,i,e)

//插入數據元素ListDelete(&L,i,e)

//刪除數據元素ClearList(&L)//重置線性表為空表CreateList(&L,n)//生成含n個數據元素的鏈表三、單鏈表操作的實現GetElem(L,i,&e)8L線性表的操作

GetElem(L,i,&e)在單鏈表中的實現:211830754256∧pppj123

在單鏈表中，任何兩個元素的存儲位置之間沒有固定的聯系，然而每個元素的存儲位置都包含在其直接前趨結點的信息中。在單鏈表中，取得第i個數據元素必須從頭指針出發(fā)尋找。L線性表的操作GetElem(L,i,&e)211839

因此，查找第i個數據元素的基本操作為：移動指針，比較j和i。

單鏈表是一種順序存取的結構，為找第i個數據元素，必須先找到第i-1個數據元素。

令指針

p

始終指向線性表中第

j

個數據元素。因此，查找第i個數據元素的基本操作為：移動10

StatusGetElem_L(LinkListL,inti,ElemType&e){

//L是帶頭結點的鏈表的頭指針，以e返回第i個元素}//GetElem_L算法時間復雜度為:O(ListLength(L))p=L->next;j=1;//

p指向第一個結點，j為計數器while(p&&j<i){p=p->next;++j;}

//

順指針向后查找，直到p指向第i個元素或p為空if(!p||j>i)

returnERROR;

//第i個元素不存在e=p->data;//取得第i個元素returnOK;StatusGetElem_L(LinkListL,11ai-1

線性表的操作

ListInsert(&L,i,e)

在單鏈表中的實現：

有序對<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1ai-1線性表的操作ListInsert(&L,i,12因此，在單鏈表中第i個結點之前進行插入的基本操作為:

找到線性表中第i-1個結點，然后修改其指向后繼的指針。

可見，在鏈表中插入結點只需要修改指針。但同時，若要在第i個結點之前插入元素，修改的是第i-1個結點的指針。因此，在單鏈表中第i個結點之前進行插入的13StatusListInsert_L(LinkListL,inti,ElemTypee){

//L為帶頭結點的單鏈表的頭指針，本算法//在鏈表中第i個結點之前插入新的元素e

}

//LinstInsert_L算法的時間復雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

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

//尋找第i-1個結點if(!p||j>i-1)

returnERROR;//i大于表長或者小于1

StatusListInsert_L(LinkList14s=(LinkList)malloc(sizeof(LNode));

//生成新結點s->data=e;s->next=p->next;p->next=s;

//插入returnOK;eai-1aiai-1sps=(LinkList)malloc(sizeof15C語言中的兩個標準函數：malloc和free

假設p和q是linklist型的變量，則執(zhí)行p=(linklist)malloc(sizeof(node))的作用是：由系統(tǒng)生成一個node型的結點，同時將該結點的起始位置賦給指針變量p;執(zhí)行free(q)的作用是由系統(tǒng)回收一個node型的結點，回收后的結點可以備作再次生成結點時用。因此，單鏈表是一種動態(tài)結構，整個可用存儲空間可為多個鏈表共同享用，每個鏈表占用的空間不需預先分配劃定，而是可以由系統(tǒng)應需求即時生成。建立線性表的鏈式存儲結構的過程就是一個動態(tài)生成鏈表的過程。即從空表的初始狀態(tài)起，依次建立各元素結點，并逐個插入鏈表。C語言中的兩個標準函數：malloc和free16線性表的操作ListDelete(&L,i,&e)在鏈表中的實現:有序對<ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1線性表的操作ListDelete(&L,i,&e)有17

在單鏈表中刪除第

i個結點的基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq在單鏈表中刪除第i個結點的基本操作為:找到線性表中18StatusListDelete_L(LinkListL,inti,ElemType&e){

//刪除以L為頭指針(帶頭結點)的單鏈表中第i個結點}//ListDelete_L算法的時間復雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個結點，并令p指向其前趨if(!(p->next)||j>i-1)

returnERROR;

//刪除位置不合理q=p->next;p->next=q->next;

//刪除并釋放結點e=q->data;free(q);returnOK;StatusListDelete_L(LinkList19操作

ClearList(&L)

在鏈表中的實現:voidClearList(&L){

//將單鏈表重新置為一個空表

while(L->next){

p=L->next;L->next=Null;

}}//ClearListfree(p);算法時間復雜度：O(ListLength(L))頭結點

a1a2…...an^Lp操作ClearList(&L)在鏈表中的實現:void20如何從線性表得到單鏈表？鏈表是一個動態(tài)的結構，它不需要予分配空間，因此生成鏈表的過程是一個結點“逐個插入”的過程。如何從線性表得到單鏈表？鏈表是一個動態(tài)的結構，它不需21例如：逆位序輸入n個數據元素的值，建立帶頭結點的單鏈表。操作步驟：一、建立一個“空表”；二、輸入數據元素an，建立結點并插入；三、輸入數據元素an-1，建立結點并插入；ananan-1四、依次類推，直至輸入a1為止。例如：逆位序輸入n個數據元素的值，建立操作步驟：一、建立22voidCreateList_L(LinkList&L,intn){

//逆序輸入n個數據元素，建立帶頭結點的單鏈表}//CreateList_L算法的時間復雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

//先建立一個帶頭結點的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;

//插入}voidCreateList_L(LinkList&L,23回顧2.1節(jié)中三個例子的算法，看一下當線性表分別以鏈表存儲結構表示時，它們的實現算法的時間復雜度為多少？回顧2.1節(jié)中三個例子的算法，看一下當線性表分別24voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);if(!LocateElem(La,e,equal())

ListInsert(La,++La_len,e);

}//for}//union控制結構：基本操作：for循環(huán)GetElem,LocateElem和ListInsert當以順序映像實現抽象數據類型線性表時為:

O(ListLength(La)×ListLength(Lb))

當以鏈式映像實現抽象數據類型線性表時為:

O(ListLength(La)×ListLength(Lb))例2-1算法時間復雜度voidunion(List&La,ListLb)25voidpurge(List&La,ListLb){

InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);

if(ListEmpty(La)||

!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

}//for}//purge控制結構：基本操作：for循環(huán)GetElem和ListInsert當以順序映像實現抽象數據類型線性表時為:

O(ListLength(Lb))當以鏈式映像實現抽象數據類型線性表時為:

O(ListLength2(Lb))例2-2算法時間復雜度voidpurge(List&La,ListLb)26voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){

GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){

ListInsert(Lc,++k,ai);++i;}

else{

ListInsert(Lc,++k,bj);++j;}

}……控制結構：基本操作：三個并列的while循環(huán)GetElem,ListInsert當以順序映像實現抽象數據類型線性表時為:

O(ListLength(La)+ListLength(Lb))當以鏈式映像實現抽象數據類型線性表時為:

O(ListLength2(La)+ListLength2(Lb))例2-3算法時間復雜度voidMergeList(ListLa,ListL27用上述定義的單鏈表實現線性表的操作時，存在的問題：改進鏈表的設置：1．單鏈表的表長是一個隱含的值；

1．增加“表長”、“表尾指針”和“當前位置的指針”三個數據域；2．在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；3．在鏈表中，元素的“位序”概念淡化，結點的“位置”概念加強。2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。用上述定義的單鏈表實現線性表的操作時，存在的問題：改進鏈表的28四、改進的線性鏈表類型typedefstructLNode{//結點類型ElemTypedata;

structLNode*next;}*Link,*Position;typedefstruct

{//鏈表類型

Linkhead,tail;

//分別指向頭結點和最后

一個結點的指針

intlen;

//指示鏈表長度

Linkcurrent;

//指向當前被訪問的結點的//指針，初始位置指向頭結點}LinkList;

四、改進的線性鏈表類型typedefstructLNod29頭結點

a1…ai...an^headcurrenttailStatusMakeNode(Link&p,ElemTypee);

//分配由p指向的值為e的結點，并返回OK，//若分配失敗，則返回ERRORvoidFreeNode(Link&p);

//釋放p所指結點頭結點a1…ai...30鏈表的基本操作:{結構初始化和銷毀結構}StatusInitList(LinkList&L);

//構造一個空的線性鏈表L，其頭指針、

//尾指針和當前指針均指向頭結點，表長

//為零。StatusDestroyList(LinkList&L);//銷毀線性鏈表L，L不再存在。O(1)O(n)鏈表的基本操作:{結構初始化和銷毀結構}StatusIni31{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表長StatusPrior(LinkListL);

//改變當前指針指向其前驅StatusNext(LinkListL);

//改變當前指針指向其后繼ElemTypeGetCurElem(LinkListL);

//返回當前指針所指數據元素O(1)O(1)O(n)O(1)O(1){引用型操作}StatusListEmpty(Link32

StatusLocatePos(LinkListL,inti);

//改變當前指針指向第i個結點StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));

//若存在與e滿足函數compare()判定關系的

//元素，則移動當前指針指向第1個滿足條件的

//元素的前驅，并返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());

//依次對L的每個元素調用函數visit()O(n)O(n)O(n)StatusLocatePos(LinkListL33{加工型操作}StatusClearList(LinkList&L);

//重置L為空表StatusSetCurElem(LinkList&L,ElemTypee);

//更新當前指針所指數據元素StatusAppend(LinkList&L,Links);

//在表尾結點之后鏈接一串結點StatusInsAfter(LinkList&L,Elemtypee);

//將元素e插入在當前指針之后StatusDelAfter(LinkList&L,ElemType&e);

//刪除當前指針之后的結點O(1)O(n)O(s)O(1)O(1){加工型操作}StatusClearList(Link34StatusInsAfter(LinkList&L,ElemTypee){

//若當前指針在鏈表中，則將數據元素e插入在線性

//鏈表L中當前指針所指結點之后,并返回OK;

//否則返回ERROR。

}//InsAfter

if(!L.current)returnERROR;if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;

if(L.tail=L.current)L.tail=s;L.current=s;returnOK;StatusInsAfter(LinkList&L,35StatusDelAfter(LinkList&L,ElemType&e){

//若當前指針及其后繼在鏈表中，則刪除線性鏈表L中當前

//指針所指結點之后的結點，并返回OK;否則返回ERROR。}//DelAfterif(!(L.current&&L.current->next))returnERROR;q=L.current->next;L.current->next=q->next;if(L.tail=q)L.tail=L.current;//被刪結點恰為尾結點e=q->data;FreeNode(q);returnOK;StatusDelAfter(LinkList&L,36例一StatusListInsert_L(LinkListL,inti,ElemTypee){

//在帶頭結點的單鏈線性表L的第i個元素之前插入元素e}//ListInsert_L

利用上述定義的線性鏈表如何完成線性表的其它操作？if(!LocatePos(L,i-1))returnERROR;

//i值不合法，第i-1個結點不存在if(InsAfter(L,e))returnOK;

//完成插入elsereturnERROR;例一利用上述定義的線性鏈表如何完成線性表的37StatusMergeList_L(LinkList&Lc,LinkList&La,LinkList&Lb，

int(*compare)(ElemType,ElemType)){

//歸并有序表La和Lb,生成新的有序表Lc,

//并在歸并之后銷毀La和Lb,

//compare為指定的元素大小判定函數……}//MergeList_L例二StatusMergeList_L(LinkList&L38if(!InitList(Lc))returnERROR;//存儲空間分配失敗while(!(a=MAXC&&b=MAXC)){//La或Lb非空}……LocatePos(La,0);LocatePos(Lb,0);

//當前指針指向頭結點if(DelAfter(La,e))a=e;//取得La表中第一個元素aelsea=MAXC;//MAXC為常量最大值if(DelAfter(Lb,e))b=e;//取得Lb表中第一個元素belseb=MAXC;//a和b為兩表中當前比較元素DestroyList(La);DestroyList(Lb);

//銷毀鏈表La和LbreturnOK;if(!InitList(Lc))returnER39

if((*compare)(a,b)<=0){

//a≤bInsAfter(Lc,a);

if(DelAfter(La,e1))a=e1;

elsea=MAXC;}else{

//a＞bInsAfter(Lc,b);

if(DelAfter(Lb,e1))b=e1;

elseb=MAXC;

}if((*compare)(a,b)<=0){40

1.雙向鏈表五、其它形式的鏈表

鏈表中的結點有兩個指針域，其一指向直接后繼，另一指向直接前趨。bca1.雙向鏈表五、其它形式的鏈表鏈表中41typedefstructDuLNode{ElemTypedata;

//數據域

structDuLNode*prior;

//指向前驅的指針域

structDuLNode*next;

//指向后繼的指針域}

DuLNode,*DuLinkList;用C語言可描述如下：priordatanexttypedefstructDuLNode{用C語言可42

最后一個結點的指針域的指針又指回第一個結點的鏈表。a1a2…...an2.循環(huán)鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個結點的條件不再是“后繼是否為空”，而是“后繼是否為頭結點”。最后一個結點的指針域的指針又指回第一個結點的433.雙向循環(huán)鏈表空表非空表a1a2…...an3.雙向循環(huán)鏈表空表非空表a1a244雙向鏈表的操作特點：

“查詢”和單鏈表相同。

“插入”和“刪除”時需要同時修改兩個方向上的指針。雙向鏈表的操作特點：“查詢”和單鏈表相同?！?5ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入ai-1aies->next=p->next;p46ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-1ai-1刪除aiai+1p->next=p->next-47六、有序表類型ADT

Ordered_List{

數據對象:

S={xi|xiOrderedSet，i=1,2,…,n,n≥0}集合中任意兩個元素之間均可以進行比較數據關系:R={<xi-1,xi>|xi-1,xi

S,

xi-1≤xi,i=2,3,…,n}回顧例2-2的兩個算法六、有序表類型ADTOrdered_List{集合中數據48

LocateElem(L,e,&q,int(*compare)(ElemType,ElemType))初始條件：有序表L已存在。操作結果：若有序表L中存在元素e，則q指示L中第一個值為e的元素的位置，并返回函數值TRUE；否則q指示第一個大于e

的元素的前驅的位置，并返回函數值

FALSE。

基本操作：…………Compare是一個有序判定函數LocateElem(L,e,&q,基本49(12,23,34,45,56,67,78,89,98,45)例如:若e=45,則q指向

若e=88,則q指向表示值為88的元素應插入在該指針所指結點之后。(12,23,34,45,56,67,78,50voidunion(List&La,ListLb){//Lb為線性表

InitList(La);//構造(空的)線性表LA

La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個數據元素賦給e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數據元素，則插入之}//for}//union算法時間復雜度：O(n2)voidunion(List&La,ListLb)51voidpurge(List&La,ListLb){

//Lb為有序表InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

for(i=1;i<=Lb_len;i++){

}}//purge

GetElem(Lb,i,e);//取Lb中第i個數據元素賦給eif

(ListEmpty(La)||!equal(en,e))

{

ListInsert(La,++La_len,e);

en=e;}

//La中不存在和e相同的數據元素，則插入之算法時間復雜度：O(n)voidpurge(List&La,ListLb)52小結:鏈式存儲結構的優(yōu)缺點

⑴插入和刪除運算時，無須移動表中元素的位置，只需修改有關結點的指針內容；⑵不能隨機訪問表中元素，訪問時間與元素在表中的位置有關；⑶不需要一塊連續(xù)的存儲空間，只要能存放一個數據元素的空閑結點就可以被利用⑷表的規(guī)模易擴充。小結:53在實際應用中采用哪一種存儲結構更合適？

對這個問題不能一概而論，這涉及到不同實現方法的選擇問題。一般而言，對存儲結構的選擇應從以下幾條區(qū)別：⑴應有利于基本運算的實現。因為運算的具體實現以存儲結構的確定為前提，存儲結構在一定程度上、一定范圍內決定了運算的實現是否方便、高效；⑵應有利于數據的特性。除了數據的邏輯性外，其他的諸如數據規(guī)模也應在選擇存儲結構時加以考慮；⑶應有利于軟件環(huán)境。數據的存放方式對存儲結構有不同的要求，所以應依據情況適當選擇存儲結構。具體而言，即應主要從存儲空間、運算時間、程序設計語言三方面考慮。即

在實際應用中采用哪一種存儲結構更合適？54①存儲空間順序表要求預先分配存儲空間，一般在程序執(zhí)行之前是難以估計存儲空間大小，估計過大會造成浪費，估計過小又會產生空間溢出。而鏈式存儲結構的存儲空間是動態(tài)分配，只要內存空間有空間，就可動態(tài)申請內存空間，不會產生溢出。對于存儲空間的考慮也可以存儲密度的大小來衡量。其中存儲密度的大小定義為一個結點數據本身所占用的存儲量與結點結構所占用的存儲量的比值。一般地，存儲密度越大，存儲空間的利用率就越高。顯然，順序表的存儲密度為1，而鏈式存儲結構的存儲密度則小于1。①存儲空間55②運算時間順序存儲結構是一種隨機存取的結構，便于元素的隨機訪問。即表中任一元素都可在O(1)時間復雜度情況下迅速而直接地存取。而鏈式存儲結構，必須從頭指針開始順著鏈掃描才能取得，一般情況下其時間復雜度為O(n)，所以對于那些只進行查找運算而很少做插入和刪除等的運算，宜采用順序存儲結構。但在順序表中進行元素的插入和刪除運算時，需移動大量元素，平均要移動約半數的元素。尤其是當表中每個元素的信息量較復雜時所花費的時間就更為可觀。而采用鏈式存儲結構，由于進行元素的插入或刪除，只需修改指針并結合一定的查找。所以，對于那些需要經常頻繁地進行元素的插入和刪除運算的線性表，其存儲結構應采用鏈式存儲結構。②運算時間56③程序設計語言這主要是指依據某種高級語言是否提供指針類型或者依據實際需要決定存儲結構是選用靜態(tài)鏈表還是動態(tài)鏈表。總之，線性表的順序實現和鏈式實現各有優(yōu)缺點，是無法籠統(tǒng)地認定哪種優(yōu)，哪種劣。只能根據實際問題的具體實現需要，對各方面的優(yōu)缺點加以綜合平衡來確定適宜的存儲結構。③程序設計語言572.4一元多項式的表示及相加2.4一元多項式的表示及相加58在數學上，一元n次多項式

Pn(

x)=p0+p1x+p2x2+…+pnxn由n+1個系數唯一確定，可用線性表P來表示

P

=（p0,p1,p2,…,pn）每一項的指數i隱含在其系數Pi的序號里。假設Qm(x)是一元m次多項式,同樣可用線性表Q來表示

Q

=（q0,q1,q2,…,qm）設m<n，則兩個多項式相加的結果

Rn(

x)=Pn(

x)+Qm(x)可用線性表R表示

R=(p0+q0,p1+q1,p2+q2,…,pm+qm,

pm+1,…,pn)

在數學上，一元n次多項式假設Qm(x59在通常應用中，多項式的次數很高且變化很大，使得順序存儲結構的最大長度很難確定，特別是在處理形如

S(x)=1+3x10000–2x20000的一元稀疏多項式時，就要用一長度為20001的線性表來表示，表中僅有三個非零元素，這種對內存空間的浪費是應該避免的。如果只存儲非零系數項，則顯然必須同時存儲相應的指數。在通常應用中，多項式的次數很高且變化很大，使60

一般情況下的一元稀疏多項式可寫成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指數為ei

的項的非零系數，

0≤e1<e2<┄<em=n可用一個長度為m且每個元素有兩個數據項（系數項和指數項）的線性表表示：（（p1,e1）,(p2,e2),……,(pm,em)）一般情況下的一元稀疏多項式可寫成可用一個長61

P999(x)=7x3-2x12-8x999例如:可用線性表

((7,3),(-2,12),(-8,999))

表示

在最壞情況下，n+1(=m)個系數都不為零，則比只存儲每項系數的方案要多存儲一倍的數據。但對于S(x)類的多項式，這種表示將大大節(jié)省空間。P999(x)=7x3-2x12-8x999例62對于象

((p1，e1),（p2，e2),……,（pm，em))的線性表，有兩種存儲結構：順序存儲結構和鏈式存儲結構。在實際的應用程序中取用哪一種，則要視多項式作何種運算而定。⑴若只求多項式的值，運算中無須修改多項式的系數和指數值，采用順序存儲結構為宜。⑵若求兩個多項式之和，采用鏈式存儲結構為宜。對于象63多項式選擇順序存儲結構：

#definemaxlenmaxsize;typedefstruct//定義結點類型{floatcoef;//系數域intexp;//指數域}elemtp;typedefstruct{elemtpvec[maxlen];

//定義線性表為向量intlen;//線性表長度}sequenlist;//類型定義p1e1p2pme2emcoefexp多項式選擇順序存儲結構：p1e1p2pme2emcoef64多項式選擇鏈式存儲結構：

typedefstructnode//定義結點類型{floatcoef;//系數域intexp;//指數域

structnode*next;//指針域}polynode;ploynode*p,*q;多項式選擇鏈式存儲結構：65ADTPolynomial{

數據對象：

數據關系：抽象數據類型一元多項式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每個元素包含一個表示系數的實數和表示指數的整數}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n且ai-1中的指數值＜ai中的指數值

}ADTPolynomial{抽象數據類型一元多項式的定義66

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)

基本操作：操作結果：輸入m項的系數和指數，建立一元多項式P。初始條件：一元多項式P已存在。操作結果：銷毀一元多項式P。初始條件：一元多項式P已存在。操作結果：打印輸出一元多項式P。CreatPolyn(&P,m)67

PolynLength(P)

AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)……}ADTPolynomial初始條件：一元多項式P已存在。操作結果：返回一元多項式P中的項數。初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相加運算，即：

Pa=Pa＋Pb，并銷毀一元多項式Pb。PolynLength(P)初始68一元多項式的實現：typedefstruct{

//項的表示

floatcoef;//系數

intexpn;//指數}

term,ElemType;typedefOrderedLinkListpolynomial;

//

用帶表頭結點的有序鏈表表示多項式結點的數據元素類型定義為:一元多項式的實現：typedefstruct{69StatusCreatPolyn(polynomail&P,intm){

//輸入m項的系數和指數，建立表示一元多項式的有序鏈表P}//CreatPolynInitList(P);e.coef=0.0;e.expn=-1;

SetCurElem(h,e);

//設置頭結點的數據元素for(i=1;i<=m;++i){

//依次輸入m個非零項}returnOK;scanf(e.coef,e.expn);if(!LocateElem(P,e,(*cmp)()))//當前鏈表中不存在該指數項

if(!InsAfter(P,e))returnERROR;

注意:1.輸入次序不限;2.指數相同的項只能輸入一次。StatusCreatPolyn(polynomail70StatusAddPolyn(polynomial&Pc,polynomial&Pa,polynomial&Pb){

//利用兩個多項式的結點構成“和多項式”Pc=Pa＋Pb……

if(DelAfter(Pa,e1))a=e1.expnelsea=MAXE;

if(DelAfter(Pb,e2))b=e2.expnelseb=MAXE;while(!(a=MAXE&&b=MAXE)){

……}……}//AddPolynStatusAddPolyn