數(shù)據(jù)結(jié)構(gòu)：第04章 串

1、第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第四章第四章 串串2022年年3月月29日星期二日星期二第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 2第四章第四章 串串串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的串的數(shù)據(jù)對象約束為字符集數(shù)據(jù)對象約束為字符集。然而，串的基本操作和線性表有很大差別。在線性然而，串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以表的基本操作中，大多以“單個元素單個元素”作為操作對象，作為操作對象，如：

2、在線性表中查找某個元素、求取某個元素、在如：在線性表中查找某個元素、求取某個元素、在某個位置上插入一個元素和刪除一個元素等；某個位置上插入一個元素和刪除一個元素等；而在串的基本操作中，通常以而在串的基本操作中，通常以“串的整體串的整體”作為操作為操作對象作對象，如：在串中查找某個子串、求取一個子串、在串的如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。某個位置上插入一個子串以及刪除一個子串等。第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 34.1 4.1 串的定義串的定義是由零個或多個字符組成的有限序列，一

3、般記為是由零個或多個字符組成的有限序列，一般記為s=“a1a2an”(n 0)其中，其中，s是串名，用單引號（也可以是用雙引號括起來是串名，用單引號（也可以是用雙引號括起來的）括起來的字符序列是串的值。的）括起來的字符序列是串的值。ai可以是字母、數(shù)字或可以是字母、數(shù)字或其他字符；串中字符的個數(shù)其他字符；串中字符的個數(shù)n成為成為串的長度串的長度。子串子串：串中任意個：串中任意個連續(xù)連續(xù)的字符組成的子序列。的字符組成的子序列。主串主串：包含子串的串相應(yīng)地稱為主串。：包含子串的串相應(yīng)地稱為主串。位置位置：字符在序列中的序號。子串在主串中的位置則：字符在序列中的序號。子串在主串中的位置則以子串的以子

4、串的第一個第一個字符在主串中的位置來表示。字符在主串中的位置來表示。相等相等：兩個串的長度相等，并且對應(yīng)位置的字符都相：兩個串的長度相等，并且對應(yīng)位置的字符都相等。等。注意區(qū)分注意區(qū)分空串空串與與空格串空格串的區(qū)別。的區(qū)別。第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 44.1 4.1 串的定義串的定義串的邏輯結(jié)構(gòu)和線性表的區(qū)別串的邏輯結(jié)構(gòu)和線性表的區(qū)別:1. 串的數(shù)據(jù)對象約束為字符集。串的數(shù)據(jù)對象約束為字符集。2. 線性表的基本操作大多以線性表的基本操作大多以“單個元素單個元素”為操作對為操作對象，而串的基本操作通常以象，而串的基本操作通常以

5、“串的整體串的整體”作為操作對象。作為操作對象。 對于串可以定義以下運(yùn)算：對于串可以定義以下運(yùn)算：1. 置串為一個空串；置串為一個空串；2. 判斷一個串是否為空串判斷一個串是否為空串3. 求一個串的長度；求一個串的長度；4. 將兩個串拼接在一起構(gòu)成一個新串；將兩個串拼接在一起構(gòu)成一個新串；5. 在一個串中，求從串的第在一個串中，求從串的第i個字符開始連續(xù)個字符開始連續(xù)j個字符個字符所構(gòu)成的子串；所構(gòu)成的子串；6. 如果串如果串S2是是S1的子串，則可求串的子串，則可求串S2在串在串S1中第一中第一次出現(xiàn)的位置。次出現(xiàn)的位置。第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式

6、匹配算法 4.4 串應(yīng)用 54.1 4.1 串的定義串的定義串的抽象數(shù)據(jù)類型的定義串的抽象數(shù)據(jù)類型的定義ADT String 數(shù)據(jù)對象：數(shù)據(jù)對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 | ai-1, ai D, i=2,.,n 基本操作：基本操作：StrAssign (&T, chars)初始條件：初始條件：chars是字符串常量。是字符串常量。操作結(jié)果：把操作結(jié)果：把chars賦為賦為T的值。的值。StrCopy (&T, S)初始條件：串初始條件：串S存在。操作結(jié)果：由串存在。操作結(jié)果：由串S復(fù)制得串復(fù)制得串T。D

