1、 4.1 串類型的定義 4.2 串的表示和實現 4.3 串的模式匹配算法第4章 串重點: (1)ADT串的設計、實現方法和基本操作；(2)串的簡單模式匹配算法，KMP算法。 難點:串的模式匹配算法中的KMP算法。 本章重點難點 4.1 串類型的定義 4.2 串的表示和實現 4.3 串的模式匹配算法第4章 串4.1 串類型的定義 串是由零個或多個字符組成的有限序列。 記為：s=”a1a2an” (n0) 其中，s是串的名，用雙引號括起來的字符序列是串的值。 (1) 串的長度:串中字符的數目n。 (2) 空串(Null string):長度為零的串。 (3) 子串:串中任意個連續的字符組成的子序列

2、。 串的有關術語 串(String)的定義4.1 串類型的定義 (1) 串數據對象約束為字符集。 (2) 基本操作的對象不同，線性表以“單個元素”為操作對象；串以“串的整體”為操作對象，操作的一般都是子串。 串與一般線性表的區別ADT String 數據對象： 數據關系： 基本操作： ADT String 串的ADT定義見下頁D ai |aiCharacterSet,i=1,2,.,n, n0 R1 | ai-1, ai D, i=2,.,n 4.1 串類型的定義 基本操作： SubString (&Sub, S, pos, len) /求子串 Index (S, T, pos) /子串定位

3、ClearString (&S) /清空串S StrDelete (&S, pos, len) /刪除子串 Replace (&S, T, V) /把串S中符合T的子串替換 StrInsert (&S, pos, T) /插入子串4.1 串類型的定義4.2 串的表示和實現4.2.1、定長順序存儲表示4.2.2、堆分配存儲表示4.2.3、串的塊鏈存儲表示4.2.1 定長順序存儲表示 #define MAXSTRLEN 255 / 用戶可在255以內定義最大串長 typedef unsigned char SstringMAXSTRLEN+1; / 0號單元存放串的長度Sstring S; 串的順

4、序存儲C語言實現 Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2聯接而成的新串。若未截斷, 則返回TRUE，否則FALSE。 . return uncut; / Concat T1.S10 = S11.S10; TS10+1S10+S20 = S21S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截斷4.2.1 定長順序存儲表示 串的連接算法 Status Concat(SString S1, SString S2, SString &T) /

5、 用T返回由S1和S2聯接而成的新串。若未截斷, 則返回TRUE，否則FALSE。 . return uncut; / Concat else if (S10 MAXSTRSIZE) / 截斷T1.S10 = S11.S10;TS10+1MAXSTRLEN = S21MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; 4.2.1 定長順序存儲表示 串的連接算法 Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2聯接而成的新串。若未截斷, 則返回TRUE，否則FALSE。 . retur

6、n uncut; / Concat else / 截斷(僅取S1) T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; 4.2.1 定長順序存儲表示 串的連接算法4.2 串的表示和實現4.2.1、定長順序存儲表示4.2.2、堆分配存儲表示4.2.3、串的塊鏈存儲表示4.2.2 堆分配存儲表示 typedef struct char *ch; / 若是非空串，則按串長分配存儲區， / 否則ch為NULL int length; / 串長度 HString; 堆分配存儲表示的C語言實現 Status SubStri

7、ng(HString &Sub, HString S, int pos, int len) if (pos S.length | len S.length-pos+1) return ERROR; if (Sub.ch) free (Sub.ch); / 釋放舊空間 if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串 else . / 完整子串 return OK; / SubString4.2.2 堆分配存儲表示 堆分配存儲表示的求子串算法 Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1

8、 = Spos-1.pos+len-2; Sub.length = len;4.2.2 堆分配存儲表示 堆分配存儲表示的求子串算法接上頁4.2.3 串的塊鏈存儲表示字符串本身就是一個線性表，可以用鏈表存儲。存儲密度 = 數據元素所占存儲位實際分配的存儲位存儲密度 = 840=20% 鏈表存儲字符串的討論如果每個結點存儲一個字符，如采用32位地址，字符按8位記，則存儲密度是多少？4.2.3 串的塊鏈存儲表示結論：采用普通鏈表存儲字符串，存儲密度非常低，浪費空間嚴重。 鏈表存儲字符串的討論解決辦法：一個結點存儲多個字符。這就是串的塊鏈存儲。 #define CHUNKSIZE 80 typedef

