1、1數據結構課程的內容數據結構課程的內容2第第4章章 串（串（String）4.2 4.2 串的表示和實現串的表示和實現4.3 4.3 串的模式匹配算法串的模式匹配算法1. 定義定義2. 邏輯結構邏輯結構3. 存儲結構存儲結構4. 運算規(guī)則運算規(guī)則5. 實現方式實現方式4.1 4.1 串類型的定義串類型的定義3記為：記為： s = a1 , a2 , . , an (n0 ) 串名串名串值（用串值（用 括起來）括起來）串中字符個數（串中字符個數（n0n0）. n=0 . n=0 時稱為空串時稱為空串 。由一個或多個空格符組成的串。由一個或多個空格符組成的串。串串s s中任意個連續(xù)的字符序列叫中任

2、意個連續(xù)的字符序列叫s s的子串的子串; S; S叫叫主串主串。子串的第一個字符的序號。子串的第一個字符的序號。字符在串中的序號。字符在串中的序號。串長度相等，且對應位置上字符相等。串長度相等，且對應位置上字符相等。 串串即字符串，是由零個或多個字符組成的有限序列，是數據即字符串，是由零個或多個字符組成的有限序列，是數據元素為單個字符的特殊線性表。元素為單個字符的特殊線性表。4.1 4.1 串類型的定義串類型的定義若干術語：若干術語： 串長：串長： 空白串：空白串： 子串：子串：子串位置：子串位置：字符位置：字符位置： 串相等：串相等：隱含結束符隱含結束符/0 ，即即ASCII碼碼NUL4練練

3、1：串是由串是由 字符組成的序列，一般記字符組成的序列，一般記為為 。練練2：現有以下現有以下4個字符串：個字符串：a =BEI b =JING c = BEIJING d = BEI JING問：問： 他們各自的長度？他們各自的長度？ a是哪個串的子串？在主串中的位置是多少？是哪個串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1練練3：空串和空白串有無區(qū)別？空串和空白串有無區(qū)別？答：答：有區(qū)別。空串有區(qū)別。空串(Null String)(Null String)是指長度為零的串；而空白是指長度為零的串；

4、而空白串串(Blank String),(Blank String),是指包含一個或多個空白字符是指包含一個或多個空白字符 ( (空空格鍵格鍵) )的字符串的字符串. .0個或多個個或多個S=a1a2an5ADT StringObjects: D=ai | aiCharacterSet, i=1, 2,，n, n0Relations: R1= | ai-1,ai D, i=2, ，nfunctions: / 有有1313種之多種之多StrAssign(&T, chars) / 串賦值，生成值為串賦值，生成值為charschars的串的串T TStrCompare(S,T) / 串比較，若串比較

5、，若STST，返回值大于，返回值大于0 0 StrLength(S) / 求串長，即返回求串長，即返回S S的元素個數的元素個數 Concat(&T, S1, S2) / 串連接，用串連接，用T T返回返回S1S1S2S2的新串的新串SubString(&Sub, S, pos, len) / 求求S S中中pospos起長度為起長度為lenlen的子串的子串Index(S, T, pos) / 返回子串返回子串T T在在pospos之后的位置之后的位置 Replace(&S, T,V) / 用子串用子串V V替換子串替換子串T TADT String串的抽象數據類型定義（串的抽象數據類型定義

6、（參見教材參見教材P71）最最小小操操作作子子集集6 設設 s =I AM A STUDENT, t =GOOD, q=WORKER。求：。求：練習：練習： StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A)= Index(s, t)=Replace(s, STUDENT,q)=144STUDENTO30 （ s中沒有中沒有t！）！）I AM A WORKER再問：再問：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？ 見本章自測題，或

7、見嚴題集見本章自測題，或見嚴題集4.3 74.2串的表示和實現串的表示和實現 定長順序存儲表示定長順序存儲表示用一組地址連續(xù)的存儲單元存儲串值的字用一組地址連續(xù)的存儲單元存儲串值的字符序列符序列 堆分配存儲表示堆分配存儲表示用一組地址連續(xù)的存儲單元存儲串值的字用一組地址連續(xù)的存儲單元存儲串值的字符序列符序列, ,但存儲空間是在程序執(zhí)行過程中動態(tài)但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。分配而得。 串的塊鏈存儲表示串的塊鏈存儲表示鏈式方式存儲鏈式方式存儲串有三種機內表示方法：串有三種機內表示方法：順序順序存儲存儲鏈式鏈式存儲存儲 A B C I NULLhead8定長順序存儲特點：定長順序存儲特

