嚴蔚敏數據結構課件第四章

第四章串4.1串的抽象數據類型的定義4.2串的表示和實現4.3 串的模式匹配算法4.1串的抽象數據類型的定義如下：ADTString{

數據對象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}數據關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}串是有限長的字符序列，由一對雙引號相括，如:astring

基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)

StrCompare(S,T)

StrLength(S)

Concat(&T,S1,S2)SubString(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)

ClearString(&S)}ADTString

StrAssign(&T,chars)

初始條件：chars是字符串常量。

操作結果：把chars賦為T的值。

StrCopy(&T,S)

初始條件：串S存在。

操作結果：由串S復制得串T。

DestroyString(&S)

初始條件：串S存在。

操作結果：串S被銷毀。

StrEmpty(S)

初始條件：串S存在。

操作結果：若S為空串，則返回true，

否則返回false。

表示空串，空串的長度為零。

StrCompare(S,T)

初始條件：串S和T存在。

操作結果：若S

T，則返回值

0；

若S

T，則返回值

0；

若S

T，則返回值

0。例如：StrCompare(data,state)<0StrCompare(cat,case)>0

StrLength(S)

初始條件：串S存在。

操作結果：返回S的元素個數，

稱為串的長度。

Concat(&T,S1,S2)

初始條件：串S1和S2存在。

操作結果：用T返回由S1和S2

聯接而成的新串。例如：

Concate(T,man,kind)

求得T=mankind

SubString(&Sub,S,pos,len)初始條件：操作結果：

用Sub返回串S的第pos個字符起長度為len的子串。串S存在，1≤pos≤StrLength(S)

且0≤len≤StrLength(S)-pos+1。例如：

SubString(sub,commander,4,3)子串為“串”中的一個字符子序列求得sub=man;SubString(sub,commander,1,9)SubString(sub,commander,9,1)求得sub=r求得sub=commanderSubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(

student

,5,0)=

起始位置和子串長度之間存在約束關系長度為0的子串為“合法”串

Index(S,T,pos)

初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。

操作結果：

若主串S中存在和串T值相同

的子串,則返回它在主串S中第pos個

字符之后第一次出現的位置;

否則函數值為0。

假設S=

abcaabcaaabc

,T=

bca

