數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第4章【專業(yè)教育】

1、第四章 串,1,高等課堂,課前思考,從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)來(lái)說(shuō)，串是一種特殊的線性表;但就數(shù)據(jù)類型而言，串不是線性表,希望你帶著這個(gè)問(wèn)題開(kāi)始這一章的學(xué)習(xí)，并能在學(xué)完這一章的內(nèi)容之后能得出正確的結(jié)論,2,高等課堂,學(xué)習(xí)目標(biāo),1. 理解“串”類型定義中各基本操作的特點(diǎn)，并能正確利用它們進(jìn)行串的其它操作。 2. 理解串類型的各種存儲(chǔ)表示方法。 3. 理解串匹配的各種算法,3,高等課堂,重點(diǎn)和難點(diǎn),相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言，本章非整個(gè)課程的重點(diǎn)，鑒于串已是多數(shù)高級(jí)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，因此本章重點(diǎn)僅在于了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來(lái)實(shí)現(xiàn)串的其它操作。本章的難點(diǎn)

2、是理解實(shí)現(xiàn)串匹配的KMP算法的思想，但它不屬本章學(xué)習(xí)的基本要求，更不是重點(diǎn)學(xué)習(xí)內(nèi)容,知識(shí)點(diǎn),串的類型定義、串的存儲(chǔ)表示、串匹配、KMP算法,4,高等課堂,學(xué)習(xí)指南,雖然目前各常用的高級(jí)語(yǔ)言中都已經(jīng)實(shí)現(xiàn)了串類型，但由于它是通過(guò)軟件實(shí)現(xiàn)的，因此作為一個(gè)軟件工作者還是應(yīng)該了解串的實(shí)現(xiàn)方法。本章沒(méi)有必須完成的算法設(shè)計(jì)題，如果有興趣可以試試以下幾個(gè)題:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6個(gè)是練習(xí)串的基本操作的應(yīng)用，后2個(gè)是和KMP算法相關(guān)的練習(xí),5,高等課堂,4.1 串類型的定義,4.2 串的表示和實(shí)現(xiàn),4.3串的模式匹配算法,6,高等課堂,4.1串的

3、類型定義,一、 基本概念,1串的定義 串( string) 是由零個(gè)或多個(gè)字符組成的有限序列，記作s=a1a2an，其中s為串的名字，用成對(duì)的單引號(hào)括起來(lái)的字符序列為串的值，但兩邊的引號(hào)不算串值，不包含在串中。ai(1in)可以是字母、數(shù)字或其它字符。 n為串中字符的個(gè)數(shù)，稱為串的長(zhǎng)度,2空串 不含任何字符的串稱為空串，它的長(zhǎng)度n=0，記為s,3空格串 含有一個(gè)或多個(gè)空格的串，稱為空格串，它的長(zhǎng)度n為空格的個(gè)數(shù)，一般用符號(hào)“ ”表示空串,串是有限長(zhǎng)的字符序列，由一對(duì)單引號(hào)相括，如: a string,7,高等課堂,4子串、主串 通常將字符在串中的序號(hào)稱為該字符在串中的位置。子串在主串中的位置則

4、以子串的第一個(gè)字符在主串中的位置來(lái)表示。 若一個(gè)串是另一個(gè)串中連續(xù)的一段，則這個(gè)串稱為另一個(gè)串的子串，而另一個(gè)串相對(duì)于該串稱為主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，則s1為s2的子串，s2相對(duì)于s1為主串,另外，空串是任意串的子串，任意串是自身的子串。若一個(gè)串的長(zhǎng)度為n，則它的子串?dāng)?shù)目為 +1，真子串個(gè)數(shù)為 (除串本身以外的子串都稱為真子串)。 當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱這兩個(gè)串是相等的，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等, 并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等,8,高等課堂,二、串的抽象數(shù)據(jù)類型的定義如下,ADT String,數(shù)據(jù)對(duì)象,D ai |aiChar

5、acterSet, i=1,2,.,n, n0,數(shù)據(jù)關(guān)系,R1 | ai-1, ai D, i=2,.,n,9,高等課堂,基本操作,StrAssign ( m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在與T相等的子串 / Index,32,高等課堂,又如串的置換函數(shù)： Replace( / 0號(hào)單元存放串的長(zhǎng)度,38,高等課堂,或： type

6、def struct /* 串結(jié)構(gòu)定義 */ char chMAXLEN; int len; SString,39,高等課堂,按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為 “字符序列的復(fù)制,串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱之為 “截?cái)唷?特點(diǎn),40,高等課堂,Status Concat(SString S1, SString S2, SString / Concat,例如：串的聯(lián)接算法中需分三種情況處理,T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE

7、;,if (S10+S20 = MAXSTRLEN) / 未截?cái)?else if (S10 MAXSTRSIZE) / 截?cái)?else / 截?cái)?僅取S1,T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE;,T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE;,41,高等課堂,1) 串插入函數(shù)。 StrInsert(s, pos, t) /*在串s中序號(hào)為pos的字符之前插入串t */ SStr

