第四章數(shù)組、矩陣與字符串

主講人：劉曉靜青海大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用系第四章數(shù)組、矩陣與字符串第四章數(shù)組、矩陣與字符串多維數(shù)組的概念與存儲(chǔ)特殊矩陣稀疏矩陣字符串4.1多維數(shù)組的概念與存儲(chǔ)4.1.1多維數(shù)組的概念4.1.2多維數(shù)組的存儲(chǔ)表示4.1.1多維數(shù)組的概念多維數(shù)組是一維數(shù)組的推廣或擴(kuò)展。多維數(shù)組的特點(diǎn)是每一個(gè)數(shù)據(jù)元素可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。數(shù)組元素的下標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡單。例如二維數(shù)組的數(shù)組元素有兩個(gè)直接前驅(qū)，兩個(gè)直接后繼，必須有兩個(gè)下標(biāo)（行、列）以標(biāo)識(shí)該元素的位置。

a11a12…a1na21

a22…a2n

…………

am1am2…amnA=例如，元素a22受兩個(gè)線性關(guān)系的約束，在行上有一個(gè)行前驅(qū)a21和一個(gè)行后繼a23，在列上有一個(gè)列前驅(qū)a12和和一個(gè)列后繼a32。數(shù)組示例

a11a12…a1na21a22…a2n

…………

am1am2…amnA=

A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)數(shù)組——線性表的推廣二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。行向量下標(biāo)i頁向量下標(biāo)

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

j

列向量下標(biāo)

k7二維數(shù)組三維數(shù)組一維數(shù)組LOC(i)=

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

a,i=0

352749186054778341020123456789llllllllll

a+i*laa為起始地址，每個(gè)元素的存儲(chǔ)大小為L4.1.2多維數(shù)組的存儲(chǔ)表示4.1.2多維數(shù)組的存儲(chǔ)表示一維數(shù)組常被稱為向量（Vector）。二維數(shù)組A[n][m]可看成是由n個(gè)行向量組成的向量，也可看成是由m個(gè)列向量組成的向量。一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型:typedefTarray[n][m];//T為元素類型同理，一個(gè)三維數(shù)組類型可以定義為其數(shù)據(jù)元素為二維數(shù)組類型的一維數(shù)組類型。用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排列到一個(gè)序列中。4.1.2多維數(shù)組的存儲(chǔ)表示二維數(shù)組的動(dòng)態(tài)定義和初始化#include

<iostream>…………int**A;//指針數(shù)組introw=3,col=3;inti,j;A=newint*[row];for(i=0;i<row;i++)

A[i]=newint[col];for(i=0;i<row;i++)for(j=0;j<col;j++)cin>>A[i][j];…………第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2＋1)＋(j

-l2)個(gè)元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按行優(yōu)先存儲(chǔ)的尋址按列優(yōu)先存儲(chǔ)的尋址方法與此類似。行優(yōu)先存放（絕大多數(shù)程序設(shè)計(jì)語言均采用行優(yōu)先存放）設(shè)數(shù)組開始存放位置LOC(0,0)=a,每個(gè)元素占用l

個(gè)存儲(chǔ)單元，則任一數(shù)組元素的存放位置滿足：

LOC(j,k)=a+(j*m+k)*l二維數(shù)組中數(shù)組元素的順序存放列優(yōu)先存放：

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

個(gè)存儲(chǔ)單元，則任一數(shù)組元素的存放位置滿足：

LOC(j,k)=a+(k*n+j)*l二維數(shù)組中數(shù)組元素的順序存放各維元素個(gè)數(shù)為m1,m2,m3下標(biāo)為i1,i2,i3的數(shù)組元素的存儲(chǔ)地址： （按頁／行／列順序存放）

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

+i2*m3

+i3

)*l

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

行前

i3

列元素個(gè)數(shù)三維數(shù)組的存儲(chǔ)表示各維元素個(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

n維數(shù)組的存儲(chǔ)表示4.2特殊矩陣4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)4.2.2三對(duì)角矩陣的壓縮存儲(chǔ)4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)設(shè)有一個(gè)n╳n

的對(duì)稱矩陣A。對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，aij=aji，0≤i,j≤n-14.2.1對(duì)稱矩陣的壓縮存儲(chǔ)為節(jié)約存儲(chǔ)，只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線及對(duì)角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。下三角矩陣4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)方式。數(shù)組B共有n+(n-1)++1=n*(n+1)／2

