清華數(shù)據(jù)結(jié)構(gòu)課件

一維數(shù)組多維數(shù)組線性表順序表多項式稀疏矩陣字符串第二章數(shù)組一維數(shù)組定義

相同類型的數(shù)據(jù)元素的集合。一維數(shù)組的示例與順序表的不同在于數(shù)組可以按元素的下標(biāo)直接存儲和訪問數(shù)組元素。352749186054778341020123456789數(shù)組的定義和初始化#include<iostream.h>classszcl{inte; public:

szcl(){e=0;}

szcl(intvalue){e=value;} intget_value(){returne;} }main(){szcla1[3]={3,5,7},*elem;

for(inti=0;i<3;i++)

cout<<a1[i].get_value()<<“\n”;//靜態(tài)

elem=a1;

for(inti=0;i<3;i++){

cout<<elem->get_value()<<“\n”;//動態(tài)

elem++;

}

return0;}

一維數(shù)組(Array)類的定義

#include<iostream.h>#include<stdlib.h>template<classType>class

Array{Type*elements;//數(shù)組存放空間

intArraySize;//當(dāng)前長度

voidgetArray();//建立數(shù)組空間

public:Array(intSize=DefaultSize);

Array(constArray<Type>&x);

~Array(){delete[]elements;} Array<Type>

&

operator=//數(shù)組復(fù)制

(constArray<Type>

&A);Type&operator[](inti); //取元素值

intLength()const{returnArraySize;}

//取數(shù)組長度

voidReSize(intsz); //擴充數(shù)組

}

template<classType>voidArray<Type>::getArray(){

//私有函數(shù)：創(chuàng)建數(shù)組存儲空間

elements=newType[ArraySize];if(elements==NULL){

arraySize=0;cerr<<“存儲分配錯！"<<

endl;return;}}一維數(shù)組公共操作的實現(xiàn)

template<classType>

Array<Type>::Array(intsz){

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

if(sz<=0){

arraySize=0;cerr<<“非法數(shù)組大小”

<<endl;return;}

ArraySize=sz;getArray();

}

template<classType>Array<Type>::

Array(Array<Type>

&x){//復(fù)制構(gòu)造函數(shù)

intn=ArraySize=x.ArraySize;

elements=newType[n]; if(elements==NULL){

arraySize=0;cerr<<“存儲分配錯”

<<endl;return;}

Type*srcptr=x.elements;

Type*destptr=elements;

while(n--)*destptr++=*srcptr++;}template<classType>Type&Array<Type>::operator[](inti){

//按數(shù)組名及下標(biāo)

i，取數(shù)組元素的值

if(i<0||i>ArraySize-1){

cerr<<“數(shù)組下標(biāo)超界”

<<endl;returnNULL;}

returnelements[i]; }

使用該函數(shù)于賦值語句

Pos=Position[i-1]+Number[i-1]

template<classType>voidArray<Type>::Resize(intsz){if(sz>=0&&sz!=ArraySize){Type*newarray=newType[sz];

//創(chuàng)建新數(shù)組

if(newarray==NULL){

cerr<<“存儲分配錯”

<<endl;return;}intn=(sz<=ArraySize)?sz:ArraySize;

//按新的大小確定傳送元素個數(shù)

Type*srcptr=elements;//源數(shù)組指針

Type*destptr=newarray;//目標(biāo)數(shù)組指針

while(n--)*destptr++=*srcptr++;

//從源數(shù)組向目標(biāo)數(shù)組傳送

delete[]

elements; elements=newarray;

ArraySize=sz; }}

多維數(shù)組多維數(shù)組是一維數(shù)組的推廣多維數(shù)組是一種非線性結(jié)構(gòu)。其特點是每一個數(shù)據(jù)元素可以有多個直接前驅(qū)和多個直接后繼。數(shù)組元素的下標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡單。

二維數(shù)組三維數(shù)組行向量下標(biāo)i頁向量下標(biāo)

i列向量下標(biāo)j行向量下標(biāo)

j

列向量下標(biāo)

