數(shù)據(jù)結(jié)構(gòu)課件：第二章 線性表

1第二章線性表線性表順序表單鏈表多項式循環(huán)鏈表雙向鏈表2線性表(LinearList)線性表的定義線性表是n(≥0)個數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）

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

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

a1a2a3a4a5a64線性表的抽象基類

template<typenameT>classLinearList{public:LinearList();

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

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

virtualintSize()const=0;

//求表最大體積

virtualintLength()const=0;

//求表長度

virtualintSearch(Tx)const=0;

//搜索

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

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

//取值

virtualvoidsetData(inti,Tx)=0;

//賦值

5

virtualboolInsert(inti,Tx)=0;

//插入

virtualboolRemove(inti,T&x)=0;

//刪除

virtualboolIsEmpty()const=0;

//判表空

virtualboolIsFull()const=0;

//判表滿

virtualvoidSort()=0；

//排序

virtualvoidinput()=0；

//輸入

virtualvoidoutput()=0；

//輸出

virtualLinearList<T>operator= (LinearList<T>&L)=0; //復(fù)制};線性表的存儲表示有兩種：順序存儲方式和鏈表存儲方式。

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

253457164809

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

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

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

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

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

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

charch; //按data.ch引用

floatdir; //按data.dir引用

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

}data;//整體上是同一類型data

25‘s’3.36274‘t’1.0‘6’9順序表(SeqList)類的定義#include<iostream.h>

//定義在“seqList.h”中#include<stdlib.h>#include"LinearList.h"constintdefaultSize=100;template<typenameT>classSeqList:publicLinearList<T>{protected: T*data; //存放數(shù)組

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

intn; //當(dāng)前已存表項數(shù)

voidreSize(intnewSize); //改變數(shù)組空間大小10public:

SeqList(intsz=defaultSize);//構(gòu)造函數(shù)

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

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

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

intLength()const{returnn;}//計算表長度

intSearch(Tx)const;

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

intLocate(inti)const;

//定位第i個表項，函數(shù)返回表項序號

boolInsert(inti,Tx); //插入

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

……};}11順序表的構(gòu)造函數(shù)#include<stdlib.h>//操作“exit”存放在此#include“seqList.h”//操作實現(xiàn)放在“seqList.cpp”template<typenameT>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);} }};12template<typenameT>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);} Tx;

for(inti=1;i<=n;i++)//傳送各個表項

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

for(inti=1;i<=n;i++) //順序搜索

if(data[i-1]==x)returni;

//表項序號和表項位置差1

return0;

//搜索失敗};14順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功152534571648

01234data搜索

50i2534571648

i2534571648

i2534571648

i2534571648

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

pi

是搜索第

i項的概率

ci

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

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

