1、第4章 串學習要點 掌握串的基本操作以及串操作在存儲結構下的實現。 理解串的模式匹配算法。4.1 串的基本概念 基本概念串：是由多個或零個字符組成的有限序列 ，記作 S = a1a2a3an (n=0)，其中 S是串名字，a1a2a3an是串值 ai是串中字符，n是串的長度，表示串中字符數目。空串：零個字符的串稱為空串，記作 “”。空格串：由一個或多個空格組成的串。子串：串中任意個連續的字符組成的子序列。主串：包含子串的串。子串在串中的位置：子串的第一個字符在主串中的位置。串相等：串長度相等，且對應位置上字符相等。1. 空串和空格串的不同，例如 和 分別表示長度為1的空格串和長度為0的空串。2

2、. 空串是任意串的子串，任意串是其自身的子串。3. 串的邏輯結構與線性表相似，區別在于串的數據對象約束為字符集，但基本操作和線性表有很大差別。線性表大多以“單個元素”作為操作對象，而串通常以“串的整體”作為操作對象。 4.1.1 串的特性和定義串賦值 StrAssign (&T, chars)：把 chars 賦為 T 的值。串復制 StrCopy (&T, S) ：由串 S 復制得串 T。串判空 StrEmpty (S)：若 S 為空串，則返回 true，否則 返回false。串比較 StrCompare (S, T)：若S T，則返回值 0；若 ST，則返回值 0；若S T，則返回值 0。

3、求串長 StrLength(S)：返回 S 的元素個數。串清除 ClearString (&S)：將S清為空串。串聯接 Concat (&T, S1, S2)：用 T 返回由 S1 和 S2聯 接而成的新串。 4.1.2 串的抽象數據類型 串的基本操作 求子串 SubString (&Sub, S, pos, len) ：用 Sub 返回串 S 的第 pos 個字符起長度為 len 的子串。 串定位 Index (S, T, pos)：若主串 S 中存在和串 T 值相同的串，則返回它在主串 S 中第pos個字符之后第一次出現的位置。 串替換 Replace (&S, T, V)：用 V 替換主

4、串 S 中出現的所有與（模式串）T相等的不重疊的子串。 串插入 StrInsert (&S, pos, T)：在串S的第pos個字符之前插入串T。 串刪除 StrDelete (&S, pos, len)：從串S中刪除第pos個字符起長度為len的子串。 串銷毀 DestroyString(&S)：串 S 被銷毀。 例子例1：StrCompare(data, state) 0。例2：Concat ( T, man, kind)； 求得 T = mankind。例3：SubString( sub, commander , 4, 3)； 求得 sub = man 。例4：假設 S = abcaab

5、caaabc , T = bca ； 則 Index(S, T, 1) = 2; Index(S, T, 3) = 6。例5：假設 S = abcaabcaaabca, T = bca ； V = bc , 則經Replace (S, T, V)置換后得到S = abcabcaabc。例6：S = chater ，T = rac ； 則執行 StrInsert(S, 4, T) 之后得到 S = character 。 基本思想 在主串S中取從第i（i的初值為pos）個字符起、長度和串T相等的子串和串T比較，若相等，則求得函數值為i，否則i值增1至串S中不存在和串T相等的子串為止。 S 串 T

6、 串 T 串iposn-m+1 求串的定位Index(S,T,pos)void StrInsert(String &S,int pos,String T) 在串S的第pos個字符前插入T n=StrLength(S); i=pos; if(i=1 & i=n) 判斷插入位置pos是否合法 SubString(sub1,S,1,i-1); SubString(sub2,S,i,n-i+1); Concat(sub3,sub1,T); Concat(S,sub3,sub2); 求串的定位Index(S,T,pos) 定長順序存儲表示 靜態分配 每個串預先分配一個固定長度的存儲區域 實際串長可在所分

7、配的固定長度區域內變動，超過予定義長度的串值則被舍去，稱之為“截斷” 用定長數組描述：#define MAXSIZE 100 字符串的最大存儲長度 typedef char StringMAXSIZE+1; 使用0號單元存儲長度 4.2 串的存儲結構及其運算Status Concat(SString S1, SString S2, SString &T) if (S10+S20 = MAXSTRLEN) / 未截斷 T1 . S10 = S11 . S10; TS10+1 . S10+S20 = S21 . S20; T0 = S10+S20; uncut = TRUE; else if (S