Index(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;“子串在主串中的位置”意指子串中的第一個字符在主串中的位序。

Replace(&S,T,V)

初始條件：串S,T和V均已存在，

且T是非空串。

操作結果：用V替換主串S中出現

的所有與（模式串）T

相等的不重疊的子串。例如：假設S=

abcaabcaaabca

,T=bca若V=

x

,則經置換后得到

S=

axaxaax

若V=

bc

,則經置換后得到

S=

abcabcaabc

bcabcabcaStrInsert(&S,pos,T)

初始條件：串S和T存在，

1≤pos≤StrLength(S)＋1。

操作結果：在串S的第pos個字符之前插入串T。例如：S=

chater

，T=

rac

，則執(zhí)行StrInsert(S,4,T)之后得到

S=

character

StrDelete(&S,pos,len)

初始條件：串S存在

1≤pos≤StrLength(S)-len+1。

操作結果：從串S中刪除第pos個字符

起長度為len的子串。

ClearString(&S)

初始條件：串S存在。

操作結果：將S清為空串。

對于串的基本操作集可以有不同的定義方法，在使用高級程序設計語言中的串類型時，應以該語言的參考手冊為準。

gets(str)輸入一個串；

puts(str)

輸出一個串；

strcat(str1,str2)串聯接函數；

strcpy(str1,str2,k)串復制函數；

strcmp(str1,str2)串比較函數；

strlen(str)求串長函數；例如：C語言函數庫中提供下列串處理函數：

串賦值StrAssign、串復制Strcopy、串比較StrCompare、求串長StrLength、串聯接Concat以及求子串SubString

等六種操作構成串類型的最小操作子集。在上述抽象數據類型定義的13種操作中，即：這些操作不可能利用其他串操作來實現，反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）可在這個最小操作子集上實現。

例如，可利用串比較、求串長和求子串等操作實現定位函數Index(S,T,pos)。

StrCompare(SubString(S,i,StrLength(T)),T)

S串T串

T串iposn-m+1算法的基本思想為：?

0intIndex(StringS,StringT,intpos){

//T為非空串。若主串S中第pos個字符之后存在與T相等的子串，

//則返回第一個這樣的子串在S中的位置，否則返回0

if(pos>0){}//if

return0;//S中不存在與T相等的子串}//Indexn=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){}//whileSubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;else

returni;又如串的置換函數：S串

T串V串V串pospos

subinews串sub=i+mposn-pos+1voidreplace(String&S,StringT,StringV){}while(pos<=n-m+1&&i){

i=Index(S,T,pos);

if(i!=0){

SubString(sub,S,pos,i-pos);//不置換子串

Concat(news,news,

sub,V);pos=i+m;

}//if}//whileSubString(sub,S,pos,n-pos+1);//剩余串Concat(S,news,

sub);n=StrLength(S);m=StrLength(T);pos=1;StrAssign(news,NullStr);i=1;

串的邏輯結構和線性表極為相似，區(qū)別僅在于串的數據對象約束為字符集。

串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“單個元素”作為操作對象；在串的基本操作中，通常以“串的整體”作為操作對象。

在程序設計語言中，串只是作為輸入或輸出的常量出現，則只需存儲此串的串值，即字符序列即可。但在多數非數值處理的程序中，串也以變量的形式出現。4.2串的表示和實現一、串的定長順序存儲表示二、串的堆分配存儲表示三、串的塊鏈存儲表示

#defineMAXSTRLEN255//用戶可在255以內定義最大串長

typedef

unsignedcharSstring[MAXSTRLEN+1];//0號單元存放串的長度一、串的定長順序存儲表示

按這種串的表示方法實現的串的運算時，其基本操作為

“字符序列的復制”

串的實際長度可在這個予定義長度的范圍內隨意設定，超過予定義長度的串值則被舍去，稱之為“截斷”

特點:StatusConcat(SStringS1,SStringS2,SString&T){

//用T返回由S1和S2聯接而成的新串。若未截斷,則返回TRUE，否則FALSE。

returnuncut;}//Concat例如：串的聯接算法中需分三種情況處理：

T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;

}

if

(S1[0]+S2[0]<=MAXSTRLEN)

{//未截斷elseif

(S1[0]<MAXSTRSIZE){//截斷else{//截斷(僅取S1)T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;

}

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;

}

typedefstruct{char*ch;

//若是非空串，則按串實用長度分配

//存儲區(qū)，否則ch為NULL

intlength;//串長度

}HString;二、串的堆分配存儲表示

通常，C語言中提供的串類型就是以這種存儲方式實現的。系統(tǒng)利用函數malloc()和free()進行串值空間的動態(tài)管理，為每一個新產生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆”。

C語言中的串以一個空字符為結束符，串長是一個隱含值。

這類串操作實現的算法為:

先為新生成的串分配一個存儲空間，然后進行串值的復制。StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2聯接而成的新串

if(T.ch)delete(T.ch);//釋放舊空間

if(!(T.ch=newchar[S1.length+S2.length]))

exit(OVERFLOW);

T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];T.length=S1.length+S2.length;

T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];

returnOK;}//Concat

StatusSubString(HString&Sub,HStringS,

intpos,intlen){//用Sub返回串S的第pos個字符起長度為len的子串

if(pos<1||pos>S.length

||len<0||len>S.length-pos+1)

returnERROR;

if(Sub.ch)delete(Sub.ch);//釋放舊空間

if

(!len)

{

Sub.ch=NULL;Sub.length=0;

}//空子串

else{}//

完整子串

return

OK;}//SubString……if(!(Sub.ch=newchar[len]))returnERROR;Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2];Sub.length=len;voidStrInsert(Hstring&S,intpos,HStringT){//1≤pos≤StrLength(S)＋1。在串S的

