精品數(shù)據(jù)結(jié)構(gòu)串.ppt

1、4.1 串的抽象數(shù)據(jù)類(lèi)型的定義串的抽象數(shù)據(jù)類(lèi)型的定義4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)4.3 串的模式匹配算法串的模式匹配算法4.1 串的抽象數(shù)據(jù)類(lèi)型的定義如下串的抽象數(shù)據(jù)類(lèi)型的定義如下：adt string 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：d ai |aicharacterset, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：r1 | ai-1, ai d, i=2,.,n 串是有限長(zhǎng)的字符序串是有限長(zhǎng)的字符序列，由一對(duì)雙引號(hào)相列，由一對(duì)雙引號(hào)相括，如括，如: 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 是字符串常量。 操作結(jié)果：把 cha

3、rs 賦為 t 的值。 strcopy (&t, s) 初始條件：串 s 存在。 操作結(jié)果：由串 s 復(fù)制得串 t。 destroystring (&s) 初始條件：串 s 存在。 操作結(jié)果：串 s 被銷(xiāo)毀。 strempty (s)初始條件：串s存在。操作結(jié)果：若 s 為空串，則返回 true， 否則返回 false。 表示空串，空串的長(zhǎng)度為零。 strcompare (s, t)初始條件：初始條件：串 s 和 t 存在。操作結(jié)果：操作結(jié)果：若s t，則返回值 0； 若s t，則返回值 0； 若s t，則返回值 0。例如：例如：strcompare(data, state)

4、0 strlength (s) 初始條件：串 s 存在。 操作結(jié)果：返回 s 的元素個(gè)數(shù)， 稱(chēng)為串的長(zhǎng)度。 concat (&t, s1, s2) 初始條件：串 s1 和 s2 存在。 操作結(jié)果：用 t 返回由 s1 和 s2 聯(lián)接而成的新串。例如例如： concate( t, man, kind) 求得 t = mankind substring (&sub, s, pos, len)初始條件：操作結(jié)果： 用 sub 返回串 s 的第 pos 個(gè)字符起 長(zhǎng)度為 len 的子串。串 s 存在，1posstrlength(s) 且 0lenstrlength(s)-pos+1。例

5、如：例如： substring( sub, commander , 4, 3)子串為子串為“串串”中的一個(gè)字符子序列中的一個(gè)字符子序列求得 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) = 起始位置和子串長(zhǎng)度之間存在約

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

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

8、s = chater ，t = rac ， 則執(zhí)行 strinsert(s, 4, t) 之后得到 s = character strdelete (&s, pos, len)初始條件：串s存在 1posstrlength(s)-len+1。操作結(jié)果：從串s中刪除第pos個(gè)字符 起長(zhǎng)度為len的子串。 clearstring (&s) 初始條件：串s存在。 操作結(jié)果：將s清為空串。 對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類(lèi)型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。 gets(str) 輸入一個(gè)串； puts(str) 輸出一個(gè)串； st

9、rcat(str1, str2) 串聯(lián)接函數(shù)； strcpy(str1, str2, k) 串復(fù)制函數(shù)； strcmp(str1, str2) 串比較函數(shù)； strlen(str) 求串長(zhǎng)函數(shù)；例如：c語(yǔ)言函數(shù)庫(kù)中提供下列串處理函數(shù)： 串賦值串賦值strassign、串復(fù)制、串復(fù)制strcopy、 串比較串比較strcompare、求串長(zhǎng)、求串長(zhǎng)strlength、 串聯(lián)接串聯(lián)接concat以及求子串以及求子串substring 等六種操作構(gòu)成串類(lèi)型的最小操作子集等六種操作構(gòu)成串類(lèi)型的最小操作子集。在上述抽象數(shù)據(jù)類(lèi)型定義的13種操作中，即：這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn)， 反之，其他串操作

