數(shù)據(jù)結(jié)構(gòu)教學課件：第5講串

1、字符串串類型的定義串的表示和實現(xiàn)模式匹配算法串操作應用舉例 串類型的定義1、名詞術(shù)語 串（String)(或字符串），是由零個或多個字符組成的有限序列。一般記做s=a1a2an(n=0)串的長度，串中字符的數(shù)目n?？沾∟ull string),零個字符的串，它的長度為零。子串，串中任意個連續(xù)的字符組成的子序列稱為該串的子串。 你可以委婉地問你的GG：“假如你要向你喜歡的人表白的話，我的名字是你的告白語中的子串嗎？”主串，包含子串的串。位置,字符在序列中的序號為該字符在串中的位置.例:4個串a(chǎn)=BEI,b=JING, c=BEIJING,d=BEI JING兩個串相等,當且僅當這兩個串的值相等

2、.空格串 (blank string,請注意此處不是空串），由一個或多個空格組成的串.空串,用” ”表示. 串的表示和實現(xiàn) 順序存儲表示 鏈存儲表示順序存儲表示思想:用一組地址連續(xù)的存儲單元存儲串值的字符序列C語言表示:用一個字符數(shù)組存儲一個串，c 語言中以0作為串的結(jié)束標志。串的實際長度可在這預定義長度的范圍內(nèi)隨意，超過預定義長度的串值則被舍去，稱為“截斷”?；具\算實現(xiàn) 1.串聯(lián)接Concat（&T，S1，S2）S10S20S1S2TT0MAXSTRLEN( a ) S10+S20MAXSTRLENS10S20T0MAXSTRLEN( b ) S10MAXSTRLENT0MAXSTRLEN

3、( c ) S10=MAXSTRLENS2中被截去的部分S10S20S2串全部被截去S1S1S2S2TT算法實現(xiàn)Concat(SString &T,SString S1,SString S2) if (S10+S20=MAXSTRLEN) / 未截斷 T1.S10=S11.S10; TS10+1.S10+S20=S21.S20; T0=S10+S20; uncut =TRUE;else if(S10MAXSTRLEN) / 截斷 T1.S10=S11.S10; TS10+1.MAXSTRLEN=S21.MAXSTRLEN-S10; T0= MAXSTRLEN; uncut =FALSE;els

4、e / 截斷(僅取S1) T0 .MAXSTRLEN= S10 .MAXSTRLEN; uncut =FALSE;return uncut;2.求子串SubString(&Sub,S,pos,len)初始條件：串S存在，1posStrLength(S)且 0lenStrLength(S)-pos+1 。操作結(jié)果：用Sub返回串S的第pos個字符起長度為len的子串。算法思想： 求子串的過程即為復制字符序列的過程，將串S中從第pos個字符開始長度為len的字符序列復制到串Sub中。算法實現(xiàn)SubString(SString &Sub,SString S,int pos,int len)if(po

5、sS0 | lenS0-pos+1) return ERROR;Sub1.len=Spos.pos+len-1;Sub0=len;return OK; 鏈存儲表示思想:鏈串的存儲形式與一般的鏈表類似，是將存儲區(qū)分成許多結(jié)點，每個結(jié)點有一個存放字符的域和一個存放指向下一個結(jié)點的指針域。鏈串中的一個存儲結(jié)點可以存儲1個或多個字符，通常將鏈串中每個存儲結(jié)點所存儲的字符個數(shù)稱為結(jié)點大小。 w v u x y z # # head 結(jié)點大小為1的串的鏈表存儲結(jié)構(gòu)結(jié)點大小為4的串的鏈表存儲結(jié)構(gòu)串的鏈表存儲方式w vu x y z headC語言表示： #define CHUNKSIZE 80 /可由用戶定

6、義的塊(結(jié)點)大小typedef struct Chuck char chCHUNKSIZE;struct Chuck *next;Chuck;typedef struct Chuck *head,*tail; /串的頭和尾指針 int curlen; /串的當前長度LString; 串的模式匹配算法 求子串位置的定位函數(shù)Index(S,T,pos)子串定位操作通常稱做串的模式匹配(其中T稱為模式串),是各種串處理系統(tǒng)中最重要的操作之一.初始條件:串S和T存在,T非空,1=pos=StrLength(S)操作結(jié)果:若主串S中存在和串T值相同的子串,則返回它在主串S中第pos個字符之后第一次出現(xiàn)

7、的位置;否則返回值0.算法演示:Index(S,T,1)a b a b c a b c a c b a b a b c a cSTi=1j=1第一趟匹配i=2j=2i=3j=3a b a b c a b c a c b a b a b c a cST第二趟匹配i=2j=1a b a b c a b c a c b a b a b c a cST第三趟匹配i=3j=1i=4j=2i=5j=3i=6j=4i=7j=5a b a b c a b c a c b a b a b c a cST第四趟匹配i=4j=1a b a b c a b c a c b a b a b c a cST第五趟匹配i=

8、5j=1a b a b c a b c a c b a b a b c a cST第六趟匹配i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6int Index(SString S,SString T,int pos)/返回子串T在主串S中第pos個字符之后的位置。/若不存在，返回值為0。/ 其中，T非空，1posStrLength(S) i=pos; j=1;while (i=s0&jT0) return i-T0;else return 0;)/Index 算法實現(xiàn)最難的一個算法KMP算法dsfdskjgldkjgjgrglsiggls“s”不匹配時，下一次比較應

