嚴蔚敏數(shù)據(jù)結構課件第四章

1、4.1 串的抽象數(shù)據(jù)類型的定義串的抽象數(shù)據(jù)類型的定義4.2 串的表示和實現(xiàn)串的表示和實現(xiàn)4.3 串的模式匹配算法串的模式匹配算法4.1 串的抽象數(shù)據(jù)類型的定義如下串的抽象數(shù)據(jù)類型的定義如下：ADT String 數(shù)據(jù)對象數(shù)據(jù)對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關系數(shù)據(jù)關系：R1 | ai-1, ai D, i=2,.,n 串是有限長的字符序串是有限長的字符序列，由一對雙引號相列，由一對雙引號相括，如括，如: a string 基本操作基本操作： StrAssign (&T, chars) StrCopy (&T, S) Destro

2、yString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S) ADT String StrAssign (&T, chars) 初始條件：chars 是字符串常量。 操作結果：把 cha

3、rs 賦為 T 的值。 StrCopy (&T, S) 初始條件：串 S 存在。 操作結果：由串 S 復制得串 T。 DestroyString (&S) 初始條件：串 S 存在。 操作結果：串 S 被銷毀。 StrEmpty (S)初始條件：串S存在。操作結果：若 S 為空串，則返回 true， 否則返回 false。 表示空串，空串的長度為零。 StrCompare (S, T)初始條件：初始條件：串 S 和 T 存在。操作結果：操作結果：若S T，則返回值 0； 若S T，則返回值 0； 若S T，則返回值 0。例如：例如：StrCompare(data, state)

4、0 StrLength (S) 初始條件：串 S 存在。 操作結果：返回 S 的元素個數(shù)， 稱為串的長度。 Concat (&T, S1, S2) 初始條件：串 S1 和 S2 存在。 操作結果：用 T 返回由 S1 和 S2 聯(lián)接而成的新串。例如例如： Concate( T, man, kind) 求得 T = mankind SubString (&Sub, S, pos, len)初始條件：操作結果： 用 Sub 返回串 S 的第 pos 個字符起 長度為 len 的子串。串 S 存在，1posStrLength(S) 且 0lenStrLength(S)-pos+1。例

5、如：例如： SubString( sub, commander , 4, 3)子串為子串為“串串”中的一個字符子序列中的一個字符子序列求得 sub = man ; SubString( sub, commander , 1, 9)SubString( sub, commander , 9, 1)求得 sub = r 求得 sub = commander SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(student, 5, 0) = 起始位置和子串長度之間存在約

6、束關系起始位置和子串長度之間存在約束關系長度為長度為 0 的子串為的子串為“合法合法”串串 Index (S, T, pos)初始初始條件：條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結果：操作結果： 若主串 S 中存在和串 T 值相同 的子串, 則返回它在主串 S 中第pos個 字符之后第一次出現(xiàn)的位置; 否則函數(shù)值為0。 假設 S = abcaabcaaabc , T = bca Index(S, T, 1) = 2;Index(S, T, 3) = 6;Index(S, T, 8) = 0; “子串在主串中的位置子串在主串中的位置”意指子串中的第一個字符在主串

7、中的位序位序。 Replace (&S, T, V) 初始條件：串S, T和 V 均已存在， 且 T 是非空串。 操作結果：用 V 替換主串 S 中出現(xiàn) 的所有與（模式串）T 相等的不重疊不重疊的子串。例如：假設 S = abcaabcaaabca, T = bca 若 V = x , 則經置換后得到 S = axaxaax 若 V = bc , 則經置換后得到 S = abcabcaabcbca bca bca StrInsert (&S, pos, T)初始條件：串S和T存在， 1posStrLength(S)1。操作結果：在串S的第pos個字符之前 插入串T。例如：例如：