個(gè)元素。上三角矩陣下三角矩陣若

i

j,數(shù)組元素A[i][j]在數(shù)組B中的存放位置為

1+2++i+j=(i+1)*i/2+jBa00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1前i行元素總數(shù)第i行第j個(gè)元素前元素個(gè)數(shù)4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)若i<j，數(shù)組元素A[i][j]在矩陣的上三角部分,在數(shù)組B中沒有存放，可以找它的對(duì)稱元素

A[j][i]：=j*(j+1)/2+i若已知某矩陣元素位于數(shù)組B的第k個(gè)位置（k≥0），應(yīng)如何確定相應(yīng)的i,j序號(hào)呢?4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)已知矩陣元素位于一維數(shù)組B的第k個(gè)位置（k≥0），反向確定相應(yīng)的i,j序號(hào)若已知某矩陣元素位于數(shù)組B的第k個(gè)位置（k≥0），應(yīng)如何確定相應(yīng)的i,j序號(hào)呢?可尋找滿足

i(i+1)/2k<(i+1)*(i+2)/2

的i,此即為該元素的行號(hào)。

j=k-i*(i+1)/2

此即為該元素的列號(hào)。例，當(dāng)k=8,3*4/2=6k<4*5/2=10,

取i=3。則j=8-3*4/2=2。上三角矩陣Ba00a01a02a03a11a12a13a22a23

a33

0123456789若i

j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為

n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素總數(shù)第i行第j個(gè)元素前元素個(gè)數(shù)n=44.2.1對(duì)稱矩陣的壓縮存儲(chǔ)4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)若ij，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==(2*n-i-1)*i/2+j若i>j，數(shù)組元素A[i][j]在矩陣的下三角部分，在數(shù)組B中沒有存放。因此，找它的對(duì)稱元素A[j][i]。A[j][i]在數(shù)組B的第(2*n-j-1)*j/2+i的位置中找到。Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

0123456789104.2.2三對(duì)角矩陣的壓縮存儲(chǔ)4.2.2三對(duì)角矩陣的壓縮存儲(chǔ)三對(duì)角矩陣中除主對(duì)角線及在主對(duì)角線上下最臨近的兩條對(duì)角線上的元素外，所有其它元素均為0?？偣灿?n-2個(gè)非零元素。將三對(duì)角矩陣A中三條對(duì)角線上的元素按行存放在一維數(shù)組B中，且a00存放于B[0]。在三條對(duì)角線上的元素aij滿足

0

i

n-1,i-1

j

i+1考察元素A[i][j]在一維數(shù)組B中的位置。由于A[i][j]在第i行，它前面有3*i-1個(gè)非零元素,在本行中第j列前面有j-i+1個(gè)，所以元素A[i][j]在B中位置為k=2*i+j。同樣思考一下反向查找，由k如何來確定i,j。4.2.2三對(duì)角矩陣的壓縮存儲(chǔ)若已知三對(duì)角矩陣中某元素A[i][j]

在數(shù)組B[]存放于第k

個(gè)位置，則有

i=(k+1)/3（k的序號(hào)從0開始）

j=k-2*i例如，當(dāng)k=8時(shí)，

i=(8+1)/3=3,j=8-2*3=2

當(dāng)k=10時(shí)，

i=(10+1)/3=3,j=10-2*3=44.3稀疏矩陣(SparseMatrix)4.3.1稀疏矩陣及其三元數(shù)組表示4.3.2稀疏矩陣的轉(zhuǎn)置4.3.1稀疏矩陣及其三元數(shù)組表示設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s≤m×n），則稱A為稀疏矩陣。4.3.1稀疏矩陣及其三元數(shù)組表示設(shè)矩陣A中有s個(gè)非零元素。令e=s/(m*n),稱e為矩陣的稀疏因子。比較認(rèn)可的指標(biāo)：e≤0.05時(shí)稱為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，為節(jié)省存儲(chǔ)空間，應(yīng)只存儲(chǔ)非零元素。但由于非零元素的分布一般沒有規(guī)律，故在存儲(chǔ)非零元素時(shí)，必須記下它所在的行和列的位置(i,j)。每一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元素。因此，稀疏矩陣可由表示非零元的一系列三元組及其行列數(shù)唯一確定。1.稀疏矩陣的定義constintdrows=6,dcols=7,dterms=8;//非零元個(gè)數(shù)template<classE>structTriple{//三元組類

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

