數(shù)據(jù)結構課件：第四章 數(shù)組、串與廣義表

1第四章數(shù)組、串與廣義表一維數(shù)組與多維數(shù)組特殊矩陣稀疏矩陣字符串廣義表2一維數(shù)組定義

數(shù)組是相同類型的數(shù)據(jù)元素的集合，而一維數(shù)組的每個數(shù)組元素是一個序對，由下標（index）和值（value）組成。

一維數(shù)組的示例在高級語言中的一維數(shù)組只能按元素的下標直接存取數(shù)組元素的值。3527491860547783410201234567893一維數(shù)組的定義和初始化#include<iostream.h>main(){

inta[3]={3,5,7},*elem,i; //靜態(tài)數(shù)組

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

cout

<<a[i]<<

endl;elem=new

int[3];

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

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

cin

>>elem[i];

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

{

cout<<*elem<<endl;elem++;}

}

4多維數(shù)組多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的特點是每一個數(shù)據(jù)元素可以有多個直接前驅和多個直接后繼。數(shù)組元素的下標一般具有固定的下界和上界，因此它比其他復雜的非線性結構簡單。例如二維數(shù)組的數(shù)組元素有兩個直接前驅，兩個直接后繼，必須有兩個下標（行、列）以標識該元素的位置。5

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

i列向量下標j行向量下標

j

列向量下標

k6數(shù)組的連續(xù)存儲方式一維數(shù)組LOC(i)=

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

a,i=0

352749186054778341020123456789llllllllll

a+i*la7二維數(shù)組一維數(shù)組常被稱為向量（Vector）。二維數(shù)組A[m][n]可看成是由m個行向量組成的向量，也可看成是由n個列向量組成的向量。一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型:

typedefTarray2[m][n];//T為元素類型

等價于：

typedefTarray1[n];//行向量類型

typedefarray1array2[m];//二維數(shù)組類型8同理，一個三維數(shù)組類型可以定義為其數(shù)據(jù)元素為二維數(shù)組類型的一維數(shù)組類型。靜態(tài)定義的數(shù)組，其維數(shù)和維界不再改變，在編譯時靜態(tài)分配存儲空間。一旦數(shù)組空間用完則不能擴充。動態(tài)定義的數(shù)組，其維界不在說明語句中顯式定義，而是在程序運行中創(chuàng)建數(shù)組對象時通過new動態(tài)分配和初始化，在對象銷毀時通過delete動態(tài)釋放。用一維內存來表示多維數(shù)組，就必須按某種次序將數(shù)組元素排列到一個序列中。9二維數(shù)組的動態(tài)定義和初始化#include

<iostream.h>…………int**A;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];…………10

二維數(shù)組中數(shù)組元素的順序存放行優(yōu)先存放：設數(shù)組開始存放位置LOC(0,0)=a,每個元素占用l

個存儲單元

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

列優(yōu)先存放：設數(shù)組開始存放位置LOC(0,0)=a,每個元素占用l

個存儲單元

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

三維數(shù)組各維元素個數(shù)為

m1,m2,m3下標為i1,i2,i3的數(shù)組元素的存儲地址： （按頁／行／列存放）

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

+i2*m3

+i3

)*l

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

行前

i3

列元素個數(shù)13

n維數(shù)組各維元素個數(shù)為

m1,m2,m3,…,mn下標為i1,i2,i3,…,in

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

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

)*l

14特殊矩陣特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。特殊矩陣的壓縮存儲主要是針對階數(shù)很高的特殊矩陣。為節(jié)省存儲空間，對可以不存儲的元素，如零元素或對稱元素，不再存儲。對稱矩陣三對角矩陣15對稱矩陣的壓縮存儲設有一個nn的對稱矩陣A。對稱矩陣中的元素關于主對角線對稱，aij

=aji，

0≤i,j≤n-116為節(jié)約存儲，只存對角線及對角線以上的元素，或者只存對角線或對角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。下三角矩陣17上三角矩陣把它們按行存放于一個一維數(shù)組B中，稱之為對稱矩陣A的壓縮存儲方式。數(shù)組B共有n+(n-1)++1=