k數(shù)組的連續(xù)存儲方式一維數(shù)組352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la

二維數(shù)組行優(yōu)先存放：

設(shè)數(shù)組開始存放位置LOC(0,0)=a,每個元素占用d

個存儲單元

LOC(j,k)=a+(j*m+k)*d

二維數(shù)組列優(yōu)先存放：

設(shè)數(shù)組開始存放位置LOC(0,0)=a,每個元素占用d

個存儲單元

LOC(j,k)=a+(k*n+j)*d

三維數(shù)組

各維元素個數(shù)為

m1,m2,m3

下標(biāo)為i1,i2,i3的數(shù)組元素的存儲地址：

（按頁/行/列存放）

LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3

)*l

前i1頁總元素個數(shù)第i1頁的前i2行總元素個數(shù)第i2行前i3列元素個數(shù)

n維數(shù)組

各維元素個數(shù)為

m1,m2,m3,…,mn

下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲地址：

LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in

)*l

線性表(LinearList)線性表的定義和特點

定義

n（0）個數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）

ai是表中數(shù)據(jù)元素，n是表長度。

遍歷逐項訪問：

從前向后從后向前線性表的特點除第一個元素外，其他每一個元素有一個且僅有一個直接前驅(qū)。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。a1a2a3a4a5a6順序表(SequentialList)順序表的定義和特點

定義將線性表中的元素相繼存放在一個連續(xù)的存儲空間中?？衫靡痪S數(shù)組描述存儲結(jié)構(gòu)特點

線性表的順序存儲方式

遍歷順序訪問

253457164809

012345data順序表(SeqList)類的定義template<classType> classSeqList{Type*data;//順序表存儲數(shù)組

intMaxSize; //最大允許長度

intlast; //當(dāng)前最后元素下標(biāo)public: SeqList(intMaxSize=defaultSize); ~SeqList(){delete[]data;}

intLength()const

{returnlast+1;

}

intFind(Type&x)const;//查找

intLocate(inti)const; //定位

intInsert(Type&x,inti);//插入

intRemove(Type

&x); //刪除

intNext(Type

&x); //后繼

intPrior(Type

&x);//前驅(qū)

intIsEmpty(){returnlast==-1;

} intIsFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

順序表部分公共操作的實現(xiàn)

template<classType>

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

SeqList<Type>::SeqList(intsz){if(sz>0){ MaxSize=sz;last=-1; data=newType[MaxSize];

if(data==NULL){MaxSize=0;last=-1;return;}

}}template<classType> intSeqList<Type>::Find(Type

&x)const{//搜索函數(shù)：在順序表中從頭查找結(jié)點值等于//給定值x的結(jié)點

inti=0;

while(i<=last&&data[i]!=x)i++;

if(i>last)return

-1;

elsereturni; }順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功2534571648

01234data搜索50i2534571648

i2534571648

i2534571648

i2534571648

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

若搜索概率相等，則

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

次表項的插入2534571648096301234567data50插入x253457501648096301234567data50itemplate<classType>intSeqList<Type>::Insert(Type&x,inti){//在表中第

i個位置插入新元素

x

if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入不成功

else{last++;

for(intj=last;j>i;j--)data[j]=data[j-1]; data[i]=x;return1;//插入成功

}}表項的刪除253457501648096301234567data16刪除

x2534575048096301234567data

template<classType>intSeqList<Type>::Remove(Type&x){

//在表中刪除已有元素

x

inti=Find(x); //在表中搜索

x

if(i>=0){ last--

;

for(intj=i;j<=last;j++)data[j]=data[j+1];

return1; //成功刪除

} return0;//表中沒有

x}順序表的應(yīng)用：集合的“并”運算voidUnion(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();

for(inti=0;i<m;i++){ intx=B.Get(i);//在B中取一元素

intk=A.Find(x);//在A中搜索它

if(k==

-1)//若未找到插入它

{A.Insert(n,x);n++;}}}voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Find(x);//在B中搜索它

if(k==-1){A.Remove(i);n--;} elsei++;//未找到在A中刪除它

}}順序表的應(yīng)用：集合的“交”運算多項式(Polynomial)n階多項式Pn(x)有n+1項。

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

