數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第四章課件嚴(yán)蔚敏

1、第4章 串第第4章章 串串 4.1 串類型的定義串類型的定義4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)4.3 串的模式匹配算法串的模式匹配算法 第4章 串4.1 串類型的定義串類型的定義 1. 基本概念基本概念l 串串(字符串字符串) string：是零個(gè)或多個(gè)字符組成的有限序列。：是零個(gè)或多個(gè)字符組成的有限序列。 一般記為：一般記為：s=a1a2.an (n0) 棧、隊(duì)列：操作受限的線性表。棧、隊(duì)列：操作受限的線性表。 串：取值范圍受限的線性表，數(shù)據(jù)對(duì)象約束為字符集。串：取值范圍受限的線性表，數(shù)據(jù)對(duì)象約束為字符集。 其中其中s是串的名字是串的名字, 用單引號(hào)括起來的字符序列是串的值，用單引號(hào)括起來

2、的字符序列是串的值，ai(1in)可以是字母、數(shù)字或其它字符。可以是字母、數(shù)字或其它字符。l 串的長(zhǎng)度：串中字符的個(gè)數(shù)串的長(zhǎng)度：串中字符的個(gè)數(shù)n。l 空串空串(null string)： n=0時(shí)的串稱為空串，用符號(hào)時(shí)的串稱為空串，用符號(hào)“ ”表示表示 。 第4章 串l子串：串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串：串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子子 串。串。“ ”為任意串的子串。為任意串的子串。l主串：包含子串的串相應(yīng)地稱為主串。主串：包含子串的串相應(yīng)地稱為主串。第4章 串l 位置：字符在串中的序號(hào)稱為該字符在串中的位置。位置：字符在串中的序號(hào)稱為該字符在串中的位置。子串在

3、主串中的位置則以子串的第一個(gè)字符在主串子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來表示。中的位置來表示。 a=china beijing, b=beijing, c=china, 則它則它們的長(zhǎng)度分別為們的長(zhǎng)度分別為13、7和和5。b和和c是是a的子串的子串, b在在a中的位置是中的位置是7, c在在a中的位置是中的位置是1。l 串相等：當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí)串相等：當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱這兩個(gè)串是稱這兩個(gè)串是相等的，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等相等的，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等, 并且每個(gè)對(duì)并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。應(yīng)位置的字符都相等時(shí)才相等。 l 空格串：由一個(gè)或多

4、個(gè)空格組成的串。與空串不同?？崭翊河梢粋€(gè)或多個(gè)空格組成的串。與空串不同。第4章 串串的基本操作和線性表區(qū)別很大。串的基本操作和線性表區(qū)別很大。線性表線性表: 大多以大多以“單個(gè)元素單個(gè)元素”為操作對(duì)為操作對(duì)象象串串: 通常以通常以“串的整體串的整體”為操作對(duì)象為操作對(duì)象例，例，查找某個(gè)元素；插入某個(gè)元素；刪除某個(gè)元素查找某個(gè)元素；插入某個(gè)元素；刪除某個(gè)元素例，例，查找某個(gè)子串；截取某個(gè)子串；查找某個(gè)子串；截取某個(gè)子串； 在某個(gè)位置插入、刪除某個(gè)子串在某個(gè)位置插入、刪除某個(gè)子串串的邏輯結(jié)構(gòu)和線性表相似，故看作一種線性表。串的邏輯結(jié)構(gòu)和線性表相似，故看作一種線性表。s = a1a2 an ( n

5、0)第4章 串2. 串的基本運(yùn)算串的基本運(yùn)算:l 串賦值串賦值strassign(&t, chars) 初始條件初始條件: chars是字符串常量。是字符串常量。 操作結(jié)果操作結(jié)果: 生成一個(gè)值等于生成一個(gè)值等于chars的串的串t。 l 串比較串比較strcompare(s, t) 初始條件初始條件: 串串s和和t存在。存在。 操作結(jié)果操作結(jié)果: 若若st, 則返回值則返回值0;如如s=t, 則返回值則返回值=0; 若若st, 則返回值則返回值0。 l 求串長(zhǎng)求串長(zhǎng)strlength(s) 初始條件初始條件: 串串s存在。存在。 操作結(jié)果操作結(jié)果: 返回串返回串s的長(zhǎng)度的長(zhǎng)度, 即串

