數(shù)據(jù)結(jié)構(gòu)講義

數(shù)據(jù)結(jié)構(gòu)王源2016年9月第2章線性表

2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算實(shí)驗(yàn)二、鏈表及其應(yīng)用

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

ai是表中下標(biāo)為i的元素（i=0,1,…,n-1），稱ai是ai+1的直接前驅(qū)元素，ai+1是ai的直接后繼元素。線性表是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，它的表長可以改變。

線性表ADTADTLinearList{數(shù)據(jù)：

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

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

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

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

Length()：返回表中元素個(gè)數(shù)。

Find(i,x)：在x中返回表中下標(biāo)為i的元素ai。若不存在，則返回false，否則返回true。Search(x)：若x不在表中，則返回-1，否則返回x在表中的下標(biāo)。Insert(i,x)：在元素ai之后插入x。若i=-1，則x插在第一個(gè)元素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順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中元素。順序表順序表示的線性表稱為順序表

a0a1…ai

…

an-1

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

地址計(jì)算公式

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

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

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

LinearList<T>{public://公有函數(shù)

SeqList(intmSize);

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

……private://私有數(shù)據(jù)

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

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

動(dòng)態(tài)存儲(chǔ)分配構(gòu)造函數(shù)，構(gòu)建一個(gè)空線性表

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

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

Find(i,x):

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

false，否則返回true。x=elements[i];漸近時(shí)間復(fù)雜度：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){ //對(duì)i進(jìn)行越界檢查

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

x=elements[i];//通過引用參數(shù)x返回下標(biāo)為i的元素

returntrue;}

插入運(yùn)算

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

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

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;}//從后往前逐個(gè)后移元素

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

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

刪除運(yùn)算

Delete(i)：刪除元素ai。

刪除運(yùn)算的平均時(shí)間復(fù)雜度分析:

設(shè)順序表長度為n,則刪除元素ai（i=0,…,n-1）,要移動(dòng)n-i-1元素。若刪除表中每個(gè)元素的概率是相等的，即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;}//從前往后逐個(gè)前移元素

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);//??請(qǐng)復(fù)習(xí)C++，理解這一函數(shù)}線性表的順序存儲(chǔ)表示的優(yōu)缺點(diǎn)

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

注意事項(xiàng)頭指針first是指向單鏈表的頭結(jié)點(diǎn)的指針最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椋刂分禐?邏輯上相鄰的元素在物理上不一定相鄰不能出現(xiàn)“斷鏈”現(xiàn)象

結(jié)點(diǎ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

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

SingleList(){first=NULL;n=0;}析構(gòu)函數(shù)

template<classT>SingleList<T>::~SingleList(){Node<T>*p;while(first){p=first->link;deletefirst;first=p;}}33/244單鏈表的類定義小結(jié)使用面向?qū)ο蠓椒?，要把?shù)據(jù)與操作一起定義和封裝，用多個(gè)類表達(dá)一個(gè)單鏈表。

鏈表結(jié)點(diǎn)(ListNode)類鏈表(SList)類定義方式（多種方式）

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

繼承方式結(jié)構(gòu)方式34/244

classSList;

//復(fù)合方式

classListNode{

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

friendclassSList;

//鏈表類為其友元類

private:

intdata;

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

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

};classSList{ //鏈表類

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

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

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

public:

intdata;

ListNode*link;

};ListNode*first;

//表頭指針public:

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

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

protected:

intdata;

ListNode*link;

};classSList:public

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

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

搜索運(yùn)算必須從頭指針開始沿鏈逐個(gè)計(jì)數(shù)查找，稱為順序查找

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

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

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

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

插入運(yùn)算步驟：生成數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，q指向新結(jié)點(diǎn);

從first開始找第i+1個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)；將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元素所在的結(jié)點(diǎn)pfor(intj=0;j<i;j++)p=p->link;firsta0a1a2an-1…∧非空單鏈表first空單鏈表pppi=2

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

p->link=q;}else{q->link=first;//新結(jié)點(diǎn)q插在頭結(jié)點(diǎn)之前

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

單鏈表的刪除

只需修改一個(gè)指針“q->link=p->link”，但還需使用“deletep；”語句回收結(jié)點(diǎn)占用的空間。

單鏈表的步驟

從first開始找第i+1個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)，q指向p之前驅(qū)結(jié)點(diǎn);

從單鏈表中刪除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;//刪除頭結(jié)點(diǎn)

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

單鏈表運(yùn)算的優(yōu)缺點(diǎn)優(yōu)點(diǎn)

單鏈表插入和刪除只需修改一兩個(gè)指針，無需移動(dòng)元素。如已知前驅(qū)結(jié)點(diǎn)，插入刪除運(yùn)算的時(shí)間為O(1)

可以動(dòng)態(tài)分配結(jié)點(diǎn)空間，線性表的長度只受內(nèi)存大小限制。缺點(diǎn)

查找運(yùn)算費(fèi)時(shí)，只能順序查找，不能隨機(jī)查找2.3.2帶表頭結(jié)點(diǎn)的單鏈表請(qǐng)區(qū)分“表頭結(jié)點(diǎn)”和“頭結(jié)點(diǎn)”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雙向鏈表

結(jié)點(diǎn)類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;錯(cuò)誤：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多項(xiàng)式的算術(shù)運(yùn)算

多項(xiàng)式相加

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

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

多項(xiàng)式的邏輯結(jié)構(gòu)：視為線性表

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

數(shù)據(jù)元素(coef,exp)

表示多項(xiàng)式項(xiàng)coef·xexp，coef是該項(xiàng)的系數(shù)，exp是變?cè)獂的指數(shù)。

多項(xiàng)式的存儲(chǔ)表示

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

順序表示

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

多項(xiàng)式的鏈接表示多項(xiàng)式的項(xiàng)

2.4.1

項(xiàng)結(jié)點(diǎn)類項(xiàng)結(jié)點(diǎn)類

Term*InsertAfter（intc,inte）構(gòu)造一個(gè)新項(xiàng)（c,e）結(jié)點(diǎn)，插在*this項(xiàng)之后，函數(shù)返回新項(xiàng)結(jié)點(diǎn)的地址。

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

friendclassPolynominal;};

構(gòu)造函數(shù)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函數(shù)實(shí)現(xiàn)Term*Term::InsertAfter(intc,inte){link=newTerm(c,e,link); returnlink;}調(diào)用語句：q=q->InsertAfter(c,e);

重載輸出運(yùn)算符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

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

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

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

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

…

private:

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

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

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

構(gòu)造函數(shù)Polynominal::Polynominal() {theList=newTerm(0,?1);theList->link=theList; }2.4.5多項(xiàng)式的輸入和輸出輸入多項(xiàng)式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);}}

輸出多項(xiàng)式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;}

多項(xiàng)式相加

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

voidPolynominal::PolyAdd(Polynominal&r)//將多項(xiàng)式r加到多項(xiàng)式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