1、,數(shù)據(jù)結(jié)構(gòu) (DATA STRUCTURE),計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2,第四章 串,串的定義 串的表示和實(shí)現(xiàn) 串的模式匹配算法,3,4.1 串類型的定義,字符串 (String)：字符串是n ( 0 ) 個(gè)字符的有限序列，記作 S= “c1c2c3cn” 其中，S 是串名字 “c1c2c3cn”是串值 ci是串中字符 n 是串的長度。 串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個(gè)有窮字符序列。,4,子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。

2、例如，有下列四個(gè)串a(chǎn)，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出現(xiàn)的第一個(gè)字符的位置。 兩個(gè)串相等：兩個(gè)串的長度相等，并且各個(gè)對應(yīng)的字符也都相同。,5,ADT String 數(shù)據(jù)對象: D ai | aiChar, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： StrAssign ( ,7,第二種是在程序執(zhí)行過程中，利用標(biāo)準(zhǔn)函數(shù)malloc和free動(dòng)態(tài)地分配或釋放存儲字符串的存儲單元，并以一個(gè)特殊的字符作為字符串的結(jié)束

3、標(biāo)志，它的好處在于：可以根據(jù)具體情況，靈活地申請適當(dāng)數(shù)目的存儲空間，從而提高存儲資源的利用率。 不同的定義形式，算法中的處理也略有不同。,8,順序串存儲分配演示：,9,4.2.2 鏈?zhǔn)酱鎯Y(jié)構(gòu),由于串結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素為一個(gè)字符，所以最直接的鏈?zhǔn)酱鎯Y(jié)構(gòu)是每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域存放一個(gè)字符。舉例： 優(yōu)點(diǎn)是插入、刪除操作方便； 缺點(diǎn)是存儲密度較低。,10,若要將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，就可以緩解上述問題。舉例： 由于串中的字符個(gè)數(shù)不一定是每個(gè)結(jié)點(diǎn)存放字符個(gè)數(shù)的整倍數(shù)，所以，需要在最后一個(gè)結(jié)點(diǎn)的空缺位置上填充特殊的字符。 這種存儲形式優(yōu)點(diǎn)是提高了存儲密度；缺點(diǎn)是做插入、刪除字符的操作時(shí)，可能會引起結(jié)點(diǎn)之間字符的移動(dòng)，算法實(shí)現(xiàn)起來比較復(fù)雜。,11,4.3 串的模式匹配,定義 在串中尋找子串（第一個(gè)字符）在串中的位置 詞匯 在模式匹配中，子串稱為模式，串稱為目標(biāo)。 示例 目標(biāo) T : “Be