數(shù)據(jù)結(jié)構(gòu)——用C語言描述（第二版）第4章串

《數(shù)據(jù)結(jié)構(gòu)——用C語言描述（第二版）第4章串》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)——用C語言描述（第二版）第4章串（49頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第第四四章章 串串4.1 串的基本概念串的基本概念4.2 串的存儲實現(xiàn)串的存儲實現(xiàn)4.3 串的模式匹配算法串的模式匹配算法4.4 漢字串漢字串第第4章章 串串第第四四章章 串串 串又稱字符串，是一種特殊的線性表，是數(shù)據(jù)元素類型為串又稱字符串，是一種特殊的線性表，是數(shù)據(jù)元素類型為字符的線性表，其應(yīng)用非常廣泛，是許多軟件系統(tǒng)（如字符編字符的線性表，其應(yīng)用非常廣泛，是許多軟件系統(tǒng)（如字符編輯、情報檢索、詞法分析、符號處里、自然語言翻譯等系統(tǒng)）輯、情報檢索、詞法分析、符號處里、自然語言翻譯等系統(tǒng)）的操作對象。的操作對象。本章介紹串的概念和各種存儲結(jié)構(gòu)，并討論串的聯(lián)接、求本章介紹串的概念和各種存儲結(jié)構(gòu)，

2、并討論串的聯(lián)接、求子串、串的插入、刪除和置換以及串的模式匹配等運算。子串、串的插入、刪除和置換以及串的模式匹配等運算。第第4章章 串串第第四四章章 串串 串是由串是由n個個(n 0 0)字符組成的有限序列，一般記作：字符組成的有限序列，一般記作：S=“a1a2an”其中，其中，S是串名，用成對的雙引號括起來的字符序列是串的值，是串名，用成對的雙引號括起來的字符序列是串的值，ai可以可以是字母，數(shù)字或其它字符；是字母，數(shù)字或其它字符；n為串中字符的個數(shù)，稱為串的長度，長度為為串中字符的個數(shù)，稱為串的長度，長度為零的串稱為空串。需要注意的是，成對的雙引號本身僅作為標記，不屬于零的串稱為空串。需要注

3、意的是，成對的雙引號本身僅作為標記，不屬于串。串。例如，串例如，串“Beijing”和和“Bei jing”的長度分別是的長度分別是7和和8。空串和空格串是。空串和空格串是兩個不同的情況，例如，兩個不同的情況，例如，S1=“”即為空串，它的長度為即為空串，它的長度為0，空串內(nèi)無任何字，空串內(nèi)無任何字符，而符，而S2=“”為空格串，即由一個或多個空格組成，其長度為串中空格的為空格串，即由一個或多個空格組成，其長度為串中空格的個數(shù)，空格符可以出現(xiàn)在字符序列的任意部位。個數(shù)，空格符可以出現(xiàn)在字符序列的任意部位。串中任意個連續(xù)的字符組成的子序列稱為子串，一個串可以包含若干串中任意個連續(xù)的字符組成的子序

4、列稱為子串，一個串可以包含若干個子串，相應(yīng)地，包含子串的串稱為主串。字符在串中的序號稱作該字符個子串，相應(yīng)地，包含子串的串稱為主串。字符在串中的序號稱作該字符在串中的位置。當兩個串長度相等且對應(yīng)字符都相同時相等。在串中的位置。當兩個串長度相等且對應(yīng)字符都相同時相等。4.1 串的基本概念串的基本概念第第四四章章 串串 串的邏輯結(jié)構(gòu)與線性表的區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。串的邏輯結(jié)構(gòu)與線性表的區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。串結(jié)構(gòu)的形式化定義為：串結(jié)構(gòu)的形式化定義為：String=(D，R)其中，其中，D=aiaicharacter，i=1，2n，n0，R=a i-1，aiD，i=1，2

5、，n 串的基本運算有：串的基本運算有：（1）初始化）初始化ClearString（s）：初始化串）：初始化串s。（2）StrAssign（s，ch）：串賦值。）：串賦值。（3）StrCopy(s，t)：串復制。：串復制。（4）StrConcat（t，s1，s2）：串聯(lián)接。）：串聯(lián)接。（5）求串長）求串長StrLen（s）：返回）：返回s串的元素個數(shù)，即串的元素個數(shù)，即s串的長度。串的長度。（6）串比較）串比較StrCom（s，t）（7）求子串）求子串SubStr（t，s，pos，len）：返回）：返回s串的第串的第pos個字符起始的個字符起始的長度為長度為len的子串。的子串。（8）插入運算）

6、插入運算StrInsert（s，pos，t）：把串）：把串t的值插入到串的值插入到串s的第的第pos個個字符之后。字符之后。（9）刪除運算）刪除運算StrDel（s，pos，len）：將串）：將串s中從第中從第pos字符起始的長度字符起始的長度為為len的子串刪除。的子串刪除。第第四四章章 串串 （10）子串定位）子串定位StrIndex（s，t，pos）：從主串）：從主串s的第的第pos個字符起定個字符起定位串位串s中是否存在和串中是否存在和串t值相等的子串，若存在，則返回子串值相等的子串，若存在，則返回子串t在主串在主串s中中第一次出現(xiàn)的位置，否則，返回函數(shù)值第一次出現(xiàn)的位置，否則，返回函

7、數(shù)值0。例如，例如，StrIndex（“Beijing”，“jin”，1）=4；StrIndex（“Beijing”，“jng”，2）=0 （11）置換運算）置換運算StrReplace（s，pos，len,t）：用）：用t串置換串置換s串中第串中第pos字符開始的連續(xù)的字符開始的連續(xù)的len個字符。個字符。例如，例如，s=“Thatisabag！”，則，則 StrReplace（s，3，2，“is”）“Thisisabag！”有時用另一種置換運算有時用另一種置換運算StrReplace（s，t，v）表示用）表示用v串置換所有在串置換所有在s串中出現(xiàn)的與串中出現(xiàn)的與t串相等的子串。串相等的子串