10、（除串清除clearstring和串銷(xiāo)毀destroystring外）可在這個(gè)最小操作子 集上實(shí)現(xiàn)。 例如，可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(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個(gè)字符之后存在與 t相等的子串， / 則返回第一個(gè)這樣的子串在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; 串的邏輯結(jié)構(gòu)和線(xiàn)性表極為相似，區(qū)別區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。 串的基

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

14、har sstring maxstrlen + 1; / 0號(hào)單元存放串的長(zhǎng)度一、串的定長(zhǎng)順序存儲(chǔ)表示一、串的定長(zhǎng)順序存儲(chǔ)表示 按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為 “字符序列字符序列的復(fù)制的復(fù)制” 串串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱(chēng)之為“截截?cái)鄶唷?特點(diǎn)特點(diǎn): status concat(sstring s1, sstring s2, sstring &t) / 用t返回由s1和s2聯(lián)接而成的新串。若未截?cái)? 則返回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) / 未截?cái)?else if (s10 maxstrsize) / 截?cái)?else / 截?cái)?僅取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; / 若是非空串，則按串實(shí)用長(zhǎng)度分配 /存儲(chǔ)區(qū)，否則 ch 為null int length; / 串長(zhǎng)度 hstring;二、串的堆分配存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示 通常，c語(yǔ)言中提供的串類(lèi)型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc( ) 和 free( ) 進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱(chēng)串值共享的存儲(chǔ)空間為“堆堆”。 c語(yǔ)言中的串以一個(gè)空字符為結(jié)束符， 串長(zhǎng)是一個(gè)隱含值。 這類(lèi)串操作實(shí)現(xiàn)的算法為: 先為新生成的串分配一個(gè)存儲(chǔ)空間，然后 進(jìn)行串值的復(fù)制。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個(gè)字符起長(zhǎng)度為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 個(gè)字符之前插入串 t slen=s.length; tlen=t.length; / 取得s和t的串長(zhǎng) 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 串一、簡(jiǎn)單算法一、簡(jiǎn)單算法int index(sstring s, ss

21、tring t, int pos) / 返回子串t在主串s中第pos個(gè)字符之后的位置。若不存在，則函數(shù)值為0。 / 其中，t非空，1posstrlength(s)。 i = pos; j = 1; while (i = s0 & j t0) return i-t0; else return 0; / index 先比較模式串的第一個(gè)第一個(gè)字符， 再比較模式串的最后一個(gè)最后一個(gè)字符， 最后比較模式串中從第二個(gè) 到第 n-1 個(gè)字符。二、首首尾尾匹配算法匹配算法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; /重新查找匹配起始點(diǎn) 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; / 重新開(kāi)始下一次的匹配檢測(cè)kmp算法的時(shí)間復(fù)雜度可以達(dá)到o(m+n) 當(dāng) si tj 時(shí)， 已經(jīng)得到的結(jié)果: si-j+1.i-1 = t1.j-1 若已知 t1.k-1 = tj-k+1.j-1 則有 si-k+1.i-1 = t1.k-1三、三、kmp(kmp(d.e.knuth, v.r.pratt, j.h.morris) 算法算法定義：定義：模式串的next函數(shù)其它情況且時(shí)當(dāng) 1 pppppjk1 |maxk1j 0j1 - j1k- j1 -k21next int index_kmp(sstring s, sstring t, int pos)

24、 / 1posstrlength(s) i = pos; j = 1; while (i = s0 & j t0) return i-t0; / 匹配成功 else return 0; / index_kmp這實(shí)際上也是一個(gè)匹配的過(guò)程，不同在于：主串和模式串是同一個(gè)串 求 next 函數(shù)值的過(guò)程是一個(gè)遞推過(guò)程，分析如下:已知已知：next1 = 0；假設(shè)假設(shè)：nextj = k；又 tj = tk則則： nextj+1 = k+1若若： tj tk則則 需往前回朔，檢查 tj = t ？void get_next(sstring &t, int &next ) / 求模式串t的next函數(shù)值