數(shù)據(jù)結(jié)構(gòu)課件-(4)[151頁]

1、數(shù)據(jù)結(jié)構(gòu) 第4章串1數(shù)據(jù)結(jié)構(gòu)電子教案第4章串 數(shù)據(jù)結(jié)構(gòu) 第4章串2內(nèi)容提要串（即字符串）是一種特殊的線性表，它的每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。隨著計(jì)算機(jī)的發(fā)展，串在文字編輯、信息檢索、詞法掃描、符號(hào)處理及定理證明等許多領(lǐng)域得到越來越廣泛的應(yīng)用。很多高級(jí)語言都具有較強(qiáng)的串處理功能，C語言更是如此。 本章將簡要介紹串的有關(guān)概念和術(shù)語、詳細(xì)介紹串的順序存儲(chǔ)方法和鏈接存儲(chǔ)方法、串的基本運(yùn)算及其實(shí)現(xiàn)、串的模式匹配概念和實(shí)現(xiàn)算法，最后通過幾個(gè)簡單實(shí)例介紹串的應(yīng)用。數(shù)據(jù)結(jié)構(gòu) 第4章串3第4章 串4.1 串的基本概念4.2 串的存儲(chǔ)結(jié)構(gòu)4.3 串的基本運(yùn)算及實(shí)現(xiàn)4.4 串的模式匹配運(yùn)算4.5 串的簡單應(yīng)用舉例本章

2、小結(jié)習(xí)題4數(shù)據(jù)結(jié)構(gòu) 第4章串44.1 串的基本概念串（或字符串String）是由零個(gè)或多個(gè)字符組成的有限序列，一般記為：s =“a0a1an-1” （n0）其中，s稱為串名；用雙引號(hào)括起來的字符序列稱為串值；ai（0in1）稱為串元素，是構(gòu)成串的基本單位，它可以是英文字母、數(shù)字或其他字符；n稱為串的長度，它表示串中字符的個(gè)數(shù)。不包含任何字符的串稱為空串（Empty String），空串的長度為零。數(shù)據(jù)結(jié)構(gòu) 第4章串5為了確定串與常數(shù)、標(biāo)識(shí)符的區(qū)別，通常用定界符將串括起來，一般使用雙引號(hào)，但定界符不是串的內(nèi)容，例如， “ ” “” “#$%&” “12345678” “this is a str

3、ing” “PROGRAM”注意：上面這6個(gè)字符串均用雙引號(hào)作為定界符，其中：“ ”是包括一個(gè)空格的字符串，通常將一個(gè)或多個(gè)空格組成的串稱為空格串（Blank String）。“” 是不包括任何字符的空串。數(shù)據(jù)結(jié)構(gòu) 第4章串6當(dāng)且僅當(dāng)兩個(gè)串的長度相等且各對(duì)應(yīng)位置上的字符都相等時(shí)，則稱這兩個(gè)串是相等的。一個(gè)串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為該子串的主串。例如：“a”、“ab”、“abcd”等都是主串“abcde”的子串。通常，字符在序列中的序號(hào)稱為該字符在串中的位置，子串在主串中的位置是以子串的第一個(gè)字符在主串中的位置來表示的。例如，有兩個(gè)字符串A和B分別為：

4、 A=“This is a string” B=“is”則A是主串，B是A的子串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)的位置為3，因此，稱B在A中的序號(hào)（或位置）是3。數(shù)據(jù)結(jié)構(gòu) 第4章串7為了對(duì)字符串進(jìn)行處理，程序設(shè)計(jì)語言中常常需要使用兩種串：一種為串常量，另一種為串變量。串常量和整數(shù)常量、實(shí)數(shù)常量一樣，在程序執(zhí)行過程中，只能被引用而不能改變其值，常用直接量來表示。串變量和其它類型的變量一樣，它必須用名字來標(biāo)識(shí)，在程序執(zhí)行過程中，其值是可以改變的，但串變量與其它類型變量不同的是：不能使用賦值語句對(duì)其進(jìn)行賦值運(yùn)算。C語言規(guī)定，字符串存儲(chǔ)時(shí)，每個(gè)字符在內(nèi)存中占用一個(gè)字節(jié)，并用特殊字符0作為字符串的結(jié)束

5、標(biāo)記。因此，字符串在計(jì)算機(jī)中實(shí)際占用空間比串長多1個(gè)字符。數(shù)據(jù)結(jié)構(gòu) 第4章串84.2 串的存儲(chǔ)結(jié)構(gòu)4.2.1 串的順序存儲(chǔ)結(jié)構(gòu)4.2.2 串的鏈接存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第4章串94.2 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)方法與線性表的存儲(chǔ)方法類似。串的存儲(chǔ)結(jié)構(gòu)與計(jì)算機(jī)系統(tǒng)的具體編址方式有著十分密切的關(guān)系，它對(duì)串的處理效率影響相當(dāng)大。因此，要根據(jù)不同的情況，綜合考慮各種因素，選擇合適的方法來存儲(chǔ)串。此外，由于串是由單個(gè)字符組成的，所以存儲(chǔ)時(shí)有一些特殊的技巧。常用的串的存儲(chǔ)方式有：順序存儲(chǔ)結(jié)構(gòu)、鏈接存儲(chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)。為簡單起見，本節(jié)僅介紹字符串的兩種存儲(chǔ)方法：順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu) 第4章串10

6、4.2.1 串的順序存儲(chǔ)結(jié)構(gòu)串的順序存儲(chǔ)結(jié)構(gòu)的串簡稱為順序串。順序串是用一組地址連續(xù)的存儲(chǔ)單元依次存放串中各個(gè)字符。但不同的計(jì)算機(jī)系統(tǒng)對(duì)串的順序存儲(chǔ)方式的實(shí)現(xiàn)可能不同。在按字節(jié)存取的計(jì)算機(jī)中，由于一個(gè)字符只占用一個(gè)字節(jié)，因此，字符串中相鄰的字符是順序存放在相鄰的字節(jié)中，這樣既節(jié)約存儲(chǔ)空間，處理又很方便。如圖4.1所示。在按字存取的計(jì)算機(jī)中，串的順序存儲(chǔ)方式有兩種：非緊縮存儲(chǔ)方式和緊縮存儲(chǔ)方式數(shù)據(jù)結(jié)構(gòu) 第4章串11圖4.1 字節(jié)編址方式下字符串s的順序存儲(chǔ)方式示意圖【例4.1】設(shè)字符串s =“data structures”，請(qǐng)給出字節(jié)編址方式下字符串s的順序存儲(chǔ)結(jié)構(gòu)。【解】圖4.1是字節(jié)編址方