8、S = chater ，T = rac ， 則執(zhí)行 StrInsert(S, 4, T) 之后得到 S = character StrDelete (&S, pos, len)初始條件：串S存在 1posStrLength(S)-len+1。操作結果：從串S中刪除第pos個字符 起長度為len的子串。 ClearString (&S) 初始條件：串S存在。 操作結果：將S清為空串。 對于串的基本操作集可以有不同的定義方法，在使用高級程序設計語言中的串類型時，應以該語言的參考手冊為準以該語言的參考手冊為準。 gets(str) 輸入一個串； puts(str) 輸出一個串； st

9、rcat(str1, str2) 串聯(lián)接函數(shù)； strcpy(str1, str2, k) 串復制函數(shù)； strcmp(str1, str2) 串比較函數(shù)； strlen(str) 求串長函數(shù)；例如：C語言函數(shù)庫中提供下列串處理函數(shù)： 串賦值串賦值StrAssign、串復制、串復制Strcopy、 串比較串比較StrCompare、求串長、求串長StrLength、 串聯(lián)接串聯(lián)接Concat以及求子串以及求子串SubString 等六種操作構成串類型的最小操作子集等六種操作構成串類型的最小操作子集。在上述抽象數(shù)據(jù)類型定義的13種操作中，即：這些操作不可能利用其他串操作來實現(xiàn)， 反之，其他串操作

