數(shù)據(jù)結(jié)構(gòu)第4章(新)

數(shù)據(jù)結(jié)構(gòu)0第4章串4.1串類(lèi)型的定義4.2串的表示和實(shí)現(xiàn)4.3串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)14.1串類(lèi)型的定義1.基本概念串(字符串)String：是零個(gè)或多個(gè)字符組成的有限序列。一般記為：S=‘a(chǎn)1a2...an’(n≥0)

棧、隊(duì)列：操作受限的線(xiàn)性表。串：取值范圍受限的線(xiàn)性表，數(shù)據(jù)對(duì)象約束為字符集。其中S是串的名字,用單引號(hào)括起來(lái)的字符序列是串的值，ai(1≤i≤n)可以是字母、數(shù)字或其它字符。串的長(zhǎng)度：串中字符的個(gè)數(shù)n。空串(NullString)：n=0時(shí)的串稱(chēng)為空串，用符號(hào)“

”表示。數(shù)據(jù)結(jié)構(gòu)2下面是一些串的例子：

（1）a=‘LIMING’

（2）b=‘PEJINGUNIUERCITY’

（3）c=‘DATASTRUCTURE’

（4）d=‘’

（5）e=‘’

說(shuō)明：串中包含的字符個(gè)數(shù)，稱(chēng)為串的長(zhǎng)度。

長(zhǎng)度為0的串稱(chēng)為空串，它不包括任何字符，上面（4）中的串d是空串,，(5)中的e是包含一個(gè)空格符的空格串；串中所包含的字符可以是字母、數(shù)字或其他字符，這依賴(lài)于具體計(jì)算機(jī)所允許的字符集。另外,通常以字符在序列中的序號(hào)為該字符在串中的位置數(shù)據(jù)結(jié)構(gòu)3子串：串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的子串?！?/p>

”為任意串的子串。主串：包含子串的串相應(yīng)地稱(chēng)為主串。

S為一長(zhǎng)度為n的串，其中的字符各不相同，則S的所有子串的個(gè)數(shù)：

S中互異的非平凡子串（非空且不同于S本身）的個(gè)數(shù)：特別地，空串是任意串的子串，任意串是其自身的子串。數(shù)據(jù)結(jié)構(gòu)4位置：字符在串中的序號(hào)稱(chēng)為該字符在串中的位置。子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來(lái)表示。

A=‘ChinaBeijing’,B=‘Beijing’,C=‘China’,則它們的長(zhǎng)度分別為13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。串相等：當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱(chēng)這兩個(gè)串是相等的，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等,并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等?？崭翊河梢粋€(gè)或多個(gè)空格組成的串。與空串不同。數(shù)據(jù)結(jié)構(gòu)52.串的基本運(yùn)算:

串賦值StrAssign(&T,chars)

初始條件:chars是字符串常量。操作結(jié)果:生成一個(gè)值等于chars的串T。串比較StrCompare(S,T)

初始條件:串S和T存在。操作結(jié)果:若S>T,則返回值>0;如S=T,則返回值=0;

若S<T,則返回值<0。"串值大小"是按"詞典次序"進(jìn)行比較的;只有在兩個(gè)串的長(zhǎng)度相等且每個(gè)字符一一對(duì)等的情況下稱(chēng)兩個(gè)串相等。

數(shù)據(jù)結(jié)構(gòu)6求串長(zhǎng)StrLength(S)

初始條件:串S存在。操作結(jié)果:返回串S的長(zhǎng)度,即串S中的元素個(gè)數(shù)。串聯(lián)接Concat(&T,S1,S2)

初始條件:串S1和S2存在。操作結(jié)果:將T返回由S1和S2聯(lián)接而成的新串。"串聯(lián)接"操作的結(jié)果是生成一個(gè)新的串，其值是"將第二的串的第一個(gè)字符緊接在第一個(gè)串的最后一個(gè)字符之后"得到的字符序列。

