數據結構講義

數據結構王源2016年9月第2章線性表

2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項式的算術運算實驗二、鏈表及其應用

2.1線性表ADT線性表的定義線性表是n(0)個元素a0,a1,…,an-1的線性序列，記為:(a0,a1,…,an-1)。其中n是線性表中元素的個數，稱為線性表的長度；n=0時稱為空表。

ai是表中下標為i的元素（i=0,1,…,n-1），稱ai是ai+1的直接前驅元素，ai+1是ai的直接后繼元素。線性表是動態(tài)數據結構，它的表長可以改變。

線性表ADTADTLinearList{數據：

0個或多個元素的線性序列（a0,a1,...,an-1），其最大允許長度為MaxListSize。運算：

Create()：創(chuàng)建一個空線性表。

Destroy()：撤消一個線性表。

IsEmpty()：若線性表空，則返回true；否則返回false。

Length()：返回表中元素個數。

Find(i,x)：在x中返回表中下標為i的元素ai。若不存在，則返回false，否則返回true。Search(x)：若x不在表中，則返回-1，否則返回x在表中的下標。Insert(i,x)：在元素ai之后插入x。若i=-1，則x插在第一個元素a0前。若插入成功，則返回true，否則返回false。Delete(i)：刪除元素ai。若刪除成功，則返回true，否則返回false。Update(i,x)：將元素ai的值修改為x。若修改成功，則返回true，否則返回false。Output(out)：把表送至輸出流}//插入x到表：（a0,a1,...,an-1）

線性表類template<classT>classLinearList{public:……virtualboolFind(inti,T&x)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;……protected:

intn;//線性表的長度};

2.2線性表的順序表示

2.2.1順序存儲結構順序存儲表示是用一組地址連續(xù)的存儲單元依次存儲線性表中元素。順序表順序表示的線性表稱為順序表

a0a1…ai

…

an-1

…01…i…n-1…maxLength-1

地址計算公式

若已知順序表中每個元素占k個存儲單元，第一個元素a0在計算機內存中的首地址是loc(a0)，則表中任意一個元素ai在內存中的存儲地址loc(ai)為

loc(ai)=loc(a0)+i*k

隨機存取結構只要給定loc(a0)和k，就可以確定線性表中任意一個元素的存儲地址，換句話說，順序表是一種隨機存取結構。2.2.2順序表類順序表類template<classT>classSeqList:public

LinearList<T>{public://公有函數

SeqList(intmSize);

~SeqList(){delete[]elements;}boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……SingleListLinearListSeqList

……private://私有數據

intmaxLength; //順序表的最大長度

T*elements; //動態(tài)一維數組的指針};

動態(tài)存儲分配構造函數，構建一個空線性表

template<classT>SeqList<T>::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}

析構函數，撤消一個順序表template<classT>SeqList<T>::~SeqList(){delete[]elements;}2.2.3線性表運算實現(xiàn)搜索運算

Find(i,x):

查找下標為i的元素ai。在x中返回表中下標為i的元素ai(即表中第i+1個元素)。如果不存在，則返回

false，否則返回true。x=elements[i];漸近時間復雜度：O(1)

a0a1…ai

…

an-1

…01…i…n-1…maxLength-1

template<classT>boolSeqList<T>::Find(inti,T&x)const{//O(1)if(i<0||i>n?1){ //對i進行越界檢查

cout<<"OutofBounds"<<endl;returnfalse;}

x=elements[i];//通過引用參數x返回下標為i的元素

returntrue;}

插入運算

Insert(i,x)：在表中下標為i的元素ai后插入x。若i=-1，則將新元素x插在最前面。若插入成功，返回true；

插入運算的平均時間復雜度分析：設順序表長度為n，共有n+1個可插入元素的位置，并設在各位置處插入元素的概率是相等的，即Pi=1/(n+1)，在位置i（i=-1,0,…,n-1）后插入一個元素要移動n-i-1個元素。