10、（除串清除ClearString和串銷毀DestroyString外）可在這個最小操作子 集上實現(xiàn)。 例如，可利用串比較、求串長和求子串等操作實現(xiàn)定位函數(shù) Index( S, T, pos )。 StrCompare(SubString(S, i, StrLength(T), T ) S 串 T 串 T 串iposn-m+1算法的基本思想為：算法的基本思想為：? 0int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個字符之后存在與 T相等的子串， / 則返回第一個這樣的子串在S中的 位置，否則返回0 if (pos 0) / if

11、 return 0; / S中不存在與T相等的子串 / Indexn = StrLength(S); m = StrLength(T); i = pos;while ( i = n-m+1) / whileSubString (sub, S, i, m);if (StrCompare(sub,T) != 0) +i ;else return i ;又如串的置換函數(shù)： S 串 T 串 V 串 V 串pospos subinews 串sub= i+mposn-pos+1void replace(String& S, String T, String V) while ( pos = n-m

12、+1 & i) i=Index(S, T, pos); if (i!=0) SubString(sub, S, pos, i-pos); / 不置換子串 Concat(news, news, sub, V); pos = i+m; /if/whileSubString(sub, S, pos, n-pos+1); / 剩余串Concat( S, news, sub );n=StrLength(S); m=StrLength(T); pos = 1;StrAssign(news, NullStr); i=1; 串的邏輯結構和線性表極為相似，區(qū)別區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。 串的基

13、本操作和線性表有很大差別。串的基本操作和線性表有很大差別。 在線性表的基本操作中，大多以“單個元素”作為操作對象； 在串的基本操作中，通常以“串的整體”作為操作對象。 在程序設計語言中，串只是 作為輸入或輸出的常量出現(xiàn)，則只 需存儲此串的串值，即字符序列即 可。但在多數(shù)非數(shù)值處理的程序中， 串也以變量的形式出現(xiàn)。4.2 串的表示和實現(xiàn)串的表示和實現(xiàn)一、串的定長順序存儲表示一、串的定長順序存儲表示二、串的堆分配存儲表示二、串的堆分配存儲表示三、串的塊鏈存儲表示三、串的塊鏈存儲表示 #define MAXSTRLEN 255 / 用戶可在255以內定義最大串長 typedef unsigned c

14、har Sstring MAXSTRLEN + 1; / 0號單元存放串的長度一、串的定長順序存儲表示一、串的定長順序存儲表示 按這種串的表示方法實現(xiàn)的串的運算時，其基本操作為 “字符序列字符序列的復制的復制” 串串的實際長度可在這個予定義長度的范圍內隨意設定，超過予定義長度的串值則被舍去，稱之為“截截斷斷” 特點特點: Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2聯(lián)接而成的新串。若未截斷, 則返回TRUE，否則FALSE。 return uncut; / Concat例如：例如：串的聯(lián)接算法中需分三種情況

15、處理： T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截斷 else if (S10 MAXSTRSIZE) / 截斷 else / 截斷(僅取S1)T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FAL

16、SE; typedef struct char *ch; / 若是非空串，則按串實用長度分配 /存儲區(qū)，否則 ch 為NULL int length; / 串長度 HString;二、串的堆分配存儲表示二、串的堆分配存儲表示 通常，C語言中提供的串類型就是以這種存儲方式實現(xiàn)的。系統(tǒng)利用函數(shù)malloc( ) 和 free( ) 進行串值空間的動態(tài)管理，為每一個新產生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆堆”。 C語言中的串以一個空字符為結束符， 串長是一個隱含值。 這類串操作實現(xiàn)的算法為: 先為新生成的串分配一個存儲空間，然后 進行串值的復制。Status Concat(HString

17、 &T, HString S1, HString S2) / 用T返回由S1和S2聯(lián)接而成的新串 if (T.ch) delete(T.ch); / 釋放舊空間 if (!(T.ch =new charS1.length+S2.length) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat Status SubString

18、(HString &Sub, HString S, int pos, int len) / 用Sub返回串S的第pos個字符起長度為len的子串 if (pos S.length | len S.length-pos+1) return ERROR; if (Sub.ch) delete (Sub.ch); / 釋放舊空間 if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完整子串 return OK; / SubString if(!(Sub.ch = new charlen) return ERROR; Sub.ch0.le

19、n-1 = S.chpos-1.pos+len-2; Sub.length = len;void StrInsert (Hstring& S, int pos, HString T) / 1posStrLength(S)1。在串 S 的 / 第 pos 個字符之前插入串 T slen=S.length; tlen=T.length; / 取得S和T的串長 if (pos slen+1) return; / 插入位置不合法 S1.ch = new charslen ; / S1作為輔助串 S1.ch0.slen-1 = S.ch0.slen-1; / 暫存 S if (tlen0) /

20、T 非空，則為S重新分配空間并插入T / StrInsert _HSq S.ch = new charslen + tlen ; / 為 S 重新分配空間for ( i=0, k=0; ipos-1; i+) S.chk+ = S1.chi; / 保留插入位置之前的子串for ( i=0; itlen; i+) S.chk+ = T.chi; / 插入Tfor ( i=pos; i 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i mijijijinj T 串一、簡單算法一、簡單算法int Index(SString S, SS

21、tring T, int pos) / 返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為0。 / 其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i = S0 & j T0) return i-T0; else return 0; / Index 先比較模式串的第一個第一個字符， 再比較模式串的最后一個最后一個字符， 最后比較模式串中從第二個 到第 n-1 個字符。二、首首尾尾匹配算法匹配算法int Index_FL(SString S, SString T, int pos) sLength = S0; tLength

22、 = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始點 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; 檢查中間字符的匹配情況檢查中間字符的匹配情況 k = 1; j = 2; while ( j tLength & Si+k = Tj) +k; +j; if ( j = tLength ) r

23、eturn i; else +i; / 重新開始下一次的匹配檢測KMP算法的時間復雜度可以達到O(m+n) 當 Si Tj 時，假設此時應與模式中第k（kj）個字符繼續(xù)比較，則模式中前k-1個字符的子串必須滿足：T1.k-1=Si-k+1.i-1 已經得到的結果: Si-j+1.i-1 = T1.j-1 在上式中取任意多個從右到左的子串仍然相等，取k-1個，有 Si-k+1.i-1 = Tj-k+1.j-1 則有 Tj-k+1.j-1 = T1.k-1三、三、KMP(KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法算法能向右滑動多遠？ t1 tk tj tm s

24、1 si sn s1 si sn p1 tk tj tm 顯然應有：sik+1si1 = t1tk1。 s t1 而由前次的比較應有：sik+1si1 = tjk+1 tj1。 于是得到這樣的結果：t1tk1 = tjk+1 tj1。一個模式的next(j) j ： 1 2 3 4 5 6 7 8 9 模式 ： a b a a b a a a b nextj ：初始化：next1 = 0。0 沒有相應的k，next(j)為1。1 1 k = 2，下次從第二個元素開始比較。2 2 依次以此類推可得其余元素的next(j)。3 4 52滑動不會造成遺漏 引理引理 1： 正文S和模式P比較時，若si

25、pj，則 S沒有以sik0+1(nextjk01時，假設結論不成立，即存在這樣的k0，那么有p1 p2 pk01= sik0+1sik0+2 si1。 從而有， p1 p2 pk01= pjk0+1pjk0+2 pj1 (7.3) 由假設有nextjk0i。 這與nextj是滿足(7.3)式的最大值相矛盾；所以結論成立。定義：定義：模式串的next函數(shù)其它情況且時當 1 pppppjk1 |Maxk1j 0j1 - j1k- j1 -k21next int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos;

26、j = 1; while (i = S0 & j T0) return i-T0; / 匹配成功 else return 0; / Index_KMP這實際上也是一個匹配的過程，不同在于：主串和模式串是同一個串 求 next 函數(shù)值的過程是一個遞推過程，分析如下:已知已知：next1 = 0；假設假設：nextj = k；又 Tj = Tk則則： nextj+1 = k+1若若： Tj Tk則則 需往前回朔，檢查 Tj = T ？next(j)的計算 如何來計算模式P的next(j)? 首先，我們由定義可知next(1) = 0； 其次，顯然有next(2) = 1； 現(xiàn)在我們來考慮n

27、ext(j+1)。 由next(j)=k可知模式中有：p1pk1= pjk+1pj1。 現(xiàn)在存在兩種情況： pk = pj或者pk pj。 如果pk = pj，于是p1 pk1pk= pjk+1 pj1pj。從而有 next(j+1) = next(j) +1。next(j)的計算 如果pk pj，顯然next(j+1) next(j)。 這實際是在將p1 pk1pk與pjk+1 pj1pj相匹配時，出現(xiàn)了pj與pk失佩。 p1 pk1 pk pjk+1 pjk+1 pj p1 pk1 pkpk pjn下一步拿p1 pk1pk中哪個元素和pj相比較呢？滑動多遠？n向右滑動next(k)，即比較

28、pnext(k)和pj。n若這時有pnext(k) = pj，則next(j+1) = next(k) + 1；n若這時有pnext(k) pj，則再重復以上的做法，直至k = 1。next(j)的計算 int nextMaxStrLen; void get_next(SString P) j = 1; next1 = 0; k = 0； while(j = P0) if (k = 0Pk = Pj) +k; +j; nextj = k;/next(j+1)=k +1 else k = nextk; 初始化循環(huán)逐個計算元素j的next(j)若pk = pj，則next(j+1)=k +1。注意

29、此處的k, j都加了1。若pk pj，則比較pnext(k)和pj一個模式的next(j) j ： 1 2 3 4 5 6 7 8 9 模式 ： a b a a b a a a b nextj ：初始化：j = 1; next1 = 0; k = 0；10第一趟：j = 1; k = 0； k = 0 +k; +j; nextj = k;即，k = 1; j = 2; next(2) =1。 第二趟： j = 2; k = 1 P1 P2 k = nextk = 0 k = 0 +k; +j; nextj = k;即，k = 1; j = 3; next(3) =1。 1第三趟： j = 3; k = 1。 P1 = P3 +k; +j; nextj = k;即，k = 2; j = 4; next(4) =2。 2第四趟：j = 4; k = 2。 P2 P4 k = next2 = 1 P1 = P4 / k = 1 +k; +j; nextj = k;即，k = 2; j = 5; next(5) =2。 2第五趟：j = 5; k = 2。 P2 = P5 +k; +j; nextj = k;即，k = 3; j = 6; next(6) =3。 3第