第3章-字符串(完整版)
【正文】 不到 j個字符，這時可根據(jù)串的長度算出串 s中從 i開始到串尾的字符個數(shù)，并修改 j的值，從而將串 s中從 i開始到串尾的 j個字符都拷到子串中。其類型定義為： struct SeqString { /* 順序串的類型 */ int MAXNUM。 ?子串在主串中的 位置 指的是該子串的第一個字符在主串中的位置。 一個串可以記作 s=s0s1… sn1（ n ≥ 0），其中 s是串的名字，雙引號括起來的字符序列 s0s1… sn是串的值。 例如： A = 123 B = ABBABBC C = BB D = BB E = ?一個串中包括的字符個數(shù)稱作這個串的 長度 。 抽象數(shù)據(jù)類型 ADT String is operations String createNullStr (void) 創(chuàng)建一個空串。 /* 串允許的最大字符個數(shù) */ int n。 程序?qū)崿F(xiàn) 鏈接表示 在串的鏈接表示中，每個結(jié)點包含兩個字段：字符和指針，分別用于存放字符和指向下一個結(jié)點的指針。 同樣為了方便處理 ， 可在第一個結(jié)點之前增加一個頭結(jié)點 ， 如圖 (b)所示 。 其中 t稱為 目標(biāo) ， p稱為 模式 。 程序?qū)崿F(xiàn) 無回溯的模式匹配 為了提高匹配速度，在匹配過程中，一旦 pi和tj比較不等，即： pi≠tj 時，能夠確定 p右移的位數(shù)（ =1）和繼續(xù)比較的字符 ,即 tj和 pk比較（無回溯） . ?Knuth等人發(fā)現(xiàn)這個 k值存在，且僅依賴于模式 p本身前 i個字符的組成，而與目標(biāo) t無關(guān)。 next數(shù)組的存在性 在 p與任意的目標(biāo) t匹配時 ， 若發(fā)現(xiàn) pi≠tj，則意味著 p0， p1， … ， pi1已與 t中對應(yīng)的字符進(jìn)行過比較 ， 而且是相等的 ， 所以圖 (a)和(b)是相同的 。 而求出 p0… pi1中最大相同的前綴與后綴的問題，也就是需要判斷： p0… pi2 是否等于p1… pi1 如果不等，繼續(xù)判斷 p0… pi3 是否等于p2… pi1等等。 但是仔細(xì)分析一下，因為每執(zhí)行一次外層循環(huán)，i嚴(yán)格增 1， 所以外層循環(huán)正好執(zhí)行 m－ 1次； 另外 k的值從 1開始， k++恰好執(zhí)行 m－ 1次，并且只有在這一語句中 k被增值。 ? 模式匹配是子串在主串中的定位操作 ， 是一個比較常用的操作 。 ? 無回溯的模式匹配算法的技巧性很強(qiáng) ， 實現(xiàn)無回溯的模式匹配的基礎(chǔ)是依靠 next數(shù)組支持 。 因此
高考資料相關(guān)推薦
鄂ICP備17016276號-1