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

1、4. 4. 串串2 4.1 4.1 串類型的定義串類型的定義3串的抽象數(shù)據(jù)類型的定義如下：串的抽象數(shù)據(jù)類型的定義如下：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 4StrAssign (&T, chars) 初始條件：chars 是字符串常量。 操作結(jié)果：把 chars 賦為 T 的值?；静僮骰静僮鱏trCopy (&T, S) 初始條

2、件：串 S 存在。 操作結(jié)果：由串 S 復(fù)制得串 T。5 DestroyString (&S) 初始條件：串 S 存在。 操作結(jié)果：串 S 被銷毀?；静僮骰静僮鱏trEmpty (S)初始條件：串S存在。操作結(jié)果：若 S 為空串，則返回TRUE， 否則返回 FALSE。 表示空串，空串的長(zhǎng)度為零。 ClearString (&S) 初始條件：串S存在。 操作結(jié)果：將S清為空串。6StrCompare (S, T)初始條件：串S 和 T 存在。操作結(jié)果：若S T，則返回值 0； 若S T，則返回值 0； 若S T，則返回值 0。例如：例如：StrCompare(data, s

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

4、個(gè)字符起 長(zhǎng)度為 len 的子串。8例如： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9)求得 sub = commander；子串為子串為“串串” 中的一個(gè)字符子序列中的一個(gè)字符子序列基本操作基本操作SubString(sub, commander, 4, 7) sub = ? SubString(student, 5, 0) = 起始位置和子串長(zhǎng)度之間存在約束關(guān)系長(zhǎng)度為 0 的子串為“合法”串9Index (S, T, pos)初始條件：串S和T存在，T是非空串， 1posSt

5、rLength(S)。操作結(jié)果： 若主串 S 中存在和串 T 值相同的子串, 則返回它在主串 S 中第pos個(gè)字符之后第一次出現(xiàn)的位置； 否則函數(shù)值為0。 基本操作基本操作 “子串在主串中的位置子串在主串中的位置”意指子串意指子串中的第一個(gè)字符在主串中的位序。中的第一個(gè)字符在主串中的位序。假設(shè) S = abcaabcaaabc, T = bca Index(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0；10 Replace (&S, T, V) 初始條件：串S, T和 V 均已存在，且 T 是非空串。 操作結(jié)果：用V替換主串S中出

6、現(xiàn) 的所有與（模式串）T相等的不重疊的子串?；静僮骰静僮骼纾杭僭O(shè) S = abcaabcaaabca，T = bca若 V = x， 則經(jīng)置換后得到 S = axaxaax若 V = bc， 則經(jīng)置換后得到 S = abcabcaabc11 StrInsert (&S, pos, T)初始條件：串S和T存在，1posStrLength(S)1。操作結(jié)果：在串S的第pos個(gè)字符之前插入串T。例如：S = chater，T = rac， 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = character基本操作基本操作 StrDelete (&S, pos, l

7、en)初始條件：串S存在 1posStrLength(S)-len+1。操作結(jié)果：從串S中刪除第pos個(gè)字符 起長(zhǎng)度為len的子串。 12對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。 gets(str) 輸入一個(gè)串； puts(str) 輸出一個(gè)串； strcat(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ù)：13在上述抽象數(shù)據(jù)類型定義的1

8、3種操作中， 串賦值串賦值StrAssign、串復(fù)制、串復(fù)制Strcopy、 串比較串比較StrCompare、求串長(zhǎng)、求串長(zhǎng)StrLength、 串聯(lián)接串聯(lián)接Concat以及求子串以及求子串SubString 等六種操作構(gòu)成串類型的最小操作子集等六種操作構(gòu)成串類型的最小操作子集。 即：這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn)， 反之，其他串操作（除串清除ClearString和串 銷毀DestroyString外）可在這個(gè)最小操作子 集上實(shí)現(xiàn)。14 例如，可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。 StrCompare(SubString(S, i, StrLen

9、gth(T),T ) ? 0 S 串 T 串 T 串iposn-m+1算法的基本思想為：算法的基本思想為：15int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個(gè)字符之后存在與 T相等的子串，則返回第一個(gè)這樣的子串在S中的位置，否則返回0 if (pos 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

10、; / while / if return 0; / S中不存在與T相等的子串 / Index算法描述算法描述16串的置換函數(shù)串的置換函數(shù)： S 串 T 串 V 串 V 串pospos subinews 串sub17 串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。 串的基本操作和線性表有很大差別。串的基本操作和線性表有很大差別。 在線性表的基本操作中，大多以大多以“單個(gè)元素單個(gè)元素”作為作為操作對(duì)象操作對(duì)象； 在串的基本操作中，通常以通常以“串的整體串的整體”作為操作作為操作對(duì)象對(duì)象。184.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)19 #define MAXSTRLEN 25

11、5 / 用戶可在255以內(nèi)定義最大串長(zhǎng) typedef unsigned char SstringMAXSTRLEN + 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)度的串值則被舍去，稱之為“截?cái)嘟財(cái)唷?。20 Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2聯(lián)接而成的新串。若未截?cái)? 則返回TRUE，否則FALSE。 return un