n*(n+1)／2

個元素。18下三角矩陣若

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個元素前元素個數(shù)19若i<j，數(shù)組元素A[i][j]在矩陣的上三角部分,在數(shù)組B中沒有存放，可以找它的對稱元素A[j][i]：=j*(j+1)/2+i

若已知某矩陣元素位于數(shù)組B的第k個位置（k≥0），可尋找滿足

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

的i,此即為該元素的行號。

j=k

-i*(i+1)/2

此即為該元素的列號。例，當k=8,3*4/2=6k

<4*5/2=10,

取i=3。則j=8-3*4/2=2。20上三角矩陣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個元素前元素個數(shù)n=421

若i

j，數(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中沒有存放。因此，找它的對稱元素A[j][i]。A[j][i]在數(shù)組B的第(2*n-j-1)*j/2+i

的位置中找到。22三對角矩陣的壓縮存儲Ba00a01a10a11a12a21a22a23…

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

01234567891023三對角矩陣中除主對角線及在主對角線上下最臨近的兩條對角線上的元素外，所有其它元素均為0。總共有3n-2個非零元素。將三對角矩陣A中三條對角線上的元素按行存放在一維數(shù)組B中，且a00存放于B[0]。在三條對角線上的元素aij

滿足

0

i

n-1,i-1

j

i+1在一維數(shù)組B中A[i][j]在第i行，它前面有3*i-1個非零元素,在本行中第j

列前面有j-i+1個，所以元素A[i][j]在B中位置為

k=

2*i+j。24若已知三對角矩陣中某元素A[i][j]

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

個位置，則有

i=(k+1)/3

j=k

-2*i例如，當k=8時，

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

當k=10時，

i=(10+1)/3=3,j=10-2*3=425稀疏矩陣(SparseMatrix)設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。26設矩陣A中有s個非零元素。令e=s/(m*n),稱e為矩陣的稀疏因子。有人認為e≤0.05時稱之為稀疏矩陣。在存儲稀疏矩陣時，為節(jié)省存儲空間，應只存儲非零元素。但由于非零元素的分布一般沒有規(guī)律，故在存儲非零元素時，必須記下它所在的行和列的位置(i,j)。每一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元素。因此，稀疏矩陣可由表示非零元的一系列三元組及其行列數(shù)唯一確定。27稀疏矩陣的定義constintdrows=6,dcols=7,dterms=9;template<classE>structTriple{//三元組

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

E

value;//非零元素的值

voidoperator=(Triple<E>&R)//賦值

{row=R.row;col=R.col;value=R.value;}};

template<classE>classSparseMatrix{28public:SparseMatrix(intRw=drows,intCl=dcols,

intTm=dterms);

//構造函數(shù)

voidTranspose(SparseMatrix<E>&b);//轉置

voidAdd(SparseMatrix<E>&a,SparseMatrix<E>&b);//a=a+b

voidMultiply(SparseMatrix<E>&a,

SparseMatrix<E>&b);//a=a*bpvivate:intRows,Cols,Terms;//行／列／非零元素數(shù)

Triple<E>*smArray;

//三元組表};

29稀疏矩陣的構造函數(shù)template<classE>SparseMatrix<E>::SparseMatrix(intRw,intCl,

intTm){

Rows=Rw;Cols=Cl;Terms=Tm;

smArray=newTriple[Terms];//三元組表

if(smArray==NULL){

cerr<<“存儲分配失??！”<<endl;

exit(1);

}};

30稀疏矩陣的轉置一個mn

的矩陣A，它的轉置矩陣B是一個nm

的矩陣，且A[i][j]=B[j][i]。即矩陣A的行成為矩陣B的列矩陣A的列成為矩陣B的行。在稀疏矩陣的三元組表中，非零矩陣元素按行存放。當行號相同時，按列號遞增的順序存放。稀疏矩陣的轉置運算要轉化為對應三元組表的轉置。31稀疏矩陣32轉置矩陣33用三元組表表示的稀疏矩陣及其轉置原矩陣三元組表轉置矩陣三元組表34稀疏矩陣轉置算法思想設矩陣列數(shù)為

Cols，對矩陣三元組表掃描Cols次。第

k次檢測列號為

k的項。第

k次掃描找尋所有列號為

k

的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表。35稀疏矩陣的轉置template<classE>voidSparseMatrix<E>::Transpose(SparseMatrix<E>&B){//轉置this矩陣，轉置結果由B返回

B.Rows=Cols;B.Cols=Rows;

B.Terms=Terms;

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

if(Terms>0){

intCurrentB=0;//轉置三元組表存放指針

inti,k;36

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

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

}}};

37快速轉置算法設矩陣三元組表總共有t項，上述算法的時間代價為O(n*t)。當非零元素的個數(shù)

t和m*n

同數(shù)量級時，算法transmatrix的時間復雜度為O(m*n2)。若矩陣有200行，200列，10,000個非零元素，總共有2,000,000次處理?？焖俎D置算法的思想為：對原矩陣A掃描一遍，按A中每一元素的列號，立即確定在轉置矩陣B三元組表中的位置，并裝入它。38為加速轉置速度，建立輔助數(shù)組

rowSize

和

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

rowStart

表,按查到的位置直接將該項存入轉置三元組表中。39A三元組(0)(1)(2)(3)(4)(5)(6)(7)行row00112345列col36153502值value22151117-639912840稀疏矩陣的快速轉置算法template<classE>voidSparseMatrix<E>::FastTranspos(SparseMatrix<E>&B){

int*rowSize=newint[Cols];//列元素數(shù)數(shù)組

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

B.Rows=Cols;B.Cols=Rows;

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

41

for(i=0;i<Terms;i++)rowSize[smArray[i].col]++;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]; 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]++;

}42

}

