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

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

（a1,a2,…,an）

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

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

a1a2a3a4a5a64線性表的抽象基類

template<classT>classLinearList{public:LinearList(); //構(gòu)造函數(shù)～LinearList(); //析構(gòu)函數(shù)virtualintSize()const=0; //求表最大體積virtualintLength()const=0; //求表長(zhǎng)度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； //輸出//復(fù)制virtualvoidoperator=(LinearList<T,E>&L)=0;};程序：SequentialList線性表的存儲(chǔ)表示有2種：順序存儲(chǔ)方式和鏈表存儲(chǔ)方式。6順序表(SequentialList)順序表的定義將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中?？衫靡痪S數(shù)組描述存儲(chǔ)結(jié)構(gòu)順序表的特點(diǎn)所有元素的邏輯先后順序與其物理存放順序一致

253457164809

012345data7順序表的靜態(tài)存儲(chǔ)和動(dòng)態(tài)存儲(chǔ)#definemaxSize100typedefintT;typedefstruct{Tdata[maxSize];//順序表的靜態(tài)存儲(chǔ)表示intn;}SeqList;typedefintT;typedefstruct{T*data;//順序表的動(dòng)態(tài)存儲(chǔ)表示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; //最大可容納表項(xiàng)的項(xiàng)數(shù)intlast; //當(dāng)前已存表項(xiàng)數(shù) voidreSize(intnewSize); //改變數(shù)組空間大小9public: 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{returnlast+1;}//計(jì)算表長(zhǎng)度intSearch(T&x)const;

//搜索x在表中位置，函數(shù)返回表項(xiàng)序號(hào)intLocate(inti)const;

//定位第i個(gè)表項(xiàng)，函數(shù)返回表項(xiàng)序號(hào)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)建表存儲(chǔ)數(shù)組 if(data==NULL) //動(dòng)態(tài)分配失敗{cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl;exit(1);} }}11template<classT>SeqList<T>::SeqList(SeqList<T>&L){ maxSize=L.Size();last=L.Length()-1; data=newT[maxSize]; //創(chuàng)建存儲(chǔ)數(shù)組if(data==NULL) //動(dòng)態(tài)分配失敗{cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl;exit(1);} for(inti=1;i<=n;i++)//傳送各個(gè)表項(xiàng) data[i-1]=L.getData(i);}復(fù)制構(gòu)造函數(shù)12順序表的搜索算法template<classT>intSeqList<T>::search(T&x)const{//在表中順序搜索與給定值x匹配的表項(xiàng)，找到則//函數(shù)返回該表項(xiàng)是第幾個(gè)元素，否則函數(shù)返回0for(inti=0;i<=last;i++) //順序搜索if(data[i]==x)returni+1;

//表項(xiàng)序號(hào)和表項(xiàng)位置差1 return0; //搜索失敗}13順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功142534571648

01234data搜索

50i2534571648

i2534571648

i2534571648

i2534571648

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

pi

是搜索第i項(xiàng)的概率

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

搜索不成功，數(shù)據(jù)比較n次搜索性能分析16表項(xiàng)的插入2534571648096301234567data50插入x253457501648096301234567data50i17表項(xiàng)的插入算法template<classT>boolSeqList<T>::Insert(inti,T&x){//將新元素x插入到表中第i(0≤i≤last+1)個(gè)表項(xiàng)位//置。函數(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個(gè)位置data[i]=x; //插入 last++;returntrue; //插入成功}18插入算法的性能分析將新表項(xiàng)插入到第i個(gè)表項(xiàng)后面時(shí)，必須從后向前循環(huán)，逐個(gè)向后移動(dòng)n-i項(xiàng)。最好情形為在第n個(gè)表項(xiàng)后面追加，移動(dòng)表項(xiàng)個(gè)數(shù)為0，最差情形為在第1個(gè)表項(xiàng)位置插入新表項(xiàng)，移動(dòng)表項(xiàng)個(gè)數(shù)為n考慮所有插入位置，相等插入概率時(shí)，平均移動(dòng)元素個(gè)數(shù)為:19表項(xiàng)的刪除253457501648096301234567data16刪除x2534575048096301234567data20表項(xiàng)的刪除算法template<classT>boolSeqList<T>::Remove(inti,T&x){//從表中刪除第i(1≤i≤last+1)個(gè)表項(xiàng)，通過(guò)引用型參數(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++)//依次前移，填補(bǔ)data[j-1]=data[j]; last--;returntrue; }21刪除算法的性能分析刪除第i個(gè)表項(xiàng)，必須從前向后循環(huán)，逐個(gè)移動(dòng)n-i個(gè)表項(xiàng)，最好情形是刪去的第n個(gè)表項(xiàng)，移動(dòng)表項(xiàng)個(gè)數(shù)為0，最差情形是刪去第1個(gè)表項(xiàng)，移動(dòng)表項(xiàng)個(gè)數(shù)為n-1考慮表中所有可能刪除位置,相等刪除概率時(shí)，平均移動(dòng)元素個(gè)數(shù)為：22順序表的應(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++){LB.getData(i,x);

//在LB中取一元素 k=LA.Search(x);

//在LA中搜索它

if(k==0) //若在LA中未找到插入它 {LA.Insert(n1,x);n1++;}

//插入到第n個(gè)表項(xiàng)位置}}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)用：集合的“交”運(yùn)算24特點(diǎn)每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)

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

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

intdata; LinkNode*link; };classList{

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

private:ListNode*first;

//表頭指針};//鏈表中的結(jié)點(diǎn)屬于鏈表私有，別人無(wú)法訪問(wèn)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個(gè)結(jié)點(diǎn)之后。i從1開始，//i=0表示插入到首元結(jié)點(diǎn)之前。if(first==NULL||i==0){ //空表或首元結(jié)點(diǎn)前 LinkNode*newNode=newLinkNode(x); //建立一個(gè)新結(jié)點(diǎn)

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

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

newnode->link=current->link;

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

del=current->link;

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

用模板定義的單鏈表類template<classT>//定義在“LinkedList.h”structLinkNode{ //鏈表結(jié)點(diǎn)類的定義 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); //復(fù)制構(gòu)造函數(shù) ~List(){makeEmpty();} //析構(gòu)函數(shù)

voidmakeEmpty(); //將鏈表置為空表 intLength()const; //計(jì)算鏈表的長(zhǎng)度40LinkNode<T>*Search(Tx); //搜索含x元素 LinkNode<T>*Locate(inti); //定位第i個(gè)元素boolgetData(inti,T&x); //取出第i元素值voidsetData(inti,T&x); //更新第i元素值 boolInsert(inti,T&x); //在第i元素后插入 boolRemove(inti,T&x); //刪除第i個(gè)元素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é)點(diǎn) first->link=q->link;//從鏈上摘下該結(jié)點(diǎn) deleteq; //刪除 }}鏈表置空算法（保留表頭結(jié)點(diǎn)）42template<classT>intList<T>::Length()const{LinkNode<T>*p=first->link;

//檢測(cè)指針p指示第一號(hào)結(jié)點(diǎn)intcount=0;

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

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

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

//沿著鏈找含x結(jié)點(diǎn) returncurrent;}44單鏈表的定位算法template<classT>LinkNode<T,E>*List<T>::Locate(inti){//函數(shù)返回表中第i個(gè)元素的地址。若i<0或i超//出表中結(jié)點(diǎn)個(gè)數(shù)，則返回NULL。 if(i<0)returnNULL; //i不合理 LinkNode<T>*current=first;intk=0; while(current!=NULL&&k<i){current=current->link; k++;}returncurrent; //返回第i號(hào)結(jié)點(diǎn)地址或NULL}45單鏈表的插入算法template<classT>boolList<T>::Insert(inti,T&x){//將新元素x插入在鏈表中第i個(gè)結(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; //插入成功}46單鏈表的刪除算法template<classT>boolList<T,E>::Remove(inti,T&x){//刪除鏈表第i個(gè)元素,通過(guò)引用參數(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前插法建立單鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。firstnewnodefirstnewnode0048template<classT>voidList::inputFront(TendTag){LinkNode<T>*newNode,Tval;MakeEmpty(); cin>>val;while(val!=endTag){newNode=newLinkNode<T>(val);if(newNode==NULL) {cerr<<“存儲(chǔ)分配錯(cuò)誤”<<endl;exit(1);}newNode->link=first->link; //插在表前端 first->link=newNode; cin>>val;}}49循環(huán)鏈表最后一個(gè)節(jié)點(diǎn)不是指向空，而是指向第一個(gè)節(jié)點(diǎn)an-1firsta1a0first(空表)(非空表)50循環(huán)鏈表的插入51約瑟夫問(wèn)題用循環(huán)鏈表求解約瑟夫問(wèn)題n個(gè)人圍成一個(gè)圓圈，首先第2個(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=352約瑟夫問(wèn)題的解法#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個(gè)人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);//解決約瑟夫問(wèn)題}542.4.2雙向鏈表(DoublyLinkedList)雙向鏈表結(jié)點(diǎn)結(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(“存儲(chǔ)分配錯(cuò)!\n”);exit(1);}first->prior=first->next=first;

//表頭結(jié)點(diǎn)的鏈指針指向自己}57計(jì)算雙向循環(huán)鏈表的長(zhǎng)度intLength(DblListfirst){//計(jì)算帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的長(zhǎng)度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é)點(diǎn)*p后插入25firstfirst314815pp31482515q59雙向循環(huán)鏈表的插入(空表)

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

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

pqfirst25f