7、式下字符串s的順序存儲(chǔ)結(jié)構(gòu)示意圖。數(shù)據(jù)結(jié)構(gòu) 第4章串12 1、順序串的非緊縮存儲(chǔ)方式非緊縮存儲(chǔ)方式以字為單位順序存儲(chǔ)字符串的每個(gè)字符，即一個(gè)存儲(chǔ)單元只存儲(chǔ)一個(gè)字符。若字符串的長度為n，則需要n個(gè)字的存儲(chǔ)單元。如圖4.2所示?！纠?.2】假設(shè)某機(jī)器字的存儲(chǔ)單元有4個(gè)字節(jié)，那么一個(gè)字可存放4個(gè)字符。若字符串s =“data structures”，請(qǐng)給出非緊縮存儲(chǔ)方式下字符串s的順序存儲(chǔ)結(jié)構(gòu)?！窘狻繄D4.2是字編址方式下，字符串s的非緊縮存儲(chǔ)方式示意圖，圖中的陰影部分為空閑字節(jié)。數(shù)據(jù)結(jié)構(gòu) 第4章串13圖4.2 字編址方式下字符串s的非緊縮存儲(chǔ)方式示意圖 數(shù)據(jù)結(jié)構(gòu) 第4章串14 2、順序串的緊縮存儲(chǔ)

8、方式緊縮存儲(chǔ)方式以字節(jié)為單位順序存儲(chǔ)字符串的每個(gè)字符，根據(jù)機(jī)器字的長度，緊縮存儲(chǔ)方法盡可能地將多個(gè)字符存放在一個(gè)字中。假設(shè)某機(jī)器字的存儲(chǔ)單元包含有4個(gè)字節(jié)，則一個(gè)字可存放4個(gè)字符。若字符串的長度為n，則需要n/4個(gè)字的存儲(chǔ)單元。這樣，最后一個(gè)單元不一定都能完全利用上，可填充如空格之類的特殊字符或結(jié)束字符。如圖4.3所示。數(shù)據(jù)結(jié)構(gòu) 第4章串15【例4.3】假設(shè)計(jì)算機(jī)一個(gè)字的存儲(chǔ)單元為4個(gè)字節(jié)，那么一個(gè)字可以存放4個(gè)字符。若字符串s =“data structures”，請(qǐng)給出緊縮存儲(chǔ)方式下字符串s的順序存儲(chǔ)結(jié)構(gòu)?！窘狻繄D4.3是字編址方式下，字符串s的緊縮存儲(chǔ)方式示意圖。 圖4.3 字編址方式下

9、字符串s的緊縮存儲(chǔ)方式示意圖 數(shù)據(jù)結(jié)構(gòu) 第4章串163、兩種存儲(chǔ)方式的分析和比較串的緊縮存儲(chǔ)方式可以節(jié)約存儲(chǔ)空間，但處理單個(gè)字符不太方便，運(yùn)算效率較低，因?yàn)樗枰ㄙM(fèi)較多時(shí)間分離同一個(gè)字中的字符；非緊縮存儲(chǔ)方式浪費(fèi)存儲(chǔ)空間，但處理單個(gè)字符或一組連續(xù)的字符較為方便?？偟膩碚f，緊縮方式的優(yōu)勢(shì)較顯著，所以多數(shù)計(jì)算機(jī)語言和軟件都是采用緊縮方式存儲(chǔ)字符串的。這兩種方式的共同缺點(diǎn)是：插入一個(gè)字符和刪除一個(gè)字符的運(yùn)算很難，因?yàn)橐苿?dòng)其他元素，才能實(shí)現(xiàn)插入和刪除運(yùn)算。這也是順序存儲(chǔ)方法的共同缺點(diǎn)。數(shù)據(jù)結(jié)構(gòu) 第4章串17 4順序串的類型定義 在字節(jié)編址方式和非緊縮格式的字編址中，順序串可用高級(jí)語言的字符數(shù)組來實(shí)

10、現(xiàn)：#define STRMAX 64 /* 每個(gè)字符串的最大長度 */char sSTRMAX; /* 用字符數(shù)組s存儲(chǔ)串中所有字符 */在實(shí)際編程時(shí)，可在串的結(jié)尾放置一個(gè)特定的、不會(huì)出現(xiàn)在串中的字符作為串的終止符，以表示串的結(jié)束。數(shù)據(jù)結(jié)構(gòu) 第4章串18例如，C語言中以0作為串的終止符。若不設(shè)置終止符，可用一個(gè)整數(shù)slen表示字符串的實(shí)際長度，slen-1表示串中最后一個(gè)字符的存儲(chǔ)位置。順序串的類型定義與順序表類似，可定義為：#define STRMAX 64typedef struct node char dataSTRMAX; int slen; seqstring; /* seqstr

11、ing為順序串的類型 */數(shù)據(jù)結(jié)構(gòu) 第4章串194.2.2 串的鏈接存儲(chǔ)結(jié)構(gòu) 1一般的鏈接存儲(chǔ)方法采用鏈接存儲(chǔ)結(jié)構(gòu)的串稱為鏈串。把線性表的鏈接存儲(chǔ)方式應(yīng)用到字符串的存儲(chǔ)上就得到串的鏈接存儲(chǔ)結(jié)構(gòu)。鏈串與鏈表的差異僅在于其結(jié)點(diǎn)的數(shù)據(jù)域?yàn)樽址愋?。圖4.4就是一個(gè)字符串鏈接存儲(chǔ)結(jié)構(gòu)的示意圖。 數(shù)據(jù)結(jié)構(gòu) 第4章串20圖4.4 字符串的鏈接存儲(chǔ)結(jié)構(gòu)示意圖數(shù)據(jù)結(jié)構(gòu) 第4章串21串的鏈接存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：便于字符的插入和刪除運(yùn)算。串的鏈接存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：由于每個(gè)字符都需要一個(gè)結(jié)點(diǎn)來存放，使得鏈表中的結(jié)點(diǎn)數(shù)相當(dāng)多，存儲(chǔ)空間的利用率很低。此外，訪問鏈串的子串比訪問順序串的子串效率要低，它需要從頭沿著鏈表依次掃描到

12、希望的子串的開始元素，然后進(jìn)一步沿著指針獲得子串的后繼元素。數(shù)據(jù)結(jié)構(gòu) 第4章串22 2改進(jìn)的鏈接存儲(chǔ)方法改進(jìn)的鏈接存儲(chǔ)方法是：讓鏈表中每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常，將鏈表中每個(gè)結(jié)點(diǎn)數(shù)據(jù)域存儲(chǔ)的字符個(gè)數(shù)稱為結(jié)點(diǎn)的大小。假設(shè)每個(gè)結(jié)點(diǎn)存放m個(gè)字符，當(dāng)結(jié)點(diǎn)大小m1（例如m = 4）時(shí)，串的長度不一定正好是結(jié)點(diǎn)大小m的整數(shù)倍，鏈串最后一個(gè)結(jié)點(diǎn)的各個(gè)數(shù)據(jù)域不一定總能全被m個(gè)字符占滿。此時(shí)，應(yīng)在每個(gè)串的末尾還沒有被占用的數(shù)據(jù)域里加上一個(gè)不屬于字符集的特殊符號(hào)作為串的結(jié)束標(biāo)志（例如0或），以表示串的結(jié)束，見圖4.4（b）中最后一個(gè)結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu) 第4章串23 例如，圖4.4（a）所示是結(jié)點(diǎn)大小為1的鏈串，圖4.