數(shù)據(jù)結(jié)構(gòu)7求子串SubString(&Sub,S,pos,len)

初始條件:串S存在,1≤pos≤StrLength(S)且

1≤len≤StrLength(S)-pos+1。操作結(jié)果:用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。"子串"指串中任意個(gè)連續(xù)的字符組成的子序列。如：操作SubString(Sub,"commander",4,3)得到的結(jié)果是Sub="man"。顯然必須在滿(mǎn)足初始條件中規(guī)定的"起始位置"和"長(zhǎng)度"之間的約束關(guān)系時(shí)才能求得一個(gè)合法的子串。允許len的下限為0是由于空串也是合法串，但實(shí)際上求長(zhǎng)度為0的子串是沒(méi)有意義的。數(shù)據(jù)結(jié)構(gòu)8定位函數(shù)intIndex(StringS,StringT,intpos)//T為非空串。若主串S中第pos個(gè)字符之后存在與T相等的子//串，則返回第一個(gè)這樣的子串在S中的位置，否則返回0。{if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;}}return0;}數(shù)據(jù)結(jié)構(gòu)94.2串的表示和實(shí)現(xiàn)1.定長(zhǎng)順序存儲(chǔ)表示（定長(zhǎng)順序串）＃defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];定長(zhǎng)順序串的存儲(chǔ)分配是在編譯時(shí)完成的。與前面所講的線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)類(lèi)似,用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列。串長(zhǎng)的表示：①以下標(biāo)為0的數(shù)組分量存放串的實(shí)際長(zhǎng)度；②串值后加入一個(gè)不計(jì)入串長(zhǎng)的結(jié)束標(biāo)記字符，C中“\0”表串值的終結(jié)，其ASCⅡ碼值為0。超出予定義長(zhǎng)度的串值被舍去，稱(chēng)之為“截?cái)唷薄?shù)據(jù)結(jié)構(gòu)10串聯(lián)接Concat(SString&T,SString

S1,SString

S2)S1[0]+S2[0]≤MAXSTRLEN，T是正確的結(jié)果。S1[0]<MAXSTRLEN，而S1[0]+S2[0]>MAXSTRLE

則S2會(huì)有部分字符被舍棄。(3)S1[0]=MAXSTRLEN，則S2的全部字符被舍棄，T與S1相等。思考:課本是否有錯(cuò)誤,是否遺漏了S1[0]>MAXSTRLEN數(shù)據(jù)結(jié)構(gòu)11StatusConcat(SString&T,SStringS1,SStringS2){//S1,S2聯(lián)接后成為新串送入T,0下標(biāo)變量存

//放串的長(zhǎng)度。if(s1[0]+s2[0]<=MAXSTRLEN){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}

S1S2

TT[0]MAXSTRLEN1558?數(shù)據(jù)結(jié)構(gòu)12elseif(s1[0]<MAXSTRLEN){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}

S1S2

TMAXSTRLEN1058?數(shù)據(jù)結(jié)構(gòu)13else{T[1..MAXSTRLEN]=S1[1..MAXSTRLEN];T[0]=MAXSTRLEN;uncut=FALSE;}returnuncut;}//Concat高級(jí)語(yǔ)言中，可以觀(guān)察到串在存儲(chǔ)空間不夠時(shí)會(huì)自動(dòng)截取，并不報(bào)錯(cuò)，故這里并不擴(kuò)展空間。T

S1S2

MAXSTRLEN:558?數(shù)據(jù)結(jié)構(gòu)14求子串Status