delete[]rowSize;

delete[]rowStart;}帶行指針數(shù)組的二元組表稀疏矩陣的三元組表可以用帶行指針數(shù)組的二元組表代替。在行指針數(shù)組中元素個數(shù)與矩陣行數(shù)相等。第i

個元素的下標i代表矩陣的第i

行，元素的內容即為稀疏矩陣第i

行的第一個非零元素在二元組表中的存放位置。43二元組表中每個二元組只記錄非零元素的列號和元素值，且各二元組按行號遞增的順序排列。

行指針數(shù)組

row

0

0

1

3

2

4

3

6

4

7

5

7

二元組表data

col

value

0

0

12

1

2

11

2

5

13

3

6

14

4

1

-4

5

5

3

6

3

8

7

1

-9

8

4

2

44字符串(String)字符串是

n

(0

)個字符的有限序列，記作

S:“c1c2c3…cn”

其中，S

是串名字

“c1c2c3…cn”是串值

ci是串中字符

n

是串的長度，n=0稱為空串。例如,

S=“TsinghuaUniversity”。注意：空串和空白串不同，例如“”和“”分別表示長度為1的空白串和長度為0的空串。45串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應地稱為主串。通常將子串在主串中首次出現(xiàn)時，該子串首字符對應的主串中的序號，定義為子串在主串中的位置。例如，設A和B分別為

A=“This

isastring”B=“is”

則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，首次出現(xiàn)所對應的主串位置是2（從0開始）。因此，稱B在A中的位置為2。特別地，空串是任意串的子串，任意串是其自身的子串。46通常在程序中使用的串可分為兩種：串變量和串常量。串常量在程序中只能被引用但不能改變它的值，即只能讀不能寫。通常串常量是由直接量來表示的，例如語句Error(“overflow”)

中“overflow”是直接量。但有的語言允許對串常量命名，以使程序易讀、易寫。如C++中，可定義

constcharpath[]=“dir/bin/appl”;這里path是一個串常量。串變量和其它類型的變量一樣，其取值可以改變。47字符串的類定義#ifndefASTRING_H

//定義在文件“Astring.h”中#defineASTRING_H#definedefaultSize=128;//字符串的最大長度classAString{//對象:零個或多個字符的一個有限序列。private:char*ch; //串存放數(shù)組

intcurLength; //串的實際長度