template<classT>boolSeqList<T>::Insert(inti,Tx){//在元素ai之后插入xif(i<-1||i>n-1){//越界檢查

cout<<"OutOfBounds"<<endl;returnfalse;}if(n==maxLength){ //上溢出檢查

cout<<"OverFlow"<<endl;returnfalse;}//從后往前逐個后移元素

for(intj=n-1;j>i;j--)elements[j+1]=elements[j];

elements[i+1]=x;n++; returntrue;}

刪除運算

Delete(i)：刪除元素ai。

刪除運算的平均時間復雜度分析:

設順序表長度為n,則刪除元素ai（i=0,…,n-1）,要移動n-i-1元素。若刪除表中每個元素的概率是相等的，即Qi=1/n，

template<classT>boolSeqList<T>::Delete(inti){//刪除元素ai

if(!n){ //下溢出檢查

cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){ cout<<"OutOfBounds"<<endl;returnfalse;}//從前往后逐個前移元素

for(intj=i+1;j<n;j++)elements[j-1]=elements[j];

n--;returntrue;}

voidmain(){intx=10;SeqList<int>r(4);r.Insert(-1,x);r.Insert(-1,x);r.Output(cout);//??請復習C++，理解這一函數}線性表的順序存儲表示的優(yōu)缺點

優(yōu)點：隨機存??；存儲空間利用率高。缺點：插入、刪除效率低；必須按事先估計的最大元素個數分配連續(xù)的存儲空間，難以臨時擴大。2.3線性表的鏈接表示2.3.1單鏈表鏈接存儲表示單鏈表的結點結構單鏈表結構elementlinka0a1a2an-1…first∧非空單鏈表first空單鏈表=>NULL指針變量的存儲單元紅色為結點的指針域

注意事項頭指針first是指向單鏈表的頭結點的指針最后一個結點的指針域為，地址值為0邏輯上相鄰的元素在物理上不一定相鄰不能出現(xiàn)“斷鏈”現(xiàn)象

結點類#include"linearlist.h"template<classT>classSingleList；//超前聲明template<classT>classNode{private:Telement;Node<T>*link;friendclassSingleList<T>;};elementlink

單鏈表類template<classT>classSingleList:publicLinearList<T>{public:SingleList(){first=NULL;n=0;}~SingleList();boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……

…….private:

Node<T>*first;};

順序表類SeqList、單鏈表類SingleList是抽象線性表類LinearList類的派生類。SingleListLinearListSeqListNodefriend

構造函數

SingleList(){first=NULL;n=0;}析構函數

template<classT>SingleList<T>::~SingleList(){Node<T>*p;while(first){p=first->link;deletefirst;first=p;}}33/244單鏈表的類定義小結使用面向對象方法，要把數據與操作一起定義和封裝，用多個類表達一個單鏈表。

鏈表結點(ListNode)類鏈表(SList)類定義方式（多種方式）

復合方式嵌套方式

繼承方式結構方式34/244

classSList;

//復合方式

classListNode{

//鏈表結點類

friendclassSList;

//鏈表類為其友元類

private:

intdata;

//結點數據,整型

ListNode*link;//結點指針

};classSList{ //鏈表類

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

};復合方式的類定義35/244classSList{//嵌套方式private:

classListNode{//嵌套鏈表結點類

public:

intdata;

ListNode*link;

};ListNode*first;

//表頭指針public:

//鏈表操作………};嵌套方式的類定義36/244//鏈表類和鏈表結點類定義(繼承方式)classListNode{

//鏈表結點類

protected:

intdata;

ListNode*link;

};classSList:public

classListNode{//鏈表類,繼承鏈表結點類的數據和操作

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

搜索運算必須從頭指針開始沿鏈逐個計數查找，稱為順序查找

搜索運算的平均、最壞的漸近時間復雜度：O(n)

template<classT>boolSingleList<T>::Find(inti,T&x)const{//在(a0,a1,...,an?1)中找下標為i的元素aiif(i<0||i>n?1){ //對i進行越界檢查

cout<<"OutOfBounds";returnfalse;}Node<T>*p=first;for(intj=0;j<i;j++)p=p->link;x=p->element;returntrue;}

插入運算修改兩個指針域的值插入漸近時間復雜度：O(1)q->link=p->link;p->link=q；

插入運算步驟：生成數據域為x的新結點，q指向新結點;

從first開始找第i+1個結點，p指向該結點；將q插入p之后。

表長加1。

template<classT>boolSingleList<T>::Insert(inti,Tx){if(i<?1||i>n?1){cout<<"OutOfBounds";returnfalse;}Node<T>*q=newNode<T>;q->element=x; Node<T>*p=first; //找ai元素所在的結點pfor(intj=0;j<i;j++)p=p->link;firsta0a1a2an-1…∧非空單鏈表first空單鏈表pppi=2

if(i>?1){q->link=p->link; //新結點q插在p之后

p->link=q;}else{q->link=first;//新結點q插在頭結點之前

first=q;}n++;returntrue;}//刪除結點p是指刪除指針變量p所指示的結點*p。

單鏈表的刪除

只需修改一個指針“q->link=p->link”，但還需使用“deletep；”語句回收結點占用的空間。

單鏈表的步驟

從first開始找第i+1個結點，p指向該結點，q指向p之前驅結點;

從單鏈表中刪除p；釋放p之空間；

表長減1。

template<classT>boolSingleList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){cout<<"OutOfBounds"<<endl;returnfalse；}Node<T>*p=first,*q=first;for(intj=0;j<i-1;j++)q=q->link;