8、。例如，例如，s=“if（jn）j；”，t=“j”，v=“i”，則，則 StrReplace（s，t，v）=“if（in）i；”以上介紹的是有關(guān)串的一些基本運算，利用它們可以處理關(guān)于串的以上介紹的是有關(guān)串的一些基本運算，利用它們可以處理關(guān)于串的各種操作，在使用高級程序設(shè)計語言中的串類型時，對于串的基本運算各種操作，在使用高級程序設(shè)計語言中的串類型時，對于串的基本運算可以有不同的定義方法?？梢杂胁煌亩x方法。第第四四章章 串串4.2.1 串的定長順序存儲及運算實現(xiàn)串的定長順序存儲及運算實現(xiàn) 1.串的定長順序存儲串的定長順序存儲 串的順序存儲結(jié)構(gòu)簡稱順序串，是把串中的字符依次存放在一組地址串的順

9、序存儲結(jié)構(gòu)簡稱順序串，是把串中的字符依次存放在一組地址連續(xù)的存儲單元中。連續(xù)的存儲單元中。有時將為字符串分配一個固定長度的一組地址連續(xù)的存儲單元的存儲有時將為字符串分配一個固定長度的一組地址連續(xù)的存儲單元的存儲分配方法稱之為定長順序存儲分配。定長順序存儲分配的實現(xiàn)，要結(jié)合具分配方法稱之為定長順序存儲分配。定長順序存儲分配的實現(xiàn)，要結(jié)合具體的計算機編址方式進行，通常有三種實現(xiàn)方式：體的計算機編址方式進行，通常有三種實現(xiàn)方式：（1）緊縮方式）緊縮方式 緊縮方式將串長顯式地直接存儲，字符依次順序放在連續(xù)的幾個單元緊縮方式將串長顯式地直接存儲，字符依次順序放在連續(xù)的幾個單元中，這種存儲方式的優(yōu)點是充分

10、地利用了空間，然而運算不太方便。中，這種存儲方式的優(yōu)點是充分地利用了空間，然而運算不太方便。假定計算機按字編址，若串假定計算機按字編址，若串S為為“DataStructure”，表示空格表示空格字符，則字符，則S串有串有14個字符，存儲個字符，存儲S串的長度串的長度14和每個字符，一共需占用和每個字符，一共需占用4個個存儲單元，如圖存儲單元，如圖4.1所示。所示。4.2 串的存儲實現(xiàn)串的存儲實現(xiàn)第第四四章章 串串4Da1eucStraurtt圖 4.1 串 的 緊 縮 存 儲 方 式 示 例 （2）非緊縮方式）非緊縮方式 非緊縮方式是每個單元只存放一個字符，串的長度不顯式存儲，由非緊縮方式是每

11、個單元只存放一個字符，串的長度不顯式存儲，由串中字符占存儲單元的數(shù)目來隱式確定。如圖串中字符占存儲單元的數(shù)目來隱式確定。如圖4.2給出了上述串的非緊給出了上述串的非緊縮存儲。顯然，非緊縮存儲方式對于串運算比較方便，但存儲空間沒有縮存儲。顯然，非緊縮存儲方式對于串運算比較方便，但存儲空間沒有得到有效的利用。得到有效的利用。（3）單字節(jié)存儲方式）單字節(jié)存儲方式 計算機按字節(jié)編址，每個字節(jié)存放一個字符，這時的串長度由串占計算機按字節(jié)編址，每個字節(jié)存放一個字符，這時的串長度由串占用的字節(jié)數(shù)隱式確定，如圖用的字節(jié)數(shù)隱式確定，如圖4.3所示。這種存儲方式既不浪費空間，又所示。這種存儲方式既不浪費空間，又使

12、串中每個字符與唯一的地址對應(yīng)，方便了運算，對于按字節(jié)編址的計使串中每個字符與唯一的地址對應(yīng)，方便了運算，對于按字節(jié)編址的計算機而言是非常合適的。算機而言是非常合適的。第第四四章章 串串圖 4.2 非 緊 縮 方 式 示 例DautcurtsatreDautcurtsatre圖 4.3 單 字 節(jié) 存 儲 方 式 示 例0第第四四章章 串串 在在C語言中，按字節(jié)尋址。語言中，按字節(jié)尋址。C語言中的串有字符串常量和字符串變量語言中的串有字符串常量和字符串變量兩種。用雙引號括起來的字符序列為字符串常量，可以用宏定義兩種。用雙引號括起來的字符序列為字符串常量，可以用宏定義#define來來定義字符串常

13、量的標識符。定義字符串常量的標識符。例如，例如，#define CITY Beijing 對字符串變量而言，對字符串變量而言，C語言將其類型說明為字符型一維數(shù)組。語言將其類型說明為字符型一維數(shù)組。例如，例如，char ch100；其中，數(shù)組其中，數(shù)組ch是一個一維數(shù)組，這里的字符串的最大長度是由其變量是一個一維數(shù)組，這里的字符串的最大長度是由其變量說明時決定并且固定不變。通常，在字符串的最后一個字符的后面存放一說明時決定并且固定不變。通常，在字符串的最后一個字符的后面存放一個結(jié)束標志個結(jié)束標志0。為了更好地討論字符串的運算，可將順序串類型定義如下：為了更好地討論字符串的運算，可將順序串類型定義

14、如下：#define MAXLEN 81 typedef struct string char chMAXLEN；int len；SeqString；第第四四章章 串串 2.定長順序串的基本運算實現(xiàn)定長順序串的基本運算實現(xiàn) （1）求串長）求串長 int StrLen(SeqString*s)return(*s).len);（2）串的聯(lián)接）串的聯(lián)接 兩個串的聯(lián)接就是將一個串緊接著存放在另一個串的后面而得到一個兩個串的聯(lián)接就是將一個串緊接著存放在另一個串的后面而得到一個新串。新串。第第四四章章 串串 void StrConcat(SeqString *t，SeqString *s1，SeqStri

