第四章串1．教學目的：2．教學要求：掌握串的定義、基本運算的實現(xiàn)及基本串匹配算法。①理解串的七種基本運算的定義。②掌握利用這些基本運算來實現(xiàn)串的其它各種運算的方法。③掌握在順序存儲結構上實現(xiàn)串的各種操作的方法。④理解KMP算法，了解NEXT函數(shù)和改進NEXT函數(shù)的定義和計算。⑤理解串名的存儲映象和在堆存儲結構實現(xiàn)串操作的方法。3．教學重點：①熟悉串的七種基本運算的定義及實現(xiàn)方法。②熟練掌握基本串匹配算法。

在教學過程中強調串的特點，即數(shù)據(jù)元素是字符，操作對象是若干數(shù)據(jù)元素組成的序列。串的順序存儲結構及其基本操作的實現(xiàn)是重點。有回溯的模式匹配和無回溯的模式匹配(KMP)算法是本章的難點。4．教學難點：4.1串的定義及其基本運算

s是串的名字;n是串中字符的個數(shù),稱為串的長度字符在串中的序號稱為該字符在串中的位置串是一種特殊的線性表。數(shù)據(jù)元素僅由一個字符組成。

1保持線性表前驅、后繼的關系；

2對串整體進行操作。4.1.1串的基本概念定義：是零個或多個字符組成的有限序列。一般記為：s=“a1a2...an”

(n≥0)其中:

術語：1.子串串中任意個連續(xù)的字符組成的子序列稱為該串的子串。2.主串包含子串的串相應地稱為主串。通常以子串的第一個字符在主串中的位置來表示。

當兩個串的長度相等,并且每個對應位置的字符都相等，稱兩個串是相等的。3.子串在主串中的位置4.串相等4.1.2串的基本運算(1)賦值操作StrAssign(S,chars)：chars是字符串常量。生成一個值等于chars的串S。(2)求串長度StrLength(S)：串S存在。返回串S的長度，即串S中的元素個數(shù)。(3)連接函數(shù)StrCat(S,T)：串S和T存在。將串T的值連接在串S的后面。(4)求子串函數(shù)SubString(sub,S,pos,len)：串S存在，1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。用sub返回串S的第pos個字符起長度為len的子串。(5)定位函數(shù)StrIndex(S,T,pos)：串S和T存在，T是非空串，1≤pos≤StrLength(S)。若串S中存在與串T相同的子串，則返回它在串S中第pos個字符之后第一次出現(xiàn)的位置；否則返回0。注意，T不能為空串。(6)插入子串操作StrInsert(S,pos,T)：串S存在，1≤pos≤StrLength(S)+1。在串S的第pos個字符之前插入串T。4.1.2串的基本運算(7)刪除子串操作StrDelete(S,pos,len)：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。從串S中刪除第pos個字符起長度為len的子串。(8)串復制操作StrCopy(S,T)：串T存在。由串T復制得串S。(9)判空函數(shù)StrEmpty(S)：串S存在。若串S為空串，則返回TRUE，否則返回FALSE。(10)串比較操作StrCompare(S,T)：串S和T存在。若S?>?T，則返回值大于0；如S?=?T，則返回值等于0；若S?<?T，則返回值小于0。(11)串清空操作StrClear(S)：串S存在。將S清為空串。(12)替換操作StrReplace(S,T,V)：串S、T和V存在，且T是非空串。用V替換串S中出現(xiàn)的所有與T相等的不重疊的子串。4.2串的順序存儲及基本運算對串的存儲方式取決于我們對串所進行的運算。4.2.1串的定長順序存儲用一組地址連續(xù)的存儲單元存儲串值中的字符序列。為每一個串變量預分配一個固定長度的存儲區(qū)，如：

#defineMAXLEN256chars[MAXLEN];

則串的最大長度不能超過256。如何標識實際長度？可用以下方法

typedefstruct{charch[MAXLEN];intlast;}SeqString;1.類似順序表，用一個指針來指向最后一個字符。描述如下：定義一個串變量：

