華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)

第4章特殊的線性表——串華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第1頁!問題的提出查毒程序搜索引擎華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第2頁!1.串的邏輯結(jié)構(gòu)串：由零個(gè)或多個(gè)任意字符組成的有限序列。串長度：串中所包含的字符個(gè)數(shù)。空串：長度為0的串，記為：""。非空串通常記為：

S=“a1a2…an”

其中：S是串名，雙引號(hào)是定界符，雙引號(hào)引起來的部分是串值，ai（1≤i≤n）是一個(gè)任意字符。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第3頁!順序串：用數(shù)組來存儲(chǔ)串中的字符序列。（1）用一個(gè)變量來表示串的長度。2.串的存儲(chǔ)結(jié)構(gòu)——順序串如何表示串的長度？華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第4頁!順序串：用數(shù)組來存儲(chǔ)串中的字符序列。（3）用數(shù)組的0號(hào)單元存放串的長度，串值從1號(hào)單元開始存放。

2.串的存儲(chǔ)結(jié)構(gòu)——順序串如何表示串的長度？華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第5頁!3.串的基本操作串的鏈接串的比較串的復(fù)制習(xí)題4.4、4.5、4.6習(xí)題4.7。編寫一個(gè)函數(shù)來顛倒單詞在字符串里的出現(xiàn)順序?！尽冻绦騿T面試攻略(第2版)》p81】例如，把字符串“Doordonot,thereisnotry.”轉(zhuǎn)換為“try.noistherenot,doorDo”。假設(shè)所有單詞都以空格為分隔符，標(biāo)點(diǎn)符號(hào)也當(dāng)做字母來對(duì)待。請(qǐng)對(duì)你的設(shè)計(jì)思路做出解釋，并對(duì)你的解決方案的執(zhí)行效率進(jìn)行評(píng)估。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第6頁!4.串的應(yīng)用——模式匹配模式匹配：給定主串S="s1s2…sn"和模式T="t1t2…tm"，在S中尋找T的過程稱為模式匹配。如果匹配成功，返回T在S中的位置，如果匹配失敗，返回0。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第7頁!例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ijijij第

1趟abcac

4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第8頁!ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第9頁!ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第

3趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第10頁!ababcabcacbababcac

i=4，j=1失敗i回溯到5，j回溯到1第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第11頁!ababcabcacbababcac

i=5，j=1失敗i回溯到6，j回溯到1第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第12頁!ababcabcacbababcac

i=11，j=6，T中全部字符都比較完畢，匹配成功。第

6趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第13頁!intBFmatching(chars[],chart[]){i=1;j=1;

while(i<=s[0]&&j<=t[0]){if(s[i]==t[j]){i++;j++;}else{i=i-j+2;j=1;}}

if(j>t[0])return(i-j+1);

elsereturn0;}4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第14頁!4.串的應(yīng)用——BF模式匹配算法設(shè)串s長度為n，串t長度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串t的最后一個(gè)字符。例如：s="aaaaab"t="aaab“設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)×m次，第i趟成功的匹配共比較了m次，所以總共比較了i×m次，因此平均比較的次數(shù)是一般情況下，m<<n，因此最壞情況下的時(shí)間復(fù)雜度是O(nm)。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第15頁!i=3，j=3失敗；

s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第

1趟abcac

ababcabcacbab第

2趟abcac

4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第16頁!ababcabcacbababcac

第

3趟iji=7，j=5失敗s4=t2;t1≠t2∴t1≠s4ababcabcacbababcac

第

4趟4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第17頁!ababcabcacbababcac

第

3趟iji=7，j=5失敗s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac

第

6趟匹配成功4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第18頁!請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征：（1）設(shè)模式滑動(dòng)到第k個(gè)字符，則T1～Tk-1

＝Si-(k-1)

～

Si-1

S="ababc

a

b

cacbab"T="a

b

cac"ikjS="ababc

a

bcacbab"T="ab

cac"ik4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第19頁!T1…Tk-1＝Tj-(k-1)…Tj-1說明了什么？（1）k

與

j

具有函數(shù)關(guān)系，由當(dāng)前失配位置j，可以計(jì)算出滑動(dòng)位置k（即比較的新起點(diǎn)）；（2）滑動(dòng)位置k

僅與模式串T有關(guān)。從第1位往右經(jīng)過k-1位從j-1位往左經(jīng)過k-1位k＝max{k|1<k<j

且T1…Tk-1＝Tj-(k-1)…Tj-1}T1…Tk-1＝Tj-(k-1)…Tj-1的物理意義是什么？模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第20頁!4.串的應(yīng)用——KMP模式匹配算法計(jì)算next[j]的方法：當(dāng)j=1時(shí)，next[j]=0；//next[j]=0表示根本不進(jìn)行字符比較當(dāng)j>1時(shí)，next[j]的值為：模式串的位置從1到j(luò)-1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長度加1。當(dāng)無首尾相同的子串時(shí)next[j]的值為1。next[j]=1表示從模式串頭部開始進(jìn)行字符比較華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第21頁!voidGetNext(chart[]){next[1]=0;j=1;k=0;while(j<t[0])if((k==0)||(t[j]==t[k]))

