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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、，例如，執(zhí)行insert(s2, 3,“THIS”)后，s2=“b1b2b3THISb4bm”。（6）串刪除delete(s, i, j)：從串s第i個字符開始，連續(xù)刪除j個字符。若不足j個字符，則刪除到s的最后一個字符。例如，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個字符開始的連續(xù)j個字符，例如，執(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個字符開始，取連續(xù)j個字符構(gòu)成一個新串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 順序串上基本運算的實現(xiàn)（1）順序串的賦值函數(shù)S_strassign(s)：將從鍵盤輸入的一串字符

20、變量賦給串變量s。/* 順序串建立函數(shù)，從鍵盤輸入字符串賦給順序串變量s */void S_strassign(s)seqstring *s; char c; int j=1; printf(nntt請輸入一個字符串，以#作為結(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)：比較兩個順序串的大小。若s1=s2，則函數(shù)返回0；若s1s2，則函數(shù)返回正數(shù)；若s1s2，則函數(shù)返回負數(shù)。 /* 兩個順序串比較函數(shù)，函數(shù)返回值為0、正數(shù)或負數(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之后形成一個新串。/* 順序串連接函數(shù)，將順序串s2與s1連成一個新串 */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兩個順序串連接后的新串長度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個字符位置開始插入。/* 順序串的插入函數(shù)，從s串第i個位置開始插入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);/* 刪除失敗，返回錯誤信息1 */* S_STRDELETE */數(shù)據(jù)結(jié)構(gòu) 第4章串39（7）求順序串的子串函數(shù)S_substr(s, i, k, t)：從順序串s中第i個字符開始連續(xù)取k個字符存放到順序存儲的子串t中。/* 從順序串s第i個字符開始取k個子符放到順序串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 鏈串上基本運算的實現(xiàn)（1）鏈串賦值函數(shù)L_strassign（s, t）：將一個字符串常量t賦給鏈串s，函數(shù)返回指向鏈串s的頭指針。/* 將一個串常量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為指向隊尾指針 */ 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é)點鏈串head的長度。/* 求帶頭結(jié)點鏈串head的長度函數(shù) */int L_strlen(head)linkstring *head; lin

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

30、strcmp(head1, head2)linkstring *head1, *head2; linkstring *p1, *p2; int k=0;/* k為鏈串是否相等的標志 */ p1=head1;/* 指向head1的首結(jié)點 */ p2=head2;/* 指向head2的首結(jié)點 */ while(p1!=NULL)&(p2!=NULL)&(k=0) p1=p1-next; p2=p2-next; 數(shù)據(jù)結(jié)構(gòu) 第4章串43/* 將兩個鏈串進行比較，函數(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; /* 兩個鏈串相等，函數(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）兩個鏈串的連接函數(shù)L_strcat(heads, headt)：利用原鏈串空間，將兩個帶頭結(jié)點鏈串進行連接。要求將鏈串t連接到鏈串s后

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

36、/*從鏈串s第i個字符開始取j個字符存到子串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個字符開始取j個字符存到子串t中7-2 */ for (m=1;

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

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

39、若從主串s中找到模式為t的子串，則返回t子串在s中的起始位置。當s中有多個模式為t的子串時，通常只找出第一個子串的起始位置，這種情況稱為匹配成功，否則稱為匹配失敗。數(shù)據(jù)結(jié)構(gòu) 第4章串54模式匹配運算可用一個函數(shù)來實現(xiàn)，前面介紹的求子串序號就是一個實現(xiàn)模式匹配運算的函數(shù)。串的匹配運算是一個比較復(fù)雜的串運算，許多人對此提出了多個效率各不相同的模式匹配算法。這里僅介紹BF模式匹配算法及基于BF算法的兩種改進算法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”中的字符依次與目標串s=“s0s1s2sn1”中的字符進行比較。從目標串s的第一個字符開始與模式串t的第一個字符進行比較，若相等，則逐個比較后續(xù)字符；否則，從目標串s第二個字符開始重新與模式串t的第一個字符進行比較。其余類推，若模式串t的每個字符依次與目標串s中一個連續(xù)的字符序列相等，則稱匹配成功，函數(shù)返回模式串t中第一個字符在目標串s的位置；若將s的所有字符都檢測完了，還找不到與t相同的子串，則稱匹配失敗，函數(shù)返回0。數(shù)據(jù)結(jié)構(gòu) 第4章串57【例4.5】假設(shè)目標串s=“abbaba”，模式

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

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

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

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

45、共要比較mi次。數(shù)據(jù)結(jié)構(gòu) 第4章串65若對這nm+1個開始位置，匹配成功的概率為Pi且都是相等的，則在最壞的情況下，匹配成功的平均比較次數(shù)Cmax 為：若nm，則在最壞的情況下該算法的時間復(fù)雜度是O(mn)，即等于兩串長度乘積的數(shù)量級。數(shù)據(jù)結(jié)構(gòu) 第4章串66例如，兩個字符串s和t分別為：s =“gggggggga”（n=9）t =“gggb”（m=4） 由于t的前3個字符可在s中找到匹配，而t的第4個字符在s中找不到匹配，因此，每一趟匹配失敗時都要比較m=4次，然后再將指針i移到s的第2個字符，結(jié)果是t的前3個字符在s中找到匹配，而第4個字符在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模式匹配算法實現(xiàn)/* 在鏈串上求模式串t在目標串s中首次出現(xiàn)的位置1 */linkstring *L_bfindex(s, t)linkstring *s, *t; /* s, t是帶頭結(jié)點的鏈串 */ 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從第一個結(jié)點開始進行比較*/數(shù)據(jù)結(jié)構(gòu) 第4章串68 /* 在鏈串上求模式串t在目標串s中首次出現(xiàn)的位置1 */ while(sp!= NULL)&(tp!= NULL) if(sp-data=tp-data) /* 若兩個結(jié)點的字符相等，則繼續(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 */【算法分析】該算法的時間復(fù)雜度是O(mn)，它與順序串上BF算法的時間復(fù)雜度相同。數(shù)據(jù)結(jié)構(gòu) 第4章串694.4.2 BM模式匹配算法1BM算法的基本思想 該算法對BF算法的匹配過程做了兩點改進：其一是首先檢查模式串t的首尾兩個字符與主串s中對應(yīng)的字符是否匹配，若這兩對字符匹配了再檢查中間的字符；其二是在下一輪比較中，當主串s中余下的字符個數(shù)已經(jīng)小于模式串t的長度時即停止運算，因為，在這種情況下匹配不可能成功。 改進的BM算法利用主串中字符在模式串中出現(xiàn)的位置和長度等信息，減少每一趟的比較次數(shù)，從而大大提高

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

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

51、和pBB分別指向BB的第2個結(jié)點和AA的第4個結(jié)點時，二者字符進行比較的情況。顯然，改進的模式匹配算法比BF算法運算速度要快?！舅惴ǚ治觥靠梢宰C明，改進的BM算法就平均情況來說會加快處理速度，但在輸入數(shù)據(jù)最不利的情況下，其時間復(fù)雜度仍然是O(mn)。數(shù)據(jù)結(jié)構(gòu) 第4章串74 2鏈串上BM模式匹配算法實現(xiàn)/* 在鏈串上求模式BB在目標串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個結(jié)點 */ while (qb-next!=NULL)/* 查找BB末端結(jié)點 */ qb=qb-next;/* qb為指向模式串BB末端結(jié)點 */ lb=lb+1;/* 循環(huán)結(jié)束時，lb為BB長度 */ /* WHILE1 */數(shù)據(jù)結(jié)構(gòu) 第4章串75 /* 在鏈串上求模式BB在目標串AA中首次出現(xiàn)的位置-2*/ qa=ha-next;/* qa首先指向AA的第1個

53、結(jié)點 */ for(i=2; ilb，則循環(huán)結(jié)束qa指向AA第lb個結(jié)點 */ if(qa!=NULL) qa=qa-next; /* 若lanext; pa=first; if(qa-data=qb-data) /* 若首末兩端字符相等，則比較中間的字符 */數(shù)據(jù)結(jié)構(gòu) 第4章串76 /* 在鏈串上求模式BB在目標串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算法的基本思想另一種改進的模式匹配算法是克努特（Knuth）、莫里斯（Morris）和普拉特（Pratt）同時發(fā)現(xiàn)的，簡稱為KMP算法。KMP算法較BF算法有很大改進，主要是在每一趟匹配過程中出現(xiàn)字符不等時，不需要回溯指針i，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右“滑動”盡可能遠的一段距離后，

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

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

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

58、配。因為t0t1，s1=t1，必有s1t0；又因為t0=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）進行比較，k的確定與主串s并沒有關(guān)系，而只與模式串t本身的構(gòu)成有關(guān)，即從模式串t本身就可以求出k值。數(shù)據(jù)結(jié)構(gòu) 第4章串83圖4.9 KMP模式匹配的一個示例數(shù)據(jù)結(jié)構(gòu) 第4章串84現(xiàn)在我們討論一般情況。假設(shè)主串 s=“s0s1s2sn1”，模式串 t=“t0t1t2tm1”，為了實現(xiàn)KMP算

59、法，需要解決的問題是：當匹配過程產(chǎn)生失配時（即sitj），模式串“向右滑動”的距離有多遠。換句話說，當主串中第i個字符與模式中第j個字符“失配”時，主串中第i個字符（i指針不回溯）應(yīng)與模式中哪個字符再比較？數(shù)據(jù)結(jié)構(gòu) 第4章串85假設(shè)此時應(yīng)與模式中第k個字符（kj）繼續(xù)比較。當sitj（0inm，0jm1）時，存在： “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 表示當模式中第j個字符tj與主串中相應(yīng)字符si“失配”（即sitj）時，在模式中需重新與主串中字符si進行比較的字符的位置。由此可引出模式串的next j 的函數(shù)定義為：（4.3） 數(shù)據(jù)結(jié)構(gòu) 第4章串87注意：關(guān)于next j 的取值方式有兩種，一種方式是j=0時next j =0，其他情況為1；另一種是本書采用的方式，即j=0時next