8、點：用一組連續(xù)的存儲單元來存放串，用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數組來定義，數組的直接使用定長的字符數組來定義，數組的上界預先給出上界預先給出，故稱為靜態(tài)存儲分配。故稱為靜態(tài)存儲分配。例如：例如：#define Maxstrlen 255 /用戶可用的最大串長用戶可用的最大串長 typedef unsigned char SString Maxstrlen1 ; SString s; /s是一個可容納是一個可容納255個字符的順序串。個字符的順序串。注：注：一般用一般用SString0來存放串長信息；來存放串長信息；C語言約定在串尾加結束符語言約定在串尾加結束符 0，以利操作

9、加速，但不計入串長；，以利操作加速，但不計入串長；若字符串超過若字符串超過Maxstrlen 則自動截斷（因為靜態(tài)數組存不則自動截斷（因為靜態(tài)數組存不 進去）。進去）。 討論：討論：想存放想存放超長超長字符串怎么辦？字符串怎么辦？靜態(tài)數組有缺陷！靜態(tài)數組有缺陷！實現方式：實現方式：參見教材參見教材P73編程兩例，兩串連接和編程兩例，兩串連接和求子串求子串改用改用動態(tài)動態(tài)分配的一維數組分配的一維數組“堆堆”！9例：例：順序存儲方式下獲得子串的函數順序存儲方式下獲得子串的函數SubString(&Sub, S, pos, len) Status SubString(SString &Sub, SS

10、tring S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合法則告警不合法則告警 Sub1.len=Spos.pos+len-1; Sub0=len; return OK;P74P74將串將串S S中從第中從第pospos個字符開始長度為個字符開始長度為lenlen的字符序的字符序列復制到串列復制到串SubSub中中（注：串（注：串SubSub的預留長度與的預留長度與S S一樣）一樣）S = a1 , a2 , . , ann串長串長poslen10思路：思路：利用利用mallocmalloc函數合理預設串長空

11、間。函數合理預設串長空間。特點：特點： 若在操作中串值改變，還可以利用若在操作中串值改變，還可以利用reallocrealloc函數按新串函數按新串長度長度增加增加( (堆砌堆砌) )空間。空間。typedef struct char *ch; / 若非空串,按串長分配空間; 否則 ch = NULLint length; /串長度HString堆分配存儲特點：堆分配存儲特點：仍用一組連續(xù)的存儲單元來存放串，仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。約定：約定：所有按堆存儲的串，其關鍵信息放置在：所有按堆存儲的串，其關鍵

12、信息放置在：11Status StrInsert ( HString &S, int pos, HString T ) /在串在串S的第的第pos個字符之前（包括尾部）插入串個字符之前（包括尾部）插入串Tif (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

13、=S.length-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，略，略/0 S.length + = T.length; /刷新刷新S串長度串長度return OK;/StrInsert例：例：用用“堆堆”實現串插入操作實現串插入操作(教材教材P75) 121 Status StrAssign(HString &T, char *chars)2

14、 if (T.ch) free(T.ch);3 for (i=0, c=chars; c; +i, +c); /求串長度求串長度i4 if (!i) T.ch = NULL; T.length = 0; /串長串長i為為0，即空串，即空串5 else6 if (!(T.ch = (char*)malloc(i*sizeof(char)7 exit(OVERFLOW);8 T.ch0.i-1 = chars0.i-1;9 T.length =i;10 11 return OK;/StrAssign指針變量指針變量c也可以自增！也可以自增！意即每次后移一個數據意即每次后移一個數據單元。單元。附：堆

15、分配存儲表示附：堆分配存儲表示直到終值為直到終值為“假假”停止，串尾特征是停止，串尾特征是/0NULL=013討論：討論：法法1 1存儲密度為存儲密度為 ；法；法2 2存儲密度為存儲密度為 ；顯然，若顯然，若數據元素很多，用法數據元素很多，用法2 2存儲更優(yōu)存儲更優(yōu)稱為稱為塊鏈結構塊鏈結構鏈式存儲特點鏈式存儲特點 ：用鏈表存儲串值，易插入和刪除。用鏈表存儲串值，易插入和刪除。法法1 1：鏈表結點（數據域）大小取鏈表結點（數據域）大小取1 1法法2 2：鏈表結點（數據域）大小取鏈表結點（數據域）大小取n(n(例如例如n=4)n=4)9/189/189/15=3/59/15=3/5 A B C I

16、 NULLheadheadA B C D E F G H I # # # NULL14#define CHUNKSIZE 80 /可由用戶定義的塊大小可由用戶定義的塊大小typedef struct Chunk /首先定義結點類型首先定義結點類型 char ch CHUNKSIZE ; /結點中的數據域結點中的數據域 struct Chunk * next ; /結點中的指針域結點中的指針域Chunk; 塊鏈類型定義：塊鏈類型定義：typedef struct /其次定義用鏈式存儲的串類型其次定義用鏈式存儲的串類型 Chunk *head; /頭指針頭指針 Chunk *tail; /尾指針尾

17、指針 int curLen; /結點個數結點個數 Lstring; /串類型只用一次，前面可以不加串類型只用一次，前面可以不加Lstring15再次強調：再次強調：串與線性表的運算有所不同，是以串與線性表的運算有所不同，是以“串的整體串的整體”作作為操作對象，例如查找某子串，在主串某位置上插入一個子串為操作對象，例如查找某子串，在主串某位置上插入一個子串等。等。算法目的：算法目的：確定主串中所含子串第一次出現的位置確定主串中所含子串第一次出現的位置（定位定位） 即如何實現即如何實現 Index(S,T,pos)函數函數（見教材（見教材P79）4.3 串的模式匹配算法串的模式匹配算法模式匹配模式

18、匹配(Pattern Matching) (Pattern Matching) 即即子串定位運算子串定位運算。初始條件：初始條件：串串S S和和T T存在，存在，T T是非空串，是非空串，1posStrLength(s)1posStrLength(s)操作結果：操作結果：若主串若主串S S中存在和串中存在和串T T值相同的子串，則返回它在主值相同的子串，則返回它在主串串S S中第中第pospos個字符之后個字符之后第一次第一次出現的位置；否則函數值為出現的位置；否則函數值為0 0。注：注：S S稱為稱為被匹配的串被匹配的串，T T稱為稱為模式串模式串。若。若S S包含串包含串T T，則稱，則稱

19、“匹配成功匹配成功”。否則稱。否則稱 “匹配不成功匹配不成功” 。S=a b a b c a b c a c b a bT=T=a b c a cpos=516 BF算法設計思想算法設計思想（見教材（見教材P79） 將主串的第將主串的第pospos個字符和模式的第個字符和模式的第1 1個字符比較，個字符比較， 若若相等相等，繼續(xù)逐個比較后續(xù)字符；，繼續(xù)逐個比較后續(xù)字符； 若若不等不等，從主串的下一字符（，從主串的下一字符（pos+1pos+1）起，重新與第一個）起，重新與第一個字符比較。字符比較。 BF算法算法 （又稱古典或經典的、樸素的、窮舉的）（又稱古典或經典的、樸素的、窮舉的） KMP算

20、法算法（特點：速度快）（特點：速度快）算法算法種類：種類： 直到主串的一個連續(xù)子串字符序列與模式相等直到主串的一個連續(xù)子串字符序列與模式相等 。返回值。返回值為為S S中與中與T T匹配的子序列匹配的子序列第一個字符的序號第一個字符的序號，即匹配成功。，即匹配成功。否則，匹配失敗，返回值否則，匹配失敗，返回值 0 .0 .返回5S=a b a b c a b c a c b a bT=T=a b c a cIndex(S, T, 1)171 int Index(SString S, SString T, int pos) 2 i=pos; j=1;3 while ( i=S0 & jT0) r

21、eturn i-T0; /子串結束，說明匹配成功子串結束，說明匹配成功8 else return 0;9 /Index BFBF算法的實現算法的實現即即Index（）操作的實現（）操作的實現 （見教材（見教材P79） 0號單元存放串的長度，號單元存放串的長度，P73匹配成功時匹配成功時i指向的與子串最后一個字符相等的字指向的與子串最后一個字符相等的字符符18BF算法：算法：int Index(S, T,1)i=1;j=1;while(i=s0 &jT0) return i-T0; else return 0;BFBF算法在最壞的情況下需要比較字算法在最壞的情況下需要比較字符的總次數為符的總次數

22、為(n-m+1)*mO(n*m)最糟糕的情況：最糟糕的情況：主串前面主串前面n-mn-m個位置個位置都都部分匹配部分匹配到子串的最后一位，即到子串的最后一位，即這這n-mn-m位比較了位比較了m m次，別忘了最后次，別忘了最后m m位位也各比較了一次，還要加上也各比較了一次，還要加上m m！BFBF算法的最壞時間復雜度算法的最壞時間復雜度但一般情況下但一般情況下BFBF算法的時間復算法的時間復雜度為雜度為O(n+m)BF算法的效率分析討論：討論：令令n n為主串長度，為主串長度，m m為子串長為子串長度。匹配最糟糕的情況是什么？度。匹配最糟糕的情況是什么？19KMP算法算法（特點：速度快）（特

23、點：速度快） KMPKMP算法設計思想算法設計思想 KMP算法的推導過程算法的推導過程 KMPKMP算法的實現算法的實現 （關鍵技術（關鍵技術: :計算計算nextjnextj） KMPKMP算法的算法的時間復雜度時間復雜度D. E. Knuth, V. R. Pratt, J. H. Morris20能否利用已經能否利用已經部分匹配部分匹配的結果而加快模式串的滑動速度？的結果而加快模式串的滑動速度？能！能！而且主串而且主串S S的指針的指針i i不必回溯不必回溯！可提速到！可提速到O(n+m)O(n+m)！例：例： KMP KMP算法設計思想：算法設計思想： ( (參見教材參見教材P80-8

24、4P80-84）S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值應為的返回值應為i=6i=6需要討論兩個問題：需要討論兩個問題： 如何如何“記憶記憶”部分匹配結果？部分匹配結果？ 如何由如何由“記憶記憶”結果計算出主串結果計算出主串S S第第i i個字符應該與模式個字符應該與模式T T中中哪個字符再比較？即確定模式哪個字符再比較？即確定模式T T中的新比較起點中

25、的新比較起點k k. .i ii ii ik kk k a b aa b c演示程序演示程序21第一步，先第一步，先把模式把模式T所有可能的失配點所有可能的失配點j所對應的所對應的nextj計算出來計算出來；第二步：執(zhí)行定位函數第二步：執(zhí)行定位函數Index_KMP （與（與BF算法模塊非常相似）算法模塊非常相似） KMPKMP算法的實現算法的實現即即Index( )操作的實現操作的實現 （見教材（見教材P82） 1 int Index_KMP(SString S, SString T, int pos) 2 i=pos; j=1;3 while ( i=S0 & jT0) return i-

26、T0; /子串結束，說明匹配成功子串結束，說明匹配成功8 else return 0;9 /Index_KMP22 KMP算法的推導過程：算法的推導過程：（見教材（見教材P81）抓住部分匹配結果的兩個特征：抓住部分匹配結果的兩個特征：兩式聯(lián)立可得：兩式聯(lián)立可得：T1Tk-1=Tj-(k-1)j-(k-1) Tj-1注意：注意：j 為當前已知的失配位置，我們的目標是計算新起點為當前已知的失配位置，我們的目標是計算新起點 k，僅剩一個未知數僅剩一個未知數k，理論上已可解，且，理論上已可解，且k僅與模式串僅與模式串T有關！有關！ 則則S S的的i-(k-1)i-(k-1)i-1i-1位位T T的的j

27、-(k-1)j-(k-1)j-1j-1位位 即即(4-3(4-3）式含義）式含義S=a b a b c a b c a c b a bT=T=a b c a ci ik k則則T T的的1 1k-1k-1位位S S的的i-(k-1)i-(k-1)i-1i-1位位 即即(4-2(4-2）式含義）式含義i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c剛才肯定是在剛才肯定是在S的的i處和處和T的第的第j字符字符 處失配處失配設目前應與設目前應與T的第的第k字符開始比較字符開始比較23 KMP算法的推導過程算法的推導過程(續(xù)）續(xù)）：根據模式串根據模式串

28、T的規(guī)律：的規(guī)律： T1Tk-1=Tj-(k-1)j-(k-1) Tj-1和已知的當前失配位置和已知的當前失配位置j ，可以歸納出計算新起點，可以歸納出計算新起點 k的表達式。的表達式。令令k = next j ，則則next j 0 當當j1時時max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情況其他情況討論：討論： next j 有何意義？有何意義？ 一旦失配，應從模式串一旦失配，應從模式串T中第中第next j 個字符開始與個字符開始與S的失配的失配點點i 重新匹配重新匹配! next j 怎么求？怎么求？ 后面會舉例后面會舉例（參見教材（參見教

29、材P81）例：例： 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位 nextj :next j 0 當當j1時時max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情況其他情況0 1 1 2 2 3 1 2討論：討論：j=1時時, next j 0；因為屬于因為屬于“j=1”;j=2時時, next j 1；因為屬于因為屬于“其他情況其他情況”；剛才已歸納：剛才已歸納：j=3時時, k=2，只需查看，只需查看T1=T2 2。因不等，故。因不等，故“其他情其他情況況”；j=4

30、時時, k=2，3，要查看，要查看T1=T3 3 和和T1T2=T2 2 T3 3 j=5時時, k=2，3，4，要查看，要查看T1=T4 4 、T1T2=T3 3T4 和和 T1T2T3 3=T2 2T3 3T4以此類推，可得后續(xù)以此類推，可得后續(xù)nextj值。值。25討論：討論： next j 有何物理意義？有何物理意義？nextjnextj函數表征著模式中兩段字符之間相匹配的最大子函數表征著模式中兩段字符之間相匹配的最大子串的長度（除串本身外）。串的長度（除串本身外）。可見，模式中可見，模式中相似部分越多，則相似部分越多，則nextjnextj函數越大函數越大，它既，它既表示表示模式模式

31、T字符之間的相關度越高，也表示字符之間的相關度越高，也表示j j位置以前與主串位置以前與主串部部分匹配分匹配的字符數越多。的字符數越多。即：即：nextjnextj越大，模式串向右滑動得越遠，與主串進行越大，模式串向右滑動得越遠，與主串進行比較的次數越少，時間復雜度就越低。比較的次數越少，時間復雜度就越低。next j max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 模式串從首位往右模式串從首位往右直到直到k-1k-1位位模式串從模式串從j j的前一位的前一位往左直到往左直到j-(k-1)j-(k-1)位位想一想：如果主串和模式均為二進制碼流，用想一想：如果主

32、串和模式均為二進制碼流，用KMPKMP算法算法效果如何？效果如何？26next函數的改進算法函數的改進算法前面定義的前面定義的next函數在某些情況下還是有缺陷函數在某些情況下還是有缺陷例如：模式例如：模式aaaab與主串與主串aaabaaaab匹配情況：匹配情況：模式：模式： a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a ba a a a ba a a a ba a a a bnextvalj=nextvalk nextj=k且Tj=Tkn

33、extj其他nextvalj： 0 0 0 0 427討論兩個有關討論兩個有關next j 的問題：的問題： 怎樣簡捷計算怎樣簡捷計算nextj？ 可用遞推法編程實現！可用遞推法編程實現！（參見（參見P83簡捷算法）簡捷算法）計算計算nextj的時間為的時間為O(m)1 void get_next(SString T, int &next )2 /next函數值存入數組函數值存入數組next3 i=1; next1=0; j=0; /j是重復子串長是重復子串長4 while(iT0 )5 if(j= = 0|Ti= =Tj)+i;+j;nexti=j;6 else j=nextj;7 8/ g

34、et_next1 void get_nextval(SString T, int &nextval )2 /next函數修正值存入數組函數修正值存入數組nextval3 i=1; nextval1=0; j=0;4 while(iT0 )5 if(j= = 0|Ti= =Tj ) +i;+j;6 if(Ti!=Tj) nextvali=j;7 else nextvali=nextvalj; 8 else j=nextvalj; 9/ get_nextval next j 是否完美無缺？是否完美無缺？答：未必，例如當答：未必，例如當S=a b a a a a b,T=a a a a b時時仍有多余動作仍有多余動作（參見（參見P84改進算法改進算法, 稱為稱為nextval j ）28 KMPKMP算法的算法的時間復雜度時間復雜度 因為計算因為計算nextj的時間為的時間為O(m);且且Index_KMP函數（函數（沒有回