7、estroyString (&S)初始條件：串初始條件：串S存在。操作結(jié)果：串存在。操作結(jié)果：串S被銷毀。被銷毀。StrEmpty (S)初始條件：串初始條件：串S存在。存在。操作結(jié)果：若操作結(jié)果：若S為空串，則返回為空串，則返回TRUE，否則返回，否則返回FALSE。第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 64.1 4.1 串的定義串的定義串的抽象數(shù)據(jù)類型的定義串的抽象數(shù)據(jù)類型的定義StrCompare (S, T)初始條件：串初始條件：串S和和T存在。存在。操作結(jié)果：若操作結(jié)果：若S T，則返回值，則返回值 0；若；若S =T

8、， 則返回值則返回值 =0；若；若S T，則返回值，則返回值 0) n = StrLength(S); m = StrLength(T); i = pos;while ( i = n-m+1) SubString (sub, S, i, m);if (StrCompare(sub,T) != 0) +i ;else return i ; / while / ifreturn 0; / S中不存在與中不存在與T相等的子串相等的子串 / Index第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 114.2 4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)串的順序

9、存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu) PROGRAM PEX1; PROGRAM PEX1;03) 單字節(jié)存儲方式：計算機(jī)以字節(jié)單字節(jié)存儲方式：計算機(jī)以字節(jié)編址時編址時 帶結(jié)束符帶結(jié)束符 P R O G R A M P E X 1 ; 2）非緊縮格式：）非緊縮格式：1個字符個字符/字字 長度隱式表示長度隱式表示14 P R OG R A M P EX1; 1）緊縮格式：）緊縮格式：1個字符個字符/字節(jié)字節(jié) 長度顯式表示長度顯式表示 存儲密度存儲密度=串值所占存儲字節(jié)實(shí)際分配的存儲字節(jié)串值所占存儲字節(jié)實(shí)際分配的存儲字節(jié) 第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4

10、串應(yīng)用 124.2 4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)一、串的定長順序存儲表示一、串的定長順序存儲表示#define MAXSTRLEN 255/ 用戶可在用戶可在255以內(nèi)定義最大串長以內(nèi)定義最大串長typedef unsigned char SStringMAXSTRLEN + 1; / 0號單元存放串的長度號單元存放串的長度串的實(shí)際長度可在這個予定義長度的范圍內(nèi)隨意設(shè)串的實(shí)際長度可在這個予定義長度的范圍內(nèi)隨意設(shè)定，超過予定義長度的串值則被舍去，稱之為定，超過予定義長度的串值則被舍去，稱之為“截斷截斷” 。按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時，其基本操按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時，其

11、基本操作為作為“字符序列的復(fù)制字符序列的復(fù)制”。需預(yù)先定義一個串允許的最大字符個數(shù)需預(yù)先定義一個串允許的最大字符個數(shù)浪費(fèi)空間、插入刪除操作不便浪費(fèi)空間、插入刪除操作不便 第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 13一、串的定長順序存儲表示一、串的定長順序存儲表示例如：串的聯(lián)接算法中需分三種情況處理：例如：串的聯(lián)接算法中需分三種情況處理：Status Concat(SString S1, SString S2, SString &T) /用用T返返回由回由S1和和S2聯(lián)接而成的新串。若未截斷，聯(lián)接而成的新串。若未截斷， 則返回則返回

