東南大學數(shù)據(jù)結(jié)構(gòu)課件第02章線性表

第2章線性表線性表順序表循環(huán)鏈表本章課外實踐基于本章內(nèi)容，實現(xiàn)線性表不同物理結(jié)構(gòu)的排序操作，并通過隨機產(chǎn)生的100個數(shù)進行檢驗。實現(xiàn)你班同學通訊錄的不同排序結(jié)果，即分別輸入姓名、學號、手機號，輸出相應的通訊錄。2.1線性表(LinearList)線性表的定義線性表是n(≥0)個數(shù)據(jù)元素的有限序列，記作（a1,a2,…,an）

ai是表中數(shù)據(jù)元素，n是表長度。原則上講，線性表中表元素的數(shù)據(jù)類型可以不相同。但采用的存儲表示可能會對其有限制。為簡單起見，假定各元素類型相同。

線性表的特點：除第一個元素外，其他每一個元素有一個且僅有一個直接前驅(qū)。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。直接前驅(qū)和直接后繼描述了結(jié)點之間的邏輯關(guān)系（即鄰接關(guān)系）。

a1a2a3a4a5a6線性表的抽象基類

template<classT>classLinearList{public:virtualintSize()const=0; //求表最大體積

virtualintLength()const=0; //求表長度

virtualintSearch(T&x)const=0;//搜索

virtualintLocate(inti)const=0;//定位

virtualboolgetData(inti,T&x)const=0;//取值

virtualvoidsetData(inti,T&x)=0;//賦值virtualboolInsert(inti,T&x)=0;//插入

virtualboolRemove(inti,T&x)=0; //刪除

virtualboolIsEmpty()const=0;//判表空

virtualboolIsFull()const=0;//判表滿

virtualvoidinput()=0;//輸入

virtualvoidoutput()=0;//輸出

};線性表的存儲表示有兩種：順序存儲方式和鏈表存儲方式。

2.2順序表(SequentialList)順序表的定義將線性表中的元素相繼存放在一個連續(xù)的存儲空間中?？衫靡痪S數(shù)組描述存儲結(jié)構(gòu)順序表的特點所有元素的邏輯先后順序與其物理存放順序一致

253457164809

012345data順序表的靜態(tài)存儲和動態(tài)存儲#definemaxSize100typedefintT;typedefstruct{Tdata[maxSize];

//順序表的靜態(tài)存儲表示

intn;}SeqList;typedefintT;typedefstruct{T*data;

//順序表的動態(tài)存儲表示

intmaxSize,n;}SeqList;結(jié)點的變體（異質(zhì)數(shù)據(jù)）若想在線性表中存放不同類型的數(shù)據(jù)，可采用等價定義union：

typedefunion{intval; //按data.val引用

charch; //按data.ch引用

floatdir; //按data.dir引用

uniondata*link;//按data.link引用

}data;//整體上是同一類型data25‘s’3.36274‘t’1.0‘6’順序表(SeqList)類的定義#include<iostream.h> //定義在“seqList.h”中#include<stdlib.h>#include"LinearList.h"constintdefaultSize=100;template<classT>classSeqList:publicLinearList<T>{protected: T*data; //存放數(shù)組

intmaxSize; //最大可容納表項的項數(shù)

intlast;//當前最后表項號

voidreSize(intnewSize); //改變數(shù)組空間大小public: SeqList(intsz=defaultSize);//構(gòu)造函數(shù)

SeqList(SeqList<T>&L); //復制構(gòu)造函數(shù)

~SeqList(){delete[]data;} //析構(gòu)函數(shù)

intSize()const{returnmaxSize;} //求表最大容量

intLength()const{returnlast+1;}//計算表長度

intSearch(T&x)const; //搜索x在表中位置，函數(shù)返回表項序號

boolgetData(inti,T&x)const { if(i>=0&&i<=last){x=data[i];returntrue;} else{cout<<"范圍越界！"<<endl;returnfalse;} }voidsetData(inti,T&x) {if(i>=0&&i<=last)data[i]=x;}intLocate(inti)const; //定位第i個表項，函數(shù)返回表項序號

boolInsert(inti,T&x); //插入

boolRemove(inti,T&x); //刪除