intmaxSize; //存放數(shù)組的最大長度public:48

AString(intsz=defaultSize);//構造函數(shù)

AString(constchar*init);//構造函數(shù)

AString(constAString&ob);//復制構造函數(shù)

～AString(){delete[]ch;} //析構函數(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ù)返回true

49booloperator!()const{returncurLength==0;}

//判串空否。若串空,則函數(shù)返回true

AString&operator=(AString&ob);

//串賦值

AString&operator+=(AString&ob); //串連接

char&operator[](inti); //取第i個字符

intFind(AString&pat,intk)const; //串匹配};50字符串的構造函數(shù)AString::AString(intsz){//構造函數(shù)：創(chuàng)建一個空串

maxSize=sz;ch=newchar[maxSize+1];//創(chuàng)建串數(shù)組

if(ch==NULL)

{cerr<<“存儲分配錯!\n”;exit(1);}curLength=0;ch[0]=‘\0’;};51字符串的構造函數(shù)AString::AString(const

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

intlen=strlen(init);

maxSize=(len>defaultSize)?len:defaultSize;ch=newchar[maxSize+1];//創(chuàng)建串數(shù)組

if(ch==NULL)

{cerr<<“存儲分配錯!\n”;exit(1);}curLength=len;

//復制串長度

strcpy(ch,init);

//復制串值

}；52字符串的復制構造函數(shù)AString::AString(constAString&ob){

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

maxSize=ob.maxSize;//復制串最大長度

ch=newchar[curLength+1];//創(chuàng)建串數(shù)組

if(ch==NULL)

{

cerr

<<

“存儲分配錯!

\n”;

exit(1);}curLength=ob.curLength;//復制串長度

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

};

53字符串重載操作的使用示例

序號重載操作操作使用示例(設使用操作的當前串為S：‘tsinghua’)1()(intpos,intlen)取子串S1=

S(3,2),//S1結果為‘ng’2==(constAString&ob)判兩串相等S

==S1,//若S與S1相等,

結果為true，否則為false3!=(constAString&ob)判兩串不等S!=S1,//若S與S1不等，結果為true，否則為false4!()判串空否!S,//若串S為空，結果為

true，否則為false54序號重載操作操作使用示例(設使用操作的當前串為S：‘tsinghua’)5=(constAString&ob)串賦值S1

=S,//S1結果為‘tsinghua’6+=(constAString&ob)串連接若設S1為‘university’,執(zhí)行S

+=S1,//S結果為‘tsinghuauniversity’7[](inti)取第i個字符S[5],//取出字符為‘h’55提取子串的算法示例pos+len-1 pos+len-1curLen-1curLen可以全部提取只能從pos取到串尾infinityinfinitypos=2,len=3pos=5,len=4finity超出56串重載操作：提取子串AString

AString::operator()(intpos,intlen){//從串中第

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

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

AStringtemp;//建立空串對象

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

{//提取子串

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

//調整提取字符數(shù)

temp.curLength=len;

//子串長度57for(inti=0,j=pos;i<len;i++,j++) temp.ch[i]=ch[j];//傳送串數(shù)組

temp.ch[len]=‘\0’;//子串結束

}

returntemp;};

例：串st=“university”,

pos=3,len=4

使用示例subSt=st(3,4)

提取子串

subSt=“vers”58串重載操作:串賦值AString&AString::operator=(constAString&ob){

if(&ob!=this){

//若兩個串相等為自我賦值

delete[]ch;

ch=new

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

if(ch==NULL)

{cerr<<“存儲分配失敗!\n”;exit(1);} curLength=ob.curLength;strcpy(ch,ob.ch);

}

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

returnthis;};59串重載操作：取串的第i個字符charAString::operator[](inti){//串重載操作：取當前串*this的第i個字符

if(i<0&&i>=curLength)

{cout<<“字符串下標超界!\n”;

exit(1);}

returnch[i];};例：串st=“university”,

使用示例newSt=st；newChar=st[1];

數(shù)組賦值結果

newSt=“university”

提取字符結果newChar=‘n’