Evalue;//非零元素的值

Triple<E>&operator=(Triple<E>&R)//結(jié)點(diǎn)賦值

{row=R.row;col=R.col;value=R.value;}}; template<classE>classSparseMatrix{public:SparseMatrix(intRw=drows,intCl=dcols,intTm=dterms);//構(gòu)造函數(shù)~SparseMatrix(){delete[]smArray;}//析構(gòu)函數(shù)voidTranspose(SparseMatrix<E>&B);//轉(zhuǎn)置voidAdd(SparseMatrix<E>&B);//A=A+BvoidMultiply(SparseMatrix<E>&B);//A=A*Bprivate:intRows,Cols,Terms;//行／列／非零元素?cái)?shù)Triple<E>*smArray;//三元組表};2.稀疏矩陣的構(gòu)造函數(shù)template<classE>SparseMatrix<E>::SparseMatrix(intRw,intCl,intTm){Rows=Rw;Cols=Cl;Terms=Tm;smArray=newTriple[Terms];//三元組表if(smArray==NULL){cerr<<“存儲(chǔ)分配失?。　?lt;<endl;exit(1);}};4.3.2稀疏矩陣的轉(zhuǎn)置一個(gè)mn

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

的矩陣，即矩陣A的行成為矩陣B的列矩陣A的列成為矩陣B的行。在稀疏矩陣的三元組表中，非零矩陣元素按行存放。當(dāng)行號(hào)相同時(shí)，按列號(hào)遞增的順序存放。稀疏矩陣的轉(zhuǎn)置運(yùn)算要轉(zhuǎn)化為對(duì)應(yīng)三元組表的轉(zhuǎn)置。例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=4.3.2稀疏矩陣的轉(zhuǎn)置-三元組順序表轉(zhuǎn)置稀疏矩陣轉(zhuǎn)置矩陣原矩陣三元組表

轉(zhuǎn)置矩陣三元組表1.用三元組表表示的稀疏矩陣及其轉(zhuǎn)置2.稀疏矩陣轉(zhuǎn)置的樸素算法設(shè)矩陣列數(shù)為Cols，對(duì)矩陣三元組表掃描Cols次。第k次檢測列號(hào)為k的項(xiàng)。第k次掃描搜尋所有列號(hào)為k的項(xiàng)，將其行號(hào)變列號(hào)、列號(hào)變行號(hào)，順次存于轉(zhuǎn)置矩陣三元組表。2.稀疏矩陣轉(zhuǎn)置的樸素算法template<classE>voidSparseMatrix<E>::Transpose(SparseMatrix<E>&B){//轉(zhuǎn)置this矩陣，轉(zhuǎn)置結(jié)果由B返回

B.Rows=Cols;B.Cols=Rows;B.Terms=Terms;//轉(zhuǎn)置矩陣的列數(shù),行數(shù)和非零元素個(gè)數(shù)

if(Terms>0){ intCurrentB=0;//轉(zhuǎn)置三元組表存放指針

inti,k;

for(k=0;k<Cols;k++)//處理所有列號(hào)

for(i=0;i<Terms;i++)

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

B.smArray[CurrentB].col=smArray[i].row;

B.smArray[CurrentB].value=smArray[i].value;

CurrentB++;

}}};