9、該從哪里開始？有人提出“kj”根本與“模式”沒關(guān)系看都不用看只需要從“g”開頭的字符開始比較。可是，不比較你怎么知道沒關(guān)系？反正要想個辦法不要挨個比較，比如：0000000000000000000000000000000000001000001能不能把5個連續(xù)的0看做一個字符？經(jīng)過研究，KMP算法提出一個與目標串無關(guān)的預處理算法！這樣：模式=abcabcd序號=1234567假如“d”失配，意味著什么？意味著，“1”號字符a可以和“4”號字符對齊的那個字符比較！手工算一遍，感受一下：設模式串Pattern = a b c c a b c c a b c a Pattern 數(shù)組編號：0 1 2

10、 3 4 5 6 7 8 9 10 11假如失配該和誰比較？000001234567放在一個一位數(shù)組next中Next0=0Next7=3Next8=4假設next里面的值已經(jīng)知道了，那么新的匹配過程：目標串中某處T.模式串中某處M.假如“T”=“M”,那么上下字符串指示比較的“指針”i+,j+假如失配：此時nextj=k那么，由于“M”之前有k個字符和模式串前k個字符相同而且也與目標串中字符“T”之前的k個字符相同，所以，此時要與“T”繼續(xù)比較的應該是：?!這樣的算法有什么意義呢？答：原來挨個比較時，i已經(jīng)+了好遠了，但是一旦失配i的值需要調(diào)整小。而kmp算法中，i永遠向后走，速度當然快很多

11、。整個KMP算法就是依賴這個next數(shù)組的，這個next怎么求？假設已經(jīng)知道了next1next4怎樣推導出next5,next6 1 2 3 4 5 6 B = a b a b a c next = 0 0 1 2 ? ?因為next4=2，說明B1B2= B3B4，又因為B5=B3=Bnext4+1所以next5=next4+1=3可是B6!=Bnext5+1,所以B6不能簡單地等于4既然B5=B3,而B6!=B4,那么會不會和BnextB3+1相等呢？結(jié)果是不相等，那就只能是0了。有個人解釋是這樣的（和教材不一樣）一般教材上的說法是這樣的：（很多人吐槽說根本看不懂）(1)nextj =

12、-1（j=0）；(2)nextj = Maxk|1kj且pj-kpj-k+1.pj-1=p0p1.pk-1（j!=0且集合有解）；(3)nextj = 0（j!=0且集合無解）；現(xiàn)在假設已知nextj=k，那么： “p0p1.pk-1” = “pj-kpj-k+1.pj-1”假如如果pj=pk 顯然nextj+1=k+1=nextj+1由于next0=-1;所以似乎勝利在望了。譯文：比如：已知next9=3p0p1p2 = p6p7p8假如如果p3 = p9那么next10=4 問題是p3 ！= p9，next10=?如果pj!=pk，將模式串向右滑動至k(k=nextkkj)位置，使得主串的

13、pj字符與模式串的pk字符比較。如果此時pj=pk(kk)，則有pj-kpj-k+1.pj-1pj=p0p1.pk-1pk，由next函數(shù)的定義該式等價于：nextj+1=k+1=nextk+1如果此時pj!=pk，則將模式串繼續(xù)向右滑動，直至pj和模式串的某個字符pk_lucky匹配成功和的討論說明，無論經(jīng)過多少次滑動，只要主串的pj最終與模式串pk_lucky字符匹配成功，則主串字符指針(j+1)位置處的nextj+1一定可以由nextt(其中t=j)加1求得。盡管向右滑動，一直到j=nextt=-1，很不幸找不到k使得pj=pk，這相當于匹配過程中無解，此時由定義知nextj+1=0第一

14、次判斷時k=-1,導致j=1,k=0,next1=0第二次判斷時如果k!=-1,data1!=data0執(zhí)行else,k=-1假如模式串=0000000001執(zhí)行結(jié)果：初值：k=-1,j=0,next0=-1If成立導致：k=0,j=1,next1=0If成立導致：k=1,j=2,next2=1If成立導致：k=2,j=3,next3=2If成立導致：k=3,j=4,next4=3. k=7,j=8,next8=7 k=8,j=9,next9=8J=9結(jié)束假設模式串=000000000101，j=9還要執(zhí)行將導致:由于k!=-1,data8!=data9執(zhí)行else k=nextk=7.5,4,3,2,1,0,-1當k再次=-1時，執(zhí)行if語句，導致k=0,j=10,next10=00123456789至此，我們終于明白，K和J是從頭開始k為尾子串和j為尾的比較 01234567假設模式串=abcdabct程序執(zhí)行