60串重載操作:串連接AString&AString::operator+=(constAString&ob){

char*temp=ch; //暫存原串數(shù)組

intn=curLength+ob.curLength; //串長度累加

intm=(maxSize>=n)?maxSize:n;//新空間大小

ch=new

char[m];

if(ch==NULL)

{cerr<<“存儲分配錯!\n”;exit(1);} maxSize=m;curLength=n; strcpy(ch,temp);

//拷貝原串數(shù)組

strcat(ch,ob.ch); //連接ob串數(shù)組

61

delete[]temp;return

this;};例：串st1=“beijing”, st2=“university”,

使用示例st1+=st2;

連接結果

st1=“beijinguniversity” st2=“university”62串的模式匹配定義

在主串中尋找子串（第一個字符）在串中的位置詞匯

在模式匹配中，子串稱為模式，主串稱為目標。示例目標T:“Beijing”

模式P:“jin”

匹配結果=3

63樸素的模式匹配（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=364樸素的模式匹配算法intAString::Find(AString&pat,intk)const{//在當前串中從第k個字符開始尋找模式pat在當//前串中匹配的位置。若匹配成功,則函數(shù)返回首//次匹配的位置,否則返回-1。

inti,j,n=curLength,m=pat.curLength;for(i=k;i<=n-m;i++){ for(j=0;j<m;j++)

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

if(j==m)returni;

//pat掃描完,匹配成功

}

65

return

-1; //pat為空或在*this中找不到它};在最壞情況下，若設n為目標串長度，m為模式串長度，則匹配算法最多比較n-m+1趟，每趟比較都在比較到模式串尾部才出現(xiàn)不等，要做m次比較，總比較次數(shù)將達到(n-m+1)*m。在多數(shù)場合下m遠小于n，因此，算法的運行時間為O(n*m)。低效的原因在于每趟重新比較時，目標串的檢測指針要回退。66改進的模式匹配只要消除了每趟失配后為實施下一趟比較時目標指針的回退，可以提高模式匹配效率。這種處理思想是由D.E.Knuth、J.H.Morris和V.R.Pratt同時提出來的，故稱為KMP算法。實施KMP算法的時間代價：若每趟第一個不匹配，比較n-m+1趟，總比較次數(shù)最壞達(n-m)+m=n。若每趟第m個不匹配，總比較次數(shù)最壞亦達到n。67

目標T t0t1t2……tm-1…tn-1

模式pat p0p1p2……pm-1

目標T t0t1t2……tm-1tm…tn-1

模式pat p0p1……pm-2pm-1

目標T t0t1……titi+1……ti+m-2ti+m-1…tn-1

‖‖‖‖

模式pat

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

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)

為使模式P與目標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-269同樣，若 p0p1…pj-3p2p3…pj-1則再下一趟也不匹配，因為有

p0p1…pj-3ts+2ts+3…ts+j-1直到對于某一個“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ù)比較。70k的確定方法Knuth等人發(fā)現(xiàn)，對于不同的j（失配位置），k的取值不同，它僅依賴于模式P本身前j個字符的構成，與目標無關?？梢杂靡粋€next特征向量來確定：當模式P中第j個字符與目標S中相應字符失配時，模式P中應當由哪個字符（設為第k+1個）與目標中剛失配的字符重新繼續(xù)進行比較。71設模式P=p0p1...pm-2pm-1，next特征向量定義如下：示例j01234567Pabaabcacnext(j)-1001120172利用next特征向量進行匹配處理若設若在進行某一趟匹配比較時在模式P的第j位失配：如果j>0，那么在下一趟比較時模式串P的起始比較位置是pnext(j)，目標串T的指針不回溯，仍指向上一趟失配的字符；如果j=0，則目標串指針T進一，模式串指針P回到p0，繼續(xù)進行下一趟匹配比較。

73

運用KMP算法的匹配過程第1趟目標a

cabaabaabcacaabc

模式

a

baabcac

j=1next(1)=0，下次p0第2趟目標acabaabaabcacaabc

模式

abaabcac

j=0下次p0,目標指針進1

第3趟目標acabaab