3.樸素算法分析與快速轉(zhuǎn)置算法設(shè)矩陣三元組表總共有t項(xiàng)，上述算法的時(shí)間代價(jià)為O(n*t)。若矩陣有200行，200列，10,000個(gè)非零元素，總共有2,000,000次處理?？焖俎D(zhuǎn)置算法的思想為：對(duì)原矩陣A掃描一遍，按A中每一元素的列號(hào)，立即確定在轉(zhuǎn)置矩陣B三元組表中的位置，并裝入它。3.樸素算法分析與快速轉(zhuǎn)置算法為加速轉(zhuǎn)置速度，建立輔助數(shù)組rowSize和rowStart：rowSize記錄矩陣轉(zhuǎn)置前各列，即轉(zhuǎn)置后矩陣各行非零元素個(gè)數(shù)；rowStart記錄各行非零元素在轉(zhuǎn)置三元組表中開始存放位置。掃描矩陣三元組表，根據(jù)某項(xiàng)列號(hào)，確定它轉(zhuǎn)置后的行號(hào),查rowStart表,按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中。4.稀疏矩陣的快速轉(zhuǎn)置算法template<classE>voidSparseMatrix<E>::FastTranspos(SparseMatrix<E>&B){int*rowSize=newint[Cols];//列元素?cái)?shù)數(shù)組

int*rowStart=newint[Cols];//轉(zhuǎn)置位置數(shù)組

B.Rows=Cols;B.Cols=Rows;B.Terms=Terms;if(Terms>0){inti,j;for(i=0;i<Cols;i++)rowSize[i]=0;

for(i=0;i<Terms;i++)rowSize[smArray[i].col]++;//原矩陣各列非零元數(shù)

rowStart[0]=0;

for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<Terms;i++){

j=rowStart[smArray[i].col];

//第i個(gè)非零元在矩陣B中應(yīng)放的位置

B.smArray[j].row=smArray[i].col;//傳送

B.smArray[j].col=smArray[i].row; B.smArray[j].value=smArray[i].value; rowStart[smArray[i].col]++;//修改該行應(yīng)放位置

}

}

delete[]rowSize;

delete[]rowStart;}5.快速轉(zhuǎn)置運(yùn)算的時(shí)間復(fù)雜性分析程序中共有4個(gè)并列循環(huán),時(shí)間復(fù)雜度分別為O(Cols),O(Terms),O(Cols),O(Terms),

所以,快速轉(zhuǎn)置運(yùn)算的時(shí)間復(fù)雜性為

O(Cols+Terms)4.4字符串字符串的概念C++有關(guān)字符串的庫函數(shù)字符串的實(shí)現(xiàn)字符串的模式匹配4.4.1字符串的概念字符(char)：組成字符串的基本單位字符串是n(0)個(gè)字符的有限序列，記作S:“c1c2c3…cn”

其中，S是串名字“c1c2c3…cn”是串值

ci是串中字符

n是串的長度，n=0稱為空串。例如,S=“QinghaiUniversity”。注意：空串和空白串不同，例如“”和“”分別表示長度為1的空白串和長度為0的空串。4.4.1字符串的概念串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)，該子串首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的位置。例如，設(shè)A和B分別為

A=“Thisisastring”B=“is”

