1、 基本概念 串的存儲結構 串的基本操作 串的模式匹配第四章 串4.1 串的定義和基本操作串定義：是字符串的簡稱，是由零個或多個字符組成的有限序列。一般記為： S=a1a2an （n0） 其中：S是串名；用雙引號（“”）括起的字符序列是串的值；ai（1in）可以是字母、數字或其它符； n是串中字符的個數, 稱為串的長度。 空串與空格串 長度為零（n0）的串稱為空串（Null String），它不包含任何字符。由空格字符組成的串，稱為空格串（Blank String）。它的長度為串中空格字符的個數。 子串與主串 串中任意個連續字符組成的子序列稱為該串的子串。包含子串的串稱為該子串的主串。例如：串A

2、=“China Beijing”, B=“Beijing”, 則它們的長度分別為13、7。B在A中的位置是7。子串的位置 以子串的第一個字符在主串中的位置來表示。 串的比較 當且僅當兩個串的長度相等，并且各個對應位置的字符也都相同，稱兩個串相等； 當兩個串不相等時，可按“字典順序”區分大小(在C語言中，按字符ASCII碼的大小為準)。例如，有下列四個串s1，s2，s3，s4： s1= “pro”， s2= Program s3= program ，s4= program 以上四個串彼此互不相等，且s4s3s1s2。 串變量：其取值是可以改變的，它必須用名字來識別； 串常量：和整常數、實常數一樣

3、，具有固定的值，在程序中只能被引用但不能改變其值，即只能讀不能寫。 串變量與串常量例如，在C語言中，有下列語句： char x=456; /*x是一個串變量名，它的值為字符序列456，而不是整數456*/ char string1=string; /*string1是一個串變量名，字符序列string是賦給它的值*/求串長Strlen(s) ：求串s的長度，Strlen(s)的值是一個非負整數。若s是一個空串，則Strlen(s)=0串賦值StringAssign(s,string_constant) ：給串s賦值。其中string_constant可為串變量、串常量或經過適當運算所得到的串值

4、。 串復制Strcpy(s,t)：由串s復制得到串t。串聯接Strcat(s,t)：將串t聯接到串s的末尾形成新串s。 串比較Strcmp(s,t)：比較s和t的大小，若st，則返回值小于0；若st，則返回值大于0；若s=t，則返回值為0 。 串的基本操作 求子串Substr(s,pos,len,sub)：從串s中的第pos個字符開始取長度為len的子串構成串sub。 子串的定位Index(s,t)：在串s中尋找串t第一次出現時，串t首字符在串s中的位置。若找到，則返回該位置，否則返回0。 串插入StrInsert(s,pos,t)：將串t插入在串s的位置pos上。串刪除StrDelete(s

5、,pos,len)：從串s中位置pos開始，刪除len個字符。子串替換操作Replace(s,t,v)：將串s中的子串t全部替換成串v。4.2 串的表示和實現 串的定長順序存儲 串的順序存儲結構，簡稱為順序串。用一組地址連續的存儲單元來依次存放串中的字符序列，串中相鄰的字符順序存放在相鄰的存儲單元中。所謂定長，指按照預先定義的大小為每一個串分配一個固定的存儲區域。 通常有下列兩種實現方式： 第一種使用定長的字符數組存放串，一般使用一個不會在串中出現的特殊字符（如0）放在串值的末尾（不記入串長）來表示串的結束。類型定義如下:#define MaxStrSize 256 /*串可能的最大長度*/

6、typedef char SeqStringMaxStrSize; /*SeqString是順序串類型*/SeqString S; /*S是一個順序串變量*/ 這種存儲方法不能直接得到串的長度，而是判斷字符是否為0來確定串是否結束，串長是隱含的。所以串空間最大值為MaxStrSize時，最多只能放MaxStrSize-1個字符。 第二種不使用終結符,用一個整數length來指示串的實際長度，length-1表示串中最后一個字符的存儲位置。 類型定義如下： #define MaxStrSize 256 /*串可能的最大長度*/ typedef struct char chMaxStrSize;

7、int length; /*指示串的當前長度*/ SeqString; /*SeqString是順序串類型*/ 在這種方式中,字符串的串值由ch0開始存放。當然，也可以將串的實際長度存儲在0號單元中，實際串值從1號單元處開始存放。實際應用中究竟采用哪種結構，需要根據情況進行權衡。在C語言中是采用字符0作為串的終結符的方式。串的數據類型說明采用如下形式：#define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SeqString; /*使用時可不用0作為結束標志*/順序串的基本操作的實現int Strlen(SeqS