次搜索性能分析17表項的插入2534571648096301234567data50插入x253457501648096301234567data50i18表項的插入算法template<typenameT>boolSeqList<T>::Insert(inti,Tx){//將新元素x插入到表中第i(1≤i≤n+1)個表項位//置。函數(shù)返回插入成功的信息

if(n==maxSize)returnfalse;//表滿

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

for(intj=n;j>=i;j--)//依次后移

data[j]=data[j-1];

data[i-1]=x;

//插入(第i表項在data[i-1]處) n++;

returntrue;

//插入成功};19插入算法的性能分析在表中第i個位置插入，從data[i-1]

到data[n-1]成塊后移，移動n-1-(i-1)+1=n-i+1項。考慮所有插入位置，相等插入概率時，從1到n+1，平均移動元素個數(shù)為:20表項的刪除253457501648096301234567data16刪除

x2534575048096301234567data21表項的刪除算法template<typenameT>boolSeqList<T>::Remove(inti,

T&x){//從表中刪除第i(1≤i≤n)個表項，通過引用型參//數(shù)x返回被刪元素。函數(shù)返回刪除成功信息

if(n==0)returnfalse;

//表空

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

x=data[i-1];

for(intj=i;j<=n-1;j++)//依次前移，填補(bǔ)

data[j-1]=data[j]; n--;returntrue;

};

22刪除算法的性能分析刪除第i個表項，需將第i+1項到第

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

n-(i+1)+1=n-i考慮表中所有可能刪除位置（1≤i≤n-1）,相等刪除概率時，平均移動元素個數(shù)為：23順序表的應(yīng)用：集合的“并”運(yùn)算voidUnion(SeqList<int,int>&LA,SeqList<int,int>&LB){

intn1=LA.Length(),n2=LB.Length();inti,k,x;

for(i=0;i<n2;i++){

x=LB.getData(i);

//在LB中取一元素

k=LA.Search(x);

//在LA中搜索它

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

{LA.Insert(n1,x);n1++;}

//插入到第n個表項位置}}24

voidIntersection(SeqList<int,int>

&LA,SeqList<int,int>

&LB){

intn1=LA.Length();intx,k,i=0;

while(i<n1){

x=LA.getData(i);//在LA中取一元素

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

if(k==0)

//若在LB中未找到

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

elsei++;//未找到在A中刪除它

}}順序表的應(yīng)用：集合的“交”運(yùn)算25特點(diǎn)每個元素(表項)由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點(diǎn)之間可以連續(xù)，可以不連續(xù)存儲結(jié)點(diǎn)的邏輯順序與物理順序可以不一致表可擴(kuò)充單鏈表(SinglyLinkedList)datalinka1a2a3a4a5Λfirst26單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3freefirst(b)經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu)27單鏈表的結(jié)構(gòu)定義在C中定義單鏈表的結(jié)構(gòu)十分簡單：

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

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

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

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

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

鏈表結(jié)點(diǎn)(ListNode)類鏈表(List)類定義方式

復(fù)合方式嵌套方式

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

classList;

//復(fù)合方式

classListNode{

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

friendclassList;

//鏈表類為其友元類

private:

intdata;

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

整型

ListNode*link;

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

};classList{

//鏈表類

private:ListNode*first;

//表頭指針

};30classList{

//嵌套方式private:

classListNode{

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

public:

intdata;

ListNode*link;

};ListNode*first;

//表頭指針public:

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

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

protected:

intdata;

ListNode*link;

};classList:public

classListNode{

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

private:ListNode*first;

//表頭指針};32在復(fù)合方式中，鏈表結(jié)點(diǎn)類中聲明鏈表類是它的友元類，這樣可以“奉獻(xiàn)”它的私有成員給鏈表類。這種方式靈活。在嵌套方式中，鏈表結(jié)點(diǎn)類是鏈表類的私有成員，這樣限制了鏈表結(jié)點(diǎn)類的應(yīng)用范圍。在繼承方式中，鏈表類聲明為鏈表結(jié)點(diǎn)類的派生類，這在實現(xiàn)上是可行的。但在邏輯上是有問題的，如三角形

is

多邊形（繼承關(guān)系）鏈表is

鏈表結(jié)點(diǎn)（顯然概念不準(zhǔn)確）33//鏈表類和鏈表結(jié)點(diǎn)類定義(結(jié)構(gòu)方式)structListNode{

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

intdata;

ListNode*link;

};classList{

//鏈表類,直接使用鏈表結(jié)點(diǎn)類的數(shù)據(jù)和操作

private:ListNode*first;

//表頭指針

};//鏈表中的結(jié)點(diǎn)屬于鏈表私有，別人無法訪問34單鏈表中的插入與刪除操作插入

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

newnode->link=first;

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

firstnewnodenewnodefirst35(插入前)(插入后)

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

newnode->link=current->link;

current->link=newnode；newnodecurrentnewnodecurrent36

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

newnode->link=current->link;

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

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

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

LinkNode*newNode=newLinkNode(x);

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

newNode->link=first;first=newNode;

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

}

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

LinkNode*current=first; intk=1;38

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

{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;};39刪除第一種情況:刪除表中第一個元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結(jié)點(diǎn)ai-1ai-1aiaiai+1ai+1pq刪除前刪除后40單鏈表的刪除算法boolList::Remove(inti,int&x){//將鏈表中的第i個元素刪去,i從1開始。

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

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

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

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

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

41 del=current->link;

//刪中間/尾結(jié)點(diǎn)

current->link=del->link; } x=del->data;deletedel;

//取出被刪結(jié)點(diǎn)數(shù)據(jù)

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

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

q=p->link;

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

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

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

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

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

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

booloperator==(Tx){returndata.key==x;}

//重載函數(shù)，判相等

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

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

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

List(T

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

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

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

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

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

LinkNode<T>*Search(T

x); //搜索含x元素

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

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

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

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

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

boolIsEmpty()const //判表空否

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

voidsetFirst(LinkNode<T>*f){first=f;} voidSort(); //排序};49template<typenameT>

voidList<T>::makeEmpty(){

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

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

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

deleteq; //刪除

}}；鏈表置空算法（保留表頭結(jié)點(diǎn)）50firstqfirstfirstqqfirsta0a1a1a2a2a2current51template<typenameT>intList<T>::Length()const{ListNode<T>*p=first->link;

//檢測指針p指示第一號結(jié)點(diǎn)

intcount=0;

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

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

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

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

current=current->link;

//沿著鏈找含x結(jié)點(diǎn)

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

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

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

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

LinkNode<T>*newNode=

newLinkNode<T>(x); //創(chuàng)建新結(jié)點(diǎn)

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

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

LinkNode<T>*current=Locate(i-1); if(current==NULL||current->link==NULL)

returnfalse; //刪除不成功

LinkNode<T>*del=current->link;

current->link=del->link;

x=del->data; deletedel; returntrue;};57前插法建立單鏈表從一個空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。firstnewnodefirstnewnode0058template<typenameT>voidinputFront(TendTag,List<T>&L){LinkNode<T>*newNode,*newF;Tval;

newF=newLinkNode<T>;

L.setFirst(newF);//first->link默認(rèn)值為NULL

cin>>val;while(val!=endTag){

newNode=newLinkNode<T>(val);

newNode->link=newF->link; //插在表前端

newF->link=newNode; cin>>val;}};59后插法建立單鏈表每次將新結(jié)點(diǎn)加在插到鏈表的表尾；設(shè)置一個尾指針last，總是指向表中最后一個結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；尾指針last

初始時置為指向表頭結(jié)點(diǎn)地址。00newnodefirstnewnode00lastlastlastlast60template<typenameT>voidinputRear(TendTag,List<T>&L){

LinkNode<T>*newNode,*last;Tval;

last=newLinkNode<T>; //建立鏈表的頭結(jié)點(diǎn)

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

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

newNode=newLinkNode<T>(val);

last->link=newNode;last=newNode;cin>>val; //插入到表末端

}

last->link=NULL; //表收尾

};61多項式(Polynomial)n階多項式Pn(x)有n+1項。

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

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

