《數(shù)據(jù)結(jié)構(gòu)》課件1第4章 串

第4章串串的定義串的存儲結(jié)構(gòu)串的模式匹配4.1串的定義2描述各種信息的文字符號序列通常稱為字符串，簡稱串。在計(jì)算機(jī)上的非數(shù)值處理一般都是字符串?dāng)?shù)據(jù)。串是一種內(nèi)容受限的線性表。串是由零個或多個字符構(gòu)成的有限序列，記為：s="a1a2…an"例如："thisisastring"，"is"

，"

"

串長：串值中字符個數(shù)（n）空串：長度為0的串空格串：僅含有空格字符的串(n不為0)子串：串中若干相鄰字符組成的子序列主串：包含子串的串子串中第0個字符在主串中出現(xiàn)的位置稱為此子串在該主串中的位置。

串名串值串之間的大小關(guān)系：設(shè)s1="a0a1…am-1"，s2="b0b1…an-1"若m=n且ai=bi，i=0，1，…m-1，則s1=s2(2)滿足下面條件之一，則s1<s2m<n，且ai=bi，i=0，1，…m-1 例如："abc"與"abcd"存在某個0<k≤min(m，n)，使得ai=bi，i=0，1，…k-1，ak<bk

例如："abc"與"adc"(3)不滿足以上條件，則s1>s24.1串的定義3串的抽象數(shù)據(jù)類型定義4.2串的存儲結(jié)構(gòu)1.串的順序存儲4串的順序存儲結(jié)構(gòu)簡稱為順序串。類似于順序表，順序串也是用一組地址連續(xù)的存儲單元存儲串中的字符序列。為了表示串的結(jié)尾，一般在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符。例如，C++語言中用’\0’表示串的結(jié)束。4.2串的存儲結(jié)構(gòu)2.串的鏈?zhǔn)酱鎯?串采用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲時稱為鏈串，可采用帶頭結(jié)點(diǎn)的單鏈表來表示。鏈串的組織形式與一般的單鏈表類似，主要區(qū)別在于鏈串中的一個結(jié)點(diǎn)可以存儲多個字符。通常將鏈串中每個結(jié)點(diǎn)所存儲的字符個數(shù)稱為結(jié)點(diǎn)大小。在鏈?zhǔn)酱鎯Ψ绞街校Y(jié)點(diǎn)大小的選擇直接影響著串處理的效率。存儲密度小（如結(jié)點(diǎn)大小為1）時，運(yùn)算處理方便，但存儲占用量大。存儲密度大時，一些基本操作（如插入、刪除）的實(shí)現(xiàn)有所不便，而且可能引起大量字符移動結(jié)點(diǎn)大小為4的鏈表：結(jié)點(diǎn)大小為1的鏈表：結(jié)點(diǎn)大小大于1時，鏈表的最后一個結(jié)點(diǎn)不一定全被串值占滿，未占用的數(shù)據(jù)域里應(yīng)補(bǔ)上不屬于串的字符集的特殊符號4.3串的模式匹配6設(shè)T="t0t1…tn-1"，P="p0p1…pm-1"，其中0<m≤n。如要在字符串T中查找是否有與字符串P相同的子串，則稱字符串T為目標(biāo)串或主串，稱字符串P為模式串或子串，在T中從位置pos開始查找與P相同的子串第一次出現(xiàn)的位置的過程稱為字符串模式匹配。4.3串的模式匹配1.BF算法7Brute-Force算法簡稱為BF算法，也稱簡單模式匹配算法。BF算法的基本思想是蠻力匹配，即從主串s的第一個字符開始和模式串t的第一個字符進(jìn)行比較，若相等，則繼續(xù)逐個比較后續(xù)字符；否則，從主串s的第二個字符開始重新與模式串t的第一個字符進(jìn)行比較，以此類推。若從主串s的第i個字符開始，每個字符依次和模式串t中的對應(yīng)字符相等，則匹配成功，返回位置i；否則，匹配失敗，返回-1。第1趟TabaababP

abab第2趟TabaababPabab第3趟TabaababPabab第4趟TabaababPabab4.3串的模式匹配1.BF算法8(1)用start保存主串比較的開始位置，初值為0。(2)用i和j指示主串s和模式串t中當(dāng)前正待比較的字符下標(biāo)，i和j的初值均為0。(3)重復(fù)下述操作，直到s或t的所有字符比較完畢：①若s[i]和t[j]相等，則繼續(xù)比較s和t的下一對字符；②否則，下標(biāo)i和j分別回溯，開始下一趟匹配。(4)若t中所有字符全部比較完畢，則匹配成功，返回本趟匹配的起始位置；否則匹配失敗，返回0。【算法步驟】intBF(strings,stringt){ inti=0,j=0,start=0; while(i<s.length()&&j<t.length()) { if(s[i]==t[j]) { j++;i++; } else { start++; i=start; j=0; } } if(j==t.length()) returnstart+1;

else return0;}4.3串的模式匹配1.BF算法9最好情況每趟不成功的匹配都發(fā)生在模式串t的第一個字符與主串s中相應(yīng)字符的比較。假設(shè)從主串的第i個位置開始與模式串匹配成功，則前在i－1趟不成功的匹配中共比較了i－1次，第i趟成功的匹配中共比較了m次，總比較次數(shù)為i－1＋m。對于成功匹配的主串，其起始位置由1到n－m＋1，假設(shè)這n－m＋1個位置上的匹配成功概率相等，則最好情況下匹配成功的平均比較次數(shù)為：【算法分析】設(shè)主串s長度為n，模式串t長度為m。時間復(fù)雜度為n+m

時間復(fù)雜度為n×m4.3串的模式匹配2.KMP算法10BF算法簡單但效率低。造成BF算法效率低的主要原因是回溯，即在某趟匹配失敗后，主串s要回溯到本趟匹配開始字符的下一個字符，模式串t要回溯到第一個字符，而這些回溯往往是不必要的。改進(jìn)算法——KMP消除回溯

本章小結(jié)(1)串是一種內(nèi)容受限的線性表，它限定了表中的元素為字符。(2)串有兩種基本存