6、即串s中的元素個(gè)數(shù)。中的元素個(gè)數(shù)。第4章 串l 串聯(lián)接串聯(lián)接concat(&t, s1, s2) 初始條件初始條件: 串串s1和和s2存在。存在。 操作結(jié)果操作結(jié)果: 將將t返回由返回由s1和和s2聯(lián)接而成的新串。聯(lián)接而成的新串。l 求子串求子串substring(&sub, s, pos, len) 初始條件初始條件: 串串s存在存在, 1posstrlength(s)且且 1lenstrlength(s)-pos+1。 操作結(jié)果操作結(jié)果: 用用sub返回串返回串s的第的第pos個(gè)字符起長(zhǎng)度為個(gè)字符起長(zhǎng)度為len的的 子串。子串。 第4章 串4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)

7、現(xiàn) 定長(zhǎng)順序存儲(chǔ)表示定長(zhǎng)順序存儲(chǔ)表示順序存儲(chǔ)順序存儲(chǔ) 堆分配存儲(chǔ)表示堆分配存儲(chǔ)表示順序存儲(chǔ)順序存儲(chǔ) 塊鏈存儲(chǔ)表示塊鏈存儲(chǔ)表示鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)第4章 串1. 定長(zhǎng)順序存儲(chǔ)表示（定長(zhǎng)順序串）定長(zhǎng)順序存儲(chǔ)表示（定長(zhǎng)順序串）define maxstrlen 255 typedef unsigned char sstringmaxstrlen+1; l定長(zhǎng)順序串的存儲(chǔ)分配是在編譯時(shí)完成的。與前面所講的定長(zhǎng)順序串的存儲(chǔ)分配是在編譯時(shí)完成的。與前面所講的線線性表的順序存儲(chǔ)結(jié)構(gòu)類似性表的順序存儲(chǔ)結(jié)構(gòu)類似, 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列。字符序列。l超出予定義長(zhǎng)度的串

8、值被舍去，稱之為超出予定義長(zhǎng)度的串值被舍去，稱之為“截?cái)嘟財(cái)唷薄?12255第4章 串 串長(zhǎng)的表示：串長(zhǎng)的表示： 以下標(biāo)為以下標(biāo)為0的數(shù)組分量存放串的實(shí)際長(zhǎng)度；的數(shù)組分量存放串的實(shí)際長(zhǎng)度； 串值后加入一個(gè)不計(jì)入串長(zhǎng)的結(jié)束標(biāo)記字串值后加入一個(gè)不計(jì)入串長(zhǎng)的結(jié)束標(biāo)記字符，符，c中中“0”表串值的終結(jié)，其表串值的終結(jié)，其asc碼值碼值為為0。第4章 串算法算法4.2 串聯(lián)接串聯(lián)接 strcat( &t，s1，s2 )要求要求: 順序聯(lián)接串順序聯(lián)接串 s1 和串和串 s2 得到新串得到新串 t 。思想思想: 基于串基于串s1和和s2長(zhǎng)度的不同情況，串長(zhǎng)度的不同情況，串t可能出現(xiàn)可能出現(xiàn)3種情況種

9、情況:s10+s20maxstrlen，s10+s20maxstrlens10maxstrlen，s10maxstrlen，直接聯(lián)接，直接聯(lián)接，t0maxstrlen ；截?cái)嘟財(cái)鄐2，聯(lián)接，聯(lián)接，t0maxstrlen；t s1；第4章 串1255s101255t0t0 = s10 + s201255s20s10+s20maxstrlen第4章 串1255s10s10+s20maxstrlen，s10maxstrlen1255t0 255- -s101255s20 255- -s10t0maxstrlen第4章 串2. 堆分配存儲(chǔ)表示（堆串）堆分配存儲(chǔ)表示（堆串） 在在c語(yǔ)言中，已經(jīng)有一個(gè)稱為

