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

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

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

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

4、e / 截?cái)?僅取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個(gè)字符起長(zhǎng)度為len的子串。算法思想： 求子串的過(guò)程即為復(fù)制字符序列的過(guò)程，將串S中從第pos個(gè)字符開始長(zhǎng)度為len的字符序列復(fù)制到串Sub中。算法實(shí)現(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; 鏈存儲(chǔ)表示思想:鏈串的存儲(chǔ)形式與一般的鏈表類似，是將存儲(chǔ)區(qū)分成許多結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一個(gè)存放字符的域和一個(gè)存放指向下一個(gè)結(jié)點(diǎn)的指針域。鏈串中的一個(gè)存儲(chǔ)結(jié)點(diǎn)可以存儲(chǔ)1個(gè)或多個(gè)字符，通常將鏈串中每個(gè)存儲(chǔ)結(jié)點(diǎn)所存儲(chǔ)的字符個(gè)數(shù)稱為結(jié)點(diǎn)大小。 w v u x y z # # head 結(jié)點(diǎn)大小為1的串的鏈表存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)大小為4的串的鏈表存儲(chǔ)結(jié)構(gòu)串的鏈表存儲(chǔ)方式w vu x y z headC語(yǔ)言表示： #define CHUNKSIZE 80 /可由用戶定

6、義的塊(結(jié)點(diǎn))大小typedef struct Chuck char chCHUNKSIZE;struct Chuck *next;Chuck;typedef struct Chuck *head,*tail; /串的頭和尾指針 int curlen; /串的當(dāng)前長(zhǎng)度LString; 串的模式匹配算法 求子串位置的定位函數(shù)Index(S,T,pos)子串定位操作通常稱做串的模式匹配(其中T稱為模式串),是各種串處理系統(tǒng)中最重要的操作之一.初始條件:串S和T存在,T非空,1=pos=StrLength(S)操作結(jié)果:若主串S中存在和串T值相同的子串,則返回它在主串S中第pos個(gè)字符之后第一次出現(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個(gè)字符之后的位置。/若不存在，返回值為0。/ 其中，T非空，1posStrLength(S) i=pos; j=1;while (i=s0&jT0) return i-T0;else return 0;)/Index 算法實(shí)現(xiàn)最難的一個(gè)算法KMP算法dsfdskjgldkjgjgrglsiggls“s”不匹配時(shí)，下一次比較應(yīng)

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

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

11、。整個(gè)KMP算法就是依賴這個(gè)next數(shù)組的，這個(gè)next怎么求？假設(shè)已經(jīng)知道了next1next4怎樣推導(dǎo)出next5,next6 1 2 3 4 5 6 B = a b a b a c next = 0 0 1 2 ? ?因?yàn)閚ext4=2，說(shuō)明B1B2= B3B4，又因?yàn)锽5=B3=Bnext4+1所以next5=next4+1=3可是B6!=Bnext5+1,所以B6不能簡(jiǎn)單地等于4既然B5=B3,而B6!=B4,那么會(huì)不會(huì)和BnextB3+1相等呢？結(jié)果是不相等，那就只能是0了。有個(gè)人解釋是這樣的（和教材不一樣）一般教材上的說(shuō)法是這樣的：（很多人吐槽說(shuō)根本看不懂）(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且集合無(wú)解）；現(xiàn)在假設(shè)已知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 問(wèn)題是p3 ！= p9，next10=?如果pj!=pk，將模式串向右滑動(dòng)至k(k=nextkkj)位置，使得主串的

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

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