if(i==0)first=first->link;//刪除頭結點

else{p=q->link;q->link=p->link;}deletep;n--;returntrue;}

單鏈表運算的優(yōu)缺點優(yōu)點

單鏈表插入和刪除只需修改一兩個指針，無需移動元素。如已知前驅結點，插入刪除運算的時間為O(1)

可以動態(tài)分配結點空間，線性表的長度只受內存大小限制。缺點

查找運算費時，只能順序查找，不能隨機查找2.3.2帶表頭結點的單鏈表請區(qū)分“表頭結點”和“頭結點”template<classT>HeaderList<T>::HeaderList(){Node<T>*first=newNode<T>; first->link=NULL;n=0;}

template<classT>boolHeaderList<T>::Insert(inti,Tx){if(i<?1||i>n?1){cout<<"OutOfBounds"<<endl;returnfalse;}Node<T>*p=first; for(intj=0;j<=i;j++)p=p->link;Node<T>*q=newNode<T>;q->element=x;q->link=p->link; p->link=q;n++;returntrue;}

template<classT>boolHeaderList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n?1){cout<<"OutOfBounds"<<endl;returnfalse;}Node<T>*q=first,*p; for(intj=0;j<i;j++)q=q->link;p=q->link; q->link=p->link; deletep; n--;returntrue;}2.3.3單循環(huán)鏈表2.3.4雙向鏈表

結點類template<classT>classDoubleList; //超前聲明template<classT> classDNode{private:Telement;DNode<T>*lLink,*rLink;friendDoubleList<T>;};

插入操作的核心步驟如下：（1）DNode<T>*q=newDNode<T>;q->element=x;（2）q->lLink=p->lLink;q->rLink=p;p->lLink->rLink=q;p->lLink=q;錯誤：p->lLink->rLink=q；q->lLink=p->lLink;q->rLink=p;p->lLink=q;

刪除操作的核心步驟如下：（1）p->lLink->rLink=p->rLink;p->rLink->lLink=p->lLink;（2）deletep;2.4多項式的算術運算

多項式相加

p(x)=3x14?8x8+6x2+2q(x)=2x10+4x8?6x2