10、語(yǔ)言中，已經(jīng)有一個(gè)稱為“堆堆”的自由存儲(chǔ)空間，并可的自由存儲(chǔ)空間，并可用用malloc（）和（）和free（）函數(shù)完成動(dòng)態(tài)存儲(chǔ)管理。（）函數(shù)完成動(dòng)態(tài)存儲(chǔ)管理。typedef struct char * ch； int length； hstring； 應(yīng)用程序用到的內(nèi)存分配：棧分配和堆分配。應(yīng)用程序用到的內(nèi)存分配：棧分配和堆分配。堆：用戶程序動(dòng)態(tài)申請(qǐng)的地址空間。堆：用戶程序動(dòng)態(tài)申請(qǐng)的地址空間。棧：保存函數(shù)參數(shù)和塊內(nèi)局部變量的內(nèi)存區(qū)。棧：保存函數(shù)參數(shù)和塊內(nèi)局部變量的內(nèi)存區(qū)。void fun1() void fun2() int i; int *p=new int10; char p10;.; d

11、elete p;.; 第4章 串3. 串的塊鏈存儲(chǔ)表示（鏈串）串的塊鏈存儲(chǔ)表示（鏈串） a b c d e f g h i # # # a b b c i . define chunksize typedef struct chunk char chchunksize; struct chunk *next;chunk;typedef struct chunk *head; chunk *tail; int curlen;lstring; 第4章 串l存儲(chǔ)密度大，一些操作（如插入，刪除）有所不便，引存儲(chǔ)密度大，一些操作（如插入，刪除）有所不便，引起大量字符移動(dòng)，適合于在串基本保持靜態(tài)使用方式時(shí)

12、采起大量字符移動(dòng)，適合于在串基本保持靜態(tài)使用方式時(shí)采用；用；l存儲(chǔ)密度小，運(yùn)算處理方便，但存儲(chǔ)空間量大，若處理存儲(chǔ)密度小，運(yùn)算處理方便，但存儲(chǔ)空間量大，若處理過程中，需大量?jī)?nèi)外存交換，會(huì)影響總效率；過程中，需大量?jī)?nèi)外存交換，會(huì)影響總效率；l串的字符集的大小，也會(huì)影響串值存儲(chǔ)方式的選取。串的字符集的大小，也會(huì)影響串值存儲(chǔ)方式的選取。串值所占的存儲(chǔ)位存儲(chǔ)密度實(shí)際分配的存儲(chǔ)位第4章 串l作業(yè)：作業(yè)： 4.14.18第4章 串1. 樸素模式匹配算法樸素模式匹配算法(brute-force算法算法) 求子串位置的定位函數(shù)求子串位置的定位函數(shù)index( s, t, pos).l模式匹配：子串的定位操作通

13、常稱作串的模式匹配。模式匹配：子串的定位操作通常稱作串的模式匹配。l目標(biāo)串：主串目標(biāo)串：主串s。l模式串：子串模式串：子串t。l匹配成功：若存在匹配成功：若存在t的每個(gè)字符依次和的每個(gè)字符依次和s中的一個(gè)連中的一個(gè)連續(xù)字符序列相等，則稱匹配成功。返回續(xù)字符序列相等，則稱匹配成功。返回t中第一個(gè)字符中第一個(gè)字符在在s中的位置。中的位置。l匹配不成功：返回匹配不成功：返回0。4.3 串的模式匹配算法串的模式匹配算法第4章 串lbrute-force簡(jiǎn)稱為簡(jiǎn)稱為bf算法算法,亦稱簡(jiǎn)單匹配算法亦稱簡(jiǎn)單匹配算法,其基本思路是其基本思路是: 從目標(biāo)串從目標(biāo)串s=“s1s2sn”的第一個(gè)字符開始的第一個(gè)字符

14、開始和模式串和模式串t=“t1t2tm”中的第一個(gè)字符比較中的第一個(gè)字符比較,若若相等相等,則繼續(xù)逐個(gè)比較后續(xù)字符；否則從目標(biāo)則繼續(xù)逐個(gè)比較后續(xù)字符；否則從目標(biāo)串串s的第二個(gè)字符開始重新與模式串的第二個(gè)字符開始重新與模式串t的第一個(gè)的第一個(gè)字符進(jìn)行比較。依次類推字符進(jìn)行比較。依次類推,若從目標(biāo)串若從目標(biāo)串s的第的第i個(gè)個(gè)字符開始字符開始,每個(gè)字符依次和模式串每個(gè)字符依次和模式串t中的對(duì)應(yīng)字中的對(duì)應(yīng)字符相等符相等,則匹配成功則匹配成功,該算法返回該算法返回i；否則；否則,匹配失匹配失敗敗,函數(shù)返回函數(shù)返回0。第4章 串 第第 1 次次匹匹配配 s=cddcdc i=3 t=cdc j=3 失失敗