9、 struct Chunk / 結點結構 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結構 Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當前長度 LString;4.2.3 串的塊鏈存儲表示 串的塊鏈存儲的C語言實現4.3 串的模式匹配算法4.3.1 模式匹配簡單算法4.3.2 模式匹配KMP算法4.3.1 模式匹配簡單算法int Index(SString S, SString T, int pos) i = pos; j = 1; while (i = S0

10、 & j T0) return i-T0; else return 0; / Index 討論下面這種情況的時間復雜性，設S串長為n，T串長為m。 S：a b c d e f g h j k l l k c d e T：j k l4.3.1 模式匹配簡單算法 時間復雜性分析 假設從第i個位置匹配成功，前i-1次共比較了i-1次。 第i次比較了m次,共比較了i+m-1次。 i從1到n-m+1,共(n+m)(n-m+1)/2 平均需比較(n+m)/2 最好的情況平均時間復雜度為O(n+m)4.3 串的模式匹配算法4.3.1 模式匹配簡單算法4.3.2 模式匹配KMP算法主串S：子串T：4.3.1

11、模式匹配KMP算法abcdccdde例abcde1 2 3 4 5 6 7 8 9ij下圖中主串游標i指向5，子串中游標j指向5，按照簡單模式匹配算法兩處不相等時j回到1，i回到2，繼續比較，分析在這種情況下，這樣做有沒有意義？結論：沒有意義。 事例討論主串S：子串T：4.3.1 模式匹配KMP算法abcdabcdabcfeabcdabcf1 2 3 4 5 6 7 8 9ij結論：j回到1，i回到2沒有意義。例下圖中主串游標i指向8，子串中游標j指向8，按照簡單模式匹配算法兩處不相等時j回到1，i回到2，繼續比較，分析在這種情況下，這樣做有沒有意義？在什么情況下才有意義？ 事例討論主串S：子

12、串T：4.3.1 模式匹配KMP算法abcdabcdabcfeabcdabcf1 2 3 4 5 6 7 8 9ij 事例討論結論：只有i回到5，j回到1才有意義。如下圖。主串S：子串T：abcdabcdabcfeabcdabcf1 2 3 4 5 6 7 8 9ij與原來的比較圖進行對比，看有什么發現？主串S：子串T：4.3.1 模式匹配KMP算法abcdabcdabcfeabcdabcf1 2 3 4 5 6 7 8 9ij 事例討論結論：可以i不動，j回到4。如下圖。 KMP算法的思想主串指針不回溯，模式串向后滑動至某個位置上。主串S：子串T：4.3.1 模式匹配KMP算法abcdabc

13、dabcfeabcdabcf1 2 3 4 5 6 7 8 9ij 子串游標滑動到k必須滿足的條件結論：可以i不動，j回到4。如下圖。與原來的比較圖進行對比，看有什么發現？abcdabcfj假如j滑動到k,如果比較有意義:必須滿足: “t1t2tk-1” = “si-k+1si-k+2si-1” “tj-k+1tj-k+2tj-1” = “si-k+1si-k+2si-1”（部分匹配） “t1t2tk-1” = “tj-k+1tj-k+2tj-1” (真子串）主串S：Si-j Si-j+1 Si-j+2 Si-2 Si-1Si Si+1子串T： t1 t2 tj-2 tj-1 tj4.3.1

14、模式匹配KMP算法 子串游標滑動到k必須滿足的條件 max k|1kj,且“t1tk-1”=“tj-k+1tj-1” 當此集合非空時 0 當j=1時 1 其他情況nextj=表明當模式中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置。4.3.1 模式匹配KMP算法 nextj函數int Index_KMP (SString S,SString T, int pos) i= pos,j =1; while (i=S0 & jt0) return i-t0; /匹配成功 else return 0; /返回不匹配標志 4.3.1 模式匹配KMP算法 KMP算

15、法(1) next1 = 0;表明主串從下一字符si+1起和模式串重新開始匹配。i = i+1; j = 1;4.3.1 模式匹配KMP算法 求next函數值(2) 設nextj = k，則nextj+1 = ? 若tk=tj，則有“t1tk-1tk”=“tj-k+1tj-1tj” ，如果在j+1發生不匹配: 說明nextj+1 = k+1 = nextj+1。 若tktj，可把求next值問題看成是一個模式匹配問題，整個模式串既是主串，又是子串。求nextj+1,如果tj=tk;則nextj+1=k+1;如果tj tk 若tk=tj，則有“t1tk”=“tj-k+1tj”， nextj+1=k+1=nextk+1=nextnextj+1. 若tk”=tj ，則有“t1tk”=“tj-k”+1tj”， nextj+1=k”+1=nextk+1