串類型的定義串的示和實現(xiàn)串的模式匹配算法

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

2、 (3) 子串:串中任意個連續(xù)的字符組成的子序列。p 串的有關術語p 串(string)的定義 5 第第4 4章章 串串4.1 串類型的定義串類型的定義 (4) 主串 包含子串的串相應地稱為主串。 (5) 串相等 只有當兩個串的長度相等，并且各個對應位置的字符都相等，稱兩串相等。 (6) 空格串(空白串)(blank string) 由一個或多個空格組成的串。要和“空串”區(qū)別，空格串有長度就是空格的個數(shù)。p 串的有關術語 6 第第4 4章章 串串4.1 串類型的定義串類型的定義 (1) 串數(shù)據(jù)對象約束為字符集。 (2) 基本操作的對象不同，線性表以“單個元素”為操作對象；串以“串的整體”為操作

3、對象，操作的一般都是子串。p 串與一般線性表的區(qū)別 7 第第4 4章章 串串a(chǎn)dt string 數(shù)據(jù)對象數(shù)據(jù)對象： 數(shù)據(jù)關系數(shù)據(jù)關系： 基本操作：基本操作： adt string p 串的adt定義見下頁見下頁d ai |aicharacterset,i=1,2,.,n, n0 r1 | ai-1, ai d, i=2,.,n 4.1 串類型的定義串類型的定義 8 第第4 4章章 串串p 基本操作： strassign (&t, chars) /根據(jù)串常量根據(jù)串常量chars生成串生成串t strcopy (&t, s) /把串把串s中內容拷貝到中內容拷貝到t串串 destr

4、oystring(&s) /銷毀串銷毀串s strempty (s) /判斷串是否空判斷串是否空 strcompare (s, t) /比較串比較串s和和t strlength(s) /求串長求串長 concat (&t, s1, s2) /連接串連接串4.1 串類型的定義串類型的定義 9 第第4 4章章 串串p 基本操作： substring (&sub, s, pos, len) /求子串求子串 index (s, t, pos) /子串定位子串定位 clearstring (&s) /清空串清空串s strdelete (&s, pos, len)

5、 /刪除子串刪除子串 replace (&s, t, v) /把串把串s中符合中符合t的子串替換的子串替換 strinsert (&s, pos, t) /插入子串插入子串4.1 串類型的定義串類型的定義 10 第第4 4章章 串串4.2 串的表示和實現(xiàn)4.2.1、定長順序存儲表示4.2.2、堆分配存儲表示4.2.3、串的塊鏈存儲表示 11 第第4 4章章 串串4.2.1 定長順序存儲表示定長順序存儲表示 #define maxstrlen 255 / 用戶可在用戶可在255以內定義最大串長以內定義最大串長 typedef unsigned char sstringmaxstr

6、len+1; / 0號單元存放串的長度號單元存放串的長度sstring s;p 串的順序存儲c語言實現(xiàn) 12 第第4 4章章 串串 status concat(sstring s1, sstring s2, sstring &t) / 用用t返回由返回由s1和和s2聯(lián)接而成的新串。若未截斷聯(lián)接而成的新串。若未截斷, 則返回則返回true，否則，否則false。 . return uncut; / concat t1.s10 = s11.s10; ts10+1s10+s20 = s21s20; t0 = s10+s20; uncut = true; if (s10+s20 = maxst

7、rlen) / 未截斷未截斷4.2.1 定長順序存儲表示定長順序存儲表示p 串的連接算法 13 第第4 4章章 串串 status concat(sstring s1, sstring s2, sstring &t) / 用用t返回由返回由s1和和s2聯(lián)接而成的新串。若未截斷聯(lián)接而成的新串。若未截斷, 則返回則返回true，否則，否則false。 . return uncut; / concat else if (s10 maxstrsize) / 截斷截斷t1.s10 = s11.s10;ts10+1maxstrlen = s21maxstrlens10;t0 = maxstrlen