15、敗 第第 2 次次匹匹配配 s=cddcdc i=2 t=cdc j=1 失失敗敗 第第 3 次次匹匹配配 s=cddcdc i=3 t=cdc j=1 失失敗敗 第第 4 次次匹匹配配 s=cddcdc i=6 t=cdc j=3 成成功功 例如例如,設(shè)目標(biāo)串設(shè)目標(biāo)串s=“cddcdc”,模式串模式串t=“cdc”。s的長(zhǎng)度為的長(zhǎng)度為n(n=6),t的長(zhǎng)度為的長(zhǎng)度為m(m=3)。用指針。用指針i指示目標(biāo)串指示目標(biāo)串s的當(dāng)前比較的當(dāng)前比較字符位置字符位置,用指針用指針j指示模式串指示模式串t的當(dāng)前比較字符位置。的當(dāng)前比較字符位置。bf模式模式匹配過程如下所示。匹配過程如下所示。i = i j

16、+2;j = 1;第4章 串l 子串定位子串定位int index( sstring s, sstring t, int pos) i= pos; j = 1; while( i=s0 & jt0) return i-t0; else return 0;第4章 串l 樸素模式匹配算法的時(shí)間復(fù)雜度樸素模式匹配算法的時(shí)間復(fù)雜度 主串長(zhǎng)主串長(zhǎng)n； 子串長(zhǎng)子串長(zhǎng)m?？赡芷ヅ涑晒Φ奈恢茫?。可能匹配成功的位置（1 n-m+1)。最好的情況下，最好的情況下， 第第i個(gè)位置匹配成功，比較了（個(gè)位置匹配成功，比較了（i-1+m）次，平均比較次數(shù)：）次，平均比較次數(shù)： 最好情況下算法的平均時(shí)間復(fù)雜度最好情

17、況下算法的平均時(shí)間復(fù)雜度o(n+m)。最壞的情況下，最壞的情況下， 第第i個(gè)位置匹配成功，比較了（個(gè)位置匹配成功，比較了（i*m）次，平均比較次數(shù)：）次，平均比較次數(shù)： 設(shè)設(shè)nm，最壞情況下的平均時(shí)間復(fù)雜度為，最壞情況下的平均時(shí)間復(fù)雜度為o(n*m)。第4章 串2. 模式匹配的改進(jìn)算法模式匹配的改進(jìn)算法-kmp算法算法 kmp算法是算法是d.e.knuth、j.h.morris和和v.r.pratt共同提共同提出的出的,簡(jiǎn)稱簡(jiǎn)稱kmp算法。該算法較算法。該算法較bf算法有較大改進(jìn)算法有較大改進(jìn),主要是主要是消除了主串指針的回溯消除了主串指針的回溯,從而使算法效率有了某種程度的從而使算法效率有了

18、某種程度的提高。提高。 第第 1 次匹配次匹配 s s=abacaba=abacabab b i=4 p p=abab=abab j=4 失敗失敗 p p=abab=abab j=2 因因p p1 1pp2 2,s,s2 2=p=p2 2, ,必有必有s s2 2pp1 1, ,又因又因p p1 1=p=p3 3,s,s3 3=p=p3 3, ,所以必有所以必有s s3 3=p=p1 1。因此。因此, ,第二次匹配可直接從第二次匹配可直接從i=4, i=4, j=2j=2開始。開始。 第4章 串改進(jìn)：改進(jìn)：每趟匹配過程中出現(xiàn)字符比較不等時(shí)，不回溯每趟匹配過程中出現(xiàn)字符比較不等時(shí)，不回溯主指針主

19、指針i，利用已得到的，利用已得到的“部分匹配部分匹配”結(jié)果將模式向結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn)的一段距離，繼續(xù)進(jìn)行比較。右滑動(dòng)盡可能遠(yuǎn)的一段距離，繼續(xù)進(jìn)行比較。第4章 串s s1 1 s s2 2 s s3 3ssi-j+1i-j+1 s si-j+2i-j+2ssi-2i-2 s si-1i-1 s si i s si+1i+1 p p1 1 p p2 2 p pj-2j-2 p pj-1j-1 p pj j p pj+1j+1 p p1 1 p pk-1k-1 p pk k p pk+1k+1 “p1p2pk-1” = “si-k+1si-k+2si-1” “pj-k+1pj-k+2pj-1

