自學(xué)數(shù)據(jù)結(jié)構(gòu)課件--線性表順序表定義：將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中。

存儲(chǔ)結(jié)構(gòu)：數(shù)組。特點(diǎn)：線性表的順序存儲(chǔ)方式。存取方式：順序存取、隨機(jī)存取順序存儲(chǔ)結(jié)構(gòu)示意圖458990674078

012345順序表的存儲(chǔ)方式：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l

a1

a2

…ai………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle順序表（SeqList）的類型定義

#defineListSize100//最大允許長(zhǎng)度

typedefintListData;

typedefstruct

{

ListData*data;//存儲(chǔ)空間基址

intlength; //當(dāng)前元素個(gè)數(shù)

}

SeqList;順序表基本運(yùn)算初始化

voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存儲(chǔ)分配失敗!\n”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表項(xiàng)的位置，否則返回-1

intFind(SeqList&L,ListDatax){inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功2534571648

01234data搜索50i2534571648

i2534571648

i2534571648

i2534571648

i搜索失敗搜索成功的平均比較次數(shù)

若搜索概率相等，則

搜索不成功數(shù)據(jù)比較n

次按值查找：判斷x是否在表中

intIsIn(SeqList&L,ListDatax){ inti=0, found=0; while(i<L.length&&!found) if(L.data[i]!=x)i++; elsefound=1;returnfound;}求表的長(zhǎng)度

intLength(SeqList&L){returnL.length;}提取函數(shù)：在表中提取第i個(gè)元素的值

ListDataGetData(SeqList&L,inti){if(i>=0&&i<L.length)returnL.data[i];elseprintf(“參數(shù)

i不合理！\n”); }

按值查找：尋找x的后繼

intNext(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i<L.length)returni+1; elsereturn-1;}尋找x的前驅(qū)

intPrevious(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i<L.length)returni-1; elsereturn-1;}插入25345716480963

0123456750插入x2534575016480963

0123456750i順序表插入時(shí)，平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng)插入概率相等時(shí)順序表的插入

intInsert(SeqList&L,ListDatax,inti){

//在表中第i個(gè)位置插入新元素x

if(i<0||i>L.length||L.length==ListSize)return0;//插入不成功

else{ for(intj=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i]=x;L.length++; return1;//插入成功

}}刪除253457501648096316刪除

x2534575048096301234567順序表刪除平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng)刪除概率相等時(shí)順序表的刪除

intDelete(SeqList&L,ListDatax){

//在表中刪除已有元素x

inti=Find(L,x); //在表中查找xif(i>=0){ L.length--; for(intj=i;j<L.length;j++) L.data[j]=L.data[j+1];return1; //成功刪除

} return0;//表中沒有x}順序表的應(yīng)用:集合的“并”運(yùn)算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i<m;i++){ intx=GetData(B,i);//在B中取一元素

intk=Find(A,x);//在A中查找它

if(k==-1)//若未找到插入它

{Insert(A,x,n);n++;}}}集合的“交”運(yùn)算

voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i<n){intx=GetData(A,i);//在A中取一元素

intk=Find(B,x);//在B中查找它

if(k==-1){Delete(A,i);n--;} elsei++;//未找到在A中刪除它

}}順序表(SeqList)類的定義template<classType> classSeqList{Type*data;//順序表存儲(chǔ)數(shù)組

intMaxSize; //最大允許長(zhǎng)度

intlast; //當(dāng)前最后元素下標(biāo)public: SeqList(intMaxSize=defaultSize); ~SeqList(){delete[]data;}

intLength()const

{returnlast+1;

}C++描述

intFind(Type&x)const;//查找

intLocate(inti)const; //定位

intInsert(Type&x,inti);//插入

intRemove(Type

&x); //刪除

intNext(Type

&x); //后繼

intPrior(Type

&x);//前驅(qū)

intIsEmpty(){returnlast==-1;

} intIsFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

C++描述順序表部分公共操作的實(shí)現(xiàn)

template<classType>

//構(gòu)造函數(shù)

SeqList<Type>::SeqList(intsz){if(sz>0){ MaxSize=sz;last=-1; data=newType[MaxSize];

if(data==NULL){MaxSize=0;last=-1;return;}

}}C++描述template<classType> intSeqList<Type>::Find(Type

&x)const{//搜索函數(shù)：在順序表中從頭查找結(jié)點(diǎn)值等于//給定值x的結(jié)點(diǎn)

inti=0;

while(i<=last&&data[i]!=x)i++;

if(i>last)return-1;

elsereturni; }C++描述template<classType>intSeqList<Type>::Insert(Type&x,inti){//在表中第

i個(gè)位置插入新元素

x

if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入不成功

else{last++;

for(intj=last;j>i;j--)data[j]=data[j-1]; data[i]=x;return1;//插入成功

}}C++描述

template<classType>intSeqList<Type>::Remove(Type&x){

//在表中刪除已有元素

x

inti=Find(x); //在表中搜索

x

if(i>=0){ last--;

for(intj=i;j<=last;j++)data[j]=data[j+1];

return1; //成功刪除

} return0;//表中沒有

x}C++描述順序表的應(yīng)用：集合的“并”運(yùn)算

voidUnion(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();

for(inti=0;i<m;i++){ intx=B.Get(i);//在B中取一元素

intk=A.Find(x);//在A中搜索它

if(k==-1)//若未找到插入它

{A.Insert(n,x);n++;}}}C++描述順序表的應(yīng)用：集合的“交”運(yùn)算

voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Find(x);//在B中搜索它

if(k==-1){A.Remove(i);n--;} elsei++;//未找到在A中刪除它

}}C++描述鏈表（LinkedList）鏈表是線性表的鏈接存儲(chǔ)表示單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表單鏈表(SinglyLinkedList)定義：用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。例如：線性表ZHOU,ZHAO,SUN,WU,WANG,ZHANG,LI數(shù)據(jù)域指針域ZHANG13WANG1LInullZHAO37WU7ZHOU19SUN25存儲(chǔ)地址17131925313731頭指針表中節(jié)點(diǎn)位置6572413每個(gè)元素由結(jié)點(diǎn)(Node)構(gòu)成, 它包括兩個(gè)域:數(shù)據(jù)域Data和指針域Linkdatalink存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：存儲(chǔ)單元可以不連續(xù)。存取方式：順序存取。Node單鏈表結(jié)構(gòu)單鏈表的類型定義typedefcharListData;typedefstructnode{//鏈表結(jié)點(diǎn)

ListDatadata; //結(jié)點(diǎn)數(shù)據(jù)域

structnode*link;//結(jié)點(diǎn)鏈域}ListNode;typedefListNode*LinkList;//鏈表頭指針LinkListfirst;//鏈表頭指針單鏈表的類定義多個(gè)類表達(dá)一個(gè)概念(單鏈表)。鏈表結(jié)點(diǎn)(ListNode)類鏈表(List)類鏈表游標(biāo)(Iterator)類定義方式復(fù)合方式嵌套方式

繼承方式

classList;

//鏈表類定義（復(fù)合方式）

classListNode{

//鏈表結(jié)點(diǎn)類

friendclassList;

//鏈表類為其友元類

private:

intdata;

//結(jié)點(diǎn)數(shù)據(jù),整型

ListNode*link;

//結(jié)點(diǎn)指針

};classList{

//鏈表類

private:ListNode*first,*last;

//表頭指針};classList{

//鏈表類定義(嵌套方式)private:

classListNode{

//嵌套鏈表結(jié)點(diǎn)類

public:

intdata;

ListNode*link;

};ListNode*first,*last;

//表頭指針public:

//鏈表操作………};鏈表類和鏈表結(jié)點(diǎn)類定義(繼承方式)classListNode{

//鏈表結(jié)點(diǎn)類

protected:

intdata;

ListNode*link;

};classList:public

classListNode{

//鏈表類,繼承鏈表結(jié)點(diǎn)類的數(shù)據(jù)和操作

private:ListNode*first,*last;

//表頭指針};單鏈表的基本運(yùn)算插入（三種情況）

第一種情況：在第一個(gè)結(jié)點(diǎn)前插入

newnode->link=first;first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst第二種情況：在鏈表中間插入

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodepnewnodep第三種情況：在鏈表末尾插入

newnode->link=p->link; p->link=newnode；p(插入前)(插入后)newnodenewnodep算法描述intList::Insert(intx,inti){//在鏈表第

i個(gè)結(jié)點(diǎn)處插入新元素

x

ListNode*p=first;for(

k=0;k<i-1;k++)

//找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL)break;

elsep=p->link;

if(p==NULL&&first!=NULL){

cout<<“無效的插入位置!\n”;return0;}

ListNode*newnode=

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

newListNode(x,NULL);

if(first==NULL||i==0){

//插在表前

newnode->link=first; if(first==NULL)last=newnode;

first=newnode;}else{

//插在表中或末尾

newnode->link=p->link;

if(p->link==NULL)last=newnode;

p->link=newnode;}

return1;

}刪除 在單鏈表中刪除ai結(jié)點(diǎn)

q=p->link; p->link=q->link;刪除前刪除后ai-1aiai+1pqpai-1ai+1aiintList::Remove(inti){//在鏈表中刪除第i個(gè)結(jié)點(diǎn)

ListNode*p,*q;if(i==0)

//刪除表中第

1個(gè)結(jié)點(diǎn)

{q=first;p=first=first->link;}else{

p=first; intk=0;

//找第i-1個(gè)結(jié)點(diǎn)

while(p!=NULL&&k<i-1)

{p=p->link;k++;}if(p==NULL||p->link==NULL){cout<<“無效的刪除位置!\n”;return0;

}

else{

//刪除表中或表尾元素

q=p->link;

//重新鏈接

p->link=q->link;} if(

q==last)last=p; //可能修改last

Typex=q->data;deleteq;

//刪除q

returnx;

//返回第i個(gè)結(jié)點(diǎn)的值

}帶表頭結(jié)點(diǎn)的單鏈表表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的:簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。非空表空表^ana1firstfirst^插入

q->link=p->link; p->link=q;firstqfirstqfirstq^firstq^pppp插入前插入后表頭表尾qq插入pp表中intInsert(LinkListfirst,ListDatax,inti){//將新元素x插入在鏈表中第i號(hào)結(jié)點(diǎn)位置

ListNode*p=Locate(first,i-1);if(p==NULL)return0; //參數(shù)i值不合理返回0ListNode*newnode=//創(chuàng)建新結(jié)點(diǎn)

(ListNode*)malloc(sizeof(ListNode));newnode->data=x;newnode->link=p->link;//鏈入

p->link=newnode;return1; }刪除

q=p->link;p->link=q->link;deleteq;刪除前first(非空表）(空表）first^firstpq^pqfirst刪除后intdelete(LinkListfirst,inti){ //將鏈表第i號(hào)元素刪去

ListNode*p,*q p=Locate(first,i-1);//尋找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL||p->link==NULL) return0;//i值不合理或空表

q=p->link; p->link=q->link;//刪除結(jié)點(diǎn)

free(q); //釋放

return1;}前插法建立單鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。firstqfirstq^^LinkListcreateListF(void){charch;ListNode*q;LinkListhead=//建立表頭結(jié)點(diǎn)(LinkList)malloc(sizeof(ListNode));head->link=NULL;while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新結(jié)點(diǎn)

q->link=head->link;//插入到表前端

head->link=q;}returnhead;}后插法建立單鏈表每次將新結(jié)點(diǎn)加在鏈表的表尾；尾指針r,總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；^qfirst^r^first^rLinkListcreateListR(void){charch;LinkListhead=//建立表頭結(jié)點(diǎn)(LinkList)malloc(sizeof(ListNode));ListNode*q,*r=head; while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新結(jié)點(diǎn)

r->link=q;r=q;

//插入到表末端}

r->link=NULL;

returnhead;}單鏈表清空voidmakeEmpty(LinkListfirst){//刪去鏈表中除表頭結(jié)點(diǎn)外的所有其它結(jié)點(diǎn)

ListNode*q;while(first->link!=NULL){//當(dāng)鏈不空時(shí)，循環(huán)逐個(gè)刪去所有結(jié)點(diǎn)

q=first->link;first->link=q->link; free(q);//釋放

} last=first;}計(jì)算單鏈表長(zhǎng)度intLength(LinkListfirst){ListNode*p=first->link;//指針p指示第一個(gè)結(jié)點(diǎn)

intcount=0;while(p!=NULL){//逐個(gè)結(jié)點(diǎn)檢測(cè)

p=p->link;count++;} returncount;}

按值查找ListNode*Find(LinkListfirst,ListDatavalue){ //在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

ListNode*p=first->link;

//指針p指示第一個(gè)結(jié)點(diǎn)

while(p!=NULL&&p->data!=value)p=p->link;returnp;}按序號(hào)查找（定位）

ListNode*Locate(LinkListfirst,inti){//返回表中第i個(gè)元素的地址

if(i<0)returnNULL;ListNode*p=first;intk=0;while(p!=NULL&&k<i){p=p->link;k++;} //找第i個(gè)結(jié)點(diǎn)

if(k==i)returnp;//返回第i個(gè)結(jié)點(diǎn)地址

elsereturnNULL;}1ZHANG2WANG6LI5ZHAO5WU-1CHEN31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前（插入chen,刪除zhao)修改后用一維數(shù)組描述線性鏈表靜態(tài)鏈表定義constintMaxSize=100;//靜態(tài)鏈表大小typedefintListData;typedefstructnode{//靜態(tài)鏈表結(jié)點(diǎn)

ListDatadata;

intlink;}SNode;typedefstruct{//靜態(tài)鏈表

SNodeNodes[MaxSize];intnewptr; //當(dāng)前可分配空間首地址}SLinkList;鏈表空間初始化voidInitList(SLinkList*SL){SL->Nodes[0].link=1;SL->newptr=1;//當(dāng)前可分配空間從1開始

//建立帶表頭結(jié)點(diǎn)的空鏈表

for(inti=1;i<MaxSize-1;i++)SL->Nodes[i].link=i+1;//構(gòu)成空閑鏈接表

SL->Nodes[MaxSize-1].link=-1;

//鏈表收尾}在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)intFind(SLinkListSL,ListDatax){intp=SL.Nodes[0].link;//指針p指向鏈表第一個(gè)結(jié)點(diǎn)

while(p!=-1)//逐個(gè)查找有給定值的結(jié)點(diǎn)

if(SL.Nodes[p].data!=x)p=SL.Nodes[p].link;elsebreak; returnp;}在靜態(tài)鏈表中查找第i個(gè)結(jié)點(diǎn)intLocate(SLinkListSL,inti){if(i<0)return-1;//參數(shù)不合理

intj=0,p=SL.Nodes[0].link;while(p!=-1&&j<i){//循環(huán)查找第i號(hào)結(jié)點(diǎn)

p=SL.Nodes[p].link;j++;}if(i==0)return0;returnp;}在靜態(tài)鏈表第i個(gè)結(jié)點(diǎn)處插入一個(gè)新結(jié)點(diǎn)intInsert(SLinkList*SL,inti,ListDatax){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點(diǎn)

intq=SL->newptr;//分配結(jié)點(diǎn)

SL->newptr=SL->Nodes[SL->newptr].link;SL->Nodes[q].data=x;

SL->Nodes[q].link=SL.Nodes[p].link;SL->Nodes[p].link=q;

//插入

return1;}在靜態(tài)鏈表中釋放第i個(gè)結(jié)點(diǎn)intRemove(SLinkList*SL,inti){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點(diǎn)

intq=SL->Nodes[p].link;//第i號(hào)結(jié)點(diǎn)

SL->Nodes[p].link=SL->Nodes[q].link;SL->Nodes[q].link=SL->newptr;//釋放

SL->newptr=q;return1;}循環(huán)鏈表(CircularList)特點(diǎn):最后一個(gè)結(jié)點(diǎn)的link指針不為NULL，而是指向頭結(jié)點(diǎn)。只要已知表中某一結(jié)點(diǎn)的地址，就可搜尋所有結(jié)點(diǎn)的地址。存儲(chǔ)結(jié)構(gòu):鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

帶表頭結(jié)點(diǎn)的循環(huán)鏈表an-1firsta1a0first(空表)(非空表)循環(huán)鏈表的插入template<classType>classCircList;template<classType>classCircListNode{friendclassCircList<Type>;public:CircListNode(Typed=0,CircListNode<Type>*next=NULL)

:data(d),link(next){}//構(gòu)造函數(shù)private:

Typedata; //結(jié)點(diǎn)數(shù)據(jù)

CircListNode<Type>*link;//鏈接指針}

循環(huán)鏈表類的定義template<classType>classCircList{private:CircListNode<Type>*first,*current,*last;

//鏈表的表頭指針、當(dāng)前指針和表尾指針public:CircList(Typevalue); ~CircList();

intLength()const; BooleanIsEmpty()

{returnfirst->link==first;

}BooleanFind(constType&value);

TypegetData

()const;

voidFirster(){current=first;} BooleanFirst();

BooleanNext();BooleanPrior(); voidInsert(constType&value);

voidRemove();

};搜索成功搜索不成功循環(huán)鏈表的搜索算法firstfirst3131484815155757搜索15搜索25currentcurrentcurrentcurrentcurrentcurrentcurrentcurrent循環(huán)鏈表的搜索算法template<classType>CircListNode<Type>*CircList<Type>::

Find(Typevalue

){//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

CircListNode<Type>*p=first->link;

//檢測(cè)指針

p

指示第一個(gè)結(jié)點(diǎn)

while(p!=first&&p->data!=value)

p=p->link;

returnp;}if(first!=NULL){

CircListNode<Type>*second=first->link;first->link=av;av=second;

first=NULL;}利用可利用空間表回收循環(huán)鏈表firstavfirstav回收前回收后if(av==NULL)newnode=newCircListNode<Type>;else{newnode=av;av=av->link;

}從可利用空間表分配結(jié)點(diǎn)avnewnodeav分配前的可利用空間表分配后的可利用空間表和新結(jié)點(diǎn)約瑟夫問題用循環(huán)鏈表求解約瑟夫問題n個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從1開始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù),報(bào)到第m個(gè)人，令其出列。然后再?gòu)南乱粋€(gè)人開始，從1順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再令其出列，…，如此下去,直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。例如n=8m=3約瑟夫問題的解法#include<iostream.h>#include“CircList.h”voidJosephus(intn,intm){for(inti=0;i<n-1;i++){//執(zhí)行n-1次

for(intj=0;j<m-1;j++)Next();

//數(shù)m-1個(gè)人

cout<<“Deleteperson”<<getData()<<endl;Remove();//刪去

}}voidmain(){CircList<int>clist; intn,m; cout<<“EntertheNumberofContestants?”;cin>>n>>m;for(inti=1;i<=n;i++)clist.insert(i);//形成約瑟夫環(huán)

clist.Josephus(n,m);//解決約瑟夫問題}多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+1項(xiàng)。

系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列classPolynomial{public:Polynomial();//構(gòu)造函數(shù)

intoperator!();//判是否零多項(xiàng)式

floatCoef(inte);

intLeadExp();//返回最大指數(shù)

Polynomial

Add(Polynomial

poly);PolynomialMult(Polynomialpoly);

floatEval(floatx); //求值}多項(xiàng)式(Polynomial)的抽象數(shù)據(jù)類型

#include<iostream.h>classpower{

doublex;

inte;

doublemul;

public:

power(doubleval,intexp);

//構(gòu)造函數(shù)

doubleget_power(){returnmul;}

//取冪值

};創(chuàng)建power類，計(jì)算x的冪

power::power(doubleval,intexp){

//按val值計(jì)算乘冪

x=val;e=exp;mul=1.0;

if(exp==0)return;

for(;exp>0;exp--)mul=mul*x;

}main(){powerpwr(1.5,2);

cout<<pwr.get_power()<<“\n”;

}多項(xiàng)式的存儲(chǔ)表示第一種：

private:(靜態(tài)數(shù)

intdegree; 組表示)

floatcoef[maxDegree+1];

Pn(x)可以表示為：

pl.degree=n pl.coef[i]=ai,0ina0

a1

a2……an………012degreemaxDegree-1coefn第二種：private:

(動(dòng)態(tài)數(shù)

intdegree;組表示)

float*coef; Polynomial::Polynomial(intsz){ degree=sz; coef=newfloat[degree+1];

}

以上兩種存儲(chǔ)表示適用于指數(shù)連續(xù)排列的多項(xiàng)式。但對(duì)于指數(shù)不全的多項(xiàng)式如

P101(x)=3+5x50-14x101,不經(jīng)濟(jì)。第三種：

class

Polynomial; classterm{

//多項(xiàng)式的項(xiàng)定義

friendPolynomial;

private:

floatcoef;//系數(shù)

intexp; //指數(shù)

};a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

m

A(x)=2.0x1000+1.8

B(x)=1.2+51.3x50+3.7x101

兩個(gè)多項(xiàng)式存放在termArray中A.startA.finishB.startB.finishfreecoefexp1.82.01.251.33.7……01000050101……maxTerms多項(xiàng)式及其相加在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)增加了一個(gè)數(shù)據(jù)成員link，作為鏈接指針。優(yōu)點(diǎn)是：多項(xiàng)式的項(xiàng)數(shù)可以動(dòng)態(tài)地增長(zhǎng)，不存在存儲(chǔ)溢出問題。插入、刪除方便，不移動(dòng)元素。多項(xiàng)式(polynomial)類的鏈表定義structTerm{

//多項(xiàng)式結(jié)點(diǎn)定義

floatcoef;

//系數(shù)

intexp;

//指數(shù)

Term(floatc,

inte){coef=c;exp=e;

}};