13、4（b）所示則是結(jié)點(diǎn)大小為4的鏈串。 【例4.4】假設(shè)字符串s1=“program”，s2=“data structures”，若用結(jié)點(diǎn)大小為1的鏈串表示s1，用結(jié)點(diǎn)大小為4的鏈串表示s2，請(qǐng)分別給出s1和s2的鏈接存儲(chǔ)結(jié)構(gòu)。 【解】圖4.4所示是字符串s1和s2的鏈接存儲(chǔ)結(jié)構(gòu)示意圖。圖4.4（a）是鏈串s1，其結(jié)點(diǎn)大小m=1。若指針占用4個(gè)字節(jié)，字符數(shù)據(jù)域占用1個(gè)字節(jié)，則鏈串s1的存儲(chǔ)密度為20%。圖4.4（b）所示是結(jié)點(diǎn)大小m=4的鏈串s2，其存儲(chǔ)密度達(dá)到了50%。數(shù)據(jù)結(jié)構(gòu) 第4章串24顯然，改進(jìn)的串的鏈接存儲(chǔ)方法是順序存儲(chǔ)和鏈接存儲(chǔ)方法的折中方案。鏈串結(jié)點(diǎn)大小的選擇與順序串的格式選擇類似

14、。結(jié)點(diǎn)大小越大，存儲(chǔ)密度越大。雖然提高結(jié)點(diǎn)的大小會(huì)使其存儲(chǔ)密度增大，但是，進(jìn)行插入和刪除運(yùn)算時(shí)，可能會(huì)引起大量的字符移動(dòng)，給運(yùn)算帶來不便，因此，它適用于串基本不變的情況下使用。例如，在圖4.4（b）所示的字符串s2的第6個(gè)字符之后插入一個(gè)字符串“xxy”時(shí)，從s2第6個(gè)字符開始依次向后移動(dòng)9個(gè)字符，其結(jié)果如圖4.4（c）所示。結(jié)點(diǎn)大小越?。ㄈ缃Y(jié)點(diǎn)大小為1時(shí)），運(yùn)算處理方便，但其存儲(chǔ)密度下降。為簡單起見，我們常常把鏈串結(jié)點(diǎn)的大小規(guī)定為1。數(shù)據(jù)結(jié)構(gòu) 第4章串25 3鏈串的類型定義鏈串和單鏈表的差異僅在于其結(jié)點(diǎn)的數(shù)據(jù)域?yàn)樽址愋?。鏈串中每個(gè)結(jié)點(diǎn)有兩個(gè)域：數(shù)據(jù)域data存放一個(gè)字符或一個(gè)字符串（對(duì)于結(jié)

15、點(diǎn)大小不為1的鏈串），指針域next存放指向下一個(gè)結(jié)點(diǎn)的指針。一個(gè)鏈串則由頭指針head惟一確定。數(shù)據(jù)結(jié)構(gòu) 第4章串26對(duì)于結(jié)點(diǎn)大小為1的鏈串，其類型定義如下：/* 鏈串結(jié)點(diǎn)大小為1的結(jié)點(diǎn)類型 */typedef struct strnode char data; /* data為結(jié)點(diǎn)的數(shù)據(jù)域 */ struct strnode *next; /* next為指針域 */ linkstring; /* linkstring為鏈串類型 */linkstring *head ;/* head是鏈串的頭指針 */數(shù)據(jù)結(jié)構(gòu) 第4章串27對(duì)于結(jié)點(diǎn)大小不為1的鏈串，其類型定義為： /* NODESIZE為

16、鏈串結(jié)點(diǎn)的大小，由用戶自定義 */#define NODESIZE 4typedef struct strnodem char dataNODESIZE; /* data為結(jié)點(diǎn)數(shù)據(jù)域 */ struct strnodem *next;/* next為指針域 */linkstringnode;/*linkstringnode是結(jié)點(diǎn)大小為m的鏈串類型 */數(shù)據(jù)結(jié)構(gòu) 第4章串28 4.3 串的基本運(yùn)算及實(shí)現(xiàn)4.3.1 串的基本運(yùn)算4.3.2 順序串上基本運(yùn)算的實(shí)現(xiàn)4.3.3 鏈串上基本運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu) 第4章串294.3.1 串的基本運(yùn)算 假設(shè)s1=“a1a2an”，s2=“b1b2bm”，其中1

17、mn。 （1）串賦值strassign(s, t)：將一個(gè)串常量或串變量t賦給串變量s。（2）求串長strlen(s)：求s串的長度，即統(tǒng)計(jì)串中字符個(gè)數(shù)，函數(shù)返回一個(gè)整數(shù)。（3）串連接strcat(s1, s2)：將兩個(gè)串首尾連接在一起形成一個(gè)新串，例如，s=strcat(s1, s2)，則s=“a1a2anb1b2bm”。數(shù)據(jù)結(jié)構(gòu) 第4章串30（4）串比較strcmp(s1, s2)：比較兩個(gè)字符串的大小。若s1s2，則函數(shù)返回一個(gè)負(fù)數(shù)或1；若s1s2，則函數(shù)返回一個(gè)正數(shù)或1；若s1=s2，則函數(shù)返回0。（5）串插入insert(s1, i, s2)：在串s1第i個(gè)字符位置之后插入字符串s2

18、，例如，執(zhí)行insert(s2, 3,“THIS”)后，s2=“b1b2b3THISb4bm”。（6）串刪除delete(s, i, j)：從串s第i個(gè)字符開始，連續(xù)刪除j個(gè)字符。若不足j個(gè)字符，則刪除到s的最后一個(gè)字符。例如，s=“good lucky to you!”，執(zhí)行delete(s, 6, 6)后，s=“good to you！”。數(shù)據(jù)結(jié)構(gòu) 第4章串31（7）串替換replace(s1, i, j, s2)：用串s2替換串s1中從第i個(gè)字符開始的連續(xù)j個(gè)字符，例如，執(zhí)行replace(s1, 2, 3,“abc”)后，則串s1=“a1abca5a6an”。（8）串復(fù)制strcpy(

19、s1, s2)：將s2的串值復(fù)制到串s1中。（9）取子串substr(s1, i, j, s2)：從串s1第i個(gè)字符開始，取連續(xù)j個(gè)字符構(gòu)成一個(gè)新串s2，其中，1istrlen(s1)，1jstrlen(s1)i+1。例如，s=“abcdefgh”，則substr(s, 3, 4)=“cdef”。（10）子串定位index(s1, s2, i)：其功能是求子串在主串中的位置。在主串中查找是否有與子串匹配的序列，若有，則給出子串在主串中首次出現(xiàn)的位置；若無，則返回0。數(shù)據(jù)結(jié)構(gòu) 第4章串324.3.2 順序串上基本運(yùn)算的實(shí)現(xiàn)（1）順序串的賦值函數(shù)S_strassign(s)：將從鍵盤輸入的一串字符

