數(shù)據(jù)結(jié)構(gòu)C語言版第四章嚴蔚敏學習教案

1、會計學1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)C語言版第四章課語言版第四章課件嚴蔚敏件嚴蔚敏第一頁，共36頁。4.1 串類型串類型(lixng)的定義的定義 1. 基本概念基本概念串串(字符串字符串) String：是零個或多個字符組成的有限序列。：是零個或多個字符組成的有限序列。 一般一般(ybn)記為：記為：S=a1a2.an (n0) 棧、隊列：操作受限的線性表。棧、隊列：操作受限的線性表。 串：取值范圍受限的線性表，數(shù)據(jù)對象約束為字符集。串：取值范圍受限的線性表，數(shù)據(jù)對象約束為字符集。 其中其中S是串的名字是串的名字, 用單引號括起來的字符序列是串的值，用單引號括起來的字符序列是串的值

2、，ai(1in)可以是字母、數(shù)字或其它字符。可以是字母、數(shù)字或其它字符。串的長度：串中字符的個數(shù)串的長度：串中字符的個數(shù)n。空串空串(Null String)： n=0時的串稱為空串，用符號時的串稱為空串，用符號“ ”表示表示 。 第1頁/共36頁第二頁，共36頁。l子串：串中任意個連續(xù)的字符組成的子序列稱為該串的子子串：串中任意個連續(xù)的字符組成的子序列稱為該串的子 串。串。“ ”為任意串的子串。為任意串的子串。l主串：包含主串：包含(bohn)子串的串相應地稱為主串。子串的串相應地稱為主串。第2頁/共36頁第三頁，共36頁。第3頁/共36頁第四頁，共36頁。串的基本操作和線性表區(qū)別串的基本操

3、作和線性表區(qū)別(qbi)很大。很大。線性表線性表: 大多以大多以“單個元素單個元素(yun s)”為操作對象為操作對象串串: 通常通常(tngchng)以以“串的整體串的整體”為操作對象為操作對象例，例，查找某個元素；插入某個元素；刪除某個元素查找某個元素；插入某個元素；刪除某個元素例，例，查找某個子串；截取某個子串；查找某個子串；截取某個子串； 在某個位置插入、刪除某個子串在某個位置插入、刪除某個子串串的邏輯結(jié)構(gòu)和線性表相似，故看作一種線性表。串的邏輯結(jié)構(gòu)和線性表相似，故看作一種線性表。s = a1a2 an ( n0)第4頁/共36頁第五頁，共36頁。2. 串的基本運算串的基本運算: 串賦

4、值串賦值StrAssign(&T, chars) 初始條件初始條件: chars是字符串常量。是字符串常量。 操作結(jié)果操作結(jié)果: 生成一個值等于生成一個值等于chars的串的串T。 串比較串比較(bjio)StrCompare(S, T) 初始條件初始條件: 串串S和和T存在。存在。 操作結(jié)果操作結(jié)果: 若若ST, 則返回值則返回值0;如如S=T, 則返回值則返回值=0; 若若ST, 則返回值則返回值0。 求串長求串長StrLength(S) 初始條件初始條件: 串串S存在。存在。 操作結(jié)果操作結(jié)果: 返回串返回串S的長度的長度, 即串即串S中的元素個數(shù)。中的元素個數(shù)。第5頁/共36頁第六頁，

5、共36頁。l 串聯(lián)串聯(lián)(chunlin)接接Concat(&T, S1, S2)l 初始條件初始條件: 串串S1和和S2存在。存在。l 操作結(jié)果操作結(jié)果: 將將T返回由返回由S1和和S2聯(lián)接而成的新串。聯(lián)接而成的新串。l 求子串求子串SubString(&Sub, S, pos, len)l 初始條件初始條件: 串串S存在存在, 1posStrLength(S)且且l 1lenStrLength(S)-pos+1。l 操作結(jié)果操作結(jié)果: 用用Sub返回串返回串S的第的第pos個字符起長度為個字符起長度為len的的l 子串。子串。 第6頁/共36頁第七頁，共36頁。4.2 串的表示串的表示(bi

6、osh)和實和實現(xiàn)現(xiàn) 定長順序存儲表示定長順序存儲表示(biosh)順序存儲順序存儲 堆分配堆分配(fnpi)存儲表示存儲表示順序存儲順序存儲 塊鏈存儲表示塊鏈存儲表示鏈式存儲鏈式存儲第7頁/共36頁第八頁，共36頁。1. 定長順序存儲表示定長順序存儲表示(biosh)（定長順序串）（定長順序串）define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1; l定長順序串的存儲分配是在編譯定長順序串的存儲分配是在編譯(biny)時完成的。與前面所講的線性表的順序存儲結(jié)構(gòu)類似時完成的。與前面所講的線性表的順序存儲結(jié)構(gòu)類似, 用一組地址