aabcacaabc

模式

abaab

cac

j=5next(5)=2,

下次p2第4趟目標acabaaba

abcacaabc

模式

(ab)a

abcac

74用KMP算法實現(xiàn)的快速匹配算法intAString::fastFind(AString&pat,intk,intnext[])const{//從k開始尋找pat在this串中匹配的位置。若找//到，函數(shù)返回pat在this串中開始位置，否則函//數(shù)返回-1。數(shù)組next[]存放pat的next[j]值。

intposP=0,posT=k; //兩個串的掃描指針

intlengthP=pat.curLength;//模式串長度

intlengthT=curLength;//目標串長度

while(posP<lengthP&&posT<lengthT)

if(posP==-1||pat.ch[posP]==ch[posT])

{posP++;posT++;}

//對應字符匹配75

elseposP=next[posP];//求pat下趟比較位置

if(posP<lengthP)return

-1; //匹配失敗

elsereturnposT-lengthP; //匹配成功};此算法的時間復雜度取決于while循環(huán)。由于是無回溯的算法，執(zhí)行循環(huán)時，目標串字符比較有進無退，要么執(zhí)行posT和posP進1，要么查找next[]數(shù)組進行模式位置的右移，然后繼續(xù)向后比較。字符的比較次數(shù)最多為

O(lengthT)，不超過目標的長度。76next特征向量的計算設模式P=p0p1p2…pm-1由m

個字符組成，而next特征向量為next=n0n1n2…nm-1，表示了模式的字符分布特征。next特征向量從0,1,2,…,m-1逐項遞推計算:當j=0時，n0=-1。設

j>0時nj-1=k:當k=-1或j>0且pj-1=pk，則nj=k+1。當pj-1

pk

且

k

-1，令k=nk，并讓循環(huán)直到條件不滿足。當pj-1

pk

且

k

=-1，則nj=0。

77以前面的例子說明：j01234567Pabaabcacnext[j]-10011201j=4k=1p3p1k=nk=0p3=p0n4==k+1=1j=3k=0n3==k+1=1j=2k=0p1p0k=nk==-1n2==k+1=0j=1k=-1n1==k+1=0j=0n0=-1j=5k=1p4=p1n5==k+1=2j=6k=2p5p2k=nk=0p5p0k=nk=-1n5=k+1=0j=7k=0p6=p0n7=k+1=178對當前串計算next特征向量的算法voidAString::getNext(intnext[]){intj=0,k=-1,lengthP=curLength;

next[0]=-1;while(j<lengthP)

//計算next[j]if(k==-1||ch[j]==ch[k]){

j++;k++;

next[j]=k;}elsek=next[k];};

79廣義表(GeneralLists)廣義表是n(≥0)個表元素組成的有限序列，記作

LS(a1,a2,a3,…,an)LS是表名，ai是表元素，可以是表（稱為子表），可以是數(shù)據(jù)元素（稱為原子）。n為表的長度。n=0的廣義表為空表。n>0時，表的第一個表元素稱為廣義表的表頭（head），除此之外，其它表元素組成的表稱為廣義表的表尾（tail）。80廣義表的特性有次序性有長度有深度可共享可遞歸A()A長度為0，深度為1B(6,2)B長度為2，深度為1C(‘a’,(5,3,‘x’))C長度為2，深度為2D(B,C,A)D長度為3，深度為3E(B,D)E長度為？深度為？F(4,F)F長度為？深度為？81廣義表的表頭與表尾廣義表的第一個表元素即為該表的表頭，除表頭元素外其他表元素組成的表即為該表的表尾。A()head(A)和tail(A)不存在B(6,2)head(B)=6,tail(B)=(2)C(‘a’,(5,3,‘x’))head(C)=‘a’D(B,C,A)tail(C)=((5,3,’x’))E(B,D)head(((5,3,’x’)))=(5,3,’x’)F(4,F)tail(((5,3,’x’)))=()82ABCuvaxyzDuvaxyzBCAuvaxyzBCAED空表線性表再入表純表F遞歸表d83廣義表的表示list1=(a,b,c,d,e)list2=(a,(b,c,(d,e,f),(),g),h,(r,s,t))ahbcgsrtfedlist2alist1bdec84廣義表結點定義結點類型utype：=0,表頭；=1,原子數(shù)據(jù)；