指數(shù)0,1,2,…,n。按升冪排列classPolynomial{public:Polynomial();//構(gòu)造函數(shù)

intoperator!();//判是否零多項式

floatCoef(inte);

intLeadExp();//返回最大指數(shù)

Polynomial

Add(Polynomial

poly);PolynomialMult(Polynomialpoly);

floatEval(floatx); //求值}多項式(Polynomial)的抽象數(shù)據(jù)類型

#include<iostream.h>classpower{

doublex;

inte;

doublemul;

public:

power(doubleval,intexp);

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

doubleget_power(){returnmul;}//取冪值

};創(chuàng)建power類，計算x的冪

power::power(doubleval,intexp){

//按val值計算乘冪

x=val;e=exp;mul=1.0;

if(exp==0)return;

for(;exp>0;exp--)mul=mul*x;

}main(){powerpwr(1.5,2);

cout<<pwr.get_power()<<“\n”;

}

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

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

intdegree; 組表示)

floatcoef[maxDegree+1];

Pn(x)可以表示為：

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

a1

a2……an………012degreemaxDegree-1coefn第二種：private:

(動態(tài)數(shù)

intdegree;組表示)

float*coef; Polynomial::Polynomial(intsz){ degree=sz; coef=newfloat[degree+1];

}

以上兩種存儲表示適用于指數(shù)連續(xù)排列的多項式。但對于指數(shù)不全的多項式如

P101(x)=3+5x50-14x101,不經(jīng)濟。第三種：

class

Polynomial; classterm{

//多項式的項定義

friendPolynomial;

private:

floatcoef;//系數(shù)

intexp; //指數(shù)

};a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

mclass

Polynomial{//多項式定義public:……private:

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

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

//termPolynomial::termArray[MaxTerms];//intPolynomial::free=0;

intstart,finish; //多項式始末位置

}

A(x)=2.0x1000+1.8

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

兩個多項式存放在termArray中A.startA.finishB.startB.finishfreecoefexp1.82.0……01000050101……maxTerms兩個多項式的相加結(jié)果多項式另存掃描兩個相加多項式，若都未檢測完：

若當(dāng)前被檢測項指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項式。若當(dāng)前被檢測項指數(shù)不等，將指數(shù)小者加到結(jié)果多項式。若有一個多項式已檢測完，將另一個多項式剩余部分復(fù)制到結(jié)果多項式。PolynomialPolynomial::operator+(PolynomialB){PolynomialC;inta=start;

intb=B.start;C.start=free;

floatc;

while(a<=finish&&b<=B.finish)

Switch(compare(termArray[a].exp,termArray[b].exp)){//比較對應(yīng)項指數(shù)

case‘=’://指數(shù)相等

c=termArray[a].coef+//系數(shù)相加

termArray[b].coef;if(c)NewTerm(c,termArray[a].exp);a++;b++;

break;

case‘>’:

//b指數(shù)小,建立新項

NewTerm(termArray[b].coef,termArray[b].exp);

b++;

break;

case'<':

//a指數(shù)小,建立新項

NewTerm(termArray[a].coef,termArray[a].exp);

a++;

}for(;a<=finish;a++)//a未檢測完時

NewTerm(termArray[a].coef,termArray[a].exp

);

for(

;

b<=B.finish;b++)//b未檢測完時

NewTerm(termArray[b].coef,termArray[b].exp);C.finish=free-1;

returnC;}

在多項式中加入新的項

voidPolynomial::NewTerm(floatc,inte){

//把一個新的項加到多項式C(x)中

if(free>=maxTerms){cout<<"Toomanytermsinpolynomials”<<endl;return;

}termArray[free].coef=c;

termArray[free].exp=e;

free++;}

稀疏矩陣

(SparseMatrix)非零元素個數(shù)遠遠少于矩陣元素個數(shù)稀疏矩陣的定義設(shè)矩陣Amn

