【正文】 串的順序存儲中 ， 如何標識一個串的實際長度 ？ 用數(shù)組來存放串，其存儲結構與順序表相同，但串的操作是把串作為一個整體，從而有其與順序表不同的操作特性。 第 3章 特殊線性表 ——串 ⑸ StrCmp (s1， s2)： 串比較 ， 若 s1=s2， 返回 0；若s1s2, 返回 1；若 s1s2, 返回 1。 第 3章 特殊線性表 ——串 2. 串的比較 串的比較是通過組成串的 字符 之間的比較來進行的 。 (4)順序性：相鄰字符之間具有前驅(qū)后繼關系 。 空串 ：長度為 0的串。 串的長度 ：串中所包含的字符個數(shù)。 (2)si在串中出現(xiàn)的序號 i稱為該字符在串中的位置 (3)有限性：組成串的字符個數(shù)是有限的 。為了保持兼容性， Unicode字符集中的前 256個字符與擴展 ASCII碼完全相同。 ⑷ SubStr (s， i， len)： 求子串 ， 返回從串 s的第 i個字符開始取長為 len 的子串 。 第 3章 特殊線性表 ——串 串的存儲結構 1. 串的順序存儲結構 定義 ： 串的順序存儲結構是用數(shù)組來存儲串中的字符序列。 優(yōu)缺點？ 非壓縮形式：操作方便 ， 但存儲率低； 壓縮形式：存儲率高 ， 但操作復雜 。 基本思想 是：從主串 S的第一個字符開始和模式 T的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串 S的第二個字符開始和模式 T的第一個字符進行比較，重復上述過程，若 T中的字符全部比較完畢，則說明本趟匹配成功；否則匹配失敗。} else {i=ij+2。amp。 } 第 3章 特殊線性表 ——串 第 3章 特殊線性表 ——串 設主串 s=“ababcabcacbab”， 模式 t=“abcac”， BF算法的匹配過程如圖 ： a b a b c a b c a c b a b a b c 結論： i=3， j=3 失?。?i回溯到 2， j回溯到 1 第1趟 i j i j i j i j 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a i j i j 第2趟 i=2， j=1失敗 i回溯到 3， j回溯到 1 第3趟 a b a b c a b c a c b a b a b c a c i=7， j=5失敗 i回溯到 4， j回溯到 1 i j i j i j i j i j j i 第 3章 特殊線性表 ——串 第4趟 a b a b c a b c a c b a b a i j i=4， j=1失敗 i回溯到 5， j回溯到 1 j i 第5趟 a b a b c a b c a c b a b i j a j i i=5， j=1失敗 i回溯到 6， j回溯到 1 第 3章 特殊線性表 ——串 第6趟 a b a b c a b c a c b a b a b c a c i=11， j=6， t 中 全 部字符都比較完畢 ， 匹配成功 。 式中僅剩一個未知數(shù) k， 理論上已可解！ 根據(jù)模式串 T的規(guī)律： ‘ T1…T k1?=?Tj(k1) …T j1? 由當前失配位置 j(已知 ) ，可以 歸納 出計算新起點 k的表達式。 next[j]與 s無關，可以預先計算 例： 1 第 3章 特殊線性表 ——串 1. 在串 S和串 T中分別設比較的起始下標 i和 j； 2. 循環(huán)直到 S中所剩字符長度小于 T的長度或 T中所有字符均比較完畢 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個字符；否則 將 j向右滑動到 next[j]位置 ， 即 j=next[j]； 如果 j=0， 則將 i和 j分別加 1， 準備下一趟比較； 3. 如果 T中所有字符均比較完畢，則返回匹配的起始下標；否則返回 0； KMP算法用偽代碼描述 void GetNext(char T[ ], int next[ ]) { next[1]=0。而 KMP算法的時間復雜度為O(n