15、ng*s2)int i，j;if(*s1).len+(*s2).len=MAXLEN)for(i=0；i(*s1).len；i+)(*t).chi=(*s1).chi;for(j=0；j(*s2).len；j+)(*t).ch(*s1).len+j=(*s2).chj;(*t).len=(*s1).len+(*s2).len;else if(*s1).len MAXLEN)for(i=0；i(*s1).len；i+)(*t).chi=(*s1).chi;for(j=0；j MAXLEN-(*s1).len；j+)(*t).ch(*s1).len+j=(*s2).chj;(*t).len=MAX

16、LEN；else printf(“overflow！n”);第第四四章章 串串 （3）求子串）求子串 void SubString（t，s，pos，len）/*用用t返回主串返回主串s中第中第pos個字符起，長度為個字符起，長度為len的子串的子串*/SeqString *t，*s；int pos，len；int i；if(pos(*s).len)|(len(*s).len-pos+1)printf(“pos或或len超界超界n”);else for(i=0；i len；i+)(*t).chi=(*s).chpos-1+i (*t).len=len;第第四四章章 串串（4）子串的插入）子串的插

17、入 void StrInsert(SeqString*s，int pos，SeqString*t)/*在串在串s中的中的pos位置插入子串位置插入子串t*/int i；if(pos(*s).len+1)printf(“Insertion position incorrect!n”)；else if(*s).len+(*t).len=pos；i-)(*s).chi+(*t).len=(*s).chi;for(i=0；i(*t).len；i+)(*s).chi+pos=(*t).chi;(*s).len=(*s).len+(*t).len；else printf(“overflow！”)；第第四四