classPolynomial {

//多項(xiàng)式類的定義

List<Term>poly;

//構(gòu)造函數(shù)

friendPolynomial&

operator+(Polynomial&,Polynomial&);

//加法};多項(xiàng)式鏈表的相加AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x18兩個(gè)多項(xiàng)式的相加算法掃描兩個(gè)多項(xiàng)式，若都未檢測(cè)完：

若當(dāng)前被檢測(cè)項(xiàng)指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項(xiàng)式。若當(dāng)前被檢測(cè)項(xiàng)指數(shù)不等，將指數(shù)小者加到結(jié)果多項(xiàng)式。若一個(gè)多項(xiàng)式已檢測(cè)完，將另一個(gè)多項(xiàng)式剩余部分復(fù)制到結(jié)果多項(xiàng)式。AH.firstBH.firstCH.first1010-14-14-3636-910712712814814pappc-910pbAH.firstCH.first1010-14-14-3636-910712712814814papbpc-910AH.firstCH.first1010-14-14-3636-910712712814814papbpc-910AH.firstCH.first1010-14-14-3636-910712712814814pappc-910pb0AH.firstCH.first1010-14-1406-910712712814814pappc-910pbAH.firstCH.first1010-14-14-910712712814814papc-910pbAH.firstCH.first1010-14-14-910712712814814papc-910pbAH.firstCH.first1010-14-14-910712712814814pa==pc-910pbAH.firstCH.first1010-14-14-910712712814814pa==pc-910pbPolynomial&operator+(Polynomial&ah,Polynomial&bh){//兩個(gè)帶頭結(jié)點(diǎn)的按升冪排列的多項(xiàng)式相加，//返回結(jié)果多項(xiàng)式鏈表的表頭指針，結(jié)果不//另外占用存儲(chǔ),覆蓋ah和bh鏈表

ListNode<Term>*pa,*pb,*pc,*p;

Terma,b;pa=pc=ah.poly.First();

//結(jié)果存放指針

pb=p=bh.poly.First();pa=ah.poly.Next();

//多項(xiàng)式檢測(cè)指針

pb=bh.poly.Next();

//多項(xiàng)式檢測(cè)指針

deletep;

//刪去bh的表頭結(jié)點(diǎn)

while(pa!=NULL&&pb!=NULL){a=pa->data;b=pb->data;switch(compare(a.exp,b.exp)){case'==':

//pa->exp==pb->exp

a.coef=a.coef+b.coef;

//系數(shù)相加

p=pb;pb=pb->link;

deletep;

//刪去原pb所指結(jié)點(diǎn)

if(abs(a.coef)<0.0001){

p=pa;pa=pa->link;

deletep;

}

//相加為零,該項(xiàng)不要

else{

//相加不為零,加入ch鏈

pa->data=a;pc->link=pa;

pc=pa;pa=pa->link;

}break;case