多項式的順序存儲表示第一種：

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

intdegree; 組表示)floatcoef[maxDegree+1];

Pn(x)可以表示為：

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

i

na0

a1

a2……an………012degreemaxDegree-1coefn63第二種：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)濟(jì)。64第三種：

structterm{

//多項式的項定義

floatcoef;//系數(shù)

intexp; //指數(shù)

};statictermtermArray[maxTerms];//項數(shù)組

staticintfree,maxTerms;//當(dāng)前空閑位置指針

a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

m65初始化：//termPolynomial::termArray[MaxTerms];//intPolynomial::free=0;class

Polynomial{//多項式定義public:……private:intstart,finish;//多項式始末位置}66兩個多項式存儲的例子

A(x)=2.0x1000+1.8

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

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

DataTerm69多項式(polynomial)類的鏈表定義structTerm{

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

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&);};70classPolynomial{

//多項式類的定義public: Polynomal(){first=newTerm(0,-1);} //構(gòu)造函數(shù)

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

intmaxOrder(); //計算最大階數(shù)private: Term*first;

friendostream&operator<<(ostream&,constPolynomal&);friendistream&operator>>(istream&,

Polynomal&);71friendvoidAdd(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é)點(diǎn)，自動鏈接

returnlink; //插入到this結(jié)點(diǎn)后面};

72ostream&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;};73istream&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;};74ostream&operator<<(ostream&out,Polynomal&x){//Polynomal類的友元函數(shù)：輸出帶頭結(jié)點(diǎn)的多項式//鏈表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;}; 75兩個多項式的相加算法設(shè)兩個多項式都帶表頭結(jié)點(diǎn)，檢測指針pa和pb分別指示兩個鏈表當(dāng)前檢測結(jié)點(diǎn)，并設(shè)結(jié)果多項式的表頭指針為C，存放指針為pc，初始位置在C的表頭結(jié)點(diǎn)。當(dāng)pa和pb沒有檢測完各自的鏈表時，比較當(dāng)前檢測結(jié)點(diǎn)的指數(shù)域：指數(shù)不等：小者加入C鏈，相應(yīng)檢測指針pa或者pb進(jìn)1；指數(shù)相等：對應(yīng)項系數(shù)相加。若相加結(jié)果不為零，則結(jié)果加入C鏈，pa與pb進(jìn)1。76當(dāng)pa或pb指針中有一個為NULL，則把另一個鏈表的剩余部分加入到C鏈。

voidAdd(Polynomal&A,Polynomal&B, Polynomal&C){

//友元函數(shù)：兩個帶表頭結(jié)點(diǎn)的按升冪排列的

//多項式鏈表的頭指針分別是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)77

if(pa->exp==pb->exp){//對應(yīng)項指數(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; } 78

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

while(p!=NULL){ pc=pc->InsertAfter(p->coef,p->exp); p=p->link; } };79AH.firstBH.firstCH.first1010-14-14-3636-910-910712712814814多項式鏈表的相加AH=1-3x6+7x12BH=-

x4+3x6

-9x10+8x14CH=1-

x4

-9x10

+7x12+8x1480AH.firstBH.firstCH.first10-14-3636-910712814papcpb81AH.firstCH.first1010-14-3636-910712814papbpcBH.first82AH.firstCH.first1010-14-14-3636-910712814papbpcBH.first83AH.firstCH.first1010-14-14-3636-910712814papbpcBH.firsttmp=-3+3=084AH.firstCH.first1010-14-14-3636-910712814papc-910pbBH.first85AH.firstCH.first1010-14-14-3636-910712814papc-910pbBH.first71286AH.firstCH.first1010-14-14-3636-910712814papc-910pbBH.first712814p87循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表的最后一個結(jié)點(diǎn)的link

指針不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。88循環(huán)鏈表的示例帶表頭結(jié)點(diǎn)的循環(huán)鏈表

a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)89template<typenameT>structCircLinkNode{ //鏈表結(jié)點(diǎn)類定義

Tdata; CircLinkNode<T>*link;CircLinkNode(CircLinkNode<T>*next=NULL){link=next;}CircLinkNode(Td,CircLinkNode<T>*next=NULL){data=d;link=next;}

boolOperator==(Tx){returndata.key==x.key;}boolOperator!=(Tx){returndata.key!=x.key;}};循環(huán)鏈表類的定義90template<typenameT>//鏈表類定義classCircList:publicLinearList<T>{private:

CircLinkNode<T>*first,*last;//頭指針,尾指針public: CircList(constTx);

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

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

～CircList(); //析構(gòu)函數(shù)

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

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

CircLinkNode<T>*getHead()const;

//返回表頭結(jié)點(diǎn)地址91

voidsetHead(CircLinkNode<T>*p);

//設(shè)置表頭結(jié)點(diǎn)地址

CircLinkNode<T>*Search(Tx);

//搜索

CircLinkNode<T>*Locate(inti);

//定位

T*getData(inti); //提取

voidsetData(inti,Tx); //修改

boolInsert(inti,Tx);

//插入

boolRemove(inti,T&x);

//刪除};循環(huán)鏈表與單鏈表的操作實現(xiàn)，最主要的不同就是掃描到鏈尾，遇到的不是NULL，而是表頭。92搜索不成功循環(huán)鏈表的搜索算法搜索25搜索成功搜索15first31481557currentcurrentcurrentfirst31481557currentcurrentcurrentcurrentcurrent93循環(huán)鏈表的搜索算法template<typenameT>CircListNode<T>*CircList<T>::Search(T

x

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

current=first->link;

while(current!=first

&¤t->data!=x)

current=current->link;returncurrent;}94帶尾指針的循環(huán)鏈表rear3148155722如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。在表尾插入，時間復(fù)雜性O(shè)(1)在表尾刪除，時間復(fù)雜性O(shè)(n)在表頭插入，相當(dāng)于在表尾插入在表頭刪除，時間復(fù)雜性O(shè)(1)95用循環(huán)鏈表求解約瑟夫問題約瑟夫問題的提法n個人圍成一個圓圈，首先第1個人從1開始，一個人一個人順時針報數(shù),報到第m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。用不帶表頭結(jié)點(diǎn)的循環(huán)鏈表來組織。96例如n=8m=301234567123456780123456712345678012345671234567801234567123456780123456712345678012345671234567897n=8m=301234567123456780123456712345678012345671234567898求解Josephus問題的算法

#include<iostream.h>#include“CircList.h”template<typenameT>voidJosephus(CircList<T>&Js,intn,intm){CircLinkNode<T>*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;

99pre->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);