=2,子表信息info：utype=0時,存放引用計數(shù)(ref)；utype=1時,存放數(shù)據(jù)值(value)；utype=2時,存放指向子表表頭的指針(hlink)尾指針tlink：utype=0時,指向該表第一個結點；utype0時,指向同一層下一個結點

utypeinfotlink

85廣義表的存儲表示EBF0

11h20

022D011d1e1f0

11

c2C0

12220

21

aDBBCA1

b01A86廣義表的類定義#include<iostream.h>#include<stdlib.h>template<classT>structItems{

//返回值的類結構定義

intutype; //結點類型＝0/1/2

union{ //聯(lián)合

intref;

//utype=0,存放引用計數(shù)

Tvalue; //utype=1,存放數(shù)值

GenListNode<T>*hlink;

//utype=2,存放指向子表的指針

}info;87Items():utype(0),info.ref(0){}//構造函數(shù)

Items(Items<T>&R)//復制構造函數(shù)

{utype=R.utype;info=R.info;}

};template<classT>structGenListNode{ //廣義表結點類定義

intutype; //＝0/1/2

GenListNode<T>*tlink; //同層下一結點指針

union{ //等價變量

intref; //存放引用計數(shù)

Tvalue; //存放數(shù)值

GenListNode<T>*hlink; //存放子表指針

88}info;

GenListNode()

//構造函數(shù)

:utype(0),tlink(NULL),info.ref(0){}

GenListNode(GenListNode<T>&R){

//復制構造函數(shù)

utype=R.utype;tlink=R.tlink;

info=R.info;}};template<classT>classGenList{ //廣義表類定義public:89

Genlist(); //構造函數(shù)～GenList();

//析構函數(shù)

boolHead(Items<T>&x);

//x返回表頭元素

boolTail(GenList<T><); //lt返回表尾

GenListNode<T>*First();

//返回第一個元素

GenListNode<T>*Next(GenListNode<T>*elem);

//返回表元素elem的直接后繼元素

voidCopy(constGenList<T>&R);

//廣義表的復制

intLength();

//計算廣義表長度

intdepth();

//計算非遞歸表深度

90private:GenListNode<T>*first; //廣義表頭指針

GenListNode<T>*Copy(GenListNode<T>*ls);

//復制一個ls指示的無共享非遞歸表

intLength(GenListNode<T>*ls);

//求由ls指示的廣義表的長度

intdepth(GenListNode<T>*ls);

//計算由ls指示的非遞歸表的深度

boolequal(GenListNode<T>*s,GenListNode<T>*t);

//判以s和t為表頭的兩個表是否相等

voidRemove(GenListNode<T>*ls);

//釋放以ls為附加頭結點的廣義表91

voidCreatelist(istream&in,

GenListNode<T>*&ls);

//從輸入流對象輸入廣義表的字符串描述,

//建立一個帶頭結點的廣義表結構friendistream&operator>>(istream&in,

GenList<T>&L);};92廣義表類的構造和訪問成員函數(shù)template<classT>Genlist<T>::GenList(){ //構造函數(shù)

GenListNode<T>*first=newGenListNode;if(first==NULL)

{cerr

<<“存儲分配失?。n”;exit(1);} };template<classT>boolGenList<T>::Head(Items<T>&x){//若廣義表非空，則通過x返回其第一個元素的值//否則函數(shù)沒有定義

93if(first->tlink==NULL)returnfalse; //空表

else{ //非空表

x.utype=first->tlink->utype;

=first->tlink->info; returntrue; //x返回表頭的值

}};template<classT>boolGenList<T>::Tail(GenList<T><){//若廣義表非空，則通過lt返回廣義表除表頭元素//以外其他元素組成的表，否則函數(shù)沒有定義

if(first->tlink==NULL)returnfalse; //空表94else{ //非空表

lt.first->utype=0; //設置頭結點