8、ing *s, t; int pos; int i; if (poss-len) return(0); /* 插入位置不合法 */ if (s-len + t.lenlen + t.len-1;i=t.len + pos;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos=t.chi; s-len=s-len+t.len;,定長(zhǎng)順序存儲(chǔ)的操作實(shí)施,算法 串插入函數(shù),42,高等課堂,else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;it.len+pos-1;i-) s-chi=s-chi-t

9、.len; for (i=0;ichi+pos=t.chi; s-len=MAXLEN; else /* 串t的部分字符序列要舍棄 */ for (i=0;ichi+pos=t.chi; s-len=MAXSTRLEN; return(1);,43,高等課堂,2) 串刪除函數(shù)。 StrDelete(s, pos, len) /* 在串s中刪除從序號(hào)pos起len個(gè)字符 */ SString *s; int pos, len; int i; if (pos(s-len-len) return(0); for (i=pos+len;ilen;i+) s-chi-len=s-chi; s-len=s

10、-len - len; return(1);,算法 串刪除函數(shù),44,高等課堂,3) 串復(fù)制函數(shù)。 StrCopy(s, t) /* 將串t的值復(fù)制到串s中 */ SString *s, t; int i; for (i=0;ichi=t.chi; s-len=t.len;,算法 串復(fù)制函數(shù),45,高等課堂,4) 判空函數(shù)。 StrEmpty(s) /* 若串s為空(即串長(zhǎng)為0), 則返回1, 否則返回0 */ SString s; if (s.len=0) return(1); else return(0);,算法 判空函數(shù),46,高等課堂,5) 串比較函數(shù)。 StrCompare(s, t

11、) /* 若串s和t相等, 則返回0；若st，則返回1；若st，則返 回-1 */ SString s, t; int i; for (i=0;is.len,算法 串比較函數(shù),47,高等課堂,6) 求串長(zhǎng)函數(shù)。 StrLength(s)/* 返回串s的長(zhǎng)度 */ SString s; return(s.len);,算法 求串長(zhǎng)函數(shù),48,高等課堂,7) 清空函數(shù)。 StrClear(s) /* 將串s置為空串 */ SString *s; s-len=0; return(1);,算法 清空函數(shù),49,高等課堂,8) 連接函數(shù)。 Concat(s, t) /* 將串t連接在串s的后面 */ SS

12、tring *s, t; int i, flag; if (s-len + t.lenlen; ilen + t.len; i+) s-chi=t.chi-s-len; s-len+=t.len;flag=1;,50,高等課堂,else if (s-lenlen;ichi=t.chi-s-len; s-len=MAXSTRLEN;flag=0; else flag=0;/* 串s的長(zhǎng)度等于MAXLEN, 串t不被連接 */ return(flag);,算法 連接函數(shù),51,高等課堂,9) 求子串函數(shù)。 SubString(sub, s, pos, len) /* 將串s中序號(hào)pos起len個(gè)字

13、符復(fù)制到sub中 */ SString *sub, s; int pos, len; int i; if (poss.len | lens.len-pos) sub-len=0;return(0); else for (i=0;ichi=s.chi+pos; sub-len=len;return(1);,算法 求子串函數(shù),52,高等課堂,10) 定位函數(shù)。 StrIndex(s, pos, t) /* 求串t在串s中的位置 */ SString s, t; int pos; int i, j; if (t.len=0) return(0); i=pos;j=0; while (i=t.len)

14、 return(i-t.len); else return(0);,算法 定位函數(shù),53,高等課堂,typedef struct char *ch; / 若是非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū)， / 否則ch為NULL int length; / 串長(zhǎng)度 HString,二、串的堆分配存儲(chǔ)表示,特點(diǎn)：仍用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列，但其存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得,54,高等課堂,通常，C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc( )和free( )進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”。 C語(yǔ)言中的串以

