程序員 (53)

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

2、子串的第一個(gè)字符在主串的位置?？沾侨我獯淖哟?。串相等：指兩個(gè)串長(zhǎng)度相等且對(duì)應(yīng)位置上的字符也相同。串比較：兩個(gè)串比較大小時(shí)以字符的Il碼值作為依據(jù)。比較操作從兩個(gè)串的第一個(gè)字符開(kāi)始進(jìn)行，字符的Il碼值大者所在的串為大；若其中一個(gè)串先結(jié)束，則以串長(zhǎng)較大者為大。3)串的基本操作賦值操作StrAssign(s，t)：將串t的值賦給串S。聯(lián)接操作Concat(s，t)：將串t接續(xù)在串S的尾部，形成一個(gè)新串。求串長(zhǎng)StrLength(s)：返回

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

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

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