SubString(SString&Sub,SStringS,intpos,intlen){if(pos<0||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}

“字符序列的復(fù)制”數(shù)據(jù)結(jié)構(gòu)15思考：StrCopy如何實(shí)現(xiàn)？StatusStrCopy(SString&T,SStringS){}數(shù)據(jù)結(jié)構(gòu)16S.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1為串S重新分配存儲(chǔ)空間,并將S復(fù)制到新空間將S的第pos個(gè)字符及后面的字符后移，為插入T騰出位置插入T修改串長(zhǎng)串插入：在串S的第pos個(gè)字符前插入串T數(shù)據(jù)結(jié)構(gòu)17串插入StatusStrInsert(HString&S,intpos,HStringT)//在串S的pos個(gè)字符之前插入串T{if(pos<1||pos>S.length+1)returnERROR;//插入位置不適

if(T.length){if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];S.length+=T.length;}returnOK;}數(shù)據(jù)結(jié)構(gòu)182.堆分配存儲(chǔ)表示（堆串）在C語(yǔ)言中，已經(jīng)有一個(gè)稱(chēng)為“堆”的自由存儲(chǔ)空間，并可用malloc（）和free（）函數(shù)完成動(dòng)態(tài)存儲(chǔ)管理。typedefstruct{char*ch；

intlength；}HString；

比較：

#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];

數(shù)據(jù)結(jié)構(gòu)193.串的塊鏈存儲(chǔ)表示（鏈串）＃defineCHUNKSIZE<大小>typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head;Chunk*tail;intcurlen;}LString;數(shù)據(jù)結(jié)構(gòu)20存儲(chǔ)密度大，一些操作（如插入，刪除）有所不便，引起大量字符移動(dòng)，適合于在串基本保持靜態(tài)使用方式時(shí)采用；存儲(chǔ)密度小，運(yùn)算處理方便，但存儲(chǔ)空間量大，若處理過(guò)程中，需大量?jī)?nèi)外存交換，會(huì)影響總效率；串的字符集的大小，也會(huì)影響串值存儲(chǔ)方式的選取。數(shù)據(jù)結(jié)構(gòu)21總結(jié)（1）空串與空格串是不相同的，空串的長(zhǎng)度為0，空格串的長(zhǎng)度為包含的空格個(gè)數(shù)。（2）串是有限個(gè)字符的序列，是一種取值范圍受限的特殊的線(xiàn)性表。數(shù)據(jù)結(jié)構(gòu)221.樸素模式匹配算法求子串位置的定位函數(shù)Index(S,T,pos).模式匹配：子串的定位操作通常稱(chēng)作串的模式匹配。目標(biāo)串：主串S。模式串：子串T。匹配成功：若存在T的每個(gè)字符依次和S中的一個(gè)連續(xù)字符序列相等，則稱(chēng)匹配成功。返回T中第一個(gè)字符在S中的位置。匹配不成功：返回0。4.3串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)23第1趟 S abbabaT aba

第2趟 S abbaba T aba

第3趟

S abbaba T aba

第4趟 S abbaba Taba

窮舉的模式匹配過(guò)程i=i-j+2;j=1;↑j↓i數(shù)據(jù)結(jié)構(gòu)24子串定位intIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])returni-T[0];elsereturn0;}數(shù)據(jù)結(jié)構(gòu)25樸素模式匹配算法的時(shí)間復(fù)雜度主串長(zhǎng)n；子串長(zhǎng)m?？赡芷ヅ涑晒Φ奈恢茫?~n-m+1)。①最好的情況下，第i個(gè)位置匹配成功，比較了（i-1+m）次，平均比較次數(shù)：最好情況下算法的平均時(shí)間復(fù)雜度O(n+m)。②最壞的情況下，第i個(gè)位置匹配成功，比較了（i*m）次，平均比較次數(shù)：設(shè)n>>m，最壞情況下的平均時(shí)間復(fù)雜度為O(n*m)。數(shù)據(jù)結(jié)構(gòu)26分析算法的思想：