boolIsEmpty()const{return(last==-1)?true:false;}//判表空

boolIsFull()const{return(last==maxSize+1)?true:false;} //判表滿

voidinput(); //voidinput(T*In_data,intn);//輸入

voidoutput();//輸出

SeqList<T>operator=(SeqList<T>&L);//復制};順序表的構(gòu)造函數(shù)template<classT>SeqList<T>::SeqList(intsz){ if(sz>0){maxSize=sz; //n=0; data=newT[maxSize];//創(chuàng)建表存儲數(shù)組

if(data==NULL) //動態(tài)分配失敗

{cerr<<"存儲分配錯誤！"<<endl;exit(1);} }};template<classT>SeqList<T>::SeqList(SeqList<T>&L){ maxSize=L.Size();n=L.Length(); data=newT[maxSize]; //創(chuàng)建存儲數(shù)組

if(data==NULL) //動態(tài)分配失敗

{cerr<<"存儲分配錯誤！"<<endl;exit(1);} for(inti=0;i<=n-1;i++)//傳送各個表項

L.getData(i,data[i]);};復制構(gòu)造函數(shù)順序表的搜索算法template<classT>intSeqList<T>::Search(T&x)const{//在表中順序搜索與給定值x匹配的表項，找到則//函數(shù)返回該表項是第幾個元素，否則函數(shù)返回0for(inti=0;i<=last;i++) //順序搜索

if(data[i]==x)returni+1; //表項序號和表項位置差1 return0; //搜索失敗};順序搜索圖示253457164809012345data搜索

16i253457164809i253457164809i253457164809i搜索成功2534571648

01234data搜索

50i2534571648

i2534571648

i2534571648

i2534571648

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

pi

是搜索第

i項的概率

ci

是找到時的比較次數(shù)若搜索概率相等，則

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

次搜索性能分析表項的插入25345716480963

01234567data50插入x2534575016480963

01234567data50i表項的插入算法template<classT>boolSeqList<T>::Insert(inti,T&x){//將新元素x插入到表中第i(1≤i≤n+1)個表項位//置。函數(shù)返回插入成功的信息

if(last+1==maxSize)returnfalse;//表滿

if(i<0||i>last+1)returnfalse; //參數(shù)i不合理

for(intj=last+1;j>i;j--)//依次后移

data[j]=data[j-1];data[i]=x;//插入(第i表項在data[i-1]處) last++; returntrue;//插入成功};插入算法的性能分析在表中第i個位置插入，從data[i-1]

到data[n-1]成塊后移，移動n-1-(i-1)+1=n-i+1項?？紤]所有插入位置，插入概率相等時，從0到n0，平均移動元素個數(shù)為:表項的刪除2534575016480963

01234567data16刪除

x25345750480963

01234567data表項的刪除算法template<classT>boolSeqList<T>::Remove(inti,T&x){//從表中刪除第i(1≤i≤n)個表項，通過引用型參//數(shù)x返回被刪元素。函數(shù)返回刪除成功信息

if(last==-1)returnfalse; //表空

if(i<0||i>last)returnfalse; //參數(shù)i不合理

x=data[i]; for(intj=i;j<=last-1;j++)//依次前移，填補

data[j]=data[j+1]; last--;returntrue; }; 刪除算法的性能分析刪除第i個表項，需將第i+1項到第

n項全部前移，需前移的項數(shù)為

n-(i+1)+1=n-i考慮表中所有可能刪除位置（1≤i≤n-1）,相等刪除概率時，平均移動元素個數(shù)為：順序表的應用：集合的“并”運算voidUnion(SeqList<int>&LA,SeqList<int>&LB){intn1=LA.Length(),n2=LB.Length();inti,k,x;for(i=0;i<n2;i++) {LB.getData(i,x); //在LB中取一元素

k=LA.Search(x); //在LA中搜索它

if(k==0) //若在LA中未找到插入它

{LA.Insert(n1,x);n1++;} }};voidIntersection(SeqList<int>&LA,SeqList<int>&LB){intn1=LA.Length();intx,k,i=0;while(i<n1){LA.getData(i,x);//在LA中取一元素

k=LB.Search(x);//在LB中搜索它

if(k==0)//若在LB中未找到

{LA.Remove(i,x);n1--;}//在LA中刪除

elsei++;//未找到在A中刪除它}}順序表的應用：集合的“交”運算2.3單鏈表(SinglyLinkedList)順序存儲結(jié)構(gòu)的特點：優(yōu)點：結(jié)構(gòu)簡單、易于實現(xiàn)、隨機存取、存儲密度高。缺點：插入、刪除元素代價大，需要事先確定存儲空間（或改變存儲空間的大小代價大）。適用場合：插入、刪除操作少，數(shù)據(jù)元素數(shù)量相對固定。特點每個元素(表項)由結(jié)點(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點之間可以連續(xù)，也可以不連續(xù)存儲結(jié)點的邏輯順序與物理順序可以不一致鏈表適用于插入或刪除頻繁、存儲空間需求不定的情形。datalinka1a2a3a4a5Λfirst單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3

freefirst(b)經(jīng)過一段運行后的單鏈表結(jié)構(gòu)單鏈表的結(jié)構(gòu)定義在C中定義單鏈表的結(jié)構(gòu)十分簡單：

typedefintT; //結(jié)點數(shù)據(jù)的類型

typedefstructnode{//結(jié)點結(jié)構(gòu)定義

Tdata;//結(jié)點數(shù)據(jù)域

structnode*link;//結(jié)點鏈接指針域

}LinkNode;//結(jié)點命名這是一個遞歸的定義。在結(jié)構(gòu)定義時不考慮操作，以后在定義和實現(xiàn)鏈表操作時直接使用結(jié)構(gòu)的成分。單鏈表的類定義使用面向?qū)ο蠓椒?，要把?shù)據(jù)與操作一起定義和封裝，用多個類表達一個單鏈表。鏈表結(jié)點(ListNode)類鏈表(List)類定義方式復合方式嵌套方式

繼承方式結(jié)構(gòu)方式classList;

classListNode{

//鏈表結(jié)點類

friendclassList;

//鏈表類為其友元類

private:

intdata;

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

ListNode*link;//結(jié)點指針

};classList{ //鏈表類

private:ListNode*first;//表頭指針

};復合方式classList{//嵌套方式private:classListNode{//嵌套鏈表結(jié)點類

public:intdata; ListNode*link; };ListNode*first; //表頭指針public://鏈表操作………};嵌套方式classListNode{

//鏈表結(jié)點類

protected:

intdata;

ListNode*link;

};classList:public

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

private:ListNode*first;//表頭指針};繼承方式在復合方式中，鏈表結(jié)點類中聲明鏈表類是它的友元類，這樣可以“奉獻”它的私有成員給鏈表類，這種方式靈活。在嵌套方式中，鏈表結(jié)點類是鏈表類的私有成員，這樣限制了鏈表結(jié)點類的應用范圍。在繼承方式中，鏈表類聲明為鏈表結(jié)點類的派生類，這在實現(xiàn)上是可行的。但在邏輯上是有問題的，如三角形is多邊形（繼承關(guān)系）鏈表is鏈表結(jié)點（顯然概念不準確）structListNode{

//鏈表結(jié)點類

intdata;

ListNode*link;

};classList{//鏈表類,直接使用鏈表結(jié)點類的數(shù)據(jù)和操作

private:ListNode*first;//表頭指針

};//鏈表中的結(jié)點屬于鏈表私有，別人無法訪問結(jié)構(gòu)方式單鏈表的插入與刪除插入

第一種情況：在鏈表最前端插入

newnode->link=first;

first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst(插入前)(插入后)

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

newnode->link=current->link;

current->link=newnode；newnodecurrentnewnodecurrent

第三種情況：在鏈表末尾插入

newnode->link=current->link;

current->link=newnode；(插入前)(插入后)newnodenewnodecurrentcurrent

單鏈表的插入算法boolList::Insert(inti,intx){//將新元素x插入到第i個結(jié)點之后。i從1開始，//i=0表示插入到首元結(jié)點之前。

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

//空表或首元結(jié)點前

LinkNode*newNode=newLinkNode(x);

//建立一個新結(jié)點

newNode->link=first;first=newNode;

//新結(jié)點成為首元結(jié)點

}

else{//否則，尋找插入位置

LinkNode*current=first; intk=1;

while(k<i&¤t!=NULL)//找第i結(jié)點

{current=current->link;k++;}

if(current==NULL&&first!=NULL)//鏈短

{cerr<<“無效的插入位置!\n”;returnfalse;}

else{

//插入在鏈表的中間

LinkNode*newNode=newLinkNode(x); newNode->link=current->link;current->link=newNode;} }

returntrue;};刪除第一種情況:刪除表中第一個元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結(jié)點