20、” = “si-k+1si-k+2si-1”（部分匹配部分匹配） “p1p2pk-1” = “pj-k+1pj-k+2pj-1” (真子串真子串）第4章 串 max k|1kj,且且“p1pk-1”=“pj-k+1pj-1” 當(dāng)此集合非空時(shí)當(dāng)此集合非空時(shí) 0 0 當(dāng)當(dāng)j=1j=1時(shí)時(shí) 1 1 其他情況其他情況nextj=為此為此,定義定義nextj函數(shù)，表明當(dāng)模式中第函數(shù)，表明當(dāng)模式中第j個(gè)字符與主個(gè)字符與主串中相應(yīng)字符串中相應(yīng)字符“失配失配”時(shí)，在模式中需重新和主串時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符的位置。中該字符進(jìn)行比較的字符的位置。第4章 串int index_kmp (ss

21、tring s,sstring t, int pos) i= pos,j =1; while (i=s0 & jt0) return i-t0; /*匹配成功匹配成功*/ else return 0; /*返回不匹配標(biāo)志返回不匹配標(biāo)志*/ 第4章 串l如何求如何求next函數(shù)值函數(shù)值1. next1 = 0;表明主串從下一字符表明主串從下一字符si+1起和模式串重新起和模式串重新開始匹配。開始匹配。i = i+1; j = 1;2. 設(shè)設(shè)nextj = k，則，則nextj+1 = ?若若pk=pj，則有，則有“p1pk-1pk”=“pj-k+1pj-1pj” ，如果，如果在在 j+1

22、發(fā)生不匹配，說明發(fā)生不匹配，說明nextj+1 = k+1 = nextj+1。若若pkpj，可把求，可把求next值問題看成是一個(gè)模式匹配問值問題看成是一個(gè)模式匹配問 題，整個(gè)模式串既是主串，又是子串。題，整個(gè)模式串既是主串，又是子串。第4章 串 p p1 1 p p2 2p pj-k+1j-k+1ppj-1j-1 p pj j p pj+1 j+1 nextjnextj=k=k p p1 1 p pk-1k-1 p pk k p pk+1 k+1 nextknextk=k=k p p1 1 p pk k p pk k+1 +1 nextknextk=k=k” p p1 1 p pk k p

23、 pk k+1 +1 nextknextk=k=k l若若pk=pj，則有，則有“p1pk”=“pj-k+1pj”， nextj+1=k+1=nextk+1=nextnextj+1. l若若pk”=pj ，則有，則有“p1pk”=“pj-k”+1pj”， nextj+1=k”+1=nextk+1=nextnextk+1.lnextj+1=1.第4章 串 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串模式串 a b c a a b b c a b c a a b d a b 0nextj1 1 1 2 2 3 1 1 23 45 67 1 2第4章

24、串l void get_next(sstring t, int &next) i= 1; next1 = 0; j = 0; while( it0) if(j=0 | ti = tj) +i; +j; nexti = j; else j = nextj; 第4章 串lkmpkmp算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 設(shè)主串設(shè)主串s s的長(zhǎng)度為的長(zhǎng)度為n,n,模式串模式串t t長(zhǎng)度為長(zhǎng)度為m,m,在在kmpkmp算算法中求法中求nextnext數(shù)組的時(shí)間復(fù)雜度為數(shù)組的時(shí)間復(fù)雜度為o(m),o(m),在后面的匹在后面的匹配中因主串配中因主串s s的下標(biāo)不減即不回溯的下標(biāo)不減即不回溯, ,比較次數(shù)可記為比較次數(shù)可記為n,n,所以所以kmpkmp算法總的時(shí)間復(fù)雜度為算法總的時(shí)間復(fù)雜度為o(n+m)o(n+m)。kmp算法最大的特點(diǎn)就是主串的指針不需要回溯，整個(gè)匹配過程只需從頭到尾掃描一遍，這對(duì)于處理需要從外設(shè)輸入的龐大數(shù)據(jù)很有效，可以一邊讀入一邊匹配。第4