//第pos個字符之前插入串Tslen=S.length;tlen=T.length;//取得S和T的串長

if(pos<1||pos>slen+1)return;//插入位置不合法

S1.ch=newchar[slen];//S1作為輔助串

S1.ch[0..slen-1]=S.ch[0..slen-1];//暫存S

if(tlen>0)//T非空，則為S重新分配空間并插入T{}}//StrInsert_HSq

……S.ch=newchar[slen+tlen];//為S重新分配空間for(i=0,k=0;i<pos-1;i++)S.ch[k++]=S1.ch[i];//保留插入位置之前的子串for(i=0;i<tlen;i++)S.ch[k++]=T.ch[i];//插入Tfor(i=pos;i<slen;i++)S.ch[k++]=S1.ch[i];//復制插入位置之后的子串S.length=slen+tlen;deleteS1.ch;三、串的塊鏈存儲表示也可用鏈表來存儲串值，由于串的數據元素是一個字符，它只有8位二進制數，因此用鏈表存儲時，通常一個結點中存放的不是一個字符，而是一個子串。存儲密度

=數據元素所占存儲位實際分配的存儲位

#defineCHUNKSIZE80

//可由用戶定義的塊大小

typedefstructChunk{

//

結點結構

charch[CUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串的鏈表結構

Chunk*head,*tail;//串的頭和尾指針

intcurlen;//串的當前長度

}LString;

例如:

在編輯系統(tǒng)中，整個文本編輯區(qū)可以看成是一個串，每一行是一個子串，構成一個結點。即:同一行的串用定長結構(80個字符),行和行之間用指針相聯接。實際應用時，可以根據問題所需來設置結點的大小。

這是串的一種重要操作，很多軟件，若有“編輯”菜單項的話，則其中必有“查找”子菜單項。4.3 串的模式匹配算法初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。

首先，回憶一下串匹配(查找)的定義:INDEX(S,T,pos)操作結果：若主串S中存在和串T值相同的子串返回它在主串S中第pos個字符之后第一次出現的位置;否則函數值為0。intIndex(StringS,StringT,intpos){

//T為非空串。若主串S中第pos個字符之后存在與T相等的子串，則返回第一個這樣的子串在S中的位置，否則返回0

if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;

while(i<=n-m+1){

SubString(sub,S,i,m);

if(StrCompare(sub,T)!=0)++i;

else

returni;

}//while

}//if

return0;//S中不存在與T相等的子串}//Index

下面討論以定長順序結構表示串時的幾種算法。一、簡單算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法二、首尾匹配算法

S串T串

T串iposn-m+1

S串T串

T串ijj>mijijiji>njT串一、簡單算法intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數值為0。

//其中，T非空，1≤pos≤StrLength(S)。

i=pos;j=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后繼字符

else

{i=i-j+2;j=1;}

//指針后退重新開始匹配

}

if(j>T[0])returni-T[0];

elsereturn0;}//Index

先比較模式串的第一個字符，

再比較模式串的最后一個字符，

最后比較模式串中從第二個

到第n-1

個字符。二、首尾匹配算法intIndex_FL(SStringS,SStringT,intpos){sLength=S[0];tLength=T[0];i=pos;patStartChar=T[1];patEndChar=T[tLength];

while(i<=sLength–tLength+1){

if

(S[i]!=patStartChar)

++i;

//重新查找匹配起始點

else

if(S[i+tLength-1]!=patEndChar)++i;

//模式串的“尾字符”不匹配

else{}}return0;}

檢查中間字符的匹配情況

k=1;j=2;while(j<tLength&&S[i+k]==T[j])

{++k;++j;}

if(j==tLength)returni;

else++i;//重新開始下一次的匹配檢測KMP算法的時間復雜度可以達到O(m+n)

當S[i]<>T[j]時，假設此時應與模式中第k（k<j）個字符繼續(xù)比較，則模式中前k-1個字符的子串必須滿足：

T[1..k-1]=S[i-k+1..i-1]

