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

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

相同類(lèi)型的數(shù)據(jù)元素的集合。一維數(shù)組的示例與順序表的不同在于數(shù)組可以按元素的下標(biāo)直接存儲(chǔ)和訪問(wèn)數(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”;//動(dòng)態(tài)

elem++;

}

return0;}

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

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

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

intArraySize;//當(dāng)前長(zhǎ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ù)組長(zhǎng)度

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

}

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

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

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

arraySize=0;cerr<<“存儲(chǔ)分配錯(cuò)！"<<

endl;return;}}一維數(shù)組公共操作的實(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<<“存儲(chǔ)分配錯(cuò)”

<<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ù)于賦值語(yǔ)句

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<<“存儲(chǔ)分配錯(cuò)”

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

//按新的大小確定傳送元素個(gè)數(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)。其特點(diǎn)是每一個(gè)數(shù)據(jù)元素可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。數(shù)組元素的下標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡(jiǎn)單。

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

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

j

列向量下標(biāo)

k數(shù)組的連續(xù)存儲(chǔ)方式一維數(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ù)組開(kāi)始存放位置LOC(0,0)=a,每個(gè)元素占用d

個(gè)存儲(chǔ)單元

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

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

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

個(gè)存儲(chǔ)單元

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

三維數(shù)組

各維元素個(gè)數(shù)為

m1,m2,m3

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

（按頁(yè)/行/列存放）

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

)*l

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

n維數(shù)組

各維元素個(gè)數(shù)為

m1,m2,m3,…,mn

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

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

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

)*l

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

定義

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

（a1,a2,…,an）

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

遍歷逐項(xiàng)訪問(wèn)：

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

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

線性表的順序存儲(chǔ)方式

遍歷順序訪問(wèn)

253457164809

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

intMaxSize; //最大允許長(zhǎng)度

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];}}

順序表部分公共操作的實(shí)現(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é)點(diǎn)值等于//給定值x的結(jié)點(diǎn)

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

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

i個(gè)位置插入新元素

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;//插入成功

}}表項(xiàng)的刪除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;//表中沒(méi)有

x}順序表的應(yīng)用：集合的“并”運(yùn)算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)用：集合的“交”運(yùn)算多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+1項(xiàng)。

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

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

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

floatCoef(inte);

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

Polynomial

Add(Polynomial

poly);PolynomialMult(Polynomialpoly);

floatEval(floatx); //求值}多項(xiàng)式(Polynomial)的抽象數(shù)據(jù)類(lèi)型

#include<iostream.h>classpower{

doublex;

inte;

doublemul;

public:

power(doubleval,intexp);

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

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

};創(chuàng)建power類(lèi)，計(jì)算x的冪

power::power(doubleval,intexp){

//按val值計(jì)算乘冪

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”;

}

多項(xiàng)式的存儲(chǔ)表示第一種：

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

intdegree; 組表示)

floatcoef[maxDegree+1];

Pn(x)可以表示為：

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

a1

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

(動(dòng)態(tài)數(shù)

intdegree;組表示)

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

}

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

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

class

Polynomial; classterm{

//多項(xiàng)式的項(xiàng)定義

friendPolynomial;

private:

floatcoef;//系數(shù)

intexp; //指數(shù)

};a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

mclass

Polynomial{//多項(xiàng)式定義public:……private:

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

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

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

intstart,finish; //多項(xiàng)式始末位置

}

A(x)=2.0x1000+1.8

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

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

若當(dāng)前被檢測(cè)項(xiàng)指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項(xiàng)式。若當(dāng)前被檢測(cè)項(xiàng)指數(shù)不等，將指數(shù)小者加到結(jié)果多項(xiàng)式。若有一個(gè)多項(xiàng)式已檢測(cè)完，將另一個(gè)多項(xiàng)式剩余部分復(fù)制到結(jié)果多項(xiàng)式。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)){//比較對(duì)應(yīng)項(xià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ù)小,建立新項(xiàng)

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

b++;

break;

case'<':

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

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

a++;

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

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

);

for(

;

b<=B.finish;b++)//b未檢測(cè)完時(shí)

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

returnC;}

在多項(xiàng)式中加入新的項(xiàng)

voidPolynomial::NewTerm(floatc,inte){

//把一個(gè)新的項(xiàng)加到多項(xiàng)式C(x)中

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

}termArray[free].coef=c;

termArray[free].exp=e;

free++;}

稀疏矩陣

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

中有

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

col、值

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

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

introw,col; //非零元素行號(hào)/列號(hào)

Typevalue;//非零元素的值}

template<classType>classSparseMatrix{//稀疏矩陣類(lèi)定義

intRows,Cols,Terms;//行/列/非零元素?cái)?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)置一個(gè)mn

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

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

的項(xiàng)，將其行號(hào)變列號(hào)、列號(hào)變行號(hào)，順次存于轉(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ù)和非零元素個(gè)數(shù)

if(a.Terms>0){

intCurrentB=0;

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

for(int

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

//對(duì)所有列號(hào)處理一遍

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項(xiàng)，上述算法的時(shí)間代價(jià)為O(n*t)。若矩陣有200行，200列，10,000個(gè)非零元素，總共有2,000,000次處理。為加速轉(zhuǎn)置速度，建立輔助數(shù)組rowSize

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

表,按查到的位置直接將該項(xiàng)存入轉(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)個(gè)字符的有限序列，記作S:“c1c2c3…cn”

其中，S是串名字

“c1c2c3…cn”是串值

ci是串中字符

n是串的長(zhǎng)度。例如,S=“TsinghuaUniversity”

constintmaxLen=128;

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

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

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

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

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

intLength()const{

returncurLen;}

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

String&operator()(intpos,intlen);

//取*this從pos開(kāi)始len個(gè)字符組成的子串

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

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

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

//判當(dāng)前串*this與對(duì)象串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個(gè)字符

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<<“存儲(chǔ)分配錯(cuò)!

\n”;

exit(1);

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

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

}

字符串部分操作的實(shí)現(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<<“存儲(chǔ)分配錯(cuò)!

\n”;

exit(1);

}curLen=strlen(init);

//復(fù)制串長(zhǎng)度

strcpy(ch,init);

//復(fù)制串值

}String::String(

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

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

if(ch==NULL){

cerr<<“存儲(chǔ)分配錯(cuò)!\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個(gè)位置起連續(xù)提取

len個(gè)字符//形成子串返回

String*temp=newString;//動(dòng)態(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;//子串長(zhǎng)度

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<<“字符串自身賦值出錯(cuò)!\n”;

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

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;//串長(zhǎng)度累加

ch=new

char[maxLen+1];

if(ch==NULL){cerr<<“存儲(chǔ)分配錯(cuò)!\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”串的模式匹配定義在串中尋找子串（第一個(gè)字符）在串中的位置詞匯在模式匹配中，子串稱(chēng)為模式，串稱(chēng)為目標(biāo)。示例

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

模式P:“jin”

匹配結(jié)果=3

第1趟

T abbaba窮舉的模式

P aba

匹配過(guò)程

第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)兩串未檢測(cè)完

while(i<=curLen-pat.curLen)

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

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

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

//對(duì)應(yīng)字符不相等，對(duì)齊目標(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改進(jìn)的模式匹配

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

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

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

若每趟第m個(gè)不匹配，總比較次數(shù)最壞亦達(dá)到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匹配，必須滿(mǎn)足

p0

p1

p2…pj-1…pm-1