12、TRUE，否則否則FALSE。if (S10+S20 = MAXSTRLEN) / 未截斷未截斷T1.S10 = S11.S10;TS10+1.S10+S20 =S21.S20;T0 = S10+S20; uncut = TRUE; else if (S10 T,則返回值則返回值0;若若S=T返回值返回值=0，若，若ST返回值返回值0;for(i=0; iS.length & iT.length; i+)if(S.chi != T.chi)return (str1.chi - str2.chi);return (S.length -T.length);第四章 串 4.1 串的定義 4.

13、2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 17三、三、 串的塊鏈存儲表示串的塊鏈存儲表示(a) 單鏈表表示單鏈表表示a 006003b 013006c 008013d 026008e 011026f 011003Heads (b) 循環(huán)表表示循環(huán)表表示a 006003b 013006c 008013d 026008e 011026f 003 011011Heads第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 18三、三、 串的塊鏈存儲表示串的塊鏈存儲表示類類C語言描述語言描述#define CHUNKSIZE 80 / 可由

14、用戶定義的塊大小可由用戶定義的塊大小typedef struct chunk / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)char chCUNKSIZE;struct Chunk *next; Chunk;typedef struct / 串的鏈表結(jié)構(gòu)串的鏈表結(jié)構(gòu)Chunk *head, *tail; / 串的頭和尾指針串的頭和尾指針int curlen; / 串的當(dāng)前長度串的當(dāng)前長度 LString;第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 194.3 4.3 串的模式匹配算法串的模式匹配算法模式匹配模式匹配模式匹配：模式匹配：子串（又稱子串（又稱模式串模式串）

15、在主串中的）在主串中的定位定位操操作。這是串的一種重要操作，很多軟件，若有作。這是串的一種重要操作，很多軟件，若有“編輯編輯”菜單項(xiàng)的話，則其中必有菜單項(xiàng)的話，則其中必有“查找查找”子菜單項(xiàng)。子菜單項(xiàng)。首先，回憶一下串匹配首先，回憶一下串匹配(查找查找)的定義的定義:INDEX (S, T, pos)初始條件：初始條件：串串S和和T存在存在,T是非空串，是非空串，1posStrLength(S)。操作結(jié)果：操作結(jié)果：若主串若主串S中存在和串中存在和串T值相同的子串值相同的子串, 則返回它在主串則返回它在主串S中第中第pos個字符之后第一次出現(xiàn)的位置個字符之后第一次出現(xiàn)的位置; 否則函數(shù)值為否則

16、函數(shù)值為0。第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 204.3 4.3 串的模式匹配算法串的模式匹配算法1. 簡單算法簡單算法設(shè)主串設(shè)主串S=“ababcabcacbab”, 模式串模式串T=“abcac”。則普通算。則普通算法的匹配過程如下：法的匹配過程如下：第一趟匹配第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a ba b c a c第四趟匹配第四趟匹

17、配a b a b c a b c a c b a ba b c a c第五趟匹配第五趟匹配a b a b c a b c a c b a ba b c a c第六趟匹配第六趟匹配a b a b c a b c a c b a ba b c a c第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 214.3 4.3 串的模式匹配算法串的模式匹配算法1. 簡單算法簡單算法int Index(SString S, SString T, int pos) / 返回子串返回子串T在主串在主串S中第中第pos個字符之后的位置。個字符之后的位置。 若不存在，若不

18、存在，則函數(shù)值為則函數(shù)值為0。 其中，其中，T非空，非空，1posStrLength(S)。i = pos; j = 1;while (i = S0 & j T0) return i-T0;else return 0; / Index第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 224.3 4.3 串的模式匹配算法串的模式匹配算法2. 首尾匹配算法首尾匹配算法先比較模式串的第一個字符，再比較模式串的最后一個字先比較模式串的第一個字符，再比較模式串的最后一個字符，最后比較模式串中從第二個到第符，最后比較模式串中從第二個到第n-1個字符。個

19、字符。abcba主串主串: a b a b c a b c a a a b c b a a b c 模式串模式串: a a ( 2 次次) a a a ( 1+2 次次) a a a b b a ( 2+4 次次) a a a a ( 2+2 次次) a a ( 2次次) a b c b a (5 次次) 上述兩種算法的時間復(fù)雜度為上述兩種算法的時間復(fù)雜度為O(m n) 第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 234.3 4.3 串的模式匹配算法串的模式匹配算法3、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris)