7、連續(xù)的存儲單元存儲串的字符序列。用一組地址連續(xù)的存儲單元存儲串的字符序列。l超出予定義長度的串值被舍去，稱之為超出予定義長度的串值被舍去，稱之為“截斷截斷”。012255第8頁/共36頁第九頁，共36頁。第9頁/共36頁第十頁，共36頁。算法算法(sun f)4.2 串聯(lián)接串聯(lián)接 strcat( &T，S1，S2 )要求要求: 順序聯(lián)接順序聯(lián)接(lin ji)串串 S1 和串和串 S2 得到新串得到新串 T 。思想思想(sxing): 基于串基于串S1和和S2長度的不同情況，串長度的不同情況，串T可能出現(xiàn)可能出現(xiàn)3種情況種情況:S10+S20MAXSTRLEN，S10+S20MAXSTRLEN

8、S10MAXSTRLEN，S10MAXSTRLEN，直接聯(lián)接，直接聯(lián)接，T0MAXSTRLEN ；截斷截斷S2，聯(lián)接，聯(lián)接，T0MAXSTRLEN；T S1；第10頁/共36頁第十一頁，共36頁。1255S101255T0T0 = S10 + S201255S20S10+S20MAXSTRLEN第11頁/共36頁第十二頁，共36頁。1255S10S10+S20MAXSTRLEN，S10MAXSTRLEN1255T0 255- -S101255S20 255- -S10T0MAXSTRLEN第12頁/共36頁第十三頁，共36頁。2. 堆分配存儲堆分配存儲(cn ch)表示（堆串）表示（堆串） 在

9、在C語言中，已經(jīng)有一個稱為語言中，已經(jīng)有一個稱為“堆堆”的自由的自由(zyu)存儲空間，并可用存儲空間，并可用malloc（）和（）和free（）函數(shù)完成動態(tài)存儲管理。（）函數(shù)完成動態(tài)存儲管理。typedef struct char * ch； int length； HString； 應用程序用到的內(nèi)存分配應用程序用到的內(nèi)存分配(fnpi)：棧分配：棧分配(fnpi)和堆分配和堆分配(fnpi)。堆：用戶程序動態(tài)申請的地址空間。堆：用戶程序動態(tài)申請的地址空間。棧：保存函數(shù)參數(shù)和塊內(nèi)局部變量的內(nèi)存區(qū)。棧：保存函數(shù)參數(shù)和塊內(nèi)局部變量的內(nèi)存區(qū)。void Fun1() void Fun2() int

