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

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

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

4、。 串復(fù)制Strcpy(s,t)：由串s復(fù)制得到串t。串聯(lián)接Strcat(s,t)：將串t聯(lián)接到串s的末尾形成新串s。 串比較Strcmp(s,t)：比較s和t的大小，若st，則返回值小于0；若st，則返回值大于0；若s=t，則返回值為0 。 串的基本操作 求子串Substr(s,pos,len,sub)：從串s中的第pos個字符開始取長度為len的子串構(gòu)成串sub。 子串的定位Index(s,t)：在串s中尋找串t第一次出現(xiàn)時，串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 串的表示和實現(xiàn) 串的定長順序存儲 串的順序存儲結(jié)構(gòu)，簡稱為順序串。用一組地址連續(xù)的存儲單元來依次存放串中的字符序列，串中相鄰的字符順序存放在相鄰的存儲單元中。所謂定長，指按照預(yù)先定義的大小為每一個串分配一個固定的存儲區(qū)域。 通常有下列兩種實現(xiàn)方式： 第一種使用定長的字符數(shù)組存放串，一般使用一個不會在串中出現(xiàn)的特殊字符（如0）放在串值的末尾（不記入串長）來表示串的結(jié)束。類型定義如下:#define MaxStrSize 256 /*串可能的最大長度*/

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

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

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

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

10、hi; s.length=MaxStrSize /*置串s的實際長度,無0作為結(jié)束標(biāo)志*/ 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復(fù)制字符*/ 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復(fù)制到新串new中*/ for(i=0;ichs.length+i=t.chi; /*依次復(fù)制串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數(shù)起*/ 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-) /*因為數(shù)組下標(biāo)從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);串的塊鏈存儲結(jié)構(gòu) 串的鏈?zhǔn)酱鎯Y(jié)構(gòu)類型定義如下： typedef

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

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

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

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

19、i和j各加1，繼續(xù)比較后續(xù)字符，若s1t1，s2t2，smtm，返回1；否則，一定存在某個整數(shù)j(1jm)使得sitj，即第一趟匹配失敗，立即中斷本趟比較；將模式串T向右移動一個字符執(zhí)行第二趟匹配，即用T中第一個字符(j=1)與S中的第2個字符(i=2)開始依次比較； 或者在某一趟匹配中出現(xiàn)t1si-m+1，t2si-m+2，tmsi，那么匹配成功，返回序號i-m+1（本趟匹配的開始位置）； 或者當(dāng)執(zhí)行了(n-m+1)趟匹配步驟之后，即一直將T向右移到無法繼續(xù)與S比較為止，在S中沒有找到等于T的子串，那么匹配失敗。 反復(fù)執(zhí)行匹配步驟，直到出現(xiàn)下面兩種情況之一：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) /* 在目標(biāo)串s中找模式串t首次出現(xiàn)的位置，若不存在返回0。采用定長順序存儲結(jié)構(gòu)第二種方式存放串S和串T */int i,j;for(i=1,j=1;i=s.length&jt.length) return(i-t.length+1); /*匹配成功，返回模式在目的串中*/ else /*第1次出現(xiàn)的位置*/ return(0); /*匹配不成功*/ 模式匹配基本算法 算法分析 該算法的基礎(chǔ)是基于字符串的比較，匹配過程簡單，好理解，但算法效率不高。

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

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