數(shù)據(jù)結(jié)構(gòu)課件C 版第四章

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

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

一維數(shù)組的示例在高級語言中的一維數(shù)組只能按元素的下標(biāo)直接存取數(shù)組元素的值。3527491860547783410201234567892一維數(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];

while(elem)

{

cout<<*elem

<<endl;

elem++;}

}

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

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

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

j

列向量下標(biāo)

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

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

a,i=0

352749186054778341020123456789llllllllll

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

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

等價于：

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

typedef

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

<iostream.h>…………int**A;int

row=3,col=3;int

i,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];…………9

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

個存儲單元

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

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

個存儲單元

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

三維數(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ù)12

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

m1,m2,m3,…,mn下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲地址：(存放的優(yōu)先順序隨維數(shù)增大逐漸變小)

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

)*l

13特殊矩陣特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。特殊矩陣的壓縮存儲主要是針對階數(shù)很高的特殊矩陣。為節(jié)省存儲空間，對可以不存儲的元素，如零元素或?qū)ΨQ元素，不再存儲。對稱矩陣三對角矩陣14對稱矩陣的壓縮存儲設(shè)有一個n

n的對稱矩陣

A。對稱矩陣中的元素關(guān)于主對角線對稱，aij

=aji，

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

+1=

n*(n+1)／2

個元素。17下三角矩陣若

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

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

i(i+1)/2

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

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

j=k

-i*(i+1)/2

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

k

<4*5/2=10,

取i=3。則j=8-3*4/2=2。19上三角矩陣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=420

若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

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

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

01234567891022稀疏矩陣(SparseMatrix)設(shè)矩陣A中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。23設(shè)矩陣A中有s個非零元素。令e=s/(m*n),稱e為矩陣的稀疏因子。有人認(rèn)為e≤0.05時稱之為稀疏矩陣。在存儲稀疏矩陣時，為節(jié)省存儲空間，應(yīng)只存儲非零元素。但由于非零元素的分布一般沒有規(guī)律，故在存儲非零元素時，必須記下它所在的行和列的位置(i,j)。每一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元素。因此，稀疏矩陣可由表示非零元的一系列三元組及其行列數(shù)唯一確定。24稀疏矩陣的類定義及函數(shù)實現(xiàn)P142-p14525稀疏矩陣的轉(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)置。26稀疏矩陣27轉(zhuǎn)置矩陣28用三元組表表示的稀疏矩陣及其轉(zhuǎn)置原矩陣三元組表轉(zhuǎn)置矩陣三元組表29稀疏矩陣轉(zhuǎn)置算法思想設(shè)矩陣列數(shù)為

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

k次檢測列號為

k的項。第

k次掃描找尋所有列號為

k

的項，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。稀疏矩陣的轉(zhuǎn)置算法見p145-p14630快速轉(zhuǎn)置算法設(shè)矩陣三元組表總共有t項，上述算法的時間代價為O(n*t)。當(dāng)非零元素的個數(shù)

t和m*n

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

rowSize

和

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

rowStart

表,按查到的位置直接將該項存入轉(zhuǎn)置三元組表中。舉例32稀疏矩陣的快速轉(zhuǎn)置算法見p147帶行指針數(shù)組的二元組表稀疏矩陣的三元組表可以用帶行指針數(shù)組的二元組表代替。在行指針數(shù)組中元素個數(shù)與矩陣行數(shù)相等。第i

個元素的下標(biāo)i代表矩陣的第i

行，元素的內(nèi)容即為稀疏矩陣第i

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