則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，首次出現(xiàn)所對(duì)應(yīng)的主串位置是2（從0開始）。因此，稱B在A中的位置為2。特別地，空串是任意串的子串，任意串是其自身的子串。4.4.2C++有關(guān)字符串的庫函數(shù)1.strcpy字符串復(fù)制使用格式intstrcpy(char*string1,char*string2)2.strncpy字符串部分復(fù)制使用格式intstrncpy(char*string1,char*string2,intn)3.strcat字符串連接使用格式intstrcat(char*string1,char*string2)4.strncat將特定數(shù)量字符串連接到另一字符串使用格式intstrncat(char*string1,char*string2,intn)4.4.2C++有關(guān)字符串的庫函數(shù)5.strchr在給定字符串中搜尋指定字符使用格式char*strchr(char*string1,charch)6.strcspn在給定字符串中搜尋某個(gè)指定字符最后一次出現(xiàn)的地址使用格式intstrcspn(char*string1,charch)7.strlen計(jì)算字符串的長度使用格式intstrlen(constchar*string1)8.strcmp字符串比較大小使用格式intstrcmp(char*string1,char*string2)4.4.3字符串的實(shí)現(xiàn)—字符串的類定義#ifndefASTRING_H //定義在文件“Astring.h”中#defineASTRING_H#definedefaultSize=128;//字符串的最大長度classAString{//對(duì)象:零個(gè)或多個(gè)字符的一個(gè)有限序列。private:char*ch; //串存放數(shù)組intcurLength; //串的實(shí)際長度 intmaxSize; //存放串的最大長度public:AString(intsz=defaultSize);//構(gòu)造函數(shù)創(chuàng)建一個(gè)空串AString(constchar*init);//構(gòu)造函數(shù)從已有字符數(shù)組*init復(fù)制AString(constAString&ob);//復(fù)制構(gòu)造函數(shù)從已有串ob復(fù)制～AString(){delete[]ch;} //析構(gòu)函數(shù)intLength()const{returncurLength;} //求長度Astring&operator()(intpos,intlen);//求子串booloperator==(AString&ob)const{returnstrcmp(ch,ob.ch)==0;} //判串相等.若串相等,則函數(shù)返回truebooloperator!=(AString&ob)const{returnstrcmp(ch,ob.ch)!=0;} //判串不等.若串不相等,則函數(shù)返回truebooloperator!()const{returncurLength==0;} //判串空否。若串空,則函數(shù)返回trueAString&operator=(AString&ob);//串賦值A(chǔ)String&operator+=(AString&ob); //串連接char&operator[](inti); //取第i個(gè)字符intFind(AString&pat,intk)const; //串匹配};在此定義下ch[0]至ch[curLenghth-1]中存放的是當(dāng)前字符串，ch[curLenghth]=‘\0’4.4.3字符串的實(shí)現(xiàn)—字符串的構(gòu)造函數(shù)AString::AString(intsz){//構(gòu)造函數(shù)：創(chuàng)建一個(gè)空串maxSize=sz;ch=newchar[maxSize+1];//創(chuàng)建串?dāng)?shù)組if(ch==NULL){cerr<<“存儲(chǔ)分配錯(cuò)!\n”;exit(1);}curLength=0;ch[0]=‘\0’;};4.4.3字符串的實(shí)現(xiàn)—字符串的構(gòu)造函數(shù)AString::AString(constchar*init){//復(fù)制構(gòu)造函數(shù):從已有字符數(shù)組*init復(fù)制intlen=strlen(init);maxSize=(len>defaultSize)?len:defaultSize;ch=newchar[maxSize+1];//創(chuàng)建串?dāng)?shù)組if(ch==NULL){cerr<<“存儲(chǔ)分配錯(cuò)!\n”;exit(1);}curLength=len; //復(fù)制串長度strcpy(ch,init); //復(fù)制串值 }；4.4.3字符串的實(shí)現(xiàn)—提取子串的算法示例pos+len-1 pos+len-1curLen-1curLen可以全部提取只能從pos取到串尾infinityinfinitypos=2,len=3pos=5,len=4finity超出4.4.3字符串的實(shí)現(xiàn)—提取子串AStringAString::operator()(intpos,intlen){//從串中第pos個(gè)位置起連續(xù)提取len個(gè)字符形成//子串返回 AStringtemp;//建立空串對(duì)象if(pos>=0&&pos+len-1<maxLen&&len>0){//提取子串 if(pos+len-1>=curLength)len=curLength-pos;//調(diào)整提取字符數(shù)temp.curLength=len;//子串長度4.4.3字符串的實(shí)現(xiàn)—提取子串for(inti=0,j=pos;i<len;i++,j++) temp.ch[i]=ch[j];//傳送串?dāng)?shù)組 temp.ch[len]=‘\0’;//子串結(jié)束}returntemp;}; 例：串st=“university”,pos=3,len=4 使用示例subSt=st(3,4) 提取子串subSt=“vers”4.4.3字符串的實(shí)現(xiàn)—串連接AString&AString::operator+=(constAString&ob){char*temp=ch; //暫存原串?dāng)?shù)組 intn=curLength+ob.curLength; //串長度累加 intm=(maxSize>=n)?maxSize:n;//新空間大小 ch=newchar[m+1];if(ch==NULL){cerr<<“存儲(chǔ)分配錯(cuò)!\n”;exit(1);} maxSize=m;curLength=n; strcpy(ch,temp); //拷貝原串?dāng)?shù)組 strcat(ch,ob.ch); //連接ob串?dāng)?shù)組 4.4.3字符串的實(shí)現(xiàn)—串連接delete[]temp;return*this;//P161修改};例：串st1=“Qinghai”, st2=“University”, 使用示例st1+=st2; 連接結(jié)果st1=“QinghaiUniversity” st2=“University”

4.4.4字符串的模式匹配1.strcpy字符串復(fù)制使用格式intstrcpy(char*string1,char*string2)2.strncpy字符串部分復(fù)制使用格式intstrncpy(char*string1,char*string2,intn)3.strcat字符串連接使用格式intstrcat(char*string1,char*string2)4.strncat將特定數(shù)量字符串連接到另一字符串使用格式intstrncat(char*string1,char*string2,intn)4.4.4字符串的模式匹配設(shè)有兩個(gè)串t和p:t=t0t1…tn-1，p=p0p1…pm-1