15、一個(gè)空字符為結(jié)束符， 串長(zhǎng)是一個(gè)隱含值,這類串操作實(shí)現(xiàn)的算法為： 先為新生成的串分配一個(gè)存儲(chǔ)空間，然后 進(jìn)行串值的復(fù)制,55,高等課堂,Status Concat(HString / Concat,56,高等課堂,Status SubString(HString / SubString,57,高等課堂,Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len,58,高等課堂,三、串的塊鏈存儲(chǔ)表示,也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有 8 位二進(jìn)制數(shù)

16、，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串,存儲(chǔ)密度,數(shù)據(jù)元素所占存儲(chǔ)位,實(shí)際分配的存儲(chǔ)位,59,高等課堂,define CHUNKSIZE 80 / 可由用戶定義的塊大小 typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長(zhǎng)度 LString,60,高等課堂,例如: 在編輯系統(tǒng)中，整個(gè)文本編輯區(qū)可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)

17、成一個(gè)結(jié)點(diǎn)。即: 同一行的串用定長(zhǎng)結(jié)構(gòu)(80個(gè)字符), 行和行之間用指針相聯(lián)接,實(shí)際應(yīng)用時(shí)，可以根據(jù)問(wèn)題所需來(lái)設(shè)置結(jié)點(diǎn)的大小,61,高等課堂,這是串的一種重要操作，很多 軟件，若有“編輯”菜單項(xiàng)的話， 則其中必有“查找”子菜單項(xiàng),4.3串的模式匹配算法,子串的定位操作通常稱為串的模式匹配，是各種串處理系統(tǒng)中最重要的操作之一,62,高等課堂,初始條件：串S和T存在，T是非空串， 1posStrLength(S)。 操作結(jié)果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos個(gè)字符之后第一次出 現(xiàn)的位置；否則函數(shù)值為0,首先，回憶一下串匹配(查找)的定義,INDEX (S, T, pos

18、,63,高等課堂,下面討論以定長(zhǎng)順序結(jié)構(gòu) 表示串時(shí)的幾種算法,一、簡(jiǎn)單算法,二、首尾匹配算法,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,64,高等課堂,一、簡(jiǎn)單算法Brute-Force算法,例如,設(shè)目標(biāo)串s=“cddcdc”,模式串t=“cdc”。s的長(zhǎng)度為n(n=6),t的長(zhǎng)度為m(m=3)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。BF模式匹配過(guò)程如下所示,65,高等課堂,這個(gè)算法簡(jiǎn)單,易于理解,但效率不高,主要原因是:主串指針i在若干個(gè)字符序列比較相等后,若有一個(gè)字符比較不相等,仍需回溯(即i=i-j+1

19、)。該算法在最好情況下的時(shí)間復(fù)雜度為O(m),即主串的前m個(gè)字符正好等于模式串的m個(gè)字符。在最壞情況下的時(shí)間復(fù)雜度為O(n*m,66,高等課堂,int index(SqString s,SqString t) int i=0,j=0,k; while (i=t.len) k=i-t.len; /*返回匹配的第一個(gè)字符的下標(biāo)*/ else k=-1; /*模式匹配不成功*/ return k;,67,高等課堂,先比較模式串的第一個(gè)字符， 再比較模式串的最后一個(gè)字符， 最后比較模式串中從第二個(gè)到 第n-1個(gè)字符,二、首尾匹配算法,68,高等課堂,int Index_FL(SString S, SS

20、tring T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始點(diǎn) else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0;,檢查中間字符的匹配情況,69,高等課堂,k = 1; j = 2; while ( j tLength / 重新開(kāi)始下一次

21、的匹配檢測(cè),70,高等課堂,三、模式匹配的改進(jìn)算法（KMP算法,此方法由克努特(D.E.Knuth)莫里斯(J.H.Morris)普拉特(V.R.Pratt)同時(shí)發(fā)現(xiàn),1.基本思想：每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符不等時(shí)，不需回溯i指針，而是利用已得到的部分匹配結(jié)果，將模式串向右滑動(dòng)盡可能遠(yuǎn)的一段距離后繼續(xù)進(jìn)行比較。 避免多余的、不必要的比較，從而提高算法性能。算法總在0(n+m)的時(shí)間數(shù)量級(jí)上完成匹配操作,71,高等課堂,2.KMP算法匹配實(shí)例,72,高等課堂,1)模式串t中沒(méi)有真子串 真子串是指模式串t存在某個(gè)k(0kj),使得“t0t1tk”=“tj-ktj-k+1tj”成立。 例如t=cdc

22、就是這樣的模式串。在圖4.6中的第一次回溯,當(dāng)s0=t0,s1=t1,s2t2時(shí),算法中取i=1,j=0,使主串指針回溯一個(gè)位置,比較s1和t0。因t0t1,所以一定有s1t0。另外,因有t0=t2,s0=t0,s2t2,則一定可推出s2t0,所以也不必取i=2,j=0去比較s2和t0?？芍苯釉诘诙伪容^時(shí)取i=3,j=0,比較s3和t0。這樣,模式匹配過(guò)程主串指針i就可不必回溯,73,高等課堂,2)模式串中存在真子串 例如t=“abab”,由于“t0t1”=“t2t3”(這里k=1,j=3),則存在真子串。設(shè)s=“abacabab”,t=“abab”,第一次匹配過(guò)程如下所示,此時(shí)不必從i=1

23、(i=i-j+1=1),j=0重新開(kāi)始第二次匹配。因t0t1,s1=t1,必有s1t0,又因t0 =t2,s2=t2,所以必有s2=t0。因此,第二次匹配可直接從i=3,j=1開(kāi)始,74,高等課堂,現(xiàn)在我們討論一般情況。 設(shè)s=s0s1sn-1,t=t0t1tm-1,當(dāng)sitj (0in-m,0jm)時(shí),存在: t0t1tj-1=si-jsi-j+1si-1 (4.1) 若模式串中存在的真子串滿足: t0t1tk=tj-ktj-k+1tj (0kj) (4.2) 由(4.1)式說(shuō)明模式串中的子串t0t1tk-1已和主串si-ksi-k+1si-1匹配,下一次可直接比較si和tk,若不存在(4.

24、2)式,則結(jié)合(4.1)式說(shuō)明在t0t1tj-1中不存在任何以t0為首字符子串與si-j+1si-j+2si-1中以si-1為末字符的匹配子串,下一次可直接比較si和t0,75,高等課堂,為此,定義nextj函數(shù)如下: maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1” 當(dāng)此集合非空時(shí) -1 當(dāng)j=0時(shí) 0 其他情況,nextj,t=“abab”對(duì)應(yīng)的next數(shù)組如下,76,高等課堂,由模式串t求出next值的算法如下: void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.len

25、-1) if (k=-1 | t.chj=t.chk) /*k為-1或比較的字符相等時(shí)*/ j+;k+; nextj=k; else k=nextk;,77,高等課堂,int KMPIndex(SqString s,SqString t) /*KMP算法*/ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (i=t.len) v=i-t.len; /*返回匹配模式串的首字符下標(biāo)*/ else v=-1; /*返回不匹配標(biāo)志*/ return v;,78,高等課堂,設(shè)主串s的長(zhǎng)度為n,子串t長(zhǎng)度為m,在KMP算法中求next數(shù)組的時(shí)間復(fù)雜度為O

26、(m),在后面的匹配中因主串s的下標(biāo)不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時(shí)間復(fù)雜度為O(n+m,例如,設(shè)目標(biāo)串s=“aaabaaaab”,模式串t=“aaaab”。s的長(zhǎng)度為n(n=9),t的長(zhǎng)度為m(m=5)。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。KMP模式匹配過(guò)程如下所示,79,高等課堂,80,高等課堂,上述定義的next在某些情況下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配時(shí),當(dāng)i=3,j=3時(shí),s.ch3t.ch3,由nextj的指示還需進(jìn)行i=3、j=2,i=3、j=1,i=3、j=0等三次比較。實(shí)際上

27、,因?yàn)槟Ｊ街械牡?、2、3個(gè)字符和第4個(gè)字符都相等,因此,不需要再和主串中第4個(gè)字符相比較,而可以將模式一次向右滑動(dòng)4個(gè)字符的位置直接進(jìn)行i=4,j=0時(shí)的字符比較,KMP算法的改進(jìn),81,高等課堂,這就是說(shuō),若按上述定義得到nextj=k,而模式中pj=pk,則為主串中字符si和pj比較不等時(shí),不需要再和pk進(jìn)行比較,而直接和pnextk進(jìn)行比較,換句話說(shuō),此時(shí)的nextj應(yīng)和nextk相同。為此將nextj修正為nextvalj,82,高等課堂,由模式串t求出nextval值: void GetNextval(SqString t,int nextval) int j=0,k=-1; ne

28、xtval0=-1; while (jt.len) if (k=-1 | t.chj=t.chk) j+;k+; if (t.chj!=t.chk) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk;,83,高等課堂,84,高等課堂,本章小結(jié),在這一章介紹了串類型的定義及其實(shí)現(xiàn)方法，并重點(diǎn)討論了串操作中最常用的串定位操作（又稱模式匹配）的兩個(gè)算法。串的兩個(gè)顯著特點(diǎn)是，其一、它的數(shù)據(jù)元素都是字符，因此它的存儲(chǔ)結(jié)構(gòu)和線性表有很大不同，例如多數(shù)情況下，實(shí)現(xiàn)串類型采用的是堆分配的存儲(chǔ)結(jié)構(gòu)，而當(dāng)用鏈表存儲(chǔ)串值時(shí)，結(jié)點(diǎn)中數(shù)據(jù)域的類型不是字符，而是串，這種塊鏈結(jié)構(gòu)通常只在應(yīng)用程序中使用；其二、串的基本操作通常以串的整體作為操作對(duì)象，而不像線性表是以數(shù)據(jù)元素作為操作對(duì)象,85,高等課堂,串匹配”的簡(jiǎn)單算法,其算法思想直截了當(dāng)，簡(jiǎn)單易懂，適用于在一般的文檔編輯中應(yīng)用，但在