行指針數(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

34字符串(String)字符串是

n

(0

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

S:“c1c2c3…cn”

其中，S

是串名字

“c1c2c3…cn”是串值

ci

是串中字符

n

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

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

A=“This

isastring”B=“is”

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

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

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

ASTRING_H

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

int

curLength; //串的實際長度

int

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

AString(int

sz=defaultSize);//構(gòu)造函數(shù)

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

AString(const

AString&ob);//復(fù)制構(gòu)造函數(shù)

～AString(){delete[]ch;} //析構(gòu)函數(shù)

int

Length()const{returncurLength;} //求長度

Astring&operator()(int

pos,int

len);//求子串

booloperator==(AString&ob)const{returnstrcmp

(ch,ob.ch)==0;}

//判串相等.若串相等,則函數(shù)返回true

booloperator!=(AString&ob)const{returnstrcmp(ch,ob.ch)

!=0;}

//判串不等.若串不相等,則函數(shù)返回true

39

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

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

AString&operator=(AString&ob);

//串賦值

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

char&operator[](int

i); //取第i個字符

int

Find(AString&pat,

intk)const; //串匹配};40字符串的構(gòu)造函數(shù)AString::AString(int

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

maxSize=sz;

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

if(ch==NULL)

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

curLength=0;ch[0]=‘\0’;};41字符串的構(gòu)造函數(shù)AString::AString(const

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

int

len=strlen(init);

maxSize=(len>defaultSize)?

len

:

defaultSize;

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

if(ch

==NULL)

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

curLength=len;

//復(fù)制串長度

strcpy(ch,init);

//復(fù)制串值

}；42字符串的復(fù)制構(gòu)造函數(shù)AString

::AString(const

AString&ob){

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

maxSize=ob.maxSize;//復(fù)制串最大長度

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

if(ch

==NULL)

{

cerr

<<

“存儲分配錯!

\n”;

exit(1);}

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

strcpy(ch,

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

};

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

序號重載操作操作使用示例(設(shè)使用操作的當(dāng)前串為S：‘tsinghua’)

1()(intpos,int

len)取子串S1=

S(3,2),//S1結(jié)果為‘ng’

2==(const

AString&ob)判兩串相等S

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

結(jié)果為true，否則為false

3!=(const

AString&ob)判兩串不等S!=S1,//若S與S1不等，結(jié)果為true，否則為false

4!()判串空否!S,//若串S為空，結(jié)果為

true，否則為false44序號重載操作操作使用示例(設(shè)使用操作的當(dāng)前串為S：‘tsinghua’)

5=(const

AString&ob)串賦值S1

=S,//S1結(jié)果為‘tsinghua’

6+=(const

AString&ob)串連接若設(shè)S1為‘university’,執(zhí)行S

+=S1,//S結(jié)果為‘tsinghuauniversity’

7[](inti)取第i個字符S[5],//取出字符為‘h’45提取子串的算法示例pos+len-1 pos+len

-1

curLen-1

curLen可以全部提取只能從pos取到串尾infinityinfinitypos=2,len=3pos=5,len=4finity超出46串重載操作：提取子串AString

AString::operator

()(int

pos,int

len){//從串中第

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

len

個字符形成//子串返回

AStringtemp;//建立空串對象

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

&&

len>0)

{//提取子串

if(pos+len-1>=curLength)

len=curLength

-pos;

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

temp.curLength=len;

//子串長度47

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”48串重載操作:串賦值A(chǔ)String&

AString::operator=(const

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

return*this;};49串重載操作：取串的第i個字符charAString::operator[](int

i){//串重載操作：取當(dāng)前串*this的第i個字符

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

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

exit(1);}

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

使用示例newSt

=st；newChar

=st[1];

數(shù)組賦值結(jié)果

newSt

=“university”

提取字符結(jié)果newChar=‘n’

50串重載操作:串連接AString&

AString::operator+=(const

AString&ob){

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

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

int

m=(maxSize>=n)?

maxSize

:n;//新空間大小

ch=new

char[m];

if(ch

==NULL)

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

maxSize=m;

curLength=n;

strcpy(ch,temp);

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

strcat(ch,ob.ch); //連接ob串?dāng)?shù)組

51

delete[]temp;return*this;};例：串st1=“beijing

”, st2=“university”,

使用示例st1+=st2;

連接結(jié)果

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

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

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

模式P:“jin”

匹配結(jié)果=3

53樸素的模式匹配（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=354樸素的模式匹配算法int

AString::Find(AString&pat,intk)const{//在當(dāng)前串中從第k個字符開始尋找模式pat在當(dāng)//前串中匹配的位置。若匹配成功,則函數(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掃描完,匹配成功

}

55

return

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

目標(biāo)T t0t1t2……tm-1…tn-1

模式pat p0p1p2……pm-1

目標(biāo)T t0t1t2……tm-1tm…tn-1

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

目標(biāo)T t0t1……titi+1……ti+m-2ti+m-1…tn-1

‖‖‖‖

模式pat

p0p1……pm-2pm-1改進(jìn)的模式匹配58

T

t0t1…ts-1

tsts+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與目標(biāo)T匹配，必須滿足

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

如果

p0p1…pj-2

p1p2…pj-1 (2)

則立刻可以斷定

p0p1…pj-2

ts+1ts+2…ts+j-1

下一趟必不匹配p0p1…pj-259同樣，若 p0p1…pj-3

p2p3…pj-1則再下一趟也不匹配，因為有

p0p1…pj-3

ts+2ts+3…ts+j-1直到對于某一個“k”值，使得

p0p1…pk+1

pj-k-2pj-k-1…pj-1且

p0p1…pk

=

pj-k-1

pj-k

…pj-1則

p0p1…pk

=ts+j-k-1

ts+j-k…ts+j-1

‖‖‖ pj-k-1pj-k

…pj-1下一趟可以直接用pk+1與ts+j

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

63

運用KMP算法的匹配過程第1趟目標(biāo)a

cabaabaabcacaabc

模式

a

baabcac

j=1

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

模式

abaabcac

j=0

下次p0,目標(biāo)指針進(jìn)1

第3趟目標(biāo)acabaab

aabcacaabc

模式

abaab

cac

j=5

next(5)=2,

下次p2第4趟目標(biāo)acabaaba

abcacaabc

模式

(ab)a

abcac

64用KMP算法實現(xiàn)的快速匹配算法int

AString::fastFind(AString&pat,intk,

intnext[])const{//從k開始尋找pat在this串中匹配的位置。若找//到，函數(shù)返回pat在this串中開始位置，否則函//數(shù)返回-1。數(shù)組next[]存放pat的next[j]值。

int

posP=0,

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

int

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

int

lengthT=curLength;//目標(biāo)串長度

while(posP<lengthP

&&

posT<lengthT)

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

{

posP++;

posT++;}

//對應(yīng)字符匹配65

else

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

if(posP<lengthP)return

-1; //匹配失敗

elsereturn

posT-lengthP; //匹配成功};此算法的時間復(fù)雜度取決于while循環(huán)。由于是無回溯的算法，執(zhí)行循環(huán)時，目標(biāo)串字符比較有進(jìn)無退，要么執(zhí)行posT

和posP

進(jìn)1，要么查找next[]數(shù)組進(jìn)行模式位置的右移，然后繼續(xù)向后比較。字符的比較次數(shù)最多為

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

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

j>0時nj-1=k:當(dāng)k=-1或j>0且pj-1=

pk，則nj=k+1。當(dāng)pj-1

pk

且

k

-1，令k=nk，并讓

循環(huán)直到條件不滿足。當(dāng)pj-1

pk

且

k

=-1，則nj=0。

67以前面的例子說明：j01234567Pabaabcacnext[j]-10011201j=4k=1p3

p1k=nk=0p3=p0n4==k+1=1j=3k=0n3==k+1=1j=2k=0p1

p0k=nk==-1n2==k+1=0j=1k=-1n1==k+1=0j=0n0=-1j=5k=1p4=p1n5==k+1=2j=6k=2p5

p2k=nk=0p5

p0k=nk=-1n5=k+1=0j=7k=0p6=p0n7=k+1=168對當(dāng)前串計算next特征向量的算法voidAString::getNext(int

next[]){

int

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

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

LS(a1,a2,a3,…,an)LS是表名，ai

是表元素，可以是表（稱為子表），可以是數(shù)據(jù)元素（稱為原子）。n為表的長度。n=0的廣義表為空表。n>0時，表的第一個表元素稱為廣義表的表頭（head），除此之外，其它表元素組成的表稱為廣義表的表尾（tail）。70廣義表的特性有次序性有長度有深度可共享可遞歸A()A長度為0，深度為1B(6,2)B長度為2，深度為1C(‘a(chǎn)’,(5,3,‘x’))C長度為2，深度為2D(B,C,A)D長度為3，深度為3E(B,D)E長度為？深度為？F(4,F)F長度為？深度為？71廣義表的表頭與表尾廣義表的第一個表元素即為該表的表頭，除表頭元素外其他表元素組成的表即為該表的表尾。A()head(A)和tail(A)不存在B(6,2)head(B)=6,tail(B)=(2)C(‘a(chǎn)’,(5,3,‘x’))head(C)=‘a(chǎn)’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’)))=()72廣義表的表示list1=(a,b,c,d,e)list2=(a,(b,c,(d,e,f),(),g),h,(r,s,t))ahbcgsrtfed

list2alist1bdec

73廣義表結(jié)點定義結(jié)點類型utype：=0,表頭；=1,原子數(shù)據(jù)；

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

0時,指向同一層下一個結(jié)點

utypeinfotlink

74廣義表的存儲表示EBF0

11h20

022D

011d1e1f

0

11

c2

C

0

12220

21

aDBBCA1

b

01A

75廣義表的類定義#include<iostream.h>#include<stdlib.h>template<classT>struct

Items{

//返回值的類結(jié)構(gòu)定義

int

utype; //結(jié)點類型＝0/1/2

union{ //聯(lián)合

int

ref;

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

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

GenListNode<T>*hlink;

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

}info;76

Items():utype(0),info.ref(0){}//構(gòu)造函數(shù)

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

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

};template<classT>struct

GenListNode

{ //廣義表結(jié)點類定義

int

utype; //＝0/1/2

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

union{ //等價變量

int

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

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

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

77

}info;

GenListNode()

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

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

GenListNode(GenListNode<T>&R){

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

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

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

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

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

boolHead(Items<T>&x);

//x返回表頭元素

boolTail(Gen