從主串S的第pos個(gè)字符起和模式的第一個(gè)字符比較，若相等，繼續(xù)比較后續(xù)字符，否則從主串的下一個(gè)字符起再重新和模式的字符比較。以此類(lèi)推，直到模式T中的每個(gè)字符依次和主串S中的一個(gè)連續(xù)的字符序列相等，則匹配成功，函數(shù)返回T首字符在S中的位置；否則匹配不成功。問(wèn)題：當(dāng)主串與模式串存在多次部分匹配時(shí)，就顯得效率低下。如0、1串在T=“00001”,S=“0000000000001”時(shí)，每次都有四次的多余比較，而0、1串又是普遍存在的。4.3串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)272.模式匹配的改進(jìn)算法-KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,簡(jiǎn)稱(chēng)KMP算法。該算法主要是消除了主串指針的回溯,從而使算法效率有了某種程度的提高。因p1≠p2,s2=p2,必有s2≠p1,又因p1=p3,s3=p3,所以必有s3=p1。因此,第二次匹配可直接從i=4,j=2開(kāi)始。數(shù)據(jù)結(jié)構(gòu)28改進(jìn)：每趟匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，不回溯主指針i，利用已得到的“部分匹配”結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn)的一段距離，繼續(xù)進(jìn)行比較。數(shù)據(jù)結(jié)構(gòu)29s1s2s3…si-j+1si-j+2…si-2si-1sisi+1‖‖‖‖≠

p1p2…pj-2pj-1pjpj+1(在j處匹配不成功)‖‖

p1…pk-1pkpk+1①“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”（部分匹配）②“p1p2…pk-1”=“si-k+1si-k+2…si-1”(k為下一次要與i匹配的位置)③“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”(真子串）數(shù)據(jù)結(jié)構(gòu)30

max{k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1”}

當(dāng)此集合非空時(shí)

0當(dāng)j=1時(shí)

1其他情況next[j]=為此,定義next[j]函數(shù)，表明當(dāng)模式中第j個(gè)字符與主串中相應(yīng)字符“失配”時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符的位置。數(shù)據(jù)結(jié)構(gòu)31

0當(dāng)j=1時(shí)

Next[j]=M{k|1<k<j且‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’}1其它情況例：j12345678

模式串a(chǎn)baabcacnext[j]01122312練習(xí)：求下列串的next函數(shù)值串：s=“abacabaaad”

0112123422數(shù)據(jù)結(jié)構(gòu)32voidget_next(charT[],intnext[])

{

//求模式串T的next函數(shù)值并存入數(shù)組next。

i=1;next[1]=0;j=0;

while(T[j]!='\0'){

if(j==0||T[i]==T[j])

{++i;++j;next[i]=j;}

elsej=next[j];

}

}//get_next

數(shù)據(jù)結(jié)構(gòu)33intIndex_KMP(SStringS,SStringT,intpos){i=pos,j=1;while(i<S[0]&&j<T[0]){if(j==0||S[i]==T[j]){i++;j++;}else

j=next[j];/*i不變,j后退*/}if(j>T[0])returni-T[0];/*匹配成功*/elsereturn0; /*返回不匹配標(biāo)志*/}數(shù)據(jù)結(jié)構(gòu)343、模式匹配的KMP算法

i=2

第一趟主串:acabaabaabcacaabc

子串

abj=2next[2]=1i=2第二趟主串:acabaabaabcacaabc

子串a(chǎn)j=1next[1]=0i=3i=8第三趟主串:acabaabaabcacaabc

子串a(chǎn)baabcj=1j=6next[6]=3i=8i=14第四趟主串:acabaabaabcacaabc

子串a(chǎn)baabcacj=3j=9圖4.9利用模式的next函數(shù)進(jìn)行匹配的過(guò)程示例參看演示程序

j12345678模式串a(chǎn)baabcacnext[j]01122312數(shù)據(jù)結(jié)構(gòu)35j1234567891011121314151617模式串a(chǎn)bcaabbcabcaabdab0next[j]1112231123456712數(shù)據(jù)結(jié)構(gòu)36next函數(shù)的改進(jìn)j12345模式aaaabnext