數(shù)據(jù)結(jié)構(gòu)串課件

1、數(shù)據(jù)結(jié)構(gòu)串課件 第 4 章 串 陳守孔陳守孔 孟佳娜孟佳娜 陳卓陳卓 數(shù)據(jù)結(jié)構(gòu)串課件 本章目錄 w4.1串類型的定義 w4.2串的表示和實現(xiàn) n4.2.1 串的順序存儲結(jié)構(gòu) n4.2.2 串的鏈式存儲結(jié)構(gòu) w4.3 串的模式匹配 n4.3.1 樸素的模式匹配算法 n4.3.2 KMP算法 w4.4 串的應(yīng)用舉例 w4.5 算法設(shè)計舉例 數(shù)據(jù)結(jié)構(gòu)串課件 知識點和難點重點 w 知識點知識點 n基本概念基本概念 n串操作串操作 n模式匹配模式匹配 w 難點重點難點重點 n根據(jù)給定操作，編寫其它操作的算法根據(jù)給定操作，編寫其它操作的算法 (如，根據(jù)前如，根據(jù)前5個基本操作，編寫個基本操作，編寫inde

2、x,replace操作操作 n KMP算法算法 l模式串的模式串的next和和nextval函數(shù)值函數(shù)值 l手工模擬手工模擬KMP算法的執(zhí)行過程算法的執(zhí)行過程 n串的其它算法。串的其它算法。 數(shù)據(jù)結(jié)構(gòu)串課件 定義和概念 w 串（串（StringString）: :由零個或多個字符組成的有限序列。由零個或多個字符組成的有限序列。 記為：記為：s=a1a2an（n0） w 概念：概念： ns為串名為串名 na1a2an為串值為串值 nn為串的長度為串的長度 nai，字符，字符 nn=0，空串（，空串（Null String），記為：），記為： n若若ai 都是都是 ，則稱為空格串，則稱為空格串(b

3、lank string) n子串：串中子串：串中任意連續(xù)任意連續(xù)個字符組成的子序列被稱為該個字符組成的子序列被稱為該 串的子串串的子串 ，包含子串的串又被稱為該子串的，包含子串的串又被稱為該子串的主串主串 n子串在主串中的位置：子串在主串中的位置： n串的相等：兩個串的串值相等（兩個串的長度相等，串的相等：兩個串的串值相等（兩個串的長度相等， 并且各個對應(yīng)的字符也都相同并且各個對應(yīng)的字符也都相同 ） 數(shù)據(jù)結(jié)構(gòu)串課件 串的操作 n串賦值：串賦值：StringAssign(S,T)StringAssign(S,T) n求串長：求串長：StringLenth(S)StringLenth(S) n串判

4、等：串判等：StringEqual(S,T)StringEqual(S,T) n串聯(lián)接：串聯(lián)接：StringConcat(S,T)StringConcat(S,T) n求子串：求子串：SubString(S,start,length)SubString(S,start,length) n子串定位：子串定位：Index(S,T)Index(S,T) n置換：置換：Replace(S,T,V)Replace(S,T,V) n插入子串：插入子串：StringInsert(S,start,T)StringInsert(S,start,T) n刪除子串：刪除子串：StringDeleteStringDe

5、lete( (S,start,lengthS,start,length) ) （其中，前（其中，前5 5個操作為基本操作。）個操作為基本操作。） 數(shù)據(jù)結(jié)構(gòu)串課件 串運算舉例 串運算的例子： 長度分別為長度分別為1818、7 7、3 3、3 3；且；且b b、c c、d d都是都是a a的子串；的子串；b b在在a a中的中的 位置是位置是1 1，c c在在a a中的位置是中的位置是1212；c c和和d d兩串相等兩串相等 例：例： a= Welcome to Beijing b= Welcome a= Welcome to Beijing b= Welcome c= Bei d= Bei c

6、= Bei d= Bei 數(shù)據(jù)結(jié)構(gòu)串課件 子串定位（index）的實現(xiàn) int Index(String S, String T) 若主串若主串S第第i個字符之后存在與個字符之后存在與T相等的子串，則返回相等的子串，則返回T串在串在S中中 的位置，否則返回的位置，否則返回0 n=StringLength(S); m=StringLength(T); i=1; while(istr) free(S-str); 若若s已經(jīng)存在，將它占據(jù)的空間釋放掉已經(jīng)存在，將它占據(jù)的空間釋放掉 len= T-length; T串的長度串的長度 S-length=len; 賦予字符串長度賦予字符串長度 if(!le

7、n) 空串空串 S-str=(char*)malloc(sizeof(char); S-str0=0; else 非空串非空串 S-str=(char*)malloc(len+1)*sizeof(char);分配空間分配空間 if(!S-str) return ERROR; for(i=0;istri=T-stri; if return OK; StringAssign 數(shù)據(jù)結(jié)構(gòu)串課件 基本操作:串聯(lián)接 int StringConcat(STRING *S,*T) 將串將串T聯(lián)接到串聯(lián)接到串S后后 STRING temp; StringAssign(temp,S); 將將S原來的內(nèi)容保留在原來

8、的內(nèi)容保留在temp中中 S-length=S-length+T-length; 計算計算S和和T的長度之和為的長度之和為S的新長度的新長度 free(S-str); 釋放釋放S原來占據(jù)的空間原來占據(jù)的空間 S-str=(char*)malloc(S-length+1)*sizeof(char); 重新為重新為S分配空間分配空間 if(!S-str) return ERROR; else 連接兩個串的內(nèi)容連接兩個串的內(nèi)容 for(i=0;istri=temp.stri; for(j=0;jlength;j+,i+) 將將T的值賦在的值賦在S現(xiàn)有值之后現(xiàn)有值之后 S-stri=T-strj; f

9、ree(temp.str); 釋放為臨時串釋放為臨時串temp分配的空間分配的空間 return OK; if StringConcat 數(shù)據(jù)結(jié)構(gòu)串課件 int Index(STRING *S,*T) 返回子串返回子串T在主串在主串S中的位置，若中的位置，若T非非S的子串則返回的子串則返回0 i=0; j=0; 設(shè)置兩個掃描指針設(shè)置兩個掃描指針 while(ilength j+; else 對應(yīng)字符不相等時，重新比較對應(yīng)字符不相等時，重新比較 i=i-j+1; j=0; if(j=T-length) return i-T-length+1;返回子串在主串中的位置返回子串在主串中的位置 else

10、 return 0; 子串不在主串中子串不在主串中 Index 基本操作的算法:子串定位 數(shù)據(jù)結(jié)構(gòu)串課件 定長順序表示中的C表示方法 w 在C中，字符串的概念是：以0為結(jié)尾 的字符數(shù)組。 w 初始化： nString s; nS0 = 0; 數(shù)據(jù)結(jié)構(gòu)串課件 串的鏈式存儲結(jié)構(gòu) w 串串作為一種特殊的線性表（數(shù)據(jù)元素為字 符），使用順序表示時，做插入和刪除運 算，運算量很大，不方便。 w 鏈式存儲結(jié)構(gòu)：鏈式存儲結(jié)構(gòu)： s p r i n g S S s p r i n g # # # # 數(shù)據(jù)結(jié)構(gòu)串課件 串的塊鏈存儲結(jié)構(gòu) w 直接使用線性鏈表來存儲字符串：效率太低直接使用線性鏈表來存儲字符串：效率

11、太低 實際分配的存儲單元 串值所占的存儲單元 存儲密度 = = w 塊鏈式結(jié)構(gòu)的定義塊鏈式結(jié)構(gòu)的定義 #define CHUNKSIZE 80 可由用戶定義的塊大小可由用戶定義的塊大小 typedef struct Chunk 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct 串的鏈表結(jié)構(gòu)串的鏈表結(jié)構(gòu) Chunk *head, *tail; 串的頭和尾指針串的頭和尾指針 int curlen; 串的當前長度串的當前長度 LString; 數(shù)據(jù)結(jié)構(gòu)串課件 塊鏈運算：插入 H esi s de nuta# #.

12、t? He is a student. He is a bright student. 數(shù)據(jù)結(jié)構(gòu)串課件 塊鏈運算：插入 H esi b g d e ira .#tn? httus 數(shù)據(jù)結(jié)構(gòu)串課件 串的模式匹配 w 子串定位算法子串定位算法Index n基本思想：基本思想：先以主串先以主串S S中第一個字符為中第一個字符為S S子串子串 的頭一個字符，模式串的頭一個字符，模式串T T的長度作為的長度作為S S子串的子串的 長度，得到一個子串去與模式串長度，得到一個子串去與模式串T T中的字符逐中的字符逐 個比較，若子串與模式串相同，即返回個比較，若子串與模式串相同，即返回S S中子中子 串的第一

13、個字符位置作為模式串在主串串的第一個字符位置作為模式串在主串S S中的中的 位置；否則，取位置；否則，取S S中第二個字符為子串頭，將中第二個字符為子串頭，將 其往后的字符再依次和模式串其往后的字符再依次和模式串T T比較判斷是否比較判斷是否 相等，以此類推直到找到子串位置或沒有一相等，以此類推直到找到子串位置或沒有一 個子串與模式串相同為止個子串與模式串相同為止 ，前者模式匹配成，前者模式匹配成 功，后者模式匹配失敗。功，后者模式匹配失敗。 數(shù)據(jù)結(jié)構(gòu)串課件 樸素的模式匹配 w 主串主串S=S=ababcabcacbabababcabcacbab，模式串，模式串T= abcacT= abcac

14、 i=2 第一趟匹配：第一趟匹配： a b a b c a b c a c b a b a b c j=2 i=1 第二趟匹配：第二趟匹配： a b a b c a b c a c b a b a j=0 i=6 第三趟匹配：第三趟匹配： a b a b c a b c a c b a b a b c a c j=4 i=3 第四趟匹配：第四趟匹配： a b a b c a b c a c b a b a j=0 i=4 第五趟匹配：第五趟匹配： a b a b c a b c a c b a b a j=0 i=10 第六趟匹配：第六趟匹配： a b a b c a b c a c b a

15、b a b c a c（成功）（成功） j=5 數(shù)據(jù)結(jié)構(gòu)串課件 上面的模式匹配只需三趟 w 主串主串S=ababcabcacbab，模式串，模式串T= abcac i=3 第一趟匹配：第一趟匹配： a b a b c a b c a c b a b a b c j=3 (next3=1) i=3 第二趟匹配：第二趟匹配： a b a b c a b c a c b a b a b c a c j=5 (next5=2 i=7 第三趟匹配：第三趟匹配： a b a b c a b c a c b a b (a) b c a c j=5 i=7 怎么得來的呢？這就是怎么得來的呢？這就是KMP算法。

16、算法。 數(shù)據(jù)結(jié)構(gòu)串課件 KMP算法 wKMPKMPKnuth, Morris, PrattKnuth, Morris, Pratt三人發(fā)明三人發(fā)明 w特點特點 n無需回溯 n在O（nm）的時間量級上完成串的模 式匹配操作 數(shù)據(jù)結(jié)構(gòu)串課件 KMP算法 假設(shè)主串假設(shè)主串S為為s1s2s3sn，模式串，模式串T為為p1p2tm，若，若si與與tj發(fā)生失配，則有：發(fā)生失配，則有： si-j+1si-1=p1pj-1 (1) 由（由（1），若），若kj,則有：則有： si-k+1si-1= pj-k+1pj-1 (3) 若主串不回溯，設(shè)此時將模式串中第若主串不回溯，設(shè)此時將模式串中第k（kj）個字符繼續(xù)

17、比較，則有：）個字符繼續(xù)比較，則有： si-k+1si-1= p1pk-1 (2) 由（由（2）和（）和（3），則下式成立：），則下式成立： p1pk-1 =pj-k+1pj-1 （4） 該等式只與模式串有關(guān)，與主串無關(guān)。該等式只與模式串有關(guān)，與主串無關(guān)。 數(shù)據(jù)結(jié)構(gòu)串課件 若模式串若模式串P為為 abaabc，由定義可得，由定義可得next函數(shù)值函數(shù)值 j1 2 3 4 5 6 模式串模式串a(chǎn) b a a b c nextj0 1 1 2 2 3 KMP算法 = = = 其它情況 當此集合不空時且 時當 1 . jk1 |kmax 10 1111jkjk pppp j jnext next函數(shù)

18、的定義函數(shù)的定義 數(shù)據(jù)結(jié)構(gòu)串課件 i=2 第一趟匹配：第一趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b j=2 next2=1 i=2 第二趟匹配：第二趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a j=1 next1=0 i=3 i=8 第三趟匹配：第三趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b a a b c j=1 j=6 next6=3 i=8 i=12 第四趟匹配：第四趟匹配： 主串主串 a c a

19、 b a a b a a b c a c a a b c 模式串模式串 (a b) a a b c j=3 j=7 KMP算法手工模擬 主串主串 S=a c a b a a b a a b c a c a a b c 模式串模式串 P=a b a a b c 數(shù)據(jù)結(jié)構(gòu)串課件 0 1 2 3 1 1 2 3 1 0 1 1 1 2 3 4 5 1 j123456 789 模式串a(chǎn)aabca aba j1 2 3 4 5 6 7 8 9 模式串 a b c a b c a c b 求模式串的next函數(shù)值舉例 數(shù)據(jù)結(jié)構(gòu)串課件 如何求next函數(shù) 已知next1 = 0，假設(shè)nextj = k且 t

20、j = tk，則有 nextj+1 = k+1= nextj+1； 若nextj = k且 tj tk，則需往前回溯，檢查 tj = t?。 這實際上也是一個匹配的過程，不同在于主串和模 式串是同一個串。 若k=nextk且tj = tk，則nextj=nextk+1，若tj tk 則繼續(xù)往前回溯，直到存在k使tj = tk或k=0 0 1 1 2 2 3 4 3 j1234 5 678 模式串babb abab 數(shù)據(jù)結(jié)構(gòu)串課件 利用KMP算法的子串定位函數(shù) int IndexKMP(STRING *S,*T) 利用模式串利用模式串T的的next函數(shù)求函數(shù)求T在主串在主串S中的位置的中的位置的

21、KMP算法。其中算法。其中T非空非空 i=0; j=1; while(ilength +j； 繼續(xù)比較后繼字符繼續(xù)比較后繼字符 else j=nextj; 模式串向右移動模式串向右移動 while if(jT-length) return i-T-length+1; 匹配成功匹配成功 else return 0; IndexKMP 數(shù)據(jù)結(jié)構(gòu)串課件 對對S=aabcbabcaabcaabaS=aabcbabcaabcaaba，T=bcaT=bca，畫出以，畫出以T T為模為模 式串，式串，S S為目標串的匹配過程。為目標串的匹配過程。 a a b c b a b c a a b c a a b

22、a b b b c a b c b b c a bca的next值數(shù)為: 011 利用KMP算法舉例 數(shù)據(jù)結(jié)構(gòu)串課件 如何求next函數(shù) 已知已知next1=0，假設(shè)，假設(shè)nextj=k且且 pj=pk，則有，則有 nextj+1=k+1=nextj+1；若；若nextj=k且且 pj pk，則需往，則需往 前回溯，檢查前回溯，檢查 pj=p?。這實際上也是一個匹配的過程，不同在于主。這實際上也是一個匹配的過程，不同在于主 串和模式串是同一個串。若串和模式串是同一個串。若k=nextk且且pj=pk，則，則 nextj=nextk+1，若，若pj pk 則繼續(xù)往前回溯，直到存在則繼續(xù)往前回溯，

23、直到存在k 使使pj=pk或或k=0。next函數(shù)算法描述如下：函數(shù)算法描述如下： void GetNext(STRING *P,int next) 求模式串求模式串P的的next函數(shù)值并存入數(shù)組函數(shù)值并存入數(shù)組next。 i=1; next1=0; j=0; while(ilength) if(j=0|P-stri-1=P-strj-1) +i; +j; nexti=j; else j=nextj; while GetNext 數(shù)據(jù)結(jié)構(gòu)串課件 next函數(shù)的改進 問題的提出問題的提出 模式串模式串P=aaaab，其，其next函數(shù)值為函數(shù)值為01234，若主串，若主串 為為aaabaaaba

24、aaab，當，當i4，j4時時sipj，由，由nextj的指示還需的指示還需 進行進行i4、j3，i4、j2，i4、j1等三次比較。實際上，由等三次比較。實際上，由 于模式中第于模式中第1、2、3個字符和第個字符和第4個字符都相等，因此這種比較是不個字符都相等，因此這種比較是不 必要的，可以將模式串一次向右滑動必要的，可以將模式串一次向右滑動4個字符直接進行個字符直接進行i5、j1的的 比較。也就是說，若比較。也就是說，若nextj=k，當，當si與與pj失配且失配且pjpk，則下一步不，則下一步不 需將主串中的需將主串中的si與與pk比較，而是直接與比較，而是直接與nextk進行比較。由以上

25、思進行比較。由以上思 想對想對next函數(shù)進行改進，得到函數(shù)進行改進，得到nextval函數(shù)如下函數(shù)如下 j1 2 3 4 5 模式串模式串a(chǎn) a a a b nextj0 1 2 3 4 nextvalj0 0 0 0 4 數(shù)據(jù)結(jié)構(gòu)串課件 nextval函數(shù) void GetNextVal(STRING *P,int nextval) 求模式串求模式串P的的next函數(shù)修正值存入數(shù)組函數(shù)修正值存入數(shù)組nextval。 i=1; nextval1=0; j=0; while(ilength) if(j=0|P-stri-1=P-strj-1) +i; +j; if(P-stri-1!=P-st

26、rj-1) nextvali=j; else nextvali=nextvalj; else j=nextvalj; while GetNextVal 數(shù)據(jù)結(jié)構(gòu)串課件 利用nextval求模式匹配舉例 （1）p的的nextval函數(shù)值為函數(shù)值為0110132。 （2）利用利用KMP(改進的改進的nextval)算法，每趟匹配過程如下：算法，每趟匹配過程如下： 第一趟匹配：第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配：第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配：第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