其中1<m<=n(通常m<<n)模式匹配的目的是在t中找出和p相同的子串。此時(shí)，t稱為“目標(biāo)”，而p稱為“模式”。模式匹配的結(jié)果有兩種：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失?。悍祷匾粋€(gè)特定的標(biāo)志（如-1）。4.4.4字符串的模式匹配定義在主串中尋找子串（第一個(gè)字符）在串中的位置詞匯在模式匹配中，子串稱為模式，主串稱為目標(biāo)。示例目標(biāo)T:“Beijing”模式P:“jin”匹配結(jié)果=3樸素的模式匹配（B-F算法）第1趟

Tabbaba Paba

第2趟

Tabbaba P

aba

i=2j=2i=1j=0第3趟

Tabbaba Paba

第4趟

Tabbaba P

aba

i=2j=0i=6j=3intAString::Find(AString&pat,intk)const{//在當(dāng)前串中從第k個(gè)字符開始尋找模式pat在當(dāng)//前串中匹配的位置。若匹配成功,則函數(shù)返回首//次匹配的位置,否則返回-1。

inti,j,n=curLength,m=pat.curLength;for(i=k;i<=n-m;i++){//第k個(gè)字符開始

for(j=0;j<m;j++)

if(ch[i+j]!=pat.ch[j])break;//本次失配

if(j==m)returni;

//pat掃描完,匹配成功

}

return

-1; //pat為空或在*this中找不到它};

樸素的模式匹配算法4.4.4字符串的模式匹配在最壞情況下，若設(shè)n為目標(biāo)串長度，m為模式串長度，則匹配算法最多比較n-m+1趟，每趟比較都在比較到模式串尾部才出現(xiàn)不等，要做m次比較，總比較次數(shù)將達(dá)到(n-m+1)*m。在多數(shù)場合下m遠(yuǎn)小于n，因此，算法的運(yùn)行時(shí)間為O(n*m)。低效的原因在于每趟重新比較時(shí)，目標(biāo)串的檢測指針要回退(仔細(xì)理解回退的含義)。改進(jìn)的模式匹配-KMP算法如能消除每趟失配后為實(shí)施下一趟比較時(shí)目標(biāo)指針的回退，便可提高模式匹配效率。KMP--D.E.Knuth+J.H.Morris+V.R.Pratt1977,FastpatternmatchinginstringsSIAMJournalonComputing6(1):323-350.思想：利用以往比較所提供的信息，避免目標(biāo)串的回退

依次比較當(dāng)前字符對(duì)T[i]和P[j]根據(jù)模式串P，事先構(gòu)造next[]表否則，模式串回退到next[]指示的位置//目標(biāo)串不用回退若T[i]=P[j]，目標(biāo)串、模式串都前進(jìn)一個(gè)字符//i++;j++;直到模式串全部匹配實(shí)施KMP算法的時(shí)間代價(jià)：O(n+m)目標(biāo)指針的回退第1趟

Tabbaba Paba

第2趟

Tabbaba P

aba

i=2j=2i=1j=0第3趟

Tabbaba Paba

第4趟

Tabbaba P

aba

i=2j=0i=6j=3

T

t0t1…ts-1tsts+1ts+2…ts+j-1

ts+j

ts+j+1…tn-1

‖‖‖‖‖P p0p1p2…pj-1

pj

//失配

則有

tsts+1ts+2…ts+j-1=p0p1p2…pj-1(1)

繼續(xù)進(jìn)行后為使模式P與目標(biāo)T匹配，必須滿足

p0p1p2…pj-1…pm-1=ts+1ts+2ts+3…ts+j…ts+m

如果

p0p1…pj-2p1p2…pj-1 (2)

則立刻可以斷定

p0p1…pj-2ts+1ts+2…ts+j-1

下一趟必不匹配p0p1…pj-2同樣，若 p0p1…pj-3p2p3…pj-1則再下一趟也不匹配，因?yàn)橛?/p>

p0p1…pj-3ts+2ts+3…ts+j-1直到對(duì)于某一個(gè)“k”值，使得

p0p1…pk+1pj-k-2pj-k-1…pj-1且

p0p1…pk=

pj-k-1pj-k…pj-1則

p0p1…pk=ts+j-k-1ts+j-k…ts+j-1

‖‖‖ pj-k-1pj-k…pj-1下一趟可以直接用pk+1與ts+j繼續(xù)比較。k的確定方法Knuth等人發(fā)現(xiàn)，