10、 i; int *p=new int10; char p10;.; delete p;.; 第13頁/共36頁第十四頁，共36頁。3. 串的塊鏈存儲串的塊鏈存儲(cn 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; 第14頁/共36頁第十五頁，共36頁。l存儲

11、密度大，一些操作（如插入存儲密度大，一些操作（如插入(ch r)，刪除）有所不便，刪除）有所不便，引起大量字符移動，適合于在串基本保持靜態(tài)使用方式時，引起大量字符移動，適合于在串基本保持靜態(tài)使用方式時采用；采用；l存儲密度小，運算處理方便，但存儲空間量大，若處理過存儲密度小，運算處理方便，但存儲空間量大，若處理過程中，需大量內(nèi)外存交換，會影響總效率；程中，需大量內(nèi)外存交換，會影響總效率；l串的字符集的大小，也會影響串值存儲方式的選取。串的字符集的大小，也會影響串值存儲方式的選取。串值所占的存儲位存儲密度實際分配的存儲位第15頁/共36頁第十六頁，共36頁。第16頁/共36頁第十七頁，共36頁。

12、1. 樸素模式匹配算法樸素模式匹配算法(Brute-Force算法算法) 求子串位置的定位函數(shù)求子串位置的定位函數(shù)Index( S, T, pos).模式匹配：子串的定位操作通常稱作串的模式匹配。模式匹配：子串的定位操作通常稱作串的模式匹配。目標串：主串目標串：主串S。模式串：子串模式串：子串T。匹配成功：若存在匹配成功：若存在T的每個字符依次和的每個字符依次和S中的一個連續(xù)字符中的一個連續(xù)字符序列序列(xli)相等，則稱匹配成功。返回相等，則稱匹配成功。返回T中第一個字符在中第一個字符在S中的位置。中的位置。匹配不成功：返回匹配不成功：返回0。4.3 串的模式匹配算法串的模式匹配算法(sun

13、 f)第17頁/共36頁第十八頁，共36頁。的對應字符相等的對應字符相等,則匹配成功則匹配成功,該算該算法返回法返回i；否則；否則,匹配失敗匹配失敗,函數(shù)返函數(shù)返回回0。第18頁/共36頁第十九頁，共36頁。 第第 1 次次匹匹配配 s=cddcdc i=3 t=cdc j=3 失失敗敗 第第 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 成成功功 例如,設目標串s=“cddcdc”,模式串t=“cdc”。s的長度(c

14、hngd)為n(n=6),t的長度(chngd)為m(m=3)。用指針i指示目標串s的當前比較字符位置,用指針j指示模式串t的當前比較字符位置。BF模式匹配過程如下所示。i = i j +2;j = 1;第19頁/共36頁第二十頁，共36頁。第20頁/共36頁第二十一頁，共36頁。第21頁/共36頁第二十二頁，共36頁。 第第 1 次匹配次匹配 s s=abacaba=abacabab b i=4 p p=abab=abab j=4 失敗失敗 p p=abab=abab j=2 因因p1p2,s2=p2,p1p2,s2=p2,必有必有s2p1,s2p1,又因又因p1=p3,s3=p3,p1=p

15、3,s3=p3,所以必有所以必有s3=p1s3=p1。因此。因此, ,第二次匹第二次匹配可直接配可直接(zhji)(zhji)從從i=4, j=2i=4, j=2開始。開始。 第22頁/共36頁第二十三頁，共36頁。改進：每趟匹配過程中出現(xiàn)字符比較不等時，不回溯主指針改進：每趟匹配過程中出現(xiàn)字符比較不等時，不回溯主指針i，利用已得到的，利用已得到的“部分匹配部分匹配”結(jié)果將模式向右滑動盡可能遠結(jié)果將模式向右滑動盡可能遠的一段距離，繼續(xù)的一段距離，繼續(xù)(jx)進行比較。進行比較。第23頁/共36頁第二十四頁，共36頁。 “p1p2pk-1” = “si-k+1si-k+2si-1” “pj-k+

16、1pj-k+2pj-1” = “si-k+1si-k+2si-1”（部（部分分(b fen)匹配）匹配） “p1p2pk-1” = “pj-k+1pj-k+2pj-1” (真子串）真子串）第24頁/共36頁第二十五頁，共36頁。 max k|1kj, max k|1kj,且且“p1pk-1”=“pj-“p1pk-1”=“pj-k+1pj-1” k+1pj-1” 當此集合當此集合(jh)(jh)非空時非空時 0 0 當當j=1j=1時時 1 1 其他情況其他情況nextj=為此為此,定義定義nextj函數(shù)，表明當模式中第函數(shù)，表明當模式中第j個字符與主串中個字符與主串中相應字符相應字符“失配失配

17、”時，在模式中需重新和主串中該字符時，在模式中需重新和主串中該字符進行進行(jnxng)比較的字符的位置。比較的字符的位置。第25頁/共36頁第二十六頁，共36頁。int Index_KMP (SString S,SString T, int pos) i= pos,j =1; while (i=S0 & jT0) return i-T0; /*匹配成功匹配成功*/ else return 0; /*返回返回(fnhu)不匹配標不匹配標志志*/ 第26頁/共36頁第二十七頁，共36頁。第27頁/共36頁第二十八頁，共36頁。l若若pk=pj，則有，則有“p1pk”=“pj-k+1pj”， ne

18、xtj+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.第28頁/共36頁第二十九頁，共36頁。0nextj11122311 2345 6712第29頁/共36頁第三十頁，共36頁。第30頁/共36頁第三十一頁，共36頁。lKMPKMP算法的時間復雜度算法的時間復雜度 l 設主串設主串s s的長度為的長度為n,n,模式串模式串t t長度為長度為m,m,在在KMPKMP算法中算法中求求nextnext數(shù)組的時間復雜度為數(shù)組的時間復雜度為O(m),O(m),在后面的匹配中因主在后面的匹配中因主串串s s的下標的下標(xi bio)(xi bio)不減即不回溯不減即不回溯, ,比較次數(shù)可記為比較次數(shù)可記為n,n,所以所以KMPKMP算法總的時間復雜度為算法總的時間復雜度為O(n+m)O(n+m)。lKMPKMP算法最大的特點就是主串的指針不需要回溯，整個算法最大的特點就是主串的指針不需要回溯，整個匹配過程只需從頭到尾掃描一遍，這對于處理需要從外匹配過程只需從頭到尾掃描一遍，這對于處理需要從外設輸入的龐大數(shù)據(jù)很有效，可