8、; uncut = false; 4.2.1 定長順序存儲表示定長順序存儲表示p 串的連接算法 14 第第4 4章章 串串 status concat(sstring s1, sstring s2, sstring &t) / 用用t返回由返回由s1和和s2聯(lián)接而成的新串。若未截斷聯(lián)接而成的新串。若未截斷, 則返回則返回true，否則，否則false。 . return uncut; / concat else / 截斷截斷(僅取僅取s1) t0.maxstrlen = s10.maxstrlen; / t0 = s10 = maxstrlen uncut = false; 4.2.1

9、 定長順序存儲表示定長順序存儲表示p 串的連接算法 15 第第4 4章章 串串 status strdelete (ssstring &s, int pos, int len) if (poss0|len=s0) s0=pos-1; else for(i=pos+len;i=s0;i+) si-len=si; s0=s0-len; return ok;4.2.1 定長順序存儲表示定長順序存儲表示p 子串的刪除算法 16 第第4 4章章 串串4.2 串的表示和實現(xiàn)4.2.1、定長順序存儲表示4.2.2、堆分配存儲表示4.2.3、串的塊鏈存儲表示 17 第第4 4章章 串串4.2.2 堆分

10、配存儲表示堆分配存儲表示 typedef struct char *ch; / 若是非空串，則按串長分配存儲區(qū)，若是非空串，則按串長分配存儲區(qū)， / 否則否則ch為為null int length; / 串長度串長度 hstring;p 堆分配存儲表示的c語言實現(xiàn) 18 第第4 4章章 串串status concat(hstring &t, hstring s1, hstring s2) / 用用t返回由返回由s1和和s2聯(lián)接而成的新串聯(lián)接而成的新串 if (t.ch) free(t.ch); / 釋放舊空間釋放舊空間 if (!(t.ch = (char *) malloc(s1.l

11、ength+s2.length)*sizeof(char) exit (overflow); t.ch0.s1.length-1 = s1.ch0.s1.length-1; t.length = s1.length + s2.length; t.chs1.lengtht.length-1 = s2.ch0.s2.length-1;return ok; / concat4.2.2 堆分配存儲表示堆分配存儲表示p 堆分配存儲表示的串連接算法 19 第第4 4章章 串串 status substring(hstring &sub, hstring s, int pos, int len) i

12、f (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 堆分配存儲表示堆分配存儲表示p 堆分配存儲表示的求子串算法 20 第第4 4章章 串串 sub.ch = (char *)malloc(len*sizeof(char); sub.ch0.len-1 = spos-1.pos

13、+len-2; sub.length = len;4.2.2 堆分配存儲表示堆分配存儲表示p 堆分配存儲表示的求子串算法接上頁接上頁 21 第第4 4章章 串串4.2.3 串的塊鏈存儲表示串的塊鏈存儲表示字符串本身就是一個線性表，可以用鏈表存儲。存儲密度存儲密度 = 數(shù)據(jù)元素所占存儲位數(shù)據(jù)元素所占存儲位實際分配的存儲位實際分配的存儲位存儲密度存儲密度 = 840=20% p 鏈表存儲字符串的討論如果每個結點存儲一個字符，如采用32位地址，字符按8位記，則存儲密度是多少？ 22 第第4 4章章 串串4.2.3 串的塊鏈存儲表示串的塊鏈存儲表示結論：采用普通鏈表存儲字符串，存儲密度非常低，浪費空間

14、嚴重。p 鏈表存儲字符串的討論解決辦法：一個結點存儲多個字符。這就是串的塊鏈存儲。 23 第第4 4章章 串串 #define chunksize 80 typedef struct chunk / 結點結構結點結構 char chcunksize; struct chunk *next; chunk; typedef struct / 串的鏈表結構串的鏈表結構 chunk *head, *tail; / 串的頭和尾指針串的頭和尾指針 int curlen; / 串的當前長度串的當前長度 lstring;4.2.3 串的塊鏈存儲表示串的塊鏈存儲表示p 串的塊鏈存儲的c語言實現(xiàn) 24 第第4 4

15、章章 串串4.3 串的模式匹配算法4.3.1 模式匹配簡單算法4.3.2 模式匹配kmp算法 25 第第4 4章章 串串4.3 串的模式匹配算法串的模式匹配算法初始條件：串s和t存在，t是非空串， 1posstrlength(s)。index (s, t, pos)p 串匹配(查找)的定義操作結果：若主串s中存在和串t值相同的子串返回它在主串s中第pos個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。 26 第第4 4章章 串串4.3.1 模式匹配簡單算法int index(sstring s, sstring t, int pos) i = pos; j = 1; while (i = s0 &

16、amp; j t0) return i-t0; else return 0; / index 27 第第4 4章章 串串 討論下面這種情況的時間復雜性，設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 模式匹配簡單算法模式匹配簡單算法p 時間復雜性分析 假設從第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) 28 第第4 4章章 串串 討論下面這種情況的時間復雜性，

17、設s串長為n，t串長為m。 s：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 t：0 0 0 0 0 0 14.3.1 模式匹配簡單算法模式匹配簡單算法 若第i趟比較成功，共比較了多少次？ 前i-1趟比較每次都比較m次，第i趟也比較m次 共im次， i從1到n-m+1 共比較了(n-m+2)(n-m+1)m/2 平均比較次數(shù)(n-m+2)m/2 最壞的情況時間復雜度為o(n m)p 時間復雜性分析 29 第第4 4章章 串串4.3 串的模式匹配算法4.3.1 模式匹配簡單算法4.3.2 模式匹配kmp算法 30 第第4 4章章 串串主串s：子串t：4.3.1 模式

18、匹配模式匹配kmp算法算法a b c d c c d d e例例a b c d e1 2 3 4 5 6 7 8 9ij下圖中主串游標i指向5，子串中游標j指向5，按照簡單模式匹配算法兩處不相等時j回到1，i回到2，繼續(xù)比較，分析在這種情況下，這樣做有沒有意義？結論：沒有意義。p 事例討論 31 第第4 4章章 串串主串s：子串t：4.3.1 模式匹配模式匹配kmp算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ij結論：j回到1，i回到2沒有意義。例例下圖中主串游標i指向8，子串中游標j指向8，按照簡單模式匹配算法兩處

19、不相等時j回到1，i回到2，繼續(xù)比較，分析在這種情況下，這樣做有沒有意義？在什么情況下才有意義？p 事例討論 32 第第4 4章章 串串主串s：子串t：4.3.1 模式匹配模式匹配kmp算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ijp 事例討論結論：只有i回到5，j回到1才有意義。如下圖。主串s：子串t：a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ij與原來的比較圖進行對比，看有什么發(fā)現(xiàn)？ 33 第第4 4章章 串串主串主串s：子串子串t：4.3

20、.1 模式匹配模式匹配kmp算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ijp 事例討論結論：可以i不動，j回到4。如下圖。p kmp算法的思想主串指針不回溯，模式串向后滑動至某個位置上。 34 第第4 4章章 串串主串s：子串t：4.3.1 模式匹配模式匹配kmp算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ijp 子串游標滑動到k必須滿足的條件結論：可以i不動，j回到4。如下圖。與原來的比較圖進行對比，看有什么發(fā)現(xiàn)？a b c d a b

21、 c fj 35 第第4 4章章 串串假如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 模式匹配模式匹配kmp算法算法p 子串游標滑動到k必須滿足的條件 36 第第4 4章章 串串 max k|1kj,且且“t1tk-1”=“tj-

22、k+1tj-1” 當此集合非空時當此集合非空時 0 0 當當j=1j=1時時 1 1 其他情況其他情況nextj=表明當模式中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置。4.3.1 模式匹配模式匹配kmp算法算法p nextj函數(shù) 37 第第4 4章章 串串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算法算法p kmp算法 38 第第4 4章章 串串(1) next1 = 0;表明主串從下一字符表明主串從下一字