20、 算法算法設(shè)主串設(shè)主串S=“ababcabcacbab”, 模式串模式串p=“abcac”。則普通算。則普通算法的匹配過程如下：法的匹配過程如下：第一趟匹配第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a ba b c a c第四趟匹配第四趟匹配a b a b c a b c a c b a ba b c a c第五趟匹配第五趟匹配a b a b c a b c a c b a ba b c a c第六趟匹配第六

21、趟匹配a b a b c a b c a c b a ba b c a c第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 24a b c a c第一趟匹配第一趟匹配a b a b c a b c a c b a b第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a b(a)b c a c改進(jìn)后的匹配情況：改進(jìn)后的匹配情況：第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 25改進(jìn)后的模式匹配算法改進(jìn)

22、后的模式匹配算法 KMP算法算法 希望某趟在希望某趟在si和和pj匹配失敗后，指針匹配失敗后，指針i不回溯，模式不回溯，模式p向右向右“滑動滑動”至某個位置上，使得至某個位置上，使得pk 對準(zhǔn)對準(zhǔn) si 繼續(xù)向右進(jìn)繼續(xù)向右進(jìn)行。顯然，現(xiàn)在問題的關(guān)鍵是串行。顯然，現(xiàn)在問題的關(guān)鍵是串p“滑動滑動”到哪個位置上？到哪個位置上？不妨設(shè)位置為不妨設(shè)位置為k，即，即si和和pj匹配失敗后，指針匹配失敗后，指針i不動，模式不動，模式p向右向右“滑動滑動”，使，使pk和和si對準(zhǔn)繼續(xù)向右進(jìn)行比較，要滿對準(zhǔn)繼續(xù)向右進(jìn)行比較，要滿足這一假設(shè)，就要有如下關(guān)系成立：足這一假設(shè)，就要有如下關(guān)系成立：p1 p2 pk-1

23、 =si-k+1 si-k+2 si-1 (4.1)(4.1)式左邊是式左邊是pk前面的前面的k-1個字符，右邊是個字符，右邊是si 前面的前面的k-1個字符。個字符。第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 26改進(jìn)后的模式匹配算法改進(jìn)后的模式匹配算法 KMP算法算法 而本趟匹配失敗是在而本趟匹配失敗是在si和和pj之處，已經(jīng)得到的部分匹之處，已經(jīng)得到的部分匹配結(jié)果是：配結(jié)果是：p1 p2 pj-1 =si-j+1 si-j+2 si-1 (4.2)因?yàn)橐驗(yàn)閗j，所以有：，所以有：pj-k+1 pj-k+2 pj-1 =si-k+1 si

24、-k+2 si-1 (4.3)(4.3)式左邊是式左邊是 pj前面的前面的k-1個字符，右邊是個字符，右邊是si 前面的前面的k-1個字符，通過個字符，通過(4.1)和和(4.3)得到關(guān)系：得到關(guān)系：p1 p2 pk-1 =pj-k+1 pj-k+2 pj-1 (4.4)結(jié)論：結(jié)論：某趟在某趟在si和和pj匹配失敗后，如果模式串中有滿匹配失敗后，如果模式串中有滿足關(guān)系足關(guān)系(4)的子串存在，即：模式中的前的子串存在，即：模式中的前k-1個字符與模式個字符與模式中中pj字符前面的字符前面的k-1個字符相等時，模式個字符相等時，模式p就可以向右就可以向右“滑滑動動”至使至使pk和和si對準(zhǔn)，繼續(xù)向