中有

t個非零元素，若t遠遠小于矩陣元素的總數(shù)mn，則稱矩陣A為稀疏矩陣。為節(jié)省存儲空間，應(yīng)只存儲非零元素。非零元素的分布一般沒有規(guī)律，應(yīng)在存儲非零元素時，同時存儲該非零元素的行下標(biāo)row、列下標(biāo)

col、值

value。每一個非零元素由一個三元組唯一確定：

(行號row,列號col,值value)稀疏矩陣的抽象數(shù)據(jù)類型template<classType>classSparseMatrix;template<classType>classTrituple{ //三元組friendclassSparseMatrix<Type>private:

introw,col; //非零元素行號/列號

Typevalue;//非零元素的值}

template<classType>classSparseMatrix{//稀疏矩陣類定義

intRows,Cols,Terms;//行/列/非零元素數(shù)

Trituple<Type>smArray[MaxTerms];

public://三元組表

SparseMatrix(intMaxRow,intMaxcol);

SparseMatrix<Type>&Transpose(SparseMatrix<Type>&);//轉(zhuǎn)置

SparseMatrix<Type>&Add(SparseMatrix

<Type>a,SparseMatrix<Type>b);//相加

SparseMatrix<Type>&Multiply(SparseMatrix

<Type>a,SparseMatrix<Type>b);//相乘}

稀疏矩陣的轉(zhuǎn)置一個mn

的矩陣A，它的轉(zhuǎn)置矩陣B是一個nm

的矩陣，且A[i][j]=B[j][i]。即矩陣A的行成為矩陣B的列，矩陣A的列成為矩陣B的行。在稀疏矩陣的三元組表中，非零矩陣元素按行存放。當(dāng)行號相同時，按列號遞增的順序存放。稀疏矩陣的轉(zhuǎn)置運算要轉(zhuǎn)化為對應(yīng)三元組表的轉(zhuǎn)置。稀疏矩陣轉(zhuǎn)置矩陣用三元組表表示的稀疏矩陣及其轉(zhuǎn)置稀疏矩陣轉(zhuǎn)置算法思想設(shè)矩陣列數(shù)為Cols，對矩陣三元組表掃描Cols次。第k次檢測列號為k的項。第k次掃描找尋所有列號為k

的項，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。稀疏矩陣的轉(zhuǎn)置

template<classType>SparseMatrix<Type>&SparseMatrix<Type>::Transpose(SparseMatrix<Type>&a){SparseMatrix<Type>b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;

b.Terms=a.Terms;

//轉(zhuǎn)置矩陣的列數(shù),行數(shù)和非零元素個數(shù)

if(a.Terms>0){

intCurrentB=0;

//轉(zhuǎn)置三元組表存放指針

for(int

k=0;k<a.Cols;k++)

//對所有列號處理一遍

for(inti=0;i<a.Terms;i++)

if(a.smArray[i].col==k){ b.smArray[CurrentB].row=k;

b.smArray[CurrentB].col=a.smArray[i].row;

b.smArray[CurrentB].value=a.smArray[i].value;

CurrentB++;

}

}

returnb;}快速轉(zhuǎn)置算法設(shè)矩陣三元組表總共有t項，上述算法的時間代價為O(n*t)。若矩陣有200行，200列，10,000個非零元素，總共有2,000,000次處理。為加速轉(zhuǎn)置速度，建立輔助數(shù)組rowSize

和rowStart，記錄矩陣轉(zhuǎn)置后各行非零元素個數(shù)和各行元素在轉(zhuǎn)置三元組表中開始存放位置。掃描矩陣三元組表，根據(jù)某項列號，確定它轉(zhuǎn)置后的行號,查rowStart

表,按查到的位置直接將該項存入轉(zhuǎn)置三元組表中

for(inti=0;i<a.Cols;i++)

rowSize[i]=0; for(i=0;i<a.Terms;i++)

rowSize[a.smArray[i].col]++;

rowStart[0]=0; for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];稀疏矩陣的快速轉(zhuǎn)置template<classType>SparseMatrix<Type>&SparseMatrix<Type>::FastTranspos(SparseMatrix<Type>&a){

int*rowSize=newint[a.Cols];

int*rowStart=newint[a.Cols];SparseMatrix<Type>b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;

b.Terms=a.Terms;if(a.Terms>0){for(inti=0;i<Cols;i++)rowSize[i]=0;

for(i=0;i<Terms;i++)rowSize[smArray[i].col]++;

rowStart[0]=0;

for(i=1;i<a.Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<a.Terms;i++){ intj=rowStart[a.smArray[i].col]; b.smArray[j].row=a.smArray[i].col; b.smArray[j].col=a.smArray[i].row; b.smArray[j].value=a.smArray[i].value; rowStart[a.smArray[i].col]++;

}}

delete[]rowSize;

delete[]rowStart;

returnb;}字符串(String)字符串是n(0)個字符的有限序列，記作S:“c1c2c3…cn”

其中，S是串名字

“c1c2c3…cn”是串值

ci是串中字符

n是串的長度。例如,S=“TsinghuaUniversity”

constintmaxLen=128;

classString{intcurLen;//串的當(dāng)前長度

char*ch;//串的存儲數(shù)組

public:String(constString&ob);String(constchar*init);String(

);~String(){delete[]ch;}

字符串抽象數(shù)據(jù)類型和類定義

intLength()const{

returncurLen;}

//求當(dāng)前串*this的實際長度

String&operator()(intpos,intlen);

//取*this從pos開始len個字符組成的子串

intoperator==(constString&ob){returnstrcmp(ch,ob.ch)==0;}

//判當(dāng)前串*this與對象串ob是否相等

intoperator!=(constString&ob)const{returnstrcmp(ch,ob.ch)!=0;}

//判當(dāng)前串*this與對象串ob是否不等

intoperator!()

const

{returncurLen==0;}

//判當(dāng)前串*this是否空串

String&operator=(String&ob);

//將串ob賦給當(dāng)前串*thisString&operator+=(String&ob);

//將串ob連接到當(dāng)前串*this之后

char&operator[](inti);

//取當(dāng)前串*this的第i個字符

intFind(String&pat)const;}

String::String(constString&ob){

//復(fù)制構(gòu)造函數(shù)：從已有串ob復(fù)制

ch=newchar[maxLen+1];//創(chuàng)建串?dāng)?shù)組

if(ch==NULL){

cerr<<“存儲分配錯!

\n”;

exit(1);

}curLen=ob.curLen;//復(fù)制串長度

strcpy(ch,ob.ch);//復(fù)制串值

}

字符串部分操作的實現(xiàn)String::String(const

char*init){//復(fù)制構(gòu)造函數(shù):從已有字符數(shù)組*init復(fù)制

ch=newchar[maxLen+1];//創(chuàng)建串?dāng)?shù)組

if(ch==NULL){cerr<<“存儲分配錯!

\n”;

exit(1);

}curLen=strlen(init);

//復(fù)制串長度

strcpy(ch,init);

//復(fù)制串值

}String::String(

){//構(gòu)造函數(shù)：創(chuàng)建一個空串

ch=newchar[maxLen+1];//創(chuàng)建串?dāng)?shù)組

if(ch==NULL){

cerr<<“存儲分配錯!\n”;

exit(1);}curLen=0;ch[0]=‘\0’;}提取子串的算法示例pos+len-1 pos+len-1curLen-1curLeninfinityinfinitypos=2,len=3pos=5,len=4finity超出String&String::operator()(intpos,intlen){//從串中第

pos個位置起連續(xù)提取

len個字符//形成子串返回

String*temp=newString;//動態(tài)分配

if(pos<0||pos+len-1>=maxLen||len<0){

temp->curLen=0;

//返回空串

temp->ch[0]='\0';

}

else{//提取子串

if(pos+len-1>=curLen)len=curLen-pos;

temp->curLen=len;//子串長度

for(inti=0,j=pos;i<len;i++,j++) temp->ch[i]=ch[j];//傳送串?dāng)?shù)組

temp->ch[len]=‘\0’;//子串結(jié)束

}

return*temp;}

例：串

st=“university”,

pos=3,len=4使用示例

subSt=st(3,4)提取子串

subSt=“vers”String&String::operator=(String&ob){//串賦值：從已有串ob復(fù)制

if(&ob!=this){

delete[]ch; ch=new

char[maxLen+1];//重新分配

if(ch==NULL)

{cerr<<“內(nèi)存不足!\n”;

exit(1);}curLen=ob.curLen;//串復(fù)制

strcpy(ch,ob.ch);

}elsecout<<“字符串自身賦值出錯!\n”;

return*this;}char&String::operator[](inti){//按串名提取串中第i個字符

if(i<0&&i>=curLen

){cout<<“串下標(biāo)超界!\n”;

exit(1);}returnch[i];}例：串

st=“university”,使用示例

newSt=st；newChar=st[1];數(shù)組賦值

newSt=“university”提取字符

newChar=

‘n’String&String::operator+=(String&ob){//串連接

char*temp=ch;//暫存原串?dāng)?shù)組

curLen+=ob.curLen;//串長度累加

ch=new

char[maxLen+1];

if(ch==NULL){cerr<<“存儲分配錯!\n”;

exit(1);}strcpy(ch,temp);

//拷貝原串?dāng)?shù)組

strcat(ch,ob.ch);

//連接ob串?dāng)?shù)組

delete[]temp;return

*this;

}例：串st1=“beijing”,st2=“university”,使用示例

st1+=st2;連接結(jié)果

st1=“beijinguniversity”st2=“university”串的模式匹配定義在串中尋找子串（第一個字符）在串中的位置詞匯在模式匹配中，子串稱為模式，串稱為目標(biāo)。示例

目標(biāo)T:“Beijing”

模式P:“jin”

匹配結(jié)果=3

第1趟

T abbaba窮舉的模式

P aba

匹配過程

第2趟

T abbaba P

aba

第3趟

T abbaba P

aba

第4趟

T abba

ba Pa

ba

intString::Find(String&pat)const{

//窮舉的模式匹配

char*p=pat.ch,*s=ch;

inti=0;

if(*p&&*s) //當(dāng)兩串未檢測完

while(i<=curLen-pat.curLen)

if(*p++==*s++)//比較串字符

if(!*p)returni;//相等

else{i++;s=ch+i;p=pat.ch;}

//對應(yīng)字符不相等，對齊目標(biāo)的

//下一位置，繼續(xù)比較

return

-1; }

目標(biāo)

T

t0

t1

t2……tm-1…tn-1

模式

pat

p0

p1

p2……pm-1

目標(biāo)

T

t0

t1

t2……tm-1

tm…tn-1

模式

pat

p0

p1……pm-2pm-1

目標(biāo)

T

t0

t1……ti

ti+1……ti+m-2

ti+m-1…tn-1 ‖‖‖‖

模式

pat

p0

p1……pm-2pm-1改進的模式匹配

窮舉的模式匹配算法時間代價：最壞情況比較n-m+1趟，每趟比較m次，總比較次數(shù)達(n-m+1)*m

原因在于每趟重新比較時，目標(biāo)串的檢測指針要回退。改進的模式匹配算法可使目標(biāo)串的檢測指針每趟不回退。

改進的模式匹配(KMP)算法的時間代價：若每趟第一個不匹配，比較n-m+1趟，總比較次數(shù)最壞達(n-m)+m=n

若每趟第m個不匹配，總比較次數(shù)最壞亦達到nTt0

t1…ts-1

ts

ts+1

ts+2…ts+j-1

ts+j

ts+j+1…tn-1

‖‖‖‖‖P

p0

p1

p2…pj-1

pjpj+1

則有

tsts+1

ts+2…ts+j

=p0

p1

p2…pj(1)

為使模式P與目標(biāo)T匹配，必須滿足

p0

p1

p2…pj-1…pm-1