18、章章 串串（5）子串的刪除）子串的刪除 void StrDel(s，pos，len)/*從串從串s中刪除第中刪除第pos字符起始的長度為字符起始的長度為len的子串的子串*/SeqString *s；int pos，len;int i，j，k；char*p，*q；if(pos(*s).len)printf(“Deleted position incorrect!n”)；else if(pos=len)(*s).len=0；/*刪除整個串刪除整個串*/else第第四四章章 串串 if(pos+len-10）/*將被刪除位置后的字符向前移動將被刪除位置后的字符向前移動*/*q=*p；+p；+q；k

19、-；*q=*p;(*s).len=(*s).len-len；else printf(“no characteds deleted!n”)；/*沒有沒有l(wèi)en個字符可刪除個字符可刪除*/第第四四章章 串串 （6）串的置換）串的置換 void StrReplace(s，t，v)/*用用v串替代串替代s串中所有的串中所有的t子串子串*/SeqString *s，*t，*v；int start，pos，m，n，q；n=(*s).len；m=(*t).len；q=(*v).len；pos=1；do start=StrIndex(s，t，pos)；/*定位函數(shù)定位函數(shù)*/if(start!=0)StrDe

20、l(s，start，m)；StrInsert(s，v，start)；pos=start+q；(*s).len=(*s).len+q-m；n=(*s).len；while(posst!=NULL)free(t-st)；/*釋放釋放t空間空間*/while(charsi!=0)/*統(tǒng)計統(tǒng)計chars中字符個數(shù)中字符個數(shù)*/i+;len=i;if(！len)printf(“串常量為空串串常量為空串n”)；t-st=NULL;t-length=0;else if(!(t-st=(char*)malloc(i*sizeof(char)return(0);for(i=0；isti=charsi;t-len

21、gth=len;return(1);/*StrAssign*/第第四四章章 串串（2）串聯(lián)接）串聯(lián)接StrConcat(t，s1，s2)StrConcat(HeapString*t，HeapString*s1，HeapString*s2)if(t-st!=NULL)free(t-st)；/*釋放釋放t原空間原空間*/if(!(t-st=(char*)malloc(（s1-length+s2-length）*sizeof(char)return(0);for(i=0；ilength；i+)/*逐字符賦值逐字符賦值*/t-sti=s1-sti;for(i=0；ilength；i+)/*逐字符賦值逐

22、字符賦值*/t-sts1-length+i=s2-sti；t-length=s1-length+s2-length；return(1);/*StrConcat*/第第四四章章 串串（3）求子串）求子串SubString(t,s,pos,len)SubString(HeapString *t，HeapString *s，int i，int len)if(poss-length)|(lens-length-pos+1)printf(“子串位置或長度有錯誤子串位置或長度有錯誤n”);return(0);if(t-st!=NULL)free(t-st)；/*釋放釋放t原空間原空間*/if(len=0)

23、/*空子串空子串*/t-st=NULL;t-length=0;else t-st=(char*)malloc(len*sizeof(char);for(i=0；isti=s-stpos-1+i;t-length=len;return(1);/*SubString*/第第四四章章 串串（4）插入函數(shù)）插入函數(shù)StrInsert(s,pos,t)StrInsert(HeapString*s，int pos，HeapString*t)int i;char*temp;if(poss-length|s-length=0)return(0);temp=(char*)malloc(s-length+t-le

24、ngth)*sizeof(char);if(temp=NULL)return(0);for(i=0；isti;for(i=0；ilength；i+)tempi+pos=t-sti;for(i=pos；ilength；i+)tempi+t-length=s-sti;s-length+=t-length;free(s-st);s-st=temp;return(1);/*StrInsert*/第第四四章章 串串 （5）刪除函數(shù)）刪除函數(shù)StrDelete(s,pos,t)StrDelete(HeapString*s，int pos，int len)int i;char*temp;if(pos(s-l

25、ength-len)return(0);temp=(char*)malloc(s-length-len)*sizeof(char);if(temp=NULL)return(0);for(i=0;isti;for(i=pos；ilength-len；i+)tempi=s-sti+len;s-length=s-length-len;free(s-st);s-st=temp;return(1);/*StrDelete*/第第四四章章 串串 4.2.3串的塊鏈存儲表示串的塊鏈存儲表示 順序串上的插入和刪除操作運算需要移動大量的字符。因此，順序串上的插入和刪除操作運算需要移動大量的字符。因此，可以采可以

26、采用用單鏈表方式來存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。單鏈表方式來存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。但在利用但在利用鏈表存儲串值時，每個結(jié)點既可以存放一個字符，也可以存放多個字符，鏈表存儲串值時，每個結(jié)點既可以存放一個字符，也可以存放多個字符，即存在一個即存在一個“結(jié)點大小結(jié)點大小”的問題。結(jié)點的大小是指結(jié)點的數(shù)據(jù)域可存放字的問題。結(jié)點的大小是指結(jié)點的數(shù)據(jù)域可存放字符的個數(shù)。如圖符的個數(shù)。如圖4.6中所示的鏈表，其結(jié)點大小分別為中所示的鏈表，其結(jié)點大小分別為4和和1。第第四四章章 串串 一般的，為了提高存儲密度，可使每個結(jié)點存放多個字符。顯然，當一般的，為了提高存儲密度，可使每個

27、結(jié)點存放多個字符。顯然，當結(jié)點大小大于結(jié)點大小大于 1 1時，時，由于串長不一定是結(jié)點大小的整數(shù)倍，最后一個結(jié)點由于串長不一定是結(jié)點大小的整數(shù)倍，最后一個結(jié)點的數(shù)據(jù)域不一定剛好全被串值填滿，此時就需要以特殊的字符如的數(shù)據(jù)域不一定剛好全被串值填滿，此時就需要以特殊的字符如或或其它的非串值字符填充。通常，將這種結(jié)構(gòu)中的結(jié)點稱為塊，相應(yīng)的鏈表其它的非串值字符填充。通常，將這種結(jié)構(gòu)中的結(jié)點稱為塊，相應(yīng)的鏈表稱為塊鏈結(jié)構(gòu)。塊鏈結(jié)構(gòu)的類型可定義如下：稱為塊鏈結(jié)構(gòu)。塊鏈結(jié)構(gòu)的類型可定義如下：#define BLOCKSIZE 8 /*塊大小定義塊大小定義*/typedef struct Blocknode

28、/*塊類型定義塊類型定義*/char dataBLOCKSIZE；struct Blocknode *next；BLOCK；typedef struct /*塊鏈類型定義塊鏈類型定義*/BLOCK *head,*tail；int length；BLString；BLString *s，*p，*head；/*s，p，head為塊鏈指針類型為塊鏈指針類型*/第第四四章章 串串4.3 串的模式匹配算法串的模式匹配算法4.3.1 串的簡單模式匹配算法串的簡單模式匹配算法 設(shè)有兩個串設(shè)有兩個串s和和t，在串，在串s中查找值等于中查找值等于t的子串的過程稱為模式匹配，的子串的過程稱為模式匹配，其中，其中，

29、s串稱為主串或目標串，串稱為主串或目標串，t串稱為模式串。若在主串串稱為模式串。若在主串s中存在模式為中存在模式為t的子串，則稱匹配成功，否則稱為匹配失敗。串的簡單模式匹配實際的子串，則稱匹配成功，否則稱為匹配失敗。串的簡單模式匹配實際上是子串的定位運算，是一種帶回溯的模式匹配。上是子串的定位運算，是一種帶回溯的模式匹配。例如，圖例如，圖4.7給出了給出了s=“ababcabcacbab”，t=“abcac”的簡單模式匹配的簡單模式匹配過程。過程。第第四四章章 串串第 一 趟 匹 配 a b a b c a b c a c b a ba b c i=3 j=3i=3j=3匹 配 失 敗第 二

30、趟 匹 配 a b a b c a b c a c b a ba i=2 j=1i=2j=1匹 配 失 敗第 三 趟 匹 配 a b a b c a b c a c b a ba b c a c i=7 j=5i=7j=5匹 配 失 敗第 四 趟 匹 配 a b a b c a b c a c b a ba i=4 j=1i=4j=1匹 配 失 敗第 五 趟 匹 配 a b a b c a b c a c b a ba i=5 j=1i=5j=1匹 配 失 敗第 六 趟 匹 配 a b a b c a b c a c b a ba b ca c i=1 1 j=6i=1 1j=6匹 配 成 功

31、圖 4.7 串 的 簡 單 模 式 匹 配 過 程 示 意 圖第第四四章章 串串s1 s2 s3 s4 si-j+1 si-j+2 si-2 si-1 si si+1.圖 4.8 某 一 趟 的 模 式 匹 配 狀 態(tài) 示 意 圖 t1 t2 tj-2 tj-1tj tj+1.其模式匹配過程可描述為：設(shè)在某一趟匹配時，其模式匹配過程可描述為：設(shè)在某一趟匹配時，s串中的第串中的第i個字符與個字符與t串串中的第中的第j個字符比較，若個字符比較，若sitj，則應(yīng)有，則應(yīng)有si-1=tj-1，si-2=tj-2，si-j+1=t1，如圖，如圖4.8所示。因此，當所示。因此，當si與與tj匹配失敗時，新

32、的一趟匹配開始應(yīng)該是匹配失敗時，新的一趟匹配開始應(yīng)該是t1與與si-j+2繼續(xù)進繼續(xù)進行比較，行比較，i指針從當前位置回溯到新位置。指針從當前位置回溯到新位置。其基本思想是：首先從主串其基本思想是：首先從主串s的第的第 start（1startStrLen(s)）個字符起和）個字符起和模式串模式串t的第一個字符進行比較，若相等，則繼續(xù)比較后續(xù)字符，否則，從主的第一個字符進行比較，若相等，則繼續(xù)比較后續(xù)字符，否則，從主串串s的下一個字符起再重新和模式的下一個字符起再重新和模式t的第一個字符比較，依此類推，直至模式的第一個字符比較，依此類推，直至模式t的每一個字符依次和主串的每一個字符依次和主串s

33、中的一個連續(xù)的字符序列相等時為止，此時稱匹配中的一個連續(xù)的字符序列相等時為止，此時稱匹配成功，函數(shù)值為與模式成功，函數(shù)值為與模式t中第一個字符相等的字符在主串中第一個字符相等的字符在主串s中的位置；否則稱中的位置；否則稱匹配不成功，函數(shù)值返回匹配不成功，函數(shù)值返回0。第第四四章章 串串算法描述如下：算法描述如下：int StrIndex（SeqString*s，SeqString *t，int start）/*在目標串在目標串s中定位模式串中定位模式串t的位置的位置*/int i，j;if(start(*s).len)|(*t).len=0)return(0)；else i=start；j=1

34、；while(i(*s).len)&(j(*t).len)if（(*s).chi=(*t).chj）i+；j+；else i=i-j+2；j=1；if(j=(*t).len)return(i-(*t).len)；else return(0)；在上面算法中可以引入起始查找位置指針在上面算法中可以引入起始查找位置指針start，即從，即從s串的串的start位置位置起始查找第一個與起始查找第一個與t串相同的子串，使函數(shù)更為通用。串相同的子串，使函數(shù)更為通用。第第四四章章 串串 該算法匹配過程由于存在回溯，算法的效率不高。在最好情況下，算該算法匹配過程由于存在回溯，算法的效率不高。在最好情況下，算法

35、的時間復雜度為法的時間復雜度為O(n+m)。在最壞情況下的時間復雜度為在最壞情況下的時間復雜度為O(nm)。最壞最壞的情況是在每一趟匹配失敗時，都是模式的情況是在每一趟匹配失敗時，都是模式t的最后一個字符與的最后一個字符與s中相應(yīng)的字中相應(yīng)的字符比較時才不相等。符比較時才不相等。例如，當模式串為例如，當模式串為“00000001”，而目標串為，而目標串為“00000000000000000000000000000000000000000000000000001”時，時，整個匹配過程中指針整個匹配過程中指針i需回溯需回溯45次，在算法中次，在算法中while循環(huán)了循環(huán)了468（indexm）次，

36、算法的效率很低。有時，我們也將該算法稱為樸素的）次，算法的效率很低。有時，我們也將該算法稱為樸素的模式匹配。在下一節(jié)中，我們將介紹另一種較好的模式匹配。在下一節(jié)中，我們將介紹另一種較好的KMP模式匹配算法。模式匹配算法。第第四四章章 串串4.3.2 一種改進的模式匹配算法一種改進的模式匹配算法 D.E.Knuth與與V.R.Pratt和和J.H.Morris同時發(fā)現(xiàn)通過對上一節(jié)的簡單模式同時發(fā)現(xiàn)通過對上一節(jié)的簡單模式匹配算法進行一些改進，就可以匹配算法進行一些改進，就可以消除算法中主串消除算法中主串s s指針的回溯指針的回溯，完成串的模完成串的模式匹配，式匹配，而且算法可以在而且算法可以在O(

37、n+m)的時間數(shù)量級上完成串的模式匹配操作。的時間數(shù)量級上完成串的模式匹配操作。人們把該改進算法稱它為克努特莫里斯普拉特算法人們把該改進算法稱它為克努特莫里斯普拉特算法(簡稱為簡稱為KMP算法算法)，如圖如圖4.9模式匹配過程。可以看出，其改進之處在于整個匹配過程對主串而模式匹配過程?？梢钥闯觯涓倪M之處在于整個匹配過程對主串而言無需回溯，每當某一趟匹配過程中出現(xiàn)字符比較不等即匹配失敗時，目言無需回溯，每當某一趟匹配過程中出現(xiàn)字符比較不等即匹配失敗時，目標串標串i指針不需要回溯，而是利用已得到的指針不需要回溯，而是利用已得到的“部分匹配部分匹配”的結(jié)果將模式向右的結(jié)果將模式向右移動盡可能遠的一

38、段距離后，繼續(xù)進行比較，從而消除回溯。移動盡可能遠的一段距離后，繼續(xù)進行比較，從而消除回溯。第第四四章章 串串第一趟匹配 a b a b c a b c a c b a ba b ci=3j=3i=3j=3匹配失敗第三趟匹配 a b a b c a b c a c b a bi=11j=6i=11j=6匹配成功j=2i=7(a)b c a c第二趟匹配 a b a b c a b c a c b a bi=7j=5i=7j=5匹配失敗i=3j=1 a b c a c圖4.9 改進算法的模式匹配過程示意圖第第四四章章 串串 一般的情況討論如下：一般的情況討論如下：假設(shè)主串假設(shè)主串s為為“s1s2

39、sn”，模式串，模式串t為為“t1t2.tm”，要設(shè)計一個無回溯的，要設(shè)計一個無回溯的匹配算法，關(guān)鍵在于確定在匹配過程中，當主串中匹配算法，關(guān)鍵在于確定在匹配過程中，當主串中si與與tj比較不等（即比較不等（即“失失配配”）時，模式串）時，模式串t中的哪一個字符應(yīng)與中的哪一個字符應(yīng)與si繼續(xù)進行比較？繼續(xù)進行比較？假設(shè)將這個字符記做假設(shè)將這個字符記做tk，顯然，有，顯然，有k0時，表示一旦匹配過程中出現(xiàn)時，表示一旦匹配過程中出現(xiàn)si與與tj不相不相等時，可用等時，可用t中的中的nextj位置的字符繼續(xù)與位置的字符繼續(xù)與si比較；若比較；若nextj=0，則表示，則表示t中中任何字符都不與任何字

40、符都不與si比較，需重新比較比較，需重新比較t1與與s i+1?？梢?，對于任何的模式串可見，對于任何的模式串t而言，只要能確定而言，只要能確定nextj（j=1，2，m）的值，就可以用來加速匹配過程。的值，就可以用來加速匹配過程。模式串的模式串的next函數(shù)的定義為：函數(shù)的定義為：nextj0 當j 1時max k|1kj且“t1t2.tk-1”=“tj-k+1.tj-1”當 此 集 合 不 空 時1 其 它情 況第第四四章章 串串 next函數(shù)的意義是：若模式串函數(shù)的意義是：若模式串t中存在滿足等式中存在滿足等式“t1t2t k-1”=“t j-k+1 t j-k+2t j-1”的兩個子串，

41、則當匹配過程中主串中第的兩個子串，則當匹配過程中主串中第i個字符與模式中第個字符與模式中第j個字符個字符比較不等時，僅需將模式向右移動至模式中的第比較不等時，僅需將模式向右移動至模式中的第k個字符和主串中的第個字符和主串中的第i個字個字符對齊，匹配僅需從模式中的第符對齊，匹配僅需從模式中的第k個字符與主串中的第個字符與主串中的第i個字符繼續(xù)比較即可，個字符繼續(xù)比較即可，如圖如圖4.10所示。所示。另外，若在另外，若在“t1t2.tj-1”中不存在首尾相等的子串，則中不存在首尾相等的子串，則k=1，表示一旦有表示一旦有si與與tj不相等時，則用不相等時，則用t1與與si繼續(xù)進行比較。特別地，若繼

42、續(xù)進行比較。特別地，若j=1，當，當t1與與si比較不相等時，此時不能繼續(xù)右移，只要將比較不相等時，此時不能繼續(xù)右移，只要將t1與與s i+1繼續(xù)比較即可進行新繼續(xù)比較即可進行新一趟的匹配，所以在一趟的匹配，所以在next定義中，定義中，nextj=0。圖4.10 改進的模式匹配狀態(tài)示意圖s1 s2 s3 s4 si-j+1 si-j+2 si-2 si-1 si si+1.t1 t2.tk tj-2 tj-1tj tj+1.t1 t2.tk tj-2 tj-1tj tj+1.i第第四四章章 串串t a a a bs a a a a b b b圖 4.1 1 k 取 最 大 值 示 例 k=3

43、t右 移 a a a b 同時，為使模式串同時，為使模式串t的右移不的右移不丟失任何匹配成功的可能，對于同時丟失任何匹配成功的可能，對于同時存在多個滿足以上性質(zhì)條件的存在多個滿足以上性質(zhì)條件的k值應(yīng)取最大值，以使得移動的位數(shù)值應(yīng)取最大值，以使得移動的位數(shù)i-k最最小。小。例如，圖例如，圖4.11中，中，s=“aaaabbb”，t=“aaab”，當，當s4與與t4比較不相等時，比較不相等時，k可取可取1，2和和3，但只有，但只有k取取3時才可保證不丟失成功的可能匹配。時才可保證不丟失成功的可能匹配。第第四四章章 串串 在求得模式的在求得模式的next函數(shù)之后，匹配過程如下：若在匹配過程中有函數(shù)之

44、后，匹配過程如下：若在匹配過程中有si=tj成立，則成立，則i和和j分別增加分別增加1，否則，否則，i不變，即主串指針不回溯，而不變，即主串指針不回溯，而j退到退到nextj的位置再比較，即用的位置再比較，即用tnextj與與si繼續(xù)比較，若此時相等，則指針各自繼續(xù)比較，若此時相等，則指針各自增加增加1，否則，否則j再退到下一個再退到下一個nextnextj值的位置，依此類推，直至出現(xiàn)值的位置，依此類推，直至出現(xiàn)下列兩種可能的情況：一是下列兩種可能的情況：一是j退到某個退到某個next值（值（nextnext.nextj）時，）時，主串和模式串中的字符進行比較，若相等，則指針各自增主串和模式串

45、中的字符進行比較，若相等，則指針各自增1繼續(xù)進行匹配；繼續(xù)進行匹配；另一種情況是另一種情況是j退到值為退到值為0（即模式的第一個字符（即模式的第一個字符“失配失配”），此時需將模），此時需將模式繼續(xù)向右移動一個位置，即從主串的下一個字符式繼續(xù)向右移動一個位置，即從主串的下一個字符si+1起和模式重新開始起和模式重新開始匹配。匹配。例如，對于模式串例如，對于模式串t=“abaabcac”：（1）j=1，next1=0；（2）j=2，沒有首尾相等的子串，沒有首尾相等的子串，next2=1；（3）j=3，同樣，也沒有首尾相等的子串，同樣，也沒有首尾相等的子串，next3=1；（4）j=4，存在首尾相

46、等的子串，存在首尾相等的子串“a”，所以，所以next4=2；.其余類推，從而可求得其余類推，從而可求得t所對應(yīng)的所對應(yīng)的next函數(shù)，如圖函數(shù)，如圖4.12（a）所示。）所示。匹配過匹配過程如圖程如圖4.12（b）所示。）所示。第第四四章章 串串模式nextjjabaabcac1234567801122312（a）模式t的next函數(shù)值第第四四章章 串串（b）利 用 n e x t函 數(shù) 進 行 匹 配 過 程第 一 趟 匹 配 a c a b a a b a a b c a c a a b ca b i=2 j=2n e x t2=1a i=2 j=1n e x t1=0第 二 趟 匹 配

47、 a c a b a a b a a b c a c a a b c i=8 j=3第 四 趟 匹 配 a c a b a a b a a b c a c a a b c(a b)a a b c a c i=1 4 j=9 i=3 j=6 n e x t6=3第 三 趟 匹 配 a c a b a a b a a b c a c a a b c i=8 j=1 a b a a b c圖 4.1 2 利 用 模 式 n e x t函 數(shù) 進 行 匹 配 過 程 示 意 圖第第四四章章 串串KMP算法描述如下：算法描述如下：int KMP(SeqString*s，SeqString*t，int s

48、tart)if(start(*s).len+1)|(*t).len=0)return(0)；else i=start；j=1；while(i=(*s).len)&(jchi=t-chj)+i；+j；else j=nextj；if(j(*t).len)return(i-(*t).len)；else return(0)；/*KMP*/第第四四章章 串串 下面介紹模式串的下面介紹模式串的next函數(shù)值的求解算法。由于模式串的函數(shù)值的求解算法。由于模式串的next函數(shù)函數(shù)值僅取決于模式串本身而和主串無關(guān)，可以從分析其定義出發(fā)用遞推的值僅取決于模式串本身而和主串無關(guān)，可以從分析其定義出發(fā)用遞推的方法求得

49、方法求得next的函數(shù)值。的函數(shù)值。由定義可得：由定義可得：next1=0 現(xiàn)假設(shè)現(xiàn)假設(shè)nextj=k，這表明在模式串中存在下列關(guān)系：，這表明在模式串中存在下列關(guān)系：“t1t2tk-1”=“tj-k+1tj-k+2tj-1”其中，其中，k為滿足為滿足1kk滿足上滿足上式。顯然，若能求得式。顯然，若能求得nextj+1與與nextj的關(guān)系，就可以求得的關(guān)系，就可以求得next函數(shù)。函數(shù)。（1）若）若tk=tj，則有：，則有：nextj+1=k+1，從而，從而 nextj+1=nextj+1第第四四章章 串串（2）若）若tktj，此時可把求，此時可把求next函數(shù)的問題看成是一個模式匹配的問題，函

50、數(shù)的問題看成是一個模式匹配的問題，整個模式串既是主串又是模式串。整個模式串既是主串又是模式串。在當前匹配的過程中，當在當前匹配的過程中，當tjtk時，應(yīng)該將模式向右移動至用模式中時，應(yīng)該將模式向右移動至用模式中的第的第nextk個字符和主串中的第個字符和主串中的第j個字符相比較。此時，個字符相比較。此時，若若nextk=k且且 tj=tk，1kkj，則，則：nextj+1=k+1，從而可得：，從而可得：nextj+1=nextk+1 同理，若同理，若tjt k，則將模式繼續(xù)向右移動直至將模式中第，則將模式繼續(xù)向右移動直至將模式中第nextk個字個字符和符和tj對齊，對齊，.，依次類推，直至，依

51、次類推，直至tj和模式中某個字符匹配成功或者不和模式中某個字符匹配成功或者不存在任何存在任何k(1kj)滿足上述等式，則：滿足上述等式，則：nextj+1=1 例如，對于圖例如，對于圖4.12（a）中的模式串）中的模式串t，已求得前，已求得前6個字符的個字符的next函數(shù)函數(shù)值，現(xiàn)要求值，現(xiàn)要求next7的值。因為的值。因為next6=3，且，且t6t3，由，由next3=1可知，需可知，需要比較要比較t6和和t1，這相當于將模式串向右移動，由于，這相當于將模式串向右移動，由于t6t1而且而且next1=0，所，所以可得以可得next7=1；同樣，；同樣，t7=t1，得，得next8=2。第第

52、四四章章 串串求求next函數(shù)的算法如下：函數(shù)的算法如下：void GetNext(SeqString*t，int&next)/*求模式串求模式串t的的next函數(shù)值并存入數(shù)組函數(shù)值并存入數(shù)組next中中*/int i=1，j=0；next1=0；while(i(*t).len)if(j=0)|(*t).chi=(*t).chj)）+i；+j；nexti=j；else j=nextj；/*GetNext*/該算法的時間復雜度為該算法的時間復雜度為O（m）。）。第第四四章章 串串 需要注意的是：需要注意的是：（1）KMP算法僅當模式與主串之間存在許多算法僅當模式與主串之間存在許多“部分匹配部分匹

53、配”的情況的情況下才顯得比算法下才顯得比算法StrIndex效率高一些，效率高一些，KMP算法的最大特點是在整個算法的最大特點是在整個匹配過程中，指示主串的指針無需回溯，對主串僅需從頭至尾掃描一遍，匹配過程中，指示主串的指針無需回溯，對主串僅需從頭至尾掃描一遍，這對于處理諸如從外設(shè)輸入的大文件等問題很有效，可以邊讀入邊匹配，這對于處理諸如從外設(shè)輸入的大文件等問題很有效，可以邊讀入邊匹配，而無需回頭重讀。而無需回頭重讀。（2）前面定義的）前面定義的next函數(shù)在某些情況下尚有缺陷?？梢詫ι鲜龅暮瘮?shù)在某些情況下尚有缺陷?？梢詫ι鲜龅膎ext函數(shù)算法進行改進，得到計算函數(shù)算法進行改進，得到計算nex

54、t函數(shù)修正值的算法，此時，匹配函數(shù)修正值的算法，此時，匹配算法不變。算法不變。第第四四章章 串串void GetNextval(seqstring*t，int&next)/*求模式串求模式串t的的next函數(shù)修正值并存入數(shù)組函數(shù)修正值并存入數(shù)組next */int i=1，j=0；next1=0；while(i(*t).len)if(j=0)|(*t).chi=(*t).chj)+i；+j；if(*t).chi!=(*t).chj)nexti=j；else nexti=nextj；else j=nextj；/*GetNextval*/第第四四章章 串串打印機用戶鍵盤管理模塊漢字處理模塊打印管理

55、模塊字庫管理模塊顯示管理模塊通信管理模塊輸入碼機內(nèi)碼機內(nèi)碼機內(nèi)碼機內(nèi)碼機內(nèi)碼機內(nèi)碼機內(nèi)碼字模點陣碼字模點陣碼字模點陣碼機內(nèi)碼機內(nèi)碼交換碼圖 4.13漢字代碼轉(zhuǎn)換關(guān)系示意圖 一個字符串在計算機內(nèi)實際上是以機內(nèi)碼存儲的，圖一個字符串在計算機內(nèi)實際上是以機內(nèi)碼存儲的，圖4.13給出了各給出了各種漢字代碼在計算機系統(tǒng)各模塊之間的轉(zhuǎn)換關(guān)系。漢字機內(nèi)碼是在系統(tǒng)種漢字代碼在計算機系統(tǒng)各模塊之間的轉(zhuǎn)換關(guān)系。漢字機內(nèi)碼是在系統(tǒng)中存儲和處理漢字信息的代碼，是漢字系統(tǒng)體系結(jié)構(gòu)設(shè)計的基礎(chǔ)。由于中存儲和處理漢字信息的代碼，是漢字系統(tǒng)體系結(jié)構(gòu)設(shè)計的基礎(chǔ)。由于漢字機內(nèi)碼的設(shè)計方案較多，在討論由漢字組成的字符串即漢字串時，漢

56、字機內(nèi)碼的設(shè)計方案較多，在討論由漢字組成的字符串即漢字串時，需要結(jié)合漢字的機內(nèi)碼來討論其存儲結(jié)構(gòu)。需要結(jié)合漢字的機內(nèi)碼來討論其存儲結(jié)構(gòu)。4.4 漢字串漢字串第第四四章章 串串）漢字（西文）漢字 （西文）漢字 圖4.14 漢字串標識法的存儲狀態(tài)示意圖 1.采用漢字串標識法的七位碼方法采用漢字串標識法的七位碼方法 以以ASCII碼集或其子集作為基集，由兩個或兩相以上的碼集或其子集作為基集，由兩個或兩相以上的ASCII字符構(gòu)字符構(gòu)成一個漢字機內(nèi)碼。在存儲時，標識漢字串機內(nèi)碼的方法較多，有的在成一個漢字機內(nèi)碼。在存儲時，標識漢字串機內(nèi)碼的方法較多，有的在漢字串的首尾用相同的特殊字符作標記，有的用不同的

57、字符作為漢字串漢字串的首尾用相同的特殊字符作標記，有的用不同的字符作為漢字串和西文串的開始標記等等。和西文串的開始標記等等。例如，用電報碼作為漢字機內(nèi)碼，其存儲狀態(tài)如圖例如，用電報碼作為漢字機內(nèi)碼，其存儲狀態(tài)如圖4.14所示。這種所示。這種存儲方法，對于順序地從前向后逐個處理的運算操作是很適用的，但對存儲方法，對于順序地從前向后逐個處理的運算操作是很適用的，但對于某些隨機性的操作卻不很方便。例如求子串運算。于某些隨機性的操作卻不很方便。例如求子串運算。第第四四章章 串串2.采用代碼標識法的八位碼方法采用代碼標識法的八位碼方法 以我國以我國“信息交換用漢字編碼字符集信息交換用漢字編碼字符集基本集

58、基本集GB2312-80”為基礎(chǔ)，在為基礎(chǔ)，在每個漢字代碼中設(shè)標志作為漢字機內(nèi)碼。將國標交換碼每個字節(jié)的最高位每個漢字代碼中設(shè)標志作為漢字機內(nèi)碼。將國標交換碼每個字節(jié)的最高位均置均置1以形成八位碼來作為漢字機內(nèi)碼。以漢字以形成八位碼來作為漢字機內(nèi)碼。以漢字“大大”為例，其機內(nèi)碼如為例，其機內(nèi)碼如圖圖4.15所示。所示。除了采用國標碼外，還有使用國標區(qū)位碼的方案。國標區(qū)位碼和國標除了采用國標碼外，還有使用國標區(qū)位碼的方案。國標區(qū)位碼和國標碼之間可用計算公式相互轉(zhuǎn)換。圖碼之間可用計算公式相互轉(zhuǎn)換。圖4.16給出了以漢字給出了以漢字“雹雹”為例的轉(zhuǎn)換過為例的轉(zhuǎn)換過程。程。目前應(yīng)用較為廣泛的是采用國標

59、碼和區(qū)位碼進行代碼標識，形成兩字目前應(yīng)用較為廣泛的是采用國標碼和區(qū)位碼進行代碼標識，形成兩字節(jié)漢字機內(nèi)碼。這種兩字節(jié)的漢字機內(nèi)碼，可以很方便地從漢字的序數(shù)計節(jié)漢字機內(nèi)碼。這種兩字節(jié)的漢字機內(nèi)碼，可以很方便地從漢字的序數(shù)計算出該漢字在字符串中的存儲位置。算出該漢字在字符串中的存儲位置。3.采用漢字標識法的多個字節(jié)代碼采用漢字標識法的多個字節(jié)代碼 在每個漢字代碼前增加一個標識字節(jié)，就形成所謂多字節(jié)的漢字機內(nèi)在每個漢字代碼前增加一個標識字節(jié)，就形成所謂多字節(jié)的漢字機內(nèi)碼。碼。例如將漢字國標碼轉(zhuǎn)換成字母和數(shù)字表示的三個字節(jié)，然后在這三個例如將漢字國標碼轉(zhuǎn)換成字母和數(shù)字表示的三個字節(jié)，然后在這三個字節(jié)之

60、前增加一個漢字標記字節(jié)，這種標記字節(jié)可用來適應(yīng)各種不同的要字節(jié)之前增加一個漢字標記字節(jié)，這種標記字節(jié)可用來適應(yīng)各種不同的要求。但是這種機內(nèi)碼的編輯性較差，占用字節(jié)量大；一般用在要求較高的求。但是這種機內(nèi)碼的編輯性較差，占用字節(jié)量大；一般用在要求較高的軟件系統(tǒng)中或傳輸過程中作為系統(tǒng)的輔助漢字機內(nèi)碼。軟件系統(tǒng)中或傳輸過程中作為系統(tǒng)的輔助漢字機內(nèi)碼。第第四四章章 串串00110100 01110011(a)“大”的國標交換碼為347310110100 11110011(b)“大”的機內(nèi)碼為B4F3圖4.15漢字代碼標識法舉例第第四四章章 串串雹的十進制區(qū)位碼1702 數(shù)制轉(zhuǎn)換 雹的十六進制區(qū)位碼1102 加2020 雹的十六進制國標碼3122 加8080 雹的十六進制機內(nèi)碼B1A2 B 1 A 2 圖4.16 漢字區(qū)位碼轉(zhuǎn)換為機內(nèi)碼的過程舉例 000101110000001 0 1 7 0 2 000100010000001 0 1 1 0 2 001100010010001 0 3 1 2 2 101100011010001 0