數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο笳Z言描述-殷人昆-第二章

第二章線性表數(shù)據(jù)結(jié)構(gòu)電子教案主講：楊同峰1第二章線性表線性表順序表單鏈表2線性表(LinearList)線性表的定義線性表是n(≥0)個數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）

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

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

a1a2a3a4a5a64線性表的抽象基類

template<classT>classLinearList{public:LinearList(); //構(gòu)造函數(shù)～LinearList(); //析構(gòu)函數(shù)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;//賦值

5virtualboolInsert(inti,T&x)=0;//插入virtualboolRemove(inti,T&x)=0; //刪除virtualboolIsEmpty()const=0; //判表空

virtualboolIsFull()const=0; //判表滿virtualvoidSort()=0； //排序virtualvoidinput()=0； //輸入virtualvoidoutput()=0； //輸出//復制virtualvoidoperator=(LinearList<T,E>&L)=0;};程序：SequentialList線性表的存儲表示有2種：順序存儲方式和鏈表存儲方式。6順序表(SequentialList)順序表的定義將線性表中的元素相繼存放在一個連續(xù)的存儲空間中。可利用一維數(shù)組描述存儲結(jié)構(gòu)順序表的特點所有元素的邏輯先后順序與其物理存放順序一致

253457164809

012345data7順序表的靜態(tài)存儲和動態(tài)存儲#definemaxSize100typedefintT;typedefstruct{Tdata[maxSize];//順序表的靜態(tài)存儲表示intn;}SeqList;typedefintT;typedefstruct{T*data;//順序表的動態(tài)存儲表示intmaxSize,n;}SeqList;8順序表(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; //當前已存表項數(shù) voidreSize(intnewSize); //改變數(shù)組空間大小9public: 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ù)返回表項序號intLocate(inti)const;

//定位第i個表項，函數(shù)返回表項序號boolInsert(inti,T&x); //插入 boolRemove(inti,T&x); //刪除};}10順序表的構(gòu)造函數(shù)//操作“exit”存放在此template<classT>SeqList<T>::SeqList(intsz){ if(sz>0){maxSize=sz;last=-1; data=newT[maxSize]; //創(chuàng)建表存儲數(shù)組 if(data==NULL) //動態(tài)分配失敗{cerr<<"存儲分配錯誤！"<<endl;exit(1);} }}11template<classT>SeqList<T>::SeqList(SeqList<T>&L){ maxSize=L.Size();last=L.Length()-1; data=newT[maxSize]; //創(chuàng)建存儲數(shù)組if(data==NULL) //動態(tài)分配失敗{cerr<<"存儲分配錯誤！"<<endl;exit(1);} for(inti=1;i<=n;i++)//傳送各個表項 data[i-1]=L.getData(i);}復制構(gòu)造函數(shù)12順序表的搜索算法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; //搜索失敗}13順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功142534571648

01234data搜索

50i2534571648

i2534571648

i2534571648

i2534571648

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

pi

是搜索第i項的概率

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

搜索不成功，數(shù)據(jù)比較n次搜索性能分析16表項的插入2534571648096301234567data50插入x253457501648096301234567data50i17表項的插入算法template<classT>boolSeqList<T>::Insert(inti,T&x){//將新元素x插入到表中第i(0≤i≤last+1)個表項位//置。函數(shù)返回插入成功的信息if(last==maxSize-1)returnfalse;//表滿 if(i<0||i>last+1)returnfalse; //參數(shù)i不合理for(intj=last;j>=i;j--)//依次后移data[j]=data[j-1];//空出第i個位置data[i]=x; //插入 last++;returntrue; //插入成功}18插入算法的性能分析將新表項插入到第i個表項后面時，必須從后向前循環(huán)，逐個向后移動n-i項。最好情形為在第n個表項后面追加，移動表項個數(shù)為0，最差情形為在第1個表項位置插入新表項，移動表項個數(shù)為n考慮所有插入位置，相等插入概率時，平均移動元素個數(shù)為:19表項的刪除253457501648096301234567data16刪除x2534575048096301234567data20表項的刪除算法template<classT>boolSeqList<T>::Remove(inti,T&x){//從表中刪除第i(1≤i≤last+1)個表項，通過引用型參數(shù)x返回被刪元素。函數(shù)返回刪除成功信息 if(last==-1)returnfalse; //表空if(i<1||i>last+1)returnfalse; //參數(shù)i不合理x=data[i-1]; for(intj=i;j<=last;j++)//依次前移，填補data[j-1]=data[j]; last--;returntrue; }21刪除算法的性能分析刪除第i個表項，必須從前向后循環(huán)，逐個移動n-i個表項，最好情形是刪去的第n個表項，移動表項個數(shù)為0，最差情形是刪去第1個表項，移動表項個數(shù)為n-1考慮表中所有可能刪除位置,相等刪除概率時，平均移動元素個數(shù)為：22順序表的應(yīng)用：集合的“并”運算voidUnion(SeqList<int,int>&LA,SeqList<int,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++;}

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

voidIntersection(SeqList<int,int>

&LA,SeqList<int,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中刪除它

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

結(jié)點之間可以連續(xù)，可以不連續(xù)存儲結(jié)點的邏輯順序與物理順序可以不一致表可擴充單鏈表(SinglyLinkedList)datalinka1a2a3a4a5Λfirst25單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3freefirst(b)經(jīng)過一段運行后的單鏈表結(jié)構(gòu)26//鏈表類和鏈表結(jié)點類定義(結(jié)構(gòu)方式)structLinkNode{

//鏈表結(jié)點類

intdata; LinkNode*link; };classList{

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

private:ListNode*first;

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

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

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

firstnewnodenewnodefirst28(插入前)(插入后)

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

newnode->link=current->link; current->link=newnode；newnodecurrentnewnodecurrent29

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

newnode->link=current->link; current->link=newnode；(插入前)(插入后)newnodenewnodecurrentcurrent30單鏈表的插入算法boolList::Insert(inti,int&x){//將新元素x插入到第i個結(jié)點之后。i從1開始，//i=0表示插入到首元結(jié)點之前。if(first==NULL||i==0){ //空表或首元結(jié)點前 LinkNode*newNode=newLinkNode(x); //建立一個新結(jié)點

if(newNode==NULL){cerr<<“存儲分配錯誤\n”；exit(1)} newNode->link=first;first=newNode;

//新結(jié)點成為首元結(jié)點} else{//否則，尋找插入位置LinkNode*current=first; 31 for(intk=1;k<i;k++)//找到第i個節(jié)點 if(current==NULL)break;elsecurrent=current->link; if(current==NULL)//鏈短 {cerr<<“無效的插入位置!\n”;returnfalse;}else{ //插入在鏈表的中間 LinkNode*newNode=newLinkNode(x); newNode->link=current->link;current->link=newNode;} } returntrue;}32刪除第一種情況:刪除表中第一個元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結(jié)點ai-1ai-1aiaiai+1ai+1pq刪除前刪除后33單鏈表的刪除算法boolList::Remove(inti,int&x){//將鏈表中的第i個元素刪去,i從1開始。LinkNode*del,*current; if(i<=1){del=first;first=first->link;} else{current=first;for(intk=1;k<i-1;k++)//找i-1號結(jié)點 if(current==NULL)break;elsecurrent=current->link; if(current==NULL||current->link==NULL) {cout<<“無效的刪除位置!\n”;returnfalse;} 34 del=current->link; //刪中間/尾結(jié)點 current->link=del->link; } x=del->data;deletedel; //取出被刪結(jié)點數(shù)據(jù) returntrue; };實現(xiàn)單鏈表的插入和刪除算法，不需要移動元素，只需修改結(jié)點指針，比順序表方便。情況復雜，要專門討論空表和在表頭插入的特殊情形。尋找插入或刪除位置只能沿著鏈順序檢測。35帶表頭結(jié)點的單鏈表表頭結(jié)點位于表的最前端，本身不帶數(shù)據(jù)，僅標志表頭非空表 空表0ana1firstfirst036在帶表頭結(jié)點的單鏈表最前端插入新結(jié)點

newnode->link=current->link;

current->link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pcurrentpcurrentfirstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pcurrentpcurrent37

del=current->link;

current->link=del->link;deletedel;從帶表頭結(jié)點的單鏈表中刪除最前端的結(jié)點(非空表）(空表）firstfirstfirst0first0currentdelcurrentdel38

用模板定義的單鏈表類template<classT>//定義在“LinkedList.h”structLinkNode{ //鏈表結(jié)點類的定義 Tdata; //數(shù)據(jù)域 LinkNode<T>*link;//鏈指針域LinkNode(LinkNode<T>*ptr=NULL) {link=NULL;}//構(gòu)造函數(shù) LinkNode(constT&item,LinkNode<T>*ptr=NULL){data=item;link=ptr;}//構(gòu)造函數(shù)};39template<classT>classList:publicLinearList<T>{protected: LinkNode<T>*first; //表頭指針public: List(){first=newLinkNode<T>;}//構(gòu)造函數(shù) List(T&x){first=newLinkNode<T>(x);}List(List<T>&L); //復制構(gòu)造函數(shù) ~List(){makeEmpty();} //析構(gòu)函數(shù)

voidmakeEmpty(); //將鏈表置為空表 intLength()const; //計算鏈表的長度40LinkNode<T>*Search(Tx); //搜索含x元素 LinkNode<T>*Locate(inti); //定位第i個元素boolgetData(inti,T&x); //取出第i元素值voidsetData(inti,T&x); //更新第i元素值 boolInsert(inti,T&x); //在第i元素后插入 boolRemove(inti,T&x); //刪除第i個元素boolIsEmpty()const //判表空否{returnfirst->link==NULL?true:false;}LinkNode<T>*getHead()const{returnfirst;}

voidSort(); //排序};41template<classT>

voidList<T>::makeEmpty(){ LinkNode<T>*q; while(first->link!=NULL){ q=first->link;//保存被刪結(jié)點 first->link=q->link;//從鏈上摘下該結(jié)點 deleteq; //刪除 }}鏈表置空算法（保留表頭結(jié)點）42template<classT>intList<T>::Length()const{LinkNode<T>*p=first->link;

//檢測指針p指示第一號結(jié)點intcount=0;

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

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

returncount;}求單鏈表的長度的算法43單鏈表的搜索算法template<classT>LinkNode<T>*List<T>::Search(Tx){//在表中搜索含數(shù)據(jù)x的結(jié)點,搜索成功時函數(shù)返//該結(jié)點地址;否則返回NULL。 LinkNode<T>*current=first->link; while(current!=NULL&¤t->data!=x) current=current->link;

//沿著鏈找含x結(jié)點 returncurrent;}44單鏈表的定位算法template<classT>LinkNode<T,E>*List<T>::Locate(inti){//函數(shù)返回表中第i個元素的地址。若i<0或i超//出表中結(jié)點個數(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é)點地址或NULL}45單鏈表的插入算法template<classT>boolList<T>::Insert(inti,T&x){//將新元素x插入在鏈表中第i個結(jié)點之后。LinkNode<T>*current=Locate(i); if(current==NULL)returnfalse; //插入不成功 LinkNode<T>*newNode=newLinkNode<T>(x); //創(chuàng)建新結(jié)點newNode->link=current->link;//鏈入current->link=newNode; returntrue; //插入成功}46單鏈表的刪除算法template<classT>boolList<T,E>::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;}47前插法建立單鏈表從一個空表開始，重復讀入數(shù)據(jù)：生成新結(jié)點將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中將該新結(jié)點插入到鏈表的前端直到讀入結(jié)束符為止。firstnewnodefirstnewnode0048template<classT>voidList::inputFront(TendTag){LinkNode<T>*newNode,Tval;MakeEmpty(); cin>>val;while(val!=endTag){newNode=newLinkNode<T>(val);if(newNode==NULL) {cerr<<“存儲分配錯誤”<<endl;exit(1);}newNode->link=first->link; //插在表前端 first->link=newNode; cin>>val;}}49循環(huán)鏈表最后一個節(jié)點不是指向空，而是指向第一個節(jié)點an-1firsta1a0first(空表)(非空表)50循環(huán)鏈表的插入51約瑟夫問題用循環(huán)鏈表求解約瑟夫問題n個人圍成一個圓圈，首先第2個人從1開始一個人一個人順時針報數(shù),報到第m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。例如n=8m=352約瑟夫問題的解法#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();cout<<“Deleteperson”<<getData()<<endl;//數(shù)m-1個人Remove();//刪去}}53voidmain(){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);//解決約瑟夫問題}542.4.2雙向鏈表(DoublyLinkedList)雙向鏈表結(jié)點結(jié)構(gòu)：priordatanext指向直接前驅(qū)指向直接后繼非空表空表firstfirst55雙向循環(huán)鏈表的定義typedefintListData;typedefstructdnode{ListNodedata;structdnode*prior,*next;}DblNode;typedefDblNode*DblList;56建立空的雙向循環(huán)鏈表voidCreateDblList(DblList&first){first=(DblNode*)malloc(sizeof(DblNode));if(first==NULL){print(“存儲分配錯!\n”);exit(1);}first->prior=first->next=first;

//表頭結(jié)點的鏈指針指向自己}57計算雙向循環(huán)鏈表的長度intLength(DblListfirst){//計算帶表頭結(jié)點的雙向循環(huán)鏈表的長度DblNode*p=first->next;intcount=0;while(p!=first){p=p->next;count++;}returncount;}58雙向循環(huán)鏈表的插入(非空表)

q->prior=p; q->next=p->next;p->next=q;q->next->prior=q;在結(jié)點*p后插入25firstfirst314815pp31482515q59雙向循環(huán)鏈表的插入(空表)

q->prior=p; q->next=p->next;

p->next=q;q->next->prior=q;

pqfirst25f