{j++;k++;next[j]=k;}elsek=next[k];}求模式串t的next函數(shù)值算法4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第22頁!例：設(shè)主串s="abcabcabd"，模式串p="abcabd"，按KMP算法進(jìn)行模式匹配，當(dāng)"s0s1s2s3s4"="p0p1p2p3p4"，且s5≠p5時(shí)，應(yīng)進(jìn)行

比較。

A、s5和p2 B、s5和p3 C、s1和p0 D、s8和p54.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第23頁!1.串的邏輯結(jié)構(gòu)兩個(gè)串相等：如果兩個(gè)串的長度相等且對(duì)應(yīng)字符都相等。子串：串中任意連續(xù)的字符組成的子序列稱為該串。主串：包含子串的串。子串的個(gè)字符在主串中的序號(hào)稱為子串的位置。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第24頁!順序串：用數(shù)組來存儲(chǔ)串中的字符序列。（2）在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符

。

2.串的存儲(chǔ)結(jié)構(gòu)——順序串如何表示串的長度？華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第25頁!鏈接串：用鏈接存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)串。p552.串的存儲(chǔ)結(jié)構(gòu)——鏈接串華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第26頁!3.串的基本操作刪除特定字符。【《程序員面試攻略(第2版)》p78】用C語言編寫一個(gè)高效率的函數(shù)來刪除字符串里的給定字符。這個(gè)函數(shù)的調(diào)用模型如下所示：voidRemoveChars(charstr[],charremove[]);注意，remove中的所有字符都必須從str中刪除干凈。比如說，如果str是“BattleoftheVowels:HawaiiVS.Grozny”，remove是“aeiou”，這個(gè)函數(shù)將把str轉(zhuǎn)換為“BttlfthVwls:Hwvs.Grzny”。請(qǐng)對(duì)你的設(shè)計(jì)思路做出解釋，并對(duì)你解決方案的執(zhí)行效率進(jìn)行評(píng)估。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第27頁!4.串的應(yīng)用——BF模式匹配算法基本思想：從主串S的個(gè)字符開始和模式T的個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串S的第二個(gè)字符開始和模式T的個(gè)字符進(jìn)行比較，重復(fù)上述過程，直到T中的字符全部比較完畢，則說明本趟匹配成功；或S中字符全部比較完，則說明匹配失敗。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第28頁!ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ji第

1趟abcac

例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第29頁!ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第30頁!ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第

3趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第31頁!ababcabcacbababcac

i=4，j=1失敗i回溯到5，j回溯到1第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第32頁!ababcabcacbababcac

i=5，j=1失敗i回溯到6，j回溯到1第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第33頁!1.在串S和串T中設(shè)比較的起始下標(biāo)i和j；2.循環(huán)直到S或T的所有字符均比較完；2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個(gè)字符；2.2否則，將i和j回溯，準(zhǔn)備下一趟比較；3.如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標(biāo)；否則，匹配失敗，返回0；4.串的應(yīng)用——BF模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第34頁!4.串的應(yīng)用——BF模式匹配算法設(shè)串s長度為n，串t長度為m，在匹配成功的情況下，考慮兩種極端情況：最好情況：不成功的匹配都發(fā)生在串t的個(gè)字符。例如：s="aaaaabcd"t="bcd"設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了i-1次，第i趟成功的匹配共比較了m次，所以總共比較了i-1+m次，所有匹配成功的可能情況共有n-m+1種，則：設(shè)從si開始與t串匹配成功的概率為pi，在等概率情況下pi=1/(nm+1)，平均比較的次數(shù)是因此最好情況下的時(shí)間復(fù)雜度是O(n+m)。華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第35頁!4.串的應(yīng)用——BF模式匹配算法為什么BF算法時(shí)間性能低？在每趟匹配不成功時(shí)存在大量回溯，沒有利用已經(jīng)部分匹配的結(jié)果。如何在匹配不成功時(shí)主串不回溯？主串不回溯，模式就需要向右滑動(dòng)一段距離。如何確定模式的滑動(dòng)距離？華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第36頁!i=3，j=3失??；

s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第

1趟abcac

ababcabcacbababcac

第

3趟4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第37頁!ababcabcacbababcac

第

3趟iji=7，j=5失敗s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac

第

5趟4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第38頁!4.串的應(yīng)用——KMP模式匹配算法結(jié)論：i可以不回溯，模式向右滑動(dòng)到的新比較起點(diǎn)k，并且k僅與模式串T有關(guān)！需要討論兩個(gè)問題：①如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動(dòng)的新比較起點(diǎn)k？②模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第39頁!請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征：兩式聯(lián)立可得：T1～Tk-1＝Tj-(k-1)

～Tj-1（2）則Tj-(k-1)～

Tj-1＝Si-(k-1)～

Si-1S="ababc

a

b

cacbab"T="a

b

cac"ikjiS="ababc

a

b

cacbab"T="a

b

cac"jk（1）設(shè)模式滑動(dòng)到第k個(gè)字符，則T1～Tk-1

＝Si-(k-1)

～

Si-1

4.串的應(yīng)用——KMP模式匹配算法華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)共44頁，您現(xiàn)在瀏覽的是第40頁!next[j]＝0當(dāng)j＝1時(shí)//不比較max{k|1<k<j且T1…Tk-1=Tj-(k-1)…Tj-1}1其他情況令k=next[j]，則：ne