25、右進(jìn)行比較即可。對準(zhǔn)，繼續(xù)向右進(jìn)行比較即可。 第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 27改進(jìn)后的模式匹配算法改進(jìn)后的模式匹配算法 （2）next函數(shù)函數(shù) 模式中的每一個模式中的每一個pj都對應(yīng)一個都對應(yīng)一個k值，由值，由(4.4)式可知，式可知，這個這個k值僅依賴與模式值僅依賴與模式p本身字符序列的構(gòu)成，而與主本身字符序列的構(gòu)成，而與主串串s無關(guān)。我們用無關(guān)。我們用nextj表示表示pj對應(yīng)的對應(yīng)的k值，根據(jù)以上分值，根據(jù)以上分析，析，next函數(shù)有如下性質(zhì)：函數(shù)有如下性質(zhì)：nextj是一個整數(shù)，且是一個整數(shù)，且0nextjj為了使為了

26、使p的右移不丟失任何匹配成功的可能，的右移不丟失任何匹配成功的可能，當(dāng)存在多個滿足當(dāng)存在多個滿足(4.4)式的式的k 值時，應(yīng)取最大的，這樣向值時，應(yīng)取最大的，這樣向右右“滑動滑動”的距離最短，的距離最短，“滑動滑動”的字符為的字符為j-nextj個。個。如果在如果在pj前不存在滿足前不存在滿足(4.4)式的子串，此時式的子串，此時若若p1pj，則，則k=1; 若若p1=pj，則，則k=0; 這時這時“滑動滑動”的最遠(yuǎn)，的最遠(yuǎn)，為為j-1個字符即用個字符即用p1 和和sj+1繼續(xù)比較。繼續(xù)比較。改進(jìn)后的模式匹配算法改進(jìn)后的模式匹配算法（2）next函數(shù)函數(shù)next函數(shù)定義如下函數(shù)定義如下 ：0

27、 當(dāng)j=1max k | 1kj 且t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 1 其他情況nextj=設(shè)有模式串：設(shè)有模式串：t=abaabcac，則它的，則它的next函數(shù)值為：函數(shù)值為： j12345678模式串模式串a(chǎn)baabcac nextj01122312第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 29改進(jìn)后的模式匹配算法改進(jìn)后的模式匹配算法(3) KMP算法算法 在求得模式的在求得模式的next函數(shù)之后，匹配可如下進(jìn)行：函數(shù)之后，匹配可如下進(jìn)行：假設(shè)以指針假設(shè)以指針i和和j分別指示主串和模式中的比較字符，令分別

28、指示主串和模式中的比較字符，令i的初值為的初值為pos，j的初值為的初值為1。若在匹配過程中。若在匹配過程中si=tj，則，則i和和j分別增，若分別增，若sitj 匹配失敗后，則匹配失敗后，則i不變，不變，j退到退到nextj位置再比較，若相等，則指針各自增，否則位置再比較，若相等，則指針各自增，否則j再退到下一個再退到下一個next值的位置，依此類推。直至下列兩種值的位置，依此類推。直至下列兩種情況：一種是情況：一種是j退到某個退到某個next值時字符比較相等，則值時字符比較相等，則i和和j分別增繼續(xù)進(jìn)行匹配分別增繼續(xù)進(jìn)行匹配; 另一種是另一種是j退到值為零（即模式退到值為零（即模式的第一個

29、字符失配），則此時的第一個字符失配），則此時i和和j也要分別增，表明也要分別增，表明從主串的下一個字符起和模式重新開始匹配。從主串的下一個字符起和模式重新開始匹配。 第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 30改進(jìn)后的模式匹配算法改進(jìn)后的模式匹配算法(3) KMP算法算法 在假設(shè)已有在假設(shè)已有next函數(shù)情況下，函數(shù)情況下，KMP算法如下：算法如下：int StrIndex_KMP(char *s,char *t,int pos)/*從串從串s的第的第pos個字符開始找首次與串個字符開始找首次與串t相等的子串相等的子串*/ int i=pos,j=1,slen,tlen; while (i=s0 & jt0) return i-t0;/*匹配成功，返回存儲位置匹配成功，返回存儲位置*/ else return 1; /StrIndex_KMP第四章 串 4.1 串的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.4 串應(yīng)用 31void get_next(SString T, int *next) / 算法算法4.7 int i=1; nex