第3章-字符串-全文預(yù)覽
【正文】 tj比較，也必然不相等。 ?由此可見 ， 若在匹配時發(fā)現(xiàn) pi≠tj， 即可直接地把 p右移 i－ k位 ， 并且只從 pk與 tj開始向右比較 。 ?k是 p0… pi1串中最大的前綴與后綴的長度（ 0≤k≤i－ 1） 。 j++}， 所以循環(huán)中 ， 執(zhí)行 i＝ next[i]的次數(shù) ， 不會超過 i++的執(zhí)行次數(shù)加 1。 ?特別地，如果 p中任何字符都不必再與 tj進行比較（這個 next[i]下面用 1表示），可以直接從 tj+1和 p0開始比較。 例 :設(shè)目標串 t＝ abbaba和 p＝ aba“ ， t的長度為 n（ n=6） ,p的長度為 m（ m=3） 該算法簡單，易于理解，但效率不高，一旦比較不等，就將 p所指的串右移一個字符，并從 p0（算法中用 pc[0]表示）開始比較。 匹配結(jié)果有兩種：如果 t中存在等于 p的子串，就指出該子串在 t中的位置，稱為匹配成功；否則稱為匹配失敗。 程序?qū)崿F(xiàn) 模式匹配 設(shè)有兩個串 t和 p： t = t0t1… tn1 p = p0p1… pm1 其中 1＜ m≤n（通常有 m n）。 創(chuàng)建帶頭結(jié)點的空鏈串 創(chuàng)建空串的方法與創(chuàng)建空鏈表類似 ， 可有如下程序?qū)崿F(xiàn)： LinkString createNullStr_link( void ) 求單鏈表示的串的子串 LinkString subStr_link(LinkString s,int i,int j) 求從 s所指的帶頭結(jié)點的鏈串中第 i(i0)個字符 開始連續(xù)取 j個字符所構(gòu)成的子串。 typedef struct StrNode *LinkString。 /* 鏈串的結(jié)點 */ typedef struct StrNode *PStrNode。 然后判斷所給參數(shù) i ， j的值是否合理， i ， j的取值應(yīng)滿足 1≤ i ≤ sn， j0。 }。 end ADT String 字符串的實現(xiàn) ?順序表示 ?鏈接表示 順序表示 字符串的順序表示，就是把串中的字符，順序地存儲在一 組地址連續(xù)的存儲單元中。 int length ( String s ) 返回串 s的長度。 ?除 s本身之外， s的其它子串稱為 s的 真子串 ?？兆址彩且粋€字符，由一個或多個空字符構(gòu)成的字符串 “ ” 不是空串。 字符串及其抽象數(shù)據(jù)類型 基本概念 字符串 簡稱串，是一種特殊的線性表，其特殊
高考資料相關(guān)推薦
鄂ICP備17016276號-1