q(x)p(x)+q(x)結果：q(x)=3x14+2x10?4x8+2

多項式的邏輯結構：視為線性表

p(x)=3x14-8x8+6x2+2

數據元素(coef,exp)

表示多項式項coef·xexp，coef是該項的系數，exp是變元x的指數。

多項式的存儲表示

p(x)=3x14-8x8+6x2+2((3,14)，(-8,8)，(6,2)，(2,0))

順序表示

線性表長度事先難以確定；算術運算需插入和刪除元素。

多項式的鏈接表示多項式的項

2.4.1

項結點類項結點類

Term*InsertAfter（intc,inte）構造一個新項（c,e）結點，插在*this項之后，函數返回新項結點的地址。

classTerm{public:Term(intc,inte);//構造函數1Term(intc,inte,Term*nxt);//構造函數2Term*InsertAfter(intc,inte);private:intcoef;intexp;Term*link;friendostream&operator<<(ostream&,constTerm&);//重載“<<”，輸出多項式的一項

friendclassPolynominal;};

構造函數Term::Term(intc,inte):coef(c),exp(e){link=0;}Term::Term(intc,inte,Term*nxt):coef(c),exp(e){link=nxt;}Term::Term(intc,inte){coef=c;exp=e;link=0;}

InsertAfter函數實現(xiàn)Term*Term::InsertAfter(intc,inte){link=newTerm(c,e,link); returnlink;}調用語句：q=q->InsertAfter(c,e);

重載輸出運算符ostream&operator<<(ostream&out,constTerm&val){//用-4x^2表示-4x2。

if(val.coef=

=0)returnout;out<<val.coef;switch(val.exp){case0:break;case1:out<<"X";break;default:out<<"X^"<<val.exp;break;}returnout;}2.4.3

多項式的C++類classPolynominal{public:Polynominal();

～Polynominal();voidAddTerms(istream&in);//建立多項式鏈表

voidOutput(ostream&out)const;//輸出多項式

voidPolyAdd(Polynominal&r); //多項式相加

…

private:

Term*theList; //單循環(huán)鏈表的表頭指針

friendostream&operator<<(ostream&,constPolynominal&);friendistream&operator>>(istream&,Polynominal&);friendPolynominal&operator+(Polynominal&,Polynominal&);};2.4.4

多項式類的實現(xiàn)

構造函數Polynominal::Polynominal() {theList=newTerm(0,?1);theList->link=theList; }2.4.5多項式的輸入和輸出輸入多項式voidPolynominal::AddTerms(istream&in){

Term*q=theList;intc,e;for(;;){ cout<<"Inputaterm(coef,exp):\n"<<endl;in>>c>>e; if(e<0)break;q=q->InsertAfter(c,e);}}

輸出多項式voidPolynominal::Output(ostream&out)const{boolstart=true;Term*p=theList->link;out<<"Thepolynominalis:\n"<<endl;for(;p!=theList;p=p->link){if(!start&&p->coef>0)out<<'+';start=false;out<<*p;}out<<endl;}

多項式相加

若p->exp==q->exp，則同類項合并，令q->coef=q->coef+p->coef；如果此時有q->coef==0，則從q(x)中刪除結點*q，指針q指向原*q的后繼，指針p指向下一項；否則，指針p、q和q1均后移一項。若p->exp>q->exp，則復制*p，新結點插在*q1與*q之間，指針q1指向新結點，指針q不動，而指針p指向下一項。若p->exp<q->exp，則將q指示的當前項保留在q(x)中，所以令指針q1和q后移一項，指針p不動。

voidPolynominal::PolyAdd(Polynominal&r)//將多項式r加到多項式this上{Term*q,*q1=theList,*p;p=r.theList->link;q=q1->link;while(p->exp>=0){while(p->exp<q->exp){q1=q;q=q->link;}

if(p->exp==q->exp){q->coef=q->coef+p->coef;if(q->coef==0){q1->link=q->li