SeqStringS;串的長度S.last+12.在串尾存儲一個特殊字符作為串的終結符比如C語言中用’\0’來表示串的結束。

chars[MAXLEN];這種存儲方法不能直接得到串的長度，是用判斷當前字符是否是’\0’來確定串是否結束，從而求得串的長度。如圖所示：edcbadcba\0ihgf…

012345678…MAXLEN-13.設定長串存儲空間chars[MAXLEN+1]用s[0]存放串的實際長度，串值存放在s[1]~s[MAXLEN]，字符的序號和存儲位置一致，應用更為方便。如圖所示：eadcbzhgf…

012345678…MAXLEN圖4.3串的定長順序存儲4.2.2順序串的基本操作1.串插入函數(shù)(StrInsert(S,pos,T))

在進行串的插入時，插入位置pos將串分為兩部分(假設為S、A，長度為S.last+1、?A.last+1)，及待插入部分(假設為T，長度為T.last+1)，則串由插入前的SA變?yōu)镾TA，可能有三種情況：(1)插入后串長(S.last?+?T.last?+?A.last)＜MAXLEN，則將A后移T.last個元素位置，再將T插入，

(2)插入后串長(S.last+T.last+A.last≥MAXLEN且pos+T.last＜MAXLEN，則A后移時會有部分字符被舍

(3)插入后串長(S.last+T.last+A.last≥MAXLEN且pos+T.last＞MAXLEN，則A全部字符被舍棄(不需后移)，并且T在插入時也有部分字符被舍棄1intStrInsert(SeqString*S,intpos,SeqStringT)2{/*在串S中序號為pos的字符之前插入串T，0≤pos≤S.last+1*/3inti;4if(pos<0||pos>S->last+1)return(0);/*插入位置不合法*/5if(S->last+T.last<MAXLEN)6{/*插入后串長<MAXLEN*/7for(i=S->last+T.last+1;i>T.last+pos;i--)8S->ch[i]=S->ch[i-T.last-1];9for(i=0;i<=T.last;i++)10S->ch[i+pos]=T.ch[i];11S->last=S->last+T.last+1;12}13else14if(pos+T.last<MAXLEN)15{/*插入后串長>MAXLEN，但串T的字符序列可以全部插入*/16for(i=MAXLEN-1;i>T.last+pos;i--)17S->ch[i]=S->ch[i-T.last-1];

18for(i=0;i<=T.last;i++)19S->ch[i+pos]=T.ch[i];20S->last=MAXLEN;21}22else23{/*串T的部分字符序列要舍棄*/24for(i=0;i<MAXLEN-pos;i++)25S->ch[i+pos]=T.ch[i];26S->last=MAXLEN;27}28return(1);29}2.串刪除函數(shù)(StrDelete(S,pos,len))函數(shù)功能：在串S中刪除從序號pos起len個字符，0≤pos≤S.last。1intStrDelete(SeqString*S,intpos,intlen)2{3inti;4if(pos<0||pos>(S->last-l))return(0);/*刪除位置不合法*/5for(i=pos+len;i<=S->last;i++)6S->ch[i-len]=S->ch[i];7S->last=S->last-l;8return(1);9}

3.串復制函數(shù)(StrCopy(S,T))函數(shù)功能：將串T的值復制到串S中。1StrCopy(SeqString*S,SeqStringT)2{3inti;4for(i=0;i<=T.last;i++)5S->ch[i]=T.ch[i];6S->last=T.last;7}4.串比較函數(shù)(StrCompare(S,T))函數(shù)功能：若串S和T相等，則返回0；若S?>?T，則返回大于0的數(shù)；若S?<?T，則返回小于0的數(shù)。1intStrCompare(SeqStringS,SeqStringT)2{3inti;4for(i=0;i<=S.last&&i<=T.last;i++)5if(S.ch[i]!=T.ch[i])6return(S.ch[i]-T.ch[i]);7return(S.last-T.last);8}

5.連接函數(shù)(StrCat(S,T))函數(shù)功能：將串T連接在串S的后面。與串的插入操作類似，在進行串的連接時(假設原來串為S，長度為S.last，待連接串為T，長度為T.last)，也可能有三種情況：(1)連接后串長(S.last+T.last)＜MAXLEN，則直接將T加在S的后面。(2)連接后串長(S.last+T.last)＞MAXLEN且S.last＜MAXLEN，則T會有部分字符被舍棄。(3)連接后串長(S.last+T.last)＞MAXLEN且S.last?=?MAXLEN，則T的全部字符被舍棄(不需連接)。

5.連接函數(shù)(StrCat(S,T))1intStrCat(SeqString*S,SeqStringT)2{/*將串T連接在串S的后面*/3inti,flag;4if(S->last+T.last<MAXLEN)5{/*連接后串長小于MAXLEN*/6for(i=S->last;i<=S->last+T.last;i++)7S->ch[i+1]=T.ch[i-S->last];8S->last=S->last+T.last+1;9flag=1;10}11else12if(S->last<MAXLEN)13{/*連接后串長大于MAXLEN，但串S的長度小于MAXLEN*/14for(i=S->last;i<MAXLEN;i++)15S->ch[i+1]=T.ch[i-S->last];16S->last=MAXLEN;17flag=0;18}19else20flag=0;/*串S的長度等于MAXLEN，串T不被連接*/21return(flag);22}

6.求子串函數(shù)(SubString(sub,S,pos,len))

函數(shù)功能：將串S中序號pos起len個字符復制到sub中。1intSubString(SeqString*sub,SeqStringS,intpos,intlen)2{3inti;4if(pos<0||pos>S.last||len<1||len>S.last-pos)5{sub->last=0;6return(0);7}8else9{for(i=0;i<len;i++)10sub->ch[i]=S.ch[i+pos];

11sub->last=len;12return(1);13}14}

7.定位函數(shù)(StrIndex(S,T,pos))求串T在串S中的位置，這種子串在主串中的定位操作通常稱作串的模式匹配，這個操作是串中基本操作最重要的一個操作。簡單來說，就是對主串的每一個字符作為子串開頭，與要匹配的字符串進行匹配。對主串做大循環(huán)，每個字符開頭做T的長度的小循環(huán)，直到匹配成功或全部遍歷完成為止。1intStrIndex(SeqStringS,SeqStringT,intpos)2{inti,j;4if(T.last==0)/*串T為空*/5return(-1);6i=pos;j=0;7while(i<=S.last&&j<=T.last)8if(S.ch[i]==T.ch[j])9{i++;10j++;11}

12else13{i=i-j+1;14j=0;15}16if(j>T.last)17return(i-j);18else19return(-1);20}假設主串的長度為n，模式串的長度為m，最壞情況下的時間復雜度為O(n?×?m)。在最壞情況下，每趟不成功的匹配都發(fā)生在T的最后一個字符。例如，

S?=?″aaaaaaaaaaab″T?=?″aaab″設匹配成功發(fā)生在si處，則在前面i-1趟匹配中共比較了(i-1)?×?m次，第i趟成功的匹配共比較了m次，所以總共比較了i?×?m次，因此最好情況下平均比較的次數(shù)是(n-m+1)?×?m。即最壞情況下的時間復雜度是O(n?×?m)。不過，這個算法的平均性能比較好，因為對于那些不成功的試匹配來說，并非每次試匹配都測試到模式串的尾部才發(fā)現(xiàn)失配，通常只測試到模式串的前幾個字符就發(fā)現(xiàn)失配了。4.3串的堆存儲結構每個串值各自存儲在一組地址連續(xù)的存儲單元中。但存儲地址在程序執(zhí)行過程中而得。特點：動態(tài)分配4.3.1堆存儲在應用程序中，參與運算的串變量之間的長度相差較大，并且操作中串值的長度變化也較大，因此為串變量預分配固定大小的空間不盡合理。堆存儲結構的基本思想是：在內存中開辟足夠多的地址連續(xù)的存儲空間作為應用程序中所有串的可利用存儲空間，稱為堆空間，如設store[SMAX+1]。根據(jù)每個串的長度，動態(tài)地為每個串在堆空間store里申請相應大小的存儲區(qū)域，將串順序存儲在所申請的存儲區(qū)域中。當在操作過程中原空間不夠了，可以根據(jù)串的實際長度重新申請，拷貝原串值后再釋放原空間。

陰影部分是已經為存在的串分配過的，free為未分配部分的起始地址，每當向store中存放一個串時，需要在串名和堆中的存儲位置建立對應關系，即串名的存儲映象。設堆空間為：

charstore[SMAX+1];

自由區(qū)指針：

intfree;(已分配區(qū)域)(未分配區(qū)域)freestore圖4.7堆結構示意圖1.帶串長度的索引表

typedefstruct{intlength;/*串長*/intstradr;/*起始地址*/}HString;索引項的結點類型為：4.3.2串名的存儲映象例如，

HstringS;S.stradr表示串S在堆中的起始位置，S.length表明串的長度。2.末尾指針的索引表

typedefstruct{charname[MAXNAME];/*串名*/intstradr,enadr;/*起始地址，末尾地址*/}ENode;索引項的結點類型為：注意：空間的動態(tài)申請和釋放4.3.3基于堆結構的基本運算堆結構上的串運算仍然基于字符序列的復制。設堆空間為：charstore[SMAX+1]；自由區(qū)指針：intfree；typedef

struct{intlength;intstradr;}

HString;設串的存儲映象類型如下：串長起始地址(已分配區(qū)域)(未分配區(qū)域)freestorelength域指示串的長度，stradr域指示串的起始位置。借助此結構可以在串名和串值之間建立一個對應關系，稱為串名的存儲映象。系統(tǒng)中所有串名的存儲映象構成一個符號表。ssecorpgnirtsmargorpa167c97b09aStartlen符號名Heap[MAXSIZE]Free=23符號表下圖是一個堆存儲及符號表，其中a=“aprogram”，b=“string”，c=“process”

1.串常量賦值StrAssign(S1,S2)功能：該運算將一個字符型數(shù)組S2中的字符串送入堆store中，并建立存儲映象S1。1intStrAssign(HString*S1,char*S2)2{3inti=0,len;4len=StrLength(S2);5if(len<0||free+len-1＞SMAX)6return0;7else8{for(i=0;i<len;i++)9store[free+i]=S2[i];/*將S2放入堆中*/10S1.stradr=free;/*S1在堆中的起始位置*/11S1.length=len;/*S1的長度*/12free=free+len;/*修改自由區(qū)指針*/13return1;14}15}2.求子串SubString(T,S,i,len)功能：該運算將串S中第i個字符開始的長度為len的子串送到一個新串T中。1intSubString(Hstring*T,HstringS,inti,intlen)2{3inti;4if(i<0||len<0||len>S.len-i+1)5return0;6else7{T->length=len;8T->stradr=S.stradr+i-1;9return1;10}11}4.4塊鏈串由于串也是一種線性表，因此也可以采用鏈式存儲。由于串的特殊性(每個元素只有一個字符)，在具體實現(xiàn)時，每個結點既可以存放一個字符，也可以存放多個字符。每個結點稱為塊，整個鏈表稱為塊鏈結構，為了便于操作，再增加一個尾指針。塊鏈結構可定義如下：#defineBLOCK-SIZE<每個結點存放的字符個數(shù)>typedef

structBlock{charch[BLOCK-SIZE];structBlock*next;}Block;typedefstruct{Block*head;Block*tail;intlength;}BLString;存儲密度越大，操作越不方便存儲密度越小，浪費空間，操作方便4.5KMP模式匹配算法4.5.1KMP模式匹配算法的原理(2)到(7)的比較是多余的S?=?″abcababca″，T?=?″abcabx″。這里很明顯看到字符串首字符?′a′?與其后面的字符串?″bcabx″?中倒數(shù)第三個字符相同。前5個字符均相等，此時觀察T?=?″abcabx″，其中首字符?′a′?與T中的第二、第三字符均不等，所以，(2)、(3)均是多余的比較。T中首字符?′a′?與T中第四位字符相等，第二位?′b′?與第五位相等，在(1)的比較過程中可以明顯看出，T中第四、第五位字符均與主串S中相應字符比較過，且相等，因此，可以斷定，T中的首字符?′a′、第二位?′b′?與主串S中第四、第五位字符也不需要比較了，肯定是相等的。KMP算法的思路

找出子串的特點，主串的i指針不回溯。希望某趟在si和tj匹配失敗后，指針i不回溯，模式T向右“滑動”至某個位置上，使得tk對準si繼續(xù)向右進行。顯然，現(xiàn)在問題的關鍵是串T“滑動”到哪個位置上?不妨設位置為k，即si和tj匹配失敗后，指針i不動，模式T向右“滑動”，使tk和si對準繼續(xù)向右進行比較，要滿足這一假設，就要有如下關系成立：

″t1t2…tk-1″=″si-k+1si-k+2…si-1″(4.1)式(4.1)左邊是tk前面的k-1個字符，右邊是si前面的k-1個字符。而本趟匹配失敗是在si和tj之處，已經得到的部分匹配結果是：

″t1t2…tj-1″=″si-j+1si-j+2…si-1″(4.2)因為k?<?j，所以有：

″tj-k+1tj-k+2…tj-1″=″si-k+1si-k+2…si-1″(4.3)式(4.3)左邊是tj前面的k-1個字符，右邊是si前面的k-1個字符，通過式(4.1)和式(4.3)得到關系：

″t1t2…tk-1″=″tj-k+1tj-k+2…tj-1″(4.4)①next[j]?是一個整數(shù)，且0≤next[j]＜j。②為了使T的右移不丟失任何匹配成功的可能，當存在多個滿足式(4.4)的k值時，應取最大的，這樣向右“滑動”的距離最短，“滑動”的字符為j-next[j]個。③如果在tj前不存在滿足式(4.4)的子串，此時若t1?≠?tj，則k?=?1；若t1?=?tj，則k?=?0；這時“滑動”的最遠，為j-1個字符，即用t1和sj+1繼續(xù)比較。4.5.2next函數(shù)因此，next函數(shù)定義如下：0當j?=?1max{k|1≤k?＜

j且?″t1t2…tk-1″

=″tj-k+1tj-k+2…tj-1″1當不存在上面的k且t1?≠?tj0當不存在上面的k且t1?=?tjnext[j]?=設有模式串T?=?″abcaababc″，則它的next函數(shù)值為：j123456789模式串abcaababcnext[j]011022323在求得模式的next函數(shù)之后，匹配可如下進行：①假設以指針i和j分別指示主串和模式中的比較字符，令i的初值為pos，j的初值為1。②若在匹配過程中si==tj，則i和j分別增1。③若si?≠?tj，匹配失敗后，則i不變，j退到next[j]位置再比較。④若相等，則指針各自增1，否則j再退到下一個next值的位置，依此類推，直至下列兩種情況：一種是j退到某個next值時字符比較相等，則i和j分別增1繼續(xù)進行匹配；另一種是j退到值為零(即模式的第一個字符失配)，則此時i和j也要分別增1，表明從主串的下一個字符起和模式重新開始匹配。4.5.3KMP算法實現(xiàn)設主串S?=?″aabcbabcaabcaababc″，子串T?=?″abcaababc″，KMP算法如下：1intStrIndex_KMP(char*S,char*T,intpos)2{/*從串S的第pos個字符開始找首次與串T相等的子串*/3inti=pos,j=1;4while(i<=S[0]&&j<=T[0]) /*S[0]?存放串S的長度，T[0]?存放串T的長度*/5if(j==0||S[i]==T[j])6{7i++;j++;8}9else10j=next[j]; /*回溯*/11if(j>T[0])12returni-T[0]; /*匹配成功，返回存儲位置*/13else14return-1;15}next函數(shù)值僅取決于模式本身而和主串無關。我們可以從分析next函數(shù)的定義出發(fā)用遞推的方法求