12、cut; / Concat串的聯(lián)接算法中需分三種情況處理：串的聯(lián)接算法中需分三種情況處理： 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.MAX

13、STRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; 21 typedef struct char *ch; / 若是非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū)， / 否則ch為NULL int length; / 串長(zhǎng)度 HString;串的堆分配存儲(chǔ)表示串的堆分配存儲(chǔ)表示 這類串操作實(shí)現(xiàn)的算法為： 先為新生成的串分配一個(gè)存儲(chǔ)空間，然后 進(jìn)行串值的復(fù)制。22Status Concat(HString &T, HString S1, HString S2) / 用T返回由S1和S2聯(lián)接而成的新串 if (T.ch) free(T.ch); / 釋放舊空間 if (

14、!(T.ch = (char *) malloc(S1.length+S2.length)*sizeof(char) 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串的聯(lián)接串的聯(lián)接23 Status SubString(HString &Sub, HString S，int pos, int len) / 用Sub返回串S

15、的第pos個(gè)字符起長(zhǎng)度為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 Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; / 完整子串 return OK; / SubString24串的塊鏈存儲(chǔ)表示串的塊鏈存儲(chǔ)表示

16、也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有 8 位二進(jìn)制數(shù)，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串。存儲(chǔ)密度存儲(chǔ)密度 = 數(shù)據(jù)元素所占存儲(chǔ)位實(shí)際分配的存儲(chǔ)位25 #define CHUNKSIZE 80 / 可由用戶定義的塊大小 typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長(zhǎng)度 LString;264.34.3串的

17、模式匹配算法串的模式匹配算法27初始條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結(jié)果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos個(gè)字符之后第一次出 現(xiàn)的位置；否則函數(shù) 值為0。 首先，回憶一下串匹配(查找)的定義:INDEX (S, T, pos)28 下面討論以定長(zhǎng)順序結(jié)構(gòu)表示串時(shí)的幾種算法。一、簡(jiǎn)單算法一、簡(jiǎn)單算法二、首尾匹配算法二、首尾匹配算法三、三、KMP(KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法算法29int Index(SString S, SString T, int pos) / 返回子串返回

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

19、S0; tLength = 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; / 檢查中間字符的匹配情況檢查中間字符的匹配情況32 k = 1; j = 2; while ( j tLength & Si+k = Tj) +k; +j; if (

20、j = tLength ) return i; else +i; / 重新開(kāi)始下一次的匹配檢測(cè)33KMP算法的時(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-1KMP(KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法算法34定義：定義：模式串的nextnext函數(shù)其它情況且時(shí)當(dāng) 1 pppppjk1|Maxk1j 0j1- j1k- j1-k21next35 int Index_KMP(SString S, S

21、String T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i = S0 & j T0) return i-T0; / 匹配成功 else return 0; / Index_KMP36這實(shí)際上也是一個(gè)匹配的過(guò)程，不同在于：主串和模式串是同一個(gè)串求next函數(shù)值的過(guò)程是一個(gè)遞推過(guò)程，分析如下:已知：next1 = 0；假設(shè)：nextj = k；又 Tj = Tk則： nextj+1 = k+1若： Tj Tk則需往前回朔，檢查 Tj = T ？37 void get_next(SString &T, int &

22、;next ) / 求模式串T的next函數(shù)值并存入數(shù)組next i = 1; next1 = 0; j = 0; while (i T0) if (j = 0 | Ti = Tj) +i; +j; nexti = j; else j = nextj; / get_next38還有一種特殊情況需要考慮：例如： S = aaabaaabaaabaaabaaab T = aaaabnextvalj=00004nextj=0123439 void get_nextval(SString &T, int &nextval) i = 1; nextval1 = 0; j = 0; whi

23、le (i T0) if (j = 0 | Ti = Tj) +i; +j; if (Ti != Tj) nextvali = j; else nextvali = nextvalj; else j = nextvalj; / get_nextval40習(xí)題F用無(wú)回溯的模式匹配法（KMP法）及快速的無(wú)回溯的模式匹配法求模式串T的nextj值，添入下面表中：j1 2 3 4 5 6 7ta a b b a a bkmp法求得的nextj值0 1 2 1 1 2 3 快速無(wú)回溯法求得的nextj值0 0 2 1 0 0 2 j1 2 3 4 5 6 7ta a b b a a bkmp法求得的nextj值 快速無(wú)回溯法求得的nextj值 41習(xí)題F輸入一個(gè)字符串，內(nèi)有數(shù)字和非數(shù)字字符，如：ak123x456 17960?302gef4563，將其中連續(xù)的數(shù)字作為一個(gè)整體，依次存放到一數(shù)組中，例如123放入,456放入，。編程統(tǒng)計(jì)其共有多少個(gè)整數(shù)，并輸出這些數(shù)。F以順序存儲(chǔ)結(jié)構(gòu)表示串，設(shè)計(jì)算法。求串S中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串及其位置并分析算