程序員 (53)

1、813串1串的定義及基本運算1)串的定義串是僅由字符構(gòu)成的有限序列，是取值范圍受限的線性表。一般記為S=A，a。…a。7，其中s是串名，單引號括起來的字符序列是串值。2)串的幾個基本概念“空串：長度為零的串，空串不包含任何字符?？崭翊河梢粋€或多個空格組成的串。雖然空格是一個空白符，但它也是一個字符，計算串長度時要將其計算在內(nèi)。子串：由串中任意長度的連續(xù)字符構(gòu)成的序列稱為子串，含有子串的串稱為主串。子串在主串中的位置指子串首次出現(xiàn)時，該

2、子串的第一個字符在主串的位置。空串是任意串的子串。串相等：指兩個串長度相等且對應(yīng)位置上的字符也相同。串比較：兩個串比較大小時以字符的Il碼值作為依據(jù)。比較操作從兩個串的第一個字符開始進行，字符的Il碼值大者所在的串為大；若其中一個串先結(jié)束，則以串長較大者為大。3)串的基本操作賦值操作StrAssign(s，t)：將串t的值賦給串S。聯(lián)接操作Concat(s，t)：將串t接續(xù)在串S的尾部，形成一個新串。求串長StrLength(s)：返回

3、串S的長度。串比較StrCompare(s，t)：比較兩個串的大小。返回值一l、0和1分別表示st3種情況。求子串SubString(s，start，len)：返回串S中從start開始的、長度為len的字符序列。以上5種最基本的串操作構(gòu)成了串的最小操作子集，利用它們就可以實現(xiàn)串的其他運算。2串的存儲結(jié)構(gòu)1)串的靜態(tài)存儲：定長存儲結(jié)構(gòu)串的靜態(tài)存儲結(jié)構(gòu)就是串的順序存儲結(jié)構(gòu)，用一組地址連續(xù)的存儲單元來存儲串值的字符序列。由于串中的元素為字符

4、，所以可通過程序語言提供的字符數(shù)組定義串的存儲空間，也可以根據(jù)串長的需要動態(tài)申請字符串的空間。2)串的鏈?zhǔn)酱鎯Γ簤K鏈字符串也可以采用鏈表作為存儲結(jié)構(gòu)，當(dāng)用鏈表存儲串中的字符時，每個結(jié)點中可以存儲一個字符，也可以存儲多個字符，但要考慮存儲密度問題。結(jié)點大小為4的塊鏈如圖8—12所示。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，結(jié)點大小的選擇和順序存儲方法中數(shù)組空間大小的選擇一樣重要，它直接影響對串處理的效率。3串的模式匹配子串的定位操作通常稱為串的模式匹配，它是各

5、種串處理系統(tǒng)中最重要的運算之一。子串也稱為模式串。1)樸素的模式匹配算法成。設(shè)模式串為’P，…P。7，KMP匹配算法的思想是：當(dāng)模式串中的字符Pi與主串中相應(yīng)的字符S：不相等時，因其前J一1個字符(7p，…PH7)已經(jīng)獲得了匹配，所以若模式串中的7P，…PH’和7P』一川…P一’相同，這時可令P。與Si進行比較，從而使i無須向前回退。在KMP算法中，依據(jù)模式串的next函數(shù)值實現(xiàn)子串的滑動。若令next[j]一k，則next[j]表示當(dāng)