ai-1ai-1aiaiai+1ai+1pq刪除前刪除后單鏈表的刪除算法boolList::Remove(inti,int&x){//將鏈表中的第i個元素刪去,i從1開始。

LinkNode*del; //暫存刪除結(jié)點指針

if(i<=1){del=first;first=first->link;} else{LinkNode*current=first;k=1;//找i-1號結(jié)點

while(k<i-1&¤t!=NULL) {current=current->link;k++;}

if(current==NULL||current->link==NULL){

cout<<“無效的刪除位置!\n”;returnfalse;}

del=current->link; //刪中間/尾結(jié)點

current->link=del->link; } x=del->data;deletedel; //取出被刪結(jié)點數(shù)據(jù)

returntrue; };實現(xiàn)單鏈表的插入和刪除算法，不需要移動元素，只需修改結(jié)點指針，比順序表方便。情況復雜，要專門討論空表和在表頭插入的特殊情形。尋找插入或刪除位置只能沿著鏈順序檢測。帶表頭結(jié)點的單鏈表表頭結(jié)點位于表的最前端，本身不帶數(shù)據(jù)，僅標志表頭。設置表頭結(jié)點的目的是統(tǒng)一空表與非空表的操作，簡化鏈表操作的實現(xiàn)。非空表 空表0an-1a1firstfirst0在帶表頭結(jié)點的單鏈表最前端插入新結(jié)點

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp

q=p->link;p->link=q->link;deleteq;從帶表頭結(jié)點的單鏈表中刪除最前端的結(jié)點(非空表）(空表）firstfirstfirst0first0pqpq單鏈表的模板類類模板將類的數(shù)據(jù)成員和成員函數(shù)設計得更完整、更靈活。類模板更易于復用。在單鏈表的類模板定義中，增加了表頭結(jié)點。

用模板定義的單鏈表類template<classT,classE>//定義在“LinkedList.h”structLinkNode{ //鏈表結(jié)點類的定義

Edata; //數(shù)據(jù)域

LinkNode<T,E>*link;//鏈指針域

LinkNode(){link=NULL;}//構(gòu)造函數(shù)

LinkNode(Eitem,LinkNode<T,E>*ptr=NULL){data=item;link=ptr;}//構(gòu)造函數(shù)

booloperator==(Tx){returndata.key==x;} //重載函數(shù)，判相等

booloperator!=(Tx){returndata.key!=x;}};template<classT,classE>classList:publicLinearList<T,E>{//單鏈表類定義,不用繼承也可實現(xiàn)protected:

LinkNode<T,E>*first; //表頭指針public:

List(){first=newLinkNode<T,E>;}//構(gòu)造函數(shù)

List(E

x){first=newLinkNode<T,E>(x);}

List(List<T,E>&L); //復制構(gòu)造函數(shù)

~List(){} //析構(gòu)函數(shù)

voidmakeEmpty(); //將鏈表置為空表

intLength()const; //計算鏈表的長度

LinkNode<T,E>*Search(T

x); //搜索含x元素

LinkNode<T,E>*Locate(inti); //定位第i個元素

E*getData(inti); //取出第i元素值

voidsetData(inti,Ex); //更新第i元素值

boolInsert(inti,Ex); //在第i元素后插入

boolRemove(inti,E&x); //刪除第i個元素

boolIsEmpty()const //判表空否

{returnfirst->link==NULL?true:false;}LinkNode<T,E>*getFirst()const{returnfirst;}

voidsetFirst(LinkNode<T,E>*f){first=f;} voidSort(); //排序};template<classT,classE>

voidList<T,E>::makeEmpty(){

LinkNode<T,E>*q; while(first->link!=NULL){

q=first->link;//保存被刪結(jié)點

first->link=q->link;//從鏈上摘下該結(jié)點

deleteq; //刪除

}}；鏈表置空算法（保留表頭結(jié)點）firstqfirstfirstqqfirsta0a1a1a2a2a2currenttemplate<classT,classE>intList<T,E>::Length()const{ListNode<T,E>*p=first->link;//檢測指針p指示第一號結(jié)點

intcount=0;

while(p!=NULL){//逐個結(jié)點檢測

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

returncount;}求單鏈表的長度的算法firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3單鏈表的搜索算法template<classT,classE>LinkNode<T,E>*List<T,E>::Search(Tx){//在表中搜索含數(shù)據(jù)x的結(jié)點,搜索成功時函數(shù)返//該結(jié)點地址;否則返回NULL。

LinkNode<T,E>*current=first->link; while(current!=NULL&¤t->data!=x)

current=current->link; //沿著鏈找含x結(jié)點

returncurrent;};單鏈表的定位算法template<classT,classE>LinkNode<T,E>*List<T,E>::Locate(inti){//函數(shù)返回表中第i個元素的地址。若i<0或i超//出表中結(jié)點個數(shù)，則返回NULL。

if(i<0)returnNULL; //i不合理

LinkNode<T,E>*current=first;intk=0; while(current!=NULL&&k<i){current=current->link; k++;}returncurrent; //返回第i號結(jié)點地址或NULL};單鏈表的插入算法template<classT,classE>boolList<T,E>::Insert(inti,Ex){//將新元素x插入在鏈表中第i個結(jié)點之后。

LinkNode<T,E>*current=Locate(i); if(current==NULL)returnfalse; //無插入位置

LinkNode<T,E>*newNode=

newLinkNode<T,E>(x); //創(chuàng)建新結(jié)點

newNode->link=current->link;//鏈入

current->link=newNode; returntrue; //插入成功};單鏈表的刪除算法template<classT,classE>boolList<T,E>::Remove(inti,E&x){//刪除鏈表第i個元素,通過引用參數(shù)x返回元素值

LinkNode<T,E>*current=Locate(i-1); if(current==NULL||current->link==NULL)returnfalse; //刪除不成功

LinkNode<T,E>*del=current->link;current->link=del->link; x=del->data; deletedel; returntrue;};前插法建立單鏈表從一個空表開始，重復讀入數(shù)據(jù)：生成新結(jié)點將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中將該新結(jié)點插入到鏈表的前端直到讀入結(jié)束符為止。firstnewnodefirstnewnode00template<classT,classE>voidinputFront(TendTag,List<T,E>&L){LinkNode<T,E>*newNode,*newF;Eval;newF=newLinkNode<T,E>; L.setFirst(newF);//first->link默認值為NULLcin>>val;while(val!=endTag){newNode=newLinkNode<T,E>(val);newNode->link=newF->link; //插在表前端

newF->link=newNode; cin>>val;}};后插法建立單鏈表每次將新結(jié)點加在插到鏈表的表尾；設置一個尾指針last，總是指向表中最后一個結(jié)點，新結(jié)點插在它的后面；尾指針last初始時置為指向表頭結(jié)點地址。00newnodefirstnewnode00lastlastlastlasttemplate<classT,classE>voidinputRear(TendTag,List<T,E>&L){LinkNode<T,E>*newNode,*last;Eval;last=newLinkNode<T,E>; //建立鏈表的頭結(jié)點

L.setFirst(last); //為鏈表L的first賦值

cin>>val;while(val!=endTag){ //last指向當前的表尾

newNode=newLinkNode<T,E>(val);last->link=newNode;last=newNode;cin>>val; //插入到表末端

}last->link=NULL; //表收尾};多項式(Polynomial)n階多項式Pn(x)有n+1項。系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列

多項式的順序存儲表示第一種：private:(靜態(tài)數(shù)intdegree; 組表示)floatcoef[maxDegree+1];Pn(x)可以表示為：

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

i

na0

a1

a2……an………012degreemaxDegree-1coefn第二種：private: (動態(tài)數(shù) intdegree;組表示) float*coef; Polynomial::Polynomial(intsz){ degree=sz; coef=newfloat[degree+1]; }以上兩種存儲表示適用于指數(shù)連續(xù)排列的多項式。但對于絕大多數(shù)項的系數(shù)為零的多項式，如P101(x)=3+5x50-4x101,不經(jīng)濟。第三種：

structterm{//多項式的項定義

floatcoef;//系數(shù)

intexp; //指數(shù) };statictermtermArray[maxTerms];//項數(shù)組staticintfree,maxTerms;//當前空閑位置指針

a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

m初始化：//termPolynomial::termArray[MaxTerms];//intPolynomial::free=0;classPolynomial{//多項式定義public:……private:intstart,finish;//多項式始末位置}兩個多項式存儲的例子

A(x)=2.0x1000+1.8B(x)=1.2+51.3x50+3.7x101

兩個多項式存放在termArray中A.startA.finishB.startB.finishfreecoefexp1.82.01.251.33.7……01000050101……maxTerms多項式順序存儲表示的缺點插入和刪除時項數(shù)可能有較大變化，因此要移動大量數(shù)據(jù)不利于多個多項式的同時處理采用多項式的鏈表表示可以克服這類困難：多項式的項數(shù)可以動態(tài)地增長，不存在存儲溢出問題。插入、刪除方便，不移動元素。多項式的鏈表存儲表示在多項式的鏈表表示中，每個結(jié)點三個數(shù)據(jù)成員：通過鏈接指針，可以將多項式各項按指數(shù)遞增的順序鏈接成一個單鏈表。在此結(jié)構(gòu)上，新項的加入和廢項的刪除執(zhí)行簡單的鏈表插入和刪除操作即可解決。多項式的鏈表結(jié)構(gòu)coefexplink

Data

Term多項式(polynomial)類的鏈表定義structTerm{ //多項式結(jié)點定義

floatcoef; //系數(shù)

intexp; //指數(shù)

Term*link; //鏈接指針

Term(floatc,inte,Term*next=NULL){coef=c;exp=e;link=next;} Term*InsertAfter(floatc,inte);friendostream&operator<<(ostream&,constTerm&);};classPolynomial{ //多項式類的定義public: Polynomal(){first=newTerm(0,-1);} //構(gòu)造函數(shù)

Polynomal(Polynomal&R);//復制構(gòu)造函數(shù)

intmaxOrder(); //計算最大階數(shù)private: Term*first;friendostream&operator<<(ostream&,constPolynomal&);friendistream&operator>>(istream&,Polynomal&);friendvoidAdd(Polynomial&A,Polynomial&B,Polynomial&C);friendvoidMul(Polynomial&A,Polynomial&B,Polynomial&C);};Term*Term::InsertAfter(floatc,inte){//在調(diào)用此函數(shù)的對象后插入一個新項

link=newTerm(c,e,link); //創(chuàng)建一個新結(jié)點，自動鏈接

returnlink; //插入到this結(jié)點后面};ostream&operator<<(ostream&out,constTerm&x){//Term的友元函數(shù)：輸出一個項x的內(nèi)容到輸出流對//象out中去。

if(x.coef==0.0)returnout;//零系數(shù)項不輸出

out<<x.coef; //輸出系數(shù)

switch(x.exp){ //輸出指數(shù)

case0:break; //指數(shù)為0,不出現(xiàn)‘X’ case1:out<<“X”;break;//在系數(shù)后輸出‘X’ default:out<<“X^”<<x.exp;break;//否則

} returnout;};istream&operator>>(istream&in,Polynomal&x){//Polynomal類的友元函數(shù)：從輸入流in輸入各項，//用尾插法建立一個多項式。

Term*rear=x.first;intc,e; //rear是尾指針

while(1){ cout<<“Inputaterm(coef,exp):”<<endl; in>>c>>e; //輸入項的系數(shù)c和指數(shù)e if(e<0)break; //用e<0控制輸入結(jié)束

rear=rear->InsertAfter(c,e); //鏈接到rear后

} returnin;};ostream&operator<<(ostream&out,Polynomal&x){//Polynomal類的友元函數(shù)：輸出帶頭結(jié)點的多項式//鏈表x。

Term*current=x.first->link; out<<“Thepolynomalis:”<<endl; out<<*current; //調(diào)用Term的重載操作”<<” while(current!=NULL){ //逐項輸出

out<<“+”<<*current; current=current->link; } out<<endl;returnout;}; 兩個多項式的相加算法設兩個多項式都帶表頭結(jié)點，檢測指針pa和pb分別指示兩個鏈表當前檢測結(jié)點，并設結(jié)果多項式的表頭指針為C，存放指針為pc，初始位置在C的表頭結(jié)點。當pa和pb沒有檢測完各自的鏈表時，比較當前檢測結(jié)點的指數(shù)域：指數(shù)不等：小者加入C鏈，相應檢測指針pa或者pb進1；指數(shù)相等：對應項系數(shù)相加。若相加結(jié)果不為零，則結(jié)果加入C鏈，pa與pb進1。當pa或pb指針中有一個為NULL，則把另一個鏈表的剩余部分加入到C鏈。

voidAdd(Polynomal&A,Polynomal&B, Polynomal&C){ //友元函數(shù)：兩個帶表頭結(jié)點的按升冪排列的

//多項式鏈表的頭指針分別是A.first和B.first, //返回的是結(jié)果多項式鏈表C. Term*pa,*pb,*pc,*p;floattemp; pc=C.first; //結(jié)果鏈尾指針

pa=A.first->link; //A鏈檢測指針

pb=B.first->link; //B鏈檢測指針

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

if(pa->exp==pb->exp){//對應項指數(shù)相等

temp=pa->coef+pb->coef; if(fabs(temp)>0.001) pc=pc->InsertAfter(temp,pa->exp); pa=pa->link;pb=pb->link; } elseif(pa->exp<pb->exp){//pa指數(shù)小

pc=pc->InsertAfter(pa->coef,pa->exp); pa=pa->link; }else{ //pb指數(shù)小

pc=pc->InsertAfter(pb->coef,pb->exp); pb=pb->link; }

p=(pa!=NULL)?pa:pb;//p指示剩余鏈

while(p!=NULL){ pc=pc->InsertAfter(p->coef,p->exp); p=p->link; } };AH.firstBH.first

CH.first

1010-14-14-3636-910-910712712814814多項式鏈表的相加AH=1-3x6+7x12BH=-

x4+3x6

-9x10+8x14CH=1-

x4

-9x10+7x12+8x14AH.firstBH.first

CH.first10-14-3636-910712814papcpb

AH.first

CH.first

1010-14-3636-910712814papbpcBH.firstAH.first

CH.first

1010-14-14-3636-910712814papbpcBH.firstAH.first

CH.first

1010-14-14-3636-910712814papbpcBH.firsttmp=-3+3=0AH.first

CH.first1010-14-14-3636-910712814papc-910pbBH.first

AH.first

CH.first1010-14-14-3636-910712814papc-910pbBH.first712

AH.first

CH.first1010-14-14-3636-910712814papc-910pbBH.first712814

p循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表的最后一個結(jié)點的link指針不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點。循環(huán)鏈表的特點是：只要知道表中某一結(jié)點的地址，就可搜尋到所有其他結(jié)點的地址。循環(huán)鏈表的示例帶表頭結(jié)點的循環(huán)鏈表a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)template<classT,classE>structCircLinkNode{ //鏈表結(jié)點類定義

Edata; CircLinkNode<T,E>*link;CircLinkNode(CircLinkNode<T,E>*next=NULL){link=next;}CircLinkNode(Ed,CircLinkNode<T,E>*next=NULL){data=d;link=next;}boolOperator==(Ex){returndata.key==x.key;}boolOperator!=(Ex){returndata.key!=x.key;}};循環(huán)鏈表類的定義template<classT,classE>//鏈表類定義classCircList:publicLinearList<T,E>{private: CircLinkNode<T,E>*first,*last;//頭指針,尾指針public: CircList(constEx); //構(gòu)造函數(shù)

CircList(CircList<T,E>&L);//復制構(gòu)造函數(shù) ～CircList(); //析構(gòu)函數(shù)

intLength()const; //計算鏈表長度

boolIsEmpty(){returnfirst->link==first;}//判表空否

CircLinkNode<T,E>*getHead()const; //返回表頭結(jié)點地址

voidsetHead(CircLinkNode<T,E>*p);//設置表頭結(jié)點地址

CircLinkNode<T,E>*Search(Tx); //搜索

CircLinkNode<T,E>*Locate(inti); //定位

E*getData(inti); //提取

voidsetData(inti,Ex); //修改

boolInsert(inti,Ex); //插入

boolRemove(inti,E&x); //刪除};循環(huán)鏈表與單鏈表的操作實現(xiàn)，最主要的不同就是掃描到鏈尾，遇到的不是NULL，而是表頭。搜索不成功循環(huán)鏈表的搜索算法搜索25搜索成功搜索15first31481557

currentcurrentcurrentfirst31481557

currentcurrentcurrentcurrentcurrent循環(huán)鏈表的搜索算法template<classT,classE>CircListNode<T,E>*CircList<T,E>::Search(T

x

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

current=first->link;

while(current!=first

&¤t->data!=x)

current=current->link;returncurrent;}帶尾指針的循環(huán)鏈表rear3148155722如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。在表尾插入，時間復雜性O(1)在表尾刪除，時間復雜性O(n)在表頭插入，相當于在表尾插入在表頭刪除，時間復雜性O(1)用循環(huán)鏈表求解約瑟夫問題約瑟夫問題的提法n個人圍成一個圓圈，首先第1個人從1開始，一個人一個人順時針報數(shù),報到第m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。用不帶表頭結(jié)點的循環(huán)鏈表來組織。例如n=8m=3012345671234567801234567123456780123456712345678012345671234567801234567123456780123456712345678n=8m=3012345671234567801234567123456780123456712345678求解Josephus問題的算法#include<iostream.h>#include“CircList.h”template<classT,classE>voidJosephus(CircList<T,E>&Js,intn,intm){CircLinkNode<T,E>*p=Js.getHead(),*pre=NULL;

inti,j;

for(i=0;i<n-1;i++){ //執(zhí)行n-1次

for(j=1;j<m;j++) //數(shù)m-1個人

{pre=p;p=p->link;}

cout<<“出列的人是”<<p->data<<endl;

pre->link=p->link;deletep; //刪去

p=pre->link; }};

voidmain(){

CircList<int,int>clist;inti,nm; cout<<“輸入游戲者人數(shù)和報數(shù)間隔:”;

cin>>n>>m;for(i=1;i<=n;i++)clist.insert(i,i);//約瑟夫環(huán)

Josephus(clist,n,m);

//解決約瑟夫問題}

雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅(qū)和后繼方向都能游歷（遍歷）的線性鏈表。雙向鏈表每個結(jié)點結(jié)構(gòu)：

雙向鏈表通常采用帶表頭結(jié)點的循環(huán)鏈表形式。前驅(qū)方向

后繼方向lLinkdatarLink結(jié)點指向

p==p->lLink->rLink==p->rLink->lLink非空表

空表p->lLinkp->rLinkplLinkrLinkfirstfirst雙向循環(huán)鏈表類的定義template<classT,classE>structDblNode{ //鏈表結(jié)點類定義Edata; //鏈表結(jié)點數(shù)據(jù)DblNode<T,E>*lLink,*rLink; //前驅(qū)、后繼指針DblNode(DblNode<T,E>*l=NULL,DblNode<T,E>*r=NULL){lLink=l;rLink=r;}//構(gòu)造函數(shù)DblNode(Evalue,DblNode<T,E>*l=NULL,DblNode<T,E>*r=NULL)

{data=value;lLink=l;rLink=r;}//構(gòu)造函數(shù)};template<classT,classE>classDblList{ //鏈表類定義public:DblList(EuniqueVal){ //構(gòu)造函數(shù)

first=newDblNode<T,E>(uniqueVal);first->rLink=first->lLink=first;};DblNode<T,E>*getFirst()const{returnfirst;}voidsetFirst(DblNode<T,E>*ptr){first=ptr;}DblNode<T,E>*Search(Tx,intd);

//在鏈表中按d指示方向?qū)ふ业扔诮o定值x的結(jié)點,

//d=0按前驅(qū)方向,d≠0按后繼方向DblNode<T,E>*Locate(inti,intd); //在鏈表中定位序號為i(≥0)的結(jié)點,d=0按前驅(qū)方

//向,d≠0按后繼方向boolInsert(inti,Ex,intd);

//在第i個結(jié)點后插入一個包含有值x的新結(jié)點,d=