20、變量賦給串變量s。/* 順序串建立函數(shù)，從鍵盤輸入字符串賦給順序串變量s */void S_strassign(s)seqstring *s; char c; int j=1; printf(nntt請(qǐng)輸入一個(gè)字符串，以#作為結(jié)束: ); scanf(%c, &c); while(c!=# &jdataj=c; j+; scanf(%c, &c); s-dataj=0; s-slen=j-1; /* S_STRASSIGN */數(shù)據(jù)結(jié)構(gòu) 第4章串33（2）求順序串的長度函數(shù)S_strlen(s)：求順序串s的長度。/* 求順序串長度函數(shù) */int S_strlen(s)seqstring *

21、s; printf(nt順序串長度length=%dn, s-slen); return (s-slen);/* 返回順序串的長度 */* S_STRLEN */數(shù)據(jù)結(jié)構(gòu) 第4章串34（3）順序串的比較函數(shù)S_strcmp(s1, s2)：比較兩個(gè)順序串的大小。若s1=s2，則函數(shù)返回0；若s1s2，則函數(shù)返回正數(shù)；若s1s2，則函數(shù)返回負(fù)數(shù)。 /* 兩個(gè)順序串比較函數(shù)，函數(shù)返回值為0、正數(shù)或負(fù)數(shù) */int S_strcmp(s1, s2) seqstring *s1, *s2; int i=0, flag=1, m=0, n1, n2; n1=S_strlen(s1); n2=S_strl

22、en(s2); while (flag=1)&(i=n1)&(idatai!=s2-datai) flag=0; if(flag=1)&(in1)&(in2) m=0; else m=s1-datai-s2-datai; return(m);/* S_STRCMP */數(shù)據(jù)結(jié)構(gòu) 第4章串35（4）順序串的連接函數(shù)S_strcat(s1, s2)：將順序串s2連到s1之后形成一個(gè)新串。/* 順序串連接函數(shù)，將順序串s2與s1連成一個(gè)新串 */int S_strcat(s1, s2)seqstring *s1, *s2; int i, j, k; i=S_strlen(s1); j=S_strle

23、n(s2); if(i+j)MAX) return(1); for (k=1;kdatai+k=s2-datak; s1-datai+j+1=0; s1-slen=i+j; printf(nt兩個(gè)順序串連接后的新串長度length=%dn, s1-slen); return(0);/* S_STRCAT */數(shù)據(jù)結(jié)構(gòu) 第4章串36（5）順序串的插入函數(shù)S_strinsert(s, i, t)：將字符串t常量插到s串中，從s串第i個(gè)字符位置開始插入。/* 順序串的插入函數(shù)，從s串第i個(gè)位置開始插入t串 */int S_strinsert(s, i, t)seqstring *s, *t; int

24、 i; int ns, nt, k, j; ns=s-slen; nt=t-slen; if(ins+1|ns+ntMAX) return(1); k=ns+nt+1; for(j=ns+1; j=i; k-, j-) s-datak=s-dataj; for (k=1; kdata!=0; k+) s-datai+k-1=t-datak; s-slen=ns+nt; return(0); /* S_STRINSERT */數(shù)據(jù)結(jié)構(gòu) 第4章串37（6）順序串的刪除函數(shù)S_strdelete(s, t)：從順序串s中刪除與串t相同的子串。 /* 順序串刪除函數(shù)，從順序串s中刪除與t串相同的子串

25、*/int S_strdelete(s, t)seqstring *s, *t; int ns, nt, k=0, ks=0, kt=0, j, flag; ns=s-slen;nt=t-slen; if (ntns | ns0 | nt0 ) return (1); while (k=ns)&(ktdataks+=t-datakt+) if (s-dataks!=t-datakt) flag=0; /* while */ 數(shù)據(jù)結(jié)構(gòu) 第4章串38/* 順序串刪除函數(shù)，從順序串s中刪除與t串相同的子串 */if (ktnt)&(k=ns) for(j=k; jdataj=s-dataj+nt;

26、s-slen=ns-nt; s-datas-slen+1=0; return (0); /* IF */* 刪除成功，函數(shù)返回成功信息0 */ else return(1);/* 刪除失敗，返回錯(cuò)誤信息1 */* S_STRDELETE */數(shù)據(jù)結(jié)構(gòu) 第4章串39（7）求順序串的子串函數(shù)S_substr(s, i, k, t)：從順序串s中第i個(gè)字符開始連續(xù)取k個(gè)字符存放到順序存儲(chǔ)的子串t中。/* 從順序串s第i個(gè)字符開始取k個(gè)子符放到順序串t中 */int S_substr(s, i, k, t)seqstring *s, *t; int i, k; int m=s-slen; if (im

27、) return (1); if (km+1) return (1); for(m=1;mdatam=s-datai+m-1; t-datam=0; t-slen=k; return (0);/* S_SUBSTR */數(shù)據(jù)結(jié)構(gòu) 第4章串404.3.3 鏈串上基本運(yùn)算的實(shí)現(xiàn)（1）鏈串賦值函數(shù)L_strassign（s, t）：將一個(gè)字符串常量t賦給鏈串s，函數(shù)返回指向鏈串s的頭指針。/* 將一個(gè)串常量t賦給鏈串s，返回鏈串s頭指針 */linkstring *L_strassign(s, t)linkstring *s; char t ; int k=0; linkstring *r, *p;

28、 s=(linkstring*)malloc(LEN); s-data=# ; r=s;/* r為指向隊(duì)尾指針 */ while(tk!=0)/* 將字符串常量t依次賦給鏈串s */ p=(linkstring *)malloc(LEN); p-data=tk+; r-next=p; r=p; r-next=NULL; return(s);/* L_STRASSIGN */數(shù)據(jù)結(jié)構(gòu) 第4章串41（2）求鏈串長度函數(shù)L_strlen(head)：求帶頭結(jié)點(diǎn)鏈串head的長度。/* 求帶頭結(jié)點(diǎn)鏈串head的長度函數(shù) */int L_strlen(head)linkstring *head; lin

29、kstring *p; int i; p=head-next; /* 指向鏈串head的首結(jié)點(diǎn) */ for(i=1;p!=NULL;i+) /* 統(tǒng)計(jì)鏈串中結(jié)點(diǎn)的個(gè)數(shù) */ p=p-next; printf(nt該串的長度為%2d, i); return(i); /* 函數(shù)返回帶頭結(jié)點(diǎn)鏈串head長度 */* L_STRLEN */數(shù)據(jù)結(jié)構(gòu) 第4章串42（3）鏈串比較函數(shù)L_strcmp(head1, head2)：將兩個(gè)帶頭結(jié)點(diǎn)鏈串進(jìn)行比較。若兩串相等，則函數(shù)返回0；若前串大于后串，則函數(shù)返回1；若前串小于后串，則返回1。/* 將兩個(gè)鏈串進(jìn)行比較，函數(shù)返回1、0、或1-1 */int L_

30、strcmp(head1, head2)linkstring *head1, *head2; linkstring *p1, *p2; int k=0;/* k為鏈串是否相等的標(biāo)志 */ p1=head1;/* 指向head1的首結(jié)點(diǎn) */ p2=head2;/* 指向head2的首結(jié)點(diǎn) */ while(p1!=NULL)&(p2!=NULL)&(k=0) p1=p1-next; p2=p2-next; 數(shù)據(jù)結(jié)構(gòu) 第4章串43/* 將兩個(gè)鏈串進(jìn)行比較，函數(shù)返回-1 、0、或1-2 */if(p1-data=p2-data) k=0; /* 兩串相等，k=0 */if(p1-datap2-da

31、ta) k=1; /* 前串大于后串，k=1 */if(p1-datadata) k=-1;/* 后串大于前串，k=-1*/if (p1=NULL&p2=NULL&k=0) k=0; /* 兩個(gè)鏈串相等，函數(shù)返回0 */if (p1-datap2-data) k=1; /* 前串大于后串，函數(shù)返回1 */if (p1-datadata) k=-1; /* 前串小于后串，函數(shù)返回-1 */return(k);/* L_STRCMP */數(shù)據(jù)結(jié)構(gòu) 第4章串44（4）兩個(gè)鏈串的連接函數(shù)L_strcat(heads, headt)：利用原鏈串空間，將兩個(gè)帶頭結(jié)點(diǎn)鏈串進(jìn)行連接。要求將鏈串t連接到鏈串s后

32、面，函數(shù)返回連接后的新鏈串頭指針。/* 連接兩個(gè)帶頭結(jié)點(diǎn)鏈串返回新鏈串頭結(jié)點(diǎn) */linkstring *L_strcat(heads, headt)linkstring *heads, *headt; linkstring *head, *sp; head=heads; if(heads=NULL) head=headt; else sp=head; while(sp-next!=NULL) sp=sp-next; sp-next=headt-next; return(head);/* L_STRCAT */數(shù)據(jù)結(jié)構(gòu) 第4章串45（5）鏈串的插入函數(shù)L_strinsert(head, i,

33、s)：在鏈串給定位置i處插入字符串s。/* 在鏈串head給定位置i處插入字符串s5-1 */linkstring *L_strinsert(head, i, s)linkstring *head; int i; char s; linkstring *p, *r, *qr; int m=0, j=0; m=L_strlen(head)-i ; if (head=NULL)|(mnext;數(shù)據(jù)結(jié)構(gòu) 第4章串46/* 在鏈串head給定位置i處插入字符串s5-2 */ while(qr!=NULL & mnext; for(j=0; sj!=#; j+) p=(linkstring *)mall

34、oc(LEN); p-data=sj; r-next=p; r=p; r-next=qr; return(head);/* 返回插入后的新鏈串頭指針 */* L_STRINSERT */數(shù)據(jù)結(jié)構(gòu) 第4章串47（6）鏈串的刪除函數(shù)L_strdelete(head, i, n)：從鏈串給定位置i開始連續(xù)刪n個(gè)字符。/* 從鏈串給定位置i連續(xù)刪除n個(gè)字符6-1 */linkstring *L_strdelete(head, i, n)linkstring *head; int i, n; linkstring *q, *r; int m=0; m=L_strlen(head)-i-n+1 ; if

35、(head=NULL)|(mnext; 數(shù)據(jù)結(jié)構(gòu) 第4章串48 /* 從鏈串給定位置i連續(xù)刪除n個(gè)字符6-2 */ m=1; while(q!=NULL & mnext; /* q為r的后繼結(jié)點(diǎn) */ m=0; r=q; /* r是指向第i個(gè)結(jié)點(diǎn)的指針 */ while(q!=NULL & mnext; /* 將q指針后移一個(gè)字符 * r-next=q-next; /* q指針要?jiǎng)h除的字符*/return(head);/* L_STRDELETE */數(shù)據(jù)結(jié)構(gòu) 第4章串49（7）求鏈串的子串函數(shù)L_substr (s, i, j, t)：從鏈串s中第i個(gè)字符開始，取連續(xù)j個(gè)子符存放到鏈串t中。

36、/*從鏈串s第i個(gè)字符開始取j個(gè)字符存到子串t中7-1 */int L_substr(s, i, j, t)linkstring *s, *t; int i, j; linkstring *p, *q, *r; int m; if(i(m=L_strlen(s) return (1); if (jm+1) return (1); t=(linkstring *)malloc(LEN); t-data=#; t-next=NULL; p=s-next; /* 從鏈串中查找子串的開始位置i */ 數(shù)據(jù)結(jié)構(gòu) 第4章串50/*從鏈串s第i個(gè)字符開始取j個(gè)字符存到子串t中7-2 */ for (m=1;

37、mnext; /* 循環(huán)結(jié)束，p指向取子串始結(jié)點(diǎn)*/r=t; m=1;/* r指向子串的尾結(jié)點(diǎn)，m統(tǒng)計(jì)字符個(gè)數(shù) */while (mdata=p-data; r-next=q; /* 將子串新結(jié)點(diǎn)連接到鏈串結(jié)尾處*/ r=q;/* r指向子串新的尾結(jié)點(diǎn) */ p=p-next; /* 將主串結(jié)點(diǎn)的指針向后移 */ m+; /* WHILE */ r-next=NULL; return (0);/* L_SUBSTR */數(shù)據(jù)結(jié)構(gòu) 第4章串514.4 串的模式匹配運(yùn)算4.4.1 BF模式匹配算法4.4.2 BM模式匹配算法4.4.3 KMP模式匹配算法數(shù)據(jù)結(jié)構(gòu) 第4章串524.4 串的模式匹配運(yùn)

38、算 子串定位運(yùn)算稱為串的模式匹配（Pattern Matching）或串匹配（String Matching）運(yùn)算，是串處理中最重要的運(yùn)算之一，應(yīng)用非常廣泛。 例如，在文本編輯程序中，我們經(jīng)常要查找某個(gè)特定單詞在文本中出現(xiàn)的位置。顯然，解決該問題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。數(shù)據(jù)結(jié)構(gòu) 第4章串53假設(shè)有兩個(gè)串s和t，且 s=“s0s1s2sn1” t=“t0t1t2tm1” 式中，0mn（通常有mn）。子串定位就是要在主串s中找出一個(gè)與子串t相同的子串。通常，我們把主串s稱為目標(biāo)串，把子串t稱為模式串，把從目標(biāo)串s中查找t子串的定位過程稱為串的“模式匹配”。模式匹配有兩種結(jié)果：

39、若從主串s中找到模式為t的子串，則返回t子串在s中的起始位置。當(dāng)s中有多個(gè)模式為t的子串時(shí)，通常只找出第一個(gè)子串的起始位置，這種情況稱為匹配成功，否則稱為匹配失敗。數(shù)據(jù)結(jié)構(gòu) 第4章串54模式匹配運(yùn)算可用一個(gè)函數(shù)來實(shí)現(xiàn)，前面介紹的求子串序號(hào)就是一個(gè)實(shí)現(xiàn)模式匹配運(yùn)算的函數(shù)。串的匹配運(yùn)算是一個(gè)比較復(fù)雜的串運(yùn)算，許多人對(duì)此提出了多個(gè)效率各不相同的模式匹配算法。這里僅介紹BF模式匹配算法及基于BF算法的兩種改進(jìn)算法BM模式匹配算法和KMP模式匹配算法。數(shù)據(jù)結(jié)構(gòu) 第4章串554.4.1 BF模式匹配算法1BF算法的基本思想一種最簡單的模式匹配算法是布魯特-福斯（Brute-Froce）算法，簡稱為樸素的模

40、式匹配算法或BF算法。數(shù)據(jù)結(jié)構(gòu) 第4章串56樸素的模式匹配的基本思想是：用模式串t=“t0t1t2tm1”中的字符依次與目標(biāo)串s=“s0s1s2sn1”中的字符進(jìn)行比較。從目標(biāo)串s的第一個(gè)字符開始與模式串t的第一個(gè)字符進(jìn)行比較，若相等，則逐個(gè)比較后續(xù)字符；否則，從目標(biāo)串s第二個(gè)字符開始重新與模式串t的第一個(gè)字符進(jìn)行比較。其余類推，若模式串t的每個(gè)字符依次與目標(biāo)串s中一個(gè)連續(xù)的字符序列相等，則稱匹配成功，函數(shù)返回模式串t中第一個(gè)字符在目標(biāo)串s的位置；若將s的所有字符都檢測(cè)完了，還找不到與t相同的子串，則稱匹配失敗，函數(shù)返回0。數(shù)據(jù)結(jié)構(gòu) 第4章串57【例4.5】假設(shè)目標(biāo)串s=“abbaba”，模式

41、串t=“aba”。若用指針I(yè) 指示目標(biāo)串s當(dāng)前待比較的字符位置，用指針j 指示模式串t當(dāng)前待比較的字符位置，請(qǐng)給出BF算法的模式匹配過程?！窘狻繄D4.5是采用BF算法進(jìn)行模式匹配的過程示意圖。數(shù)據(jù)結(jié)構(gòu) 第4章串58圖4.5 BF算法的模式匹配過程示意圖數(shù)據(jù)結(jié)構(gòu) 第4章串59根據(jù)BF算法的匹配過程，我們可以推知以下兩點(diǎn)。 若前k1趟比較中未匹配成功，則第k（k1）趟匹配是從s中第k個(gè)字符sk1開始與t中第一個(gè)字符t0進(jìn)行比較的。 假設(shè)某一趟匹配有sitj，其中0in1，0jm1，ji，則應(yīng)有si1=tj1，sij+1=t1，sij=t0。再由可知，下一趟比較是從目標(biāo)串s的第sij+1個(gè)字符和模式

42、串t的第一個(gè)字符t0開始進(jìn)行比較的。數(shù)據(jù)結(jié)構(gòu) 第4章串60因此，BF算法中某一次比較狀態(tài)和下一次比較位置的一般性過程如圖4.6所示。圖4.6 BF模式匹配的一般過程示意圖數(shù)據(jù)結(jié)構(gòu) 第4章串612順序串的BF模式匹配算法實(shí)現(xiàn)/* 順序串模式匹配運(yùn)算求模式t在目標(biāo)串s首次出現(xiàn)位置 */int S_bfindex(s, t)seqstring *s, *t;int i=0, j=0; /* 模式t和目標(biāo)串s初始位置為0 */ int n=s-slen, m=t-slen; while(in)&(jdatai=t-dataj)/* 兩個(gè)字符相等 i+; j+; else /* 匹配失敗，指針i回溯，進(jìn)

43、行下趟匹配 */ i=i-j+1; j=0; /* 從模式t第一個(gè)字符開始進(jìn)行下一趟匹配*/ if(j=m) return(i-m); else return(-1); /* S_BFINDEX */數(shù)據(jù)結(jié)構(gòu) 第4章串62 上述算法中，s-slen和t-slen分別表示串s和t的長度。當(dāng)匹配成功時(shí)j=m，i值也相應(yīng)地對(duì)應(yīng)于tm1的后一個(gè)位置，故返回的序號(hào)是im而不是im+1。 【算法分析】在最好的情況下，每趟不成功的匹配都是在模式t的第一個(gè)字符與串s中相應(yīng)的字符比較時(shí)就不相等。數(shù)據(jù)結(jié)構(gòu) 第4章串63 假設(shè)s從第i個(gè)位置開始與t串匹配成功，那么在前面i1趟匹配中字符比較次數(shù)總共是i1次，第i趟匹

44、配成功時(shí)，字符的比較次數(shù)為m次，因此，總的比較次數(shù)是i1+m。由于匹配成功時(shí)，s的開始位置只能是1nm+1。若對(duì)這nm+1個(gè)開始位置，匹配成功的概率為Pi且都是相等的，則在最好的情況下，匹配成功的平均比較次數(shù)Cmin為：故最好的情況下算法的平均時(shí)間復(fù)雜度是O(n+m)。 數(shù)據(jù)結(jié)構(gòu) 第4章串64在最壞的情況下，每趟匹配失敗時(shí)都是在模式串t的最后一個(gè)字符與s中相應(yīng)的字符比較后才不相等，新的一趟匹配開始前，指針i要回溯到im+2的位置上。在這種情況下，若第i趟匹配成功，在前面i1趟不成功的匹配中，每一趟匹配失敗時(shí)都要比較m次，因此，字符比較次數(shù)總共是(i1)m次，第i趟匹配成功時(shí)也比較了m次，所以總

45、共要比較mi次。數(shù)據(jù)結(jié)構(gòu) 第4章串65若對(duì)這nm+1個(gè)開始位置，匹配成功的概率為Pi且都是相等的，則在最壞的情況下，匹配成功的平均比較次數(shù)Cmax 為：若nm，則在最壞的情況下該算法的時(shí)間復(fù)雜度是O(mn)，即等于兩串長度乘積的數(shù)量級(jí)。數(shù)據(jù)結(jié)構(gòu) 第4章串66例如，兩個(gè)字符串s和t分別為：s =“gggggggga”（n=9）t =“gggb”（m=4） 由于t的前3個(gè)字符可在s中找到匹配，而t的第4個(gè)字符在s中找不到匹配，因此，每一趟匹配失敗時(shí)都要比較m=4次，然后再將指針i移到s的第2個(gè)字符，結(jié)果是t的前3個(gè)字符在s中找到匹配，而第4個(gè)字符在s中找不到匹配。繼續(xù)比較，比較的總趟數(shù)為nm+1=

46、94+1=6，而每一趟都要比較4次（m=4），因此，總的比較次數(shù)為4(94+1)=24。數(shù)據(jù)結(jié)構(gòu) 第4章串673鏈串的BF模式匹配算法實(shí)現(xiàn)/* 在鏈串上求模式串t在目標(biāo)串s中首次出現(xiàn)的位置1 */linkstring *L_bfindex(s, t)linkstring *s, *t; /* s, t是帶頭結(jié)點(diǎn)的鏈串 */ linkstring *first, *sp, *tp; if(s=NULL)|(t=NULL) return(NULL); /* 主串或模式為空，匹配失敗返回0 */ first=s-next; /* first是指向串s起始位置的指針 */ sp=s-next; tp=

47、t-next; /* 串s和串t從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較*/數(shù)據(jù)結(jié)構(gòu) 第4章串68 /* 在鏈串上求模式串t在目標(biāo)串s中首次出現(xiàn)的位置1 */ while(sp!= NULL)&(tp!= NULL) if(sp-data=tp-data) /* 若兩個(gè)結(jié)點(diǎn)的字符相等，則繼續(xù)比較 */ sp=sp-next; tp=tp-next; else /* 匹配失敗，串s回溯，與串t從頭開始比較 */ first=first-next; sp=first; tp=t-next; if(tp=NULL) return(first); /* 匹配成功，返回first所指子串開始位置 */ else ret

48、urn(NULL); /* 匹配失敗，返回空指針NULL */* L_BFINDEX */【算法分析】該算法的時(shí)間復(fù)雜度是O(mn)，它與順序串上BF算法的時(shí)間復(fù)雜度相同。數(shù)據(jù)結(jié)構(gòu) 第4章串694.4.2 BM模式匹配算法1BM算法的基本思想 該算法對(duì)BF算法的匹配過程做了兩點(diǎn)改進(jìn)：其一是首先檢查模式串t的首尾兩個(gè)字符與主串s中對(duì)應(yīng)的字符是否匹配，若這兩對(duì)字符匹配了再檢查中間的字符；其二是在下一輪比較中，當(dāng)主串s中余下的字符個(gè)數(shù)已經(jīng)小于模式串t的長度時(shí)即停止運(yùn)算，因?yàn)椋谶@種情況下匹配不可能成功。 改進(jìn)的BM算法利用主串中字符在模式串中出現(xiàn)的位置和長度等信息，減少每一趟的比較次數(shù)，從而大大提高

49、算法的效率。數(shù)據(jù)結(jié)構(gòu) 第4章串70 下面通過一個(gè)實(shí)例說明BM算法的匹配過程。 【例4.6】假設(shè)目標(biāo)串AA=“dttabase”，模式串BB=“taba”。若利用BM算法進(jìn)行模式匹配，請(qǐng)給出該算法在鏈接存儲(chǔ)結(jié)構(gòu)上進(jìn)行模式匹配的過程示意圖?！窘狻繄D4.7是采用BM算法進(jìn)行模式匹配時(shí)，其中某一趟模式匹配過程的示意圖。 在圖4.7中，AA為目標(biāo)串，BB為模式串。pAA和pBB分別指向AA和BB中當(dāng)前正在進(jìn)行比較的字符，而qAA和qBB分別指向目標(biāo)串AA和模式串BB的最后一個(gè)字符，k是指向目標(biāo)串AA進(jìn)行新一輪字符比較的起始位置指針。數(shù)據(jù)結(jié)構(gòu) 第4章串71圖4.7 BM算法的模式匹配過程示意圖數(shù)據(jù)結(jié)構(gòu) 第

50、4章串72 在第1趟匹配過程中，由于BB的第1個(gè)字符t與AA的第1個(gè)字符d不同，則停止檢驗(yàn)，k和qAA分別向后移動(dòng)一個(gè)結(jié)點(diǎn)，且使得pAA=k；在第2趟匹配中，因?yàn)锽B的最后一個(gè)字符a與AA的第5個(gè)字符b不同（b是此趟匹配中AA的最后一個(gè)字符），則停止檢驗(yàn)，k和qAA再分別后移一個(gè)結(jié)點(diǎn)，且使得pAA=k；在第3趟匹配中，這次BB的第1個(gè)字符t與AA的第3個(gè)字符t相同，BB的最后一個(gè)字符a與AA的第6個(gè)字符a也相同，因此pBB和pAA分別逐結(jié)點(diǎn)后移檢查其他字符是否匹配，這一趟各個(gè)字符均能匹配，故匹配成功，此時(shí)，k值指向AA的第3個(gè)結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu) 第4章串73圖4.7就是在第3趟匹配過程中，當(dāng)pAA

51、和pBB分別指向BB的第2個(gè)結(jié)點(diǎn)和AA的第4個(gè)結(jié)點(diǎn)時(shí)，二者字符進(jìn)行比較的情況。顯然，改進(jìn)的模式匹配算法比BF算法運(yùn)算速度要快。【算法分析】可以證明，改進(jìn)的BM算法就平均情況來說會(huì)加快處理速度，但在輸入數(shù)據(jù)最不利的情況下，其時(shí)間復(fù)雜度仍然是O(mn)。數(shù)據(jù)結(jié)構(gòu) 第4章串74 2鏈串上BM模式匹配算法實(shí)現(xiàn)/* 在鏈串上求模式BB在目標(biāo)串AA中首次出現(xiàn)的位置-1 */linkstring *L_bmindex(ha, hb)linkstring * ha, *hb ; linkstring *pa,*pb, *qa,*qb,*ka=NULL, *first=NULL; int i, lb=1; if

52、 (ha=NULL)|(hb=NULL) return(NULL);/* 若為空串，則返回NULL */ first=ha-next;/* first是指向AA的起始比較位置 */ qb=hb-next;/* qb首先指向BB的第1個(gè)結(jié)點(diǎn) */ while (qb-next!=NULL)/* 查找BB末端結(jié)點(diǎn) */ qb=qb-next;/* qb為指向模式串BB末端結(jié)點(diǎn) */ lb=lb+1;/* 循環(huán)結(jié)束時(shí)，lb為BB長度 */ /* WHILE1 */數(shù)據(jù)結(jié)構(gòu) 第4章串75 /* 在鏈串上求模式BB在目標(biāo)串AA中首次出現(xiàn)的位置-2*/ qa=ha-next;/* qa首先指向AA的第1個(gè)

53、結(jié)點(diǎn) */ for(i=2; ilb，則循環(huán)結(jié)束qa指向AA第lb個(gè)結(jié)點(diǎn) */ if(qa!=NULL) qa=qa-next; /* 若lanext; pa=first; if(qa-data=qb-data) /* 若首末兩端字符相等，則比較中間的字符 */數(shù)據(jù)結(jié)構(gòu) 第4章串76 /* 在鏈串上求模式BB在目標(biāo)串AA中首次出現(xiàn)的位置-3*/ while(pb!=qb) & (pa-data=pb-data) /* 若首末兩端字符相等，則從頭比較 */ pa=pa-next; pb=pb-next; /* WHILE3 */ if(pb=qb) ka=first; /* IF */ firs

54、t=first-next; /* 本趟匹配失敗，回溯，繼續(xù)下一趟比較 */ qa=qa-next; /* WHILE2 */if (ka!=NULL) return(ka);else return(NULL);/* L_BMINDEX */數(shù)據(jù)結(jié)構(gòu) 第4章串774.4.3 KMP模式匹配算法1KMP算法的基本思想另一種改進(jìn)的模式匹配算法是克努特（Knuth）、莫里斯（Morris）和普拉特（Pratt）同時(shí)發(fā)現(xiàn)的，簡稱為KMP算法。KMP算法較BF算法有很大改進(jìn)，主要是在每一趟匹配過程中出現(xiàn)字符不等時(shí)，不需要回溯指針i，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，

55、再繼續(xù)進(jìn)行比較。KMP算法把模式匹配的時(shí)間復(fù)雜度控制在O(m+n)數(shù)量級(jí)上，從而使算法效率有了一定的提高。 數(shù)據(jù)結(jié)構(gòu) 第4章串78【例4.7】假設(shè)主串 s=“ababcabcacbab”，模式串 t=“abcac”，請(qǐng)給出KMP算法進(jìn)行匹配的過程。【解】圖4.8就是采用KMP算法進(jìn)行模式匹配的過程示意圖。數(shù)據(jù)結(jié)構(gòu) 第4章串79圖4.8 KMP算法的模式匹配過程示例數(shù)據(jù)結(jié)構(gòu) 第4章串80從圖4.8中我們可以看出，第1趟匹配過程中，當(dāng)i=2，j=2時(shí)出現(xiàn)“失配”，此時(shí)指針i不動(dòng)，僅將模式t向右滑動(dòng)2個(gè)字符的位置繼續(xù)進(jìn)行i=2，j=0時(shí)的字符比較。第2趟匹配是從i=2，j=0開始的，當(dāng)i=6，j=4

56、時(shí)出現(xiàn)“失配”。經(jīng)仔細(xì)觀察可發(fā)現(xiàn)，主串第4、5和6個(gè)字符分別是“b”、“c”和“a”，由于模式t的第1個(gè)字符是“a”，因此，模式t無須再和這3個(gè)字符進(jìn)行比較，故i=3和j=0，i=4和j=0及i=5和j=0這3次比較不需要進(jìn)行，此時(shí)i指針仍然不動(dòng)，再將模式t向右滑動(dòng)3個(gè)字符繼續(xù)進(jìn)行i=6，j=1時(shí)的字符比較。因此，第3趟匹配從i=6，j=1開始比較，當(dāng)i=10，j=5時(shí)匹配成功。由此可見，在整個(gè)匹配過程中，i指針沒有回溯。數(shù)據(jù)結(jié)構(gòu) 第4章串81分析BF模式匹配算法的執(zhí)行過程可以發(fā)現(xiàn)，造成算法速度慢的原因是回溯，而這些回溯并不是必要的。這可以分成以下兩種情況進(jìn)行討論。第1種情況。參見圖4.5中主

57、串s=“abbaba”和模式串t=“aba”的模式匹配過程中第1次回溯。當(dāng)s0=t0，s1=t1，s2t2時(shí)，算法中取i=1，j=0，使主串s的下標(biāo)i值回溯一個(gè)位置，比較s1和t0。但是因?yàn)閠1t0，所以一定有s1t0。另外，因?yàn)閠0=t2，s0=t0，s2t2，則一定可以推出s2t0，所以也不必取i=2，j=0比較s2和t0?？芍苯釉诘?次比較時(shí)取i=3，j=0比較s3和t0。這樣，在模式匹配過程中，主串指針i可以不必回溯。數(shù)據(jù)結(jié)構(gòu) 第4章串82第2種情況。假設(shè)主串s=“abacabab”，模式串t=“abab”。第1次匹配過程如圖4.9（a）所示。此時(shí)，不必從i=1，j=0重新開始第2次匹

58、配。因?yàn)閠0t1，s1=t1，必有s1t0；又因?yàn)閠0=t2，s2=t2，所以必有s2=t0。因此，第2次匹配可直接從i=3，j=1開始，比較s3和t1，匹配過程如圖4.9（b）所示?？偨Y(jié)以上兩種情況可以發(fā)現(xiàn)，一旦si和tj不相等，主串s的指針可不必回溯，主串的si（或si+1）可直接與模式串的tk（0kj）進(jìn)行比較，k的確定與主串s并沒有關(guān)系，而只與模式串t本身的構(gòu)成有關(guān)，即從模式串t本身就可以求出k值。數(shù)據(jù)結(jié)構(gòu) 第4章串83圖4.9 KMP模式匹配的一個(gè)示例數(shù)據(jù)結(jié)構(gòu) 第4章串84現(xiàn)在我們討論一般情況。假設(shè)主串 s=“s0s1s2sn1”，模式串 t=“t0t1t2tm1”，為了實(shí)現(xiàn)KMP算

59、法，需要解決的問題是：當(dāng)匹配過程產(chǎn)生失配時(shí)（即sitj），模式串“向右滑動(dòng)”的距離有多遠(yuǎn)。換句話說，當(dāng)主串中第i個(gè)字符與模式中第j個(gè)字符“失配”時(shí)，主串中第i個(gè)字符（i指針不回溯）應(yīng)與模式中哪個(gè)字符再比較？數(shù)據(jù)結(jié)構(gòu) 第4章串85假設(shè)此時(shí)應(yīng)與模式中第k個(gè)字符（kj）繼續(xù)比較。當(dāng)sitj（0inm，0jm1）時(shí)，存在： “sijsij+1si1”=“t0t1t2tj1” （4.1）若模式串中存在可互相重疊的真子串滿足： “t0t1t2tk1”=“tjktjk+1tj1”（0kj）（4.2）則說明模式串中的子串“t0t1t2tk1”已與主串“siksik+1si1”匹配，下一次可直接比較si和tk；

60、若模式串中不存在可互相重疊的真子串，則說明在模式串“t0t1tj1”中不存在任何以t0為首字符的字符串與“sij+1sij+2si1”中以si1為末字符的字符串相匹配，下一次可直接比較si和t0。數(shù)據(jù)結(jié)構(gòu) 第4章串86若令next j =k，則next j 表示當(dāng)模式中第j個(gè)字符tj與主串中相應(yīng)字符si“失配”（即sitj）時(shí)，在模式中需重新與主串中字符si進(jìn)行比較的字符的位置。由此可引出模式串的next j 的函數(shù)定義為：（4.3） 數(shù)據(jù)結(jié)構(gòu) 第4章串87注意：關(guān)于next j 的取值方式有兩種，一種方式是j=0時(shí)next j =0，其他情況為1；另一種是本書采用的方式，即j=0時(shí)next