已經得到的結果:S[i-j+1..i-1]==T[1..j-1]

在上式中取任意多個從右到左的子串仍然相等，取k-1個，有

S[i-k+1..i-1]==T[j-k+1..j-1]

則有T[j-k+1..j-1]==T[1..k-1]三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法能向右滑動多遠？

t1…tk

…tj…tm

s1……si……sn

s1……si……sn

p1…tk

…tj…tm

顯然應有：si–k+1…si–1

=t1…tk–1。s

…t1…而由前次的比較應有：si–k+1…si–1

=tj–k+1

…tj–1。于是得到這樣的結果：t1…tk–1

=tj–k+1

…tj–1。一個模式的next(j)j：123456789模式：abaabaaabnext[j]：初始化：next[1]=0。0

沒有相應的k，next(j)為1。11

k=2，下次從第二個元素開始比較。22

依次以此類推可得其余元素的next(j)。3452滑動不會造成遺漏引理1：正文S和模式P比較時，若si≠pj，則S沒有以si–k0+1(next[j]<k0<i)開頭的子串匹配P。證明：當next[j]=0或1時，結論顯然成立。當next[j]>1時，假設結論不成立，即存在這樣的k0，那么有p1p2…pk0–1=si–k0+1si–k0+2…si–1。從而有，p1p2…pk0–1=pj–k0+1pj–k0+2…pj–1(7.3)由假設有next[j]<k0<i。這與next[j]是滿足(7.3)式的最大值相矛盾；所以結論成立。定義：模式串的next函數

intIndex_KMP(SStringS,SStringT,intpos){//1≤pos≤StrLength(S)i=pos;j=1;

while(i<=S[0]&&j<=T[0]){if(j=0||S[i]==T[j]){++i;++j;}//繼續(xù)比較后繼字符

elsej=next[j];//模式串向右移動

}//while

if(j>T[0])returni-T[0];//匹配成功

elsereturn0;}//Index_KMP這實際上也是一個匹配的過程，不同在于：主串和模式串是同一個串

求next函數值的過程是一個遞推過程，分析如下:已知：next[1]=0；假設：next[j]=k；又T[j]=T[k]則：

next[j+1]=k+1若：

T[j]

T[k]則需往前回朔，檢查T[j]=T[？]next(j)的計算如何來計算模式P的next(j)?首先，我們由定義可知next(1)=0；其次，顯然有next(2)=1；現在我們來考慮next(j+1)。由next(j)=k可知模式中有：p1…pk–1=pj–k+1…pj–1?，F在存在兩種情況：pk=pj或者pk

pj。⑴如果pk=pj，于是p1…pk–1pk=pj–k+1…pj–1pj。從而有next(j+1)=next(j)+1。next(j)的計算⑵如果pk

pj，顯然next(j+1)next(j)。這實際是在將p1…pk–1pk與pj–k’+1…pj–1pj相匹配時，出現了pj與pk失佩。

p1…pk–1pkpj–k+1…pj–k+1pj……p1…pk–1pkpk

pj下一步拿p1…pk–1pk中哪個元素和pj相比較呢？滑動多遠？向右滑動next(k)，即比較pnext(k)和pj。若這時有pnext(k)=pj，則next(j+1)=next(k)+1；若這時有pnext(k)

pj，則再重復以上的做法，直至k=1。next(j)的計算intnext[MaxStrLen];voidget_next(SStringP){j=1;next[1]=0;k=0；

while(j<=P[0])if(k==0‖P[k]=P[j]){++k;++j;next[j]=k;}//next(j+1)=k+1elsek=next[k];}初始化循環(huán)逐個計算元素j的next(j)若pk=pj，則next(j+1)=k+1。注意此處的k,j都加了1。若pk

pj，則比較pnext(k)和pj一個模式的next(j)j：123456789模式：abaabaaabnext[j]：初始化：j=1;next[1]=0;k=0；10第一趟：j=1;k=0；∵k=0∴{++k;++j;next[j]=k;}即，k=1;j=2;next(2)=1。