8、10 MAXSTRLEN) / 截斷 T1 . S10 = S11.S10; TS10+1 . MAXSTRLEN =S21 . MAXSTRLEN-S10; T0 = MAXSTRLEN; uncut = FALSE; else T0 . MAXSTRLEN = S10 . MAXSTRLEN; uncut = FALSE; return uncut; 4.2.1 串的靜態存儲及其實現Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合

9、法則告警 Sub1len=Spos pos+len-1; Sub0=len; return OK; 串的順序存儲的有關操作特點：1. 實現串的操作有原操作為“字符序列的復制”；2. 在操作中出現串值序列的長度超過上界時，約定用截尾法處理。 求子串函數SubString 以一組地址連續的存儲單元存放串值字符序列； 存儲空間動態分配，用malloc( )和free( )來管理。為每一個新產生的串分配一個存儲區，稱串值共享的存儲空間為“堆”。 堆分配存儲結構有順序順序存儲結構的特點，處理方便，且操作中對串長沒有限制。 串操作的實現：也是基于字符序列的復制。 用堆描述： typedef struct

10、char *ch; / 若非空串，按串長分配空間，否則 ch = NULL int length; /串長度 Hstring 4.2.2 串的動態存儲及其實現Status StrInsert ( HString &S, int pos, HString T ) if (posS.length+1) return ERROR; /pos不合法 if(T.length) /T不空，就需要重新分配S空間，以便插入T if (!（S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) exit(OVERFLOW); for ( i=S.le

11、ngth-1; i=pos-1; -i ) /為插入T而騰出pos之后的位置 S.chi+T.length = S.chi; /從S的pos位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入T S.length + = T.length; /刷新S串長度 return OK; /StrInsert 用“堆”實現串插入操作ABCDEF S.ch012345678重新分配空間，移動字符在S串的第5個字符之前插入字符串T。（S.length=6，T.lengh=3）T.chXYZ插入前012ABCDEF012345S.chposABCD

12、XY Z E FS.ch012345678插入后FE 串插入操作示意圖 串的鏈式存儲方式 結點大小：一個或多個字符 存儲密度=串值所占的存儲位 / 實際分配的存儲位 實際應用時，可以根據問題所需來設置結點的大小 串操作的實現：串值在鏈式存儲結構時操作的實現和線性表類似，對連接操作方便。ABCIheadheadABCDEFGHI# 4.2.3 串的鏈式存儲及其實現#define CHUNKSIZE 80 /可由用戶定義的塊大小typedef struct Chunk /首先定義結點類型 char ch CHUNKSIZE ; /結點中的數據域 struct Chunk * next ; /結點中

13、的指針域Chunk;typedef struct /其次定義用鏈式存儲的串類型 Chunk *head; /頭指針 Chunk *tail; /尾指針 int curLen; /結點個數 Lstring; 串的塊鏈存儲方式的描述 求子串位置的定位函數模式匹配：即子串定位運算（Index函數），即如何實現 Index(S,T,pos)函數，也就是在串中尋找子串（第一個字符）在串中的位置。 初始條件：串S和T存在，T是非空串，1posStrLength(s)操作結果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現的位置；否則函數值為0。注：S稱為被匹配的串（或稱主

14、串），T稱為模式串。若S包含串T，則稱“匹配成功”。否則稱 “匹配不成功” 。4.3 串的模式匹配算法1. 將主串的第pos個字符和模式的第1個字符比較： 若相等，繼續逐個比較后續字符； 若不等，從主串的下一字符（pos+1）起，重新與第一個字符比較。 2. 直到主串的一個連續子串字符序列與模式相等 。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值 0 。 注：該算法又稱為樸素的串匹配算法。4.3.1 樸素的模式匹配算法 匹配過程（已知S是主串，T是模式串，從pos=5的位置開始實現）：第1趟 S a b c d a b b a b a a b a b a b

15、 T a b a第2趟 S a b c d a b b a b a a b a b a b T a b a 第3趟 S a b c d a b b a b a a b a b a b T a b a第4趟 S a b c d a b b a b a a b a b a b T a b a 匹配過程Pos=5int Index(SString S，SString T，int pos) i=pos; j=1; while (i=S0 & jT0) return i-T0; else return 0; 指針i回溯語句i=i-j+2，可以這樣理解： 在本趟匹配中，有SiTj，但前面的字符都匹配， 即有Si-1=Tj-1，Si-2=Tj-2，Si-j+1=T1，因此，下一趟匹配時，i應從i-j+1的下一位置開始，即有i=i-j+1+1。 匹配算法 最好的情況時間復雜度為O(n+m