8、tring s) /*s是結構體類型*/ return(s.length); 求串長Strlen(s) ：返回串s的元素個數。SeqString *Strcpy(SeqString s，SeqString *t) int i; for(i=0;is.length;i+) tchi=s.chi; tlength=s.length; /*置串t的長度*/ return(t); 串復制Strcpy(s,t)：將串s復制到串t中。將串t聯接到串s的末尾形成新串s。若t完全聯接到s的末尾，表示聯接成功則返回1，否則不成功返回0。串聯接Strcat(s,t)：int Strcat(SeqString s,

9、 SeqString t) int i; if(s.length+t.length=MaxStrSize) /*可不用0作為結束標志*/ /*判斷串s和t的長度之和是否超過串的最大長度*/ for(i=0;it.length;i+) /*串t聯接到串s之后*/ s.chi+s.length=t.chi; s.length=s.length+t.length; /*置串s的實際長度*/ return(1); else /*只把t串的前半部分聯接到串s后，使s達到長度為MaxStrSize */ for(i=0;iMaxStrSize-s.length;i+) s.chi+s.length=t.c

10、hi; s.length=MaxStrSize /*置串s的實際長度,無0作為結束標志*/ return(0); SeqString *Substr(SeqString s,int pos,int len, SeqString *sub) int i; if(pos= s.length|len s.length-pos+1) /*判斷pos和len的合法性*/ printf(parameter error!); return NULL; for(i=0;i len;i+) subchi=s.chpos+i-1; /*向子串sub復制字符*/ sublength=len; /*置串sub的長度*

11、/ return(sub); 求子串Substr(s,pos,len,sub)：從串s中的第pos個字符開始取長度為len的子串sub，并返回串sub。SeqString *StrDelete(SeqString *s, int pos, int len) int i; if(pos= slength|len= slength) /*判斷pos和len的合法性*/ printf(parameter error!); return NULL; for(i=pos+len-1;ich= (char *)malloc(s.length+t.length) return(0); /*分配空間失敗*/

12、for(i=0;ichi=s.chi; /*將串s復制到新串new中*/ for(i=0;ichs.length+i=t.chi; /*依次復制串t中字符到新串new中串s之后*/ new-length=s.length+t.length; /*新串new的實際長度*/ return(new); 兩次申請空間 串插入：將串t插入在串s的位置pos處，并返回串sHstring *StrInsert(Hstring *s, int pos, Hstring *t) char *p; int i; if(poss-length) /*插入位置不合法，這位置是從1數起*/ printf(paramet

13、er error!); return NULL; if(t-length) /*串t非空,重新分配空間，插入串t*/ if(!p=(char*)realloc(s-ch,(s-length+t-length)*sizeof(char) return(0); /*重新分配空間失敗*/ s-ch=p; for(i=s-length-1;i=pos-1;i-) /*因為數組下標從0起*/ s-chi+t-length=s-chi; /*向后移動字符，騰出位置*/ for(i=0;ilength;i+) /*插入串t*/ s-chpos+i-1=t-chi; s-length=s-length+t-l

14、ength; /*更新串s的長度*/retrun(s);串刪除：從串s中位置pos開始，刪除len個字符int StrDelete(Hstring *s, int pos,int len) char *p; int i; if(poslength-pos ch+pos-1; /*使指針p指向刪除的開始位置*/ for(i=0;ilength-pos- len;i+) *(p+i)=*(p+len+i); /*刪除字符,使后面的字符前移*/ s-length=s-length-len; /*更改串s的長度*/ return(1);串的塊鏈存儲結構 串的鏈式存儲結構類型定義如下： typedef

15、struct char ch; /*單字符*/ struct cnode *next; cnode,*LinkString; LinkString head; /*head是鏈串的頭指針*/ 串的鏈式存儲結構簡稱鏈串。 ABCDEhead結點大小為1的鏈串表示 在這種存儲結構下，結點數據域的類型是單字符，所以與前面講的單鏈表的操作一樣。 結點大小為1時，鏈串結構便于進行插入和刪除運算，但每個結點的指針域所占空間比字符域所占空間要大得多，存儲空間利用率低。存儲密度較低。所謂存儲密度為： 為了有效利用存儲空間，可在鏈串的每個結點中存放多個字符，稱這樣的結點為塊，每個結點中所容納的字符個數為塊的大小

16、，稱這樣的串存儲結構為塊鏈結構 塊鏈結構中，結點大小大于1時，串的長度不一定正好是結點大小的整數倍，因此要用特殊字符”#”來填充最后一個結點，以表示串的終結。 結點大小為1時，串的操作較方便，但是存儲空間占用較大，空間利用率低；提高結點的大小使得存儲空間利用率增大，但做插入、刪除運算時，需要考慮結點的拆分與合并，可能會引起大量字符的移動，給運算帶來不便。 在串的鏈式結構中，結點大小的選擇很重要，直接影響到串的處理效率和內存空間利用率。#define CHUNKSIZE=4 /*定義塊大小*/typedef struct Chunk /*定義塊鏈結點結構*/ char strCHUNKSIZE;

17、 / *一塊存儲空間大小*/ struct Chunk *next; Chunk;typedef struct /*定義塊鏈存儲結構*/ Chunk *head,*tail; /*鏈表頭指針和尾指針*/ int strlen; /*串的實際長度*/ Lstring; 為了便于串進行操作如串聯結，在鏈表中設置尾指針指示最后一個結點，同時設置一個分量表示串的實際長度。串的塊鏈存儲結構類型定義如下：4.3 串的模式匹配算法 在一個文本中，我們經常要查找某一特定的單詞，這也叫子串定位操作又稱為串的模式匹配(Pattern Matching)或串匹配，它是串處理系統中的重要操作之一 。基本的模式匹配算法

18、 子串定位操作是要在主串中找出一個與子串相同的子串。一般將主串稱為目標串，子串稱之為模式串。 設S為目標串，T為模式串，把從目標串S中查找模式串T的過程成為“模式匹配”。匹配的結果有兩種：如果S中有模式為T的子串，則返回該子串在S中的位置，若S中有多個模式為T的子串時，則返回的是模式串T在S中第一次出現的位置，這種情況稱匹配成功；否則，稱為匹配失敗。設有兩個串S（目標串）和T（模式串），其中： S=s1s2s3sn T=t1t2t3tm（1mn，通常有mn） 模式匹配算法的基本思想是：用T中字符依次與S中字符比較：從S中的第一個字符(i=1)和T中第一個字符(j=1)開始比較，如果s1t1，則

19、i和j各加1，繼續比較后續字符，若s1t1，s2t2，smtm，返回1；否則，一定存在某個整數j(1jm)使得sitj，即第一趟匹配失敗，立即中斷本趟比較；將模式串T向右移動一個字符執行第二趟匹配，即用T中第一個字符(j=1)與S中的第2個字符(i=2)開始依次比較； 或者在某一趟匹配中出現t1si-m+1，t2si-m+2，tmsi，那么匹配成功，返回序號i-m+1（本趟匹配的開始位置）； 或者當執行了(n-m+1)趟匹配步驟之后，即一直將T向右移到無法繼續與S比較為止，在S中沒有找到等于T的子串，那么匹配失敗。 反復執行匹配步驟，直到出現下面兩種情況之一：S a c a c b a c b

20、 a b c aT a c b a bi =3j=3S a c a c b a c b a b c aT a c b a bi =2j =1S a c a c b a c b a b c aT a c b a bi=7j=5第一趟匹配S3T3第二趟匹配S2T1第三趟匹配S7T5(含n=10個字符)(含m=5個字符)S a c a c b a c b a b c aT a c b a b i =4j=1S a c a c b a c b a b c aT a c b a bi =5j =1S a c a c b a c b a b c aT a c b a bi=10j=5第五趟匹配S5T1第四

21、趟匹配S4T1第六趟匹配成功此匹配成功時，返回n-m+1(即10-5+1)int Index(SeqString s , SeqString t) /* 在目標串s中找模式串t首次出現的位置，若不存在返回0。采用定長順序存儲結構第二種方式存放串S和串T */int i,j;for(i=1,j=1;i=s.length&jt.length) return(i-t.length+1); /*匹配成功，返回模式在目的串中*/ else /*第1次出現的位置*/ return(0); /*匹配不成功*/ 模式匹配基本算法 算法分析 該算法的基礎是基于字符串的比較，匹配過程簡單，好理解，但算法效率不高。

22、在某趟匹配過程中，若出現字符比較不等，則指向主串的指針需要回溯，要從模式串的第一個字符重新開始比較。 設主串和模式串的長度分別為n、m，在最壞情況下（即第i趟匹配成功，前面 i-1趟不成功），每趟比較了m次，第i趟也比較了m次，那么上述算法所執行的字符比較的總次數(最多)為m(n-m+1)。算法的時間復雜度為O(m(n-m)，若nm，則時間復雜度為O(mn) 。 KMP(克努特、莫里斯、普拉特)算法的基本思想：每當一趟匹配過程中出現字符比較不等時，指向主串的指針i不回溯，而是利用已經得到的“部分匹配”結果將模式串向右滑動一段距離后繼續進行比較。模式匹配的改進算法KMP算法假設下一次主串中的第i

23、個字符就與模式串中的第k(kk，根據()和()可推出： t1t2t3 tk-1= tj-k+1tj-k+2tj-1 在模式串的前j-1個字符中應存在兩個長度為k-1的相同的最大子串，兩子串t1t2tk-1與tj-k+1tj-k+2tj-1 相等，即 t1= tj-k+1，t2= tj-k+2，tk-1=tj-1。 0 當j=1時 nextj= Maxk | 1kj且t1t2tk-1=tj-k+1tj-k+2tj-1 當此集合不空 1 其他情況 根據以上的討論，我們得出：當模式串T中第j個字符與主串S中第i個字符失配時，模式串中要重新與主串中字符si進行比較的字符位置k的函數nextj=k 為：例：根據定義可推出下列模式串的next函數值： 位置j 1 2 3 4 5 6 7 8 9 10 11 12 模式串 b