華中科技電子與信息工程系大二上學(xué)期學(xué)習(xí)數(shù)構(gòu)數(shù)據(jù)結(jié)構(gòu)課件

第四章串引言：字符串，簡(jiǎn)稱串，計(jì)算機(jī)處理的非數(shù)值對(duì)象基本上就是字符串?dāng)?shù)據(jù)。如：匯編和各種語(yǔ)言的編譯程序、文字編輯程序、語(yǔ)言翻譯系統(tǒng)等都以字符串為處理對(duì)象的。而計(jì)算機(jī)硬件結(jié)構(gòu)是適應(yīng)數(shù)值計(jì)算需要而設(shè)計(jì)的，實(shí)現(xiàn)串處理時(shí)，合適存儲(chǔ)結(jié)構(gòu)的選擇就很重要。內(nèi)容：串類型的定義串的表示和實(shí)現(xiàn)串的模式匹配算法4.1串類型的定義1、串的定義串：n個(gè)字符的有限序列，記為：s=‘a(chǎn)1,a2,……..,an’

串名串值（用‘’括起來(lái)）串相等：串長(zhǎng)度相等，且對(duì)應(yīng)位置上字符相等，否則，串不相等。

串的長(zhǎng)度：串中字符個(gè)數(shù)（n>=0），n=0為空串。子串：串S中任意個(gè)連續(xù)的字符序列，叫s的子串;S叫主串.空格串：n個(gè)空格組成的串例如:(1)a=‘BEI’,n=3b=‘JING’,n=4c=‘BEIJING’n=7d=‘BEI

JING’n=8(2)a、b為c子串.(3)a的位置：在c中

a的位置=1;

在d中

a的位置=1;b的位置：在c中

a的位置=4;

在d中

a的位置=5;2、串的抽象數(shù)據(jù)類型定義串的抽象數(shù)據(jù)類型定義見(jiàn)教材P71-72串賦值StrAssign:給串賦值串比較StrCompare:比較兩串是否相等求串長(zhǎng)StrLength:求串的長(zhǎng)度串聯(lián)接Concat:將一個(gè)串聯(lián)接到另一串的尾部求子串SubString:找出串s從i位置后長(zhǎng)度為m的子串.串的幾種常見(jiàn)操作4.2串的表示及實(shí)現(xiàn)

定長(zhǎng)順序存儲(chǔ)表示用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列堆分配存儲(chǔ)表示用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列,但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。串的塊鏈存儲(chǔ)表示鏈?zhǔn)椒绞酱鎯?chǔ)1、定長(zhǎng)順序存儲(chǔ)表示

#defineMAXSTRLEN255//最大串長(zhǎng)

typedefunsignedcharSString[MAXSTRLEN+1];

用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，每個(gè)串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)?？捎枚ㄩL(zhǎng)數(shù)組實(shí)現(xiàn)，描述如下：在PASCAL中：串長(zhǎng)信息存放在SString[0]中；在C語(yǔ)言中：在串尾加結(jié)束字符‘\0’，串長(zhǎng)隱含

串長(zhǎng)信息標(biāo)識(shí)：

在此種存儲(chǔ)結(jié)構(gòu)中，如果在操作中出現(xiàn)串值長(zhǎng)度超過(guò)上界MAXSTRLEN時(shí)，約定采用截尾法處理特點(diǎn)：舉例：串的聯(lián)結(jié)和求子串見(jiàn)教材P73-752、堆存儲(chǔ)表示系統(tǒng)將一個(gè)容量較大、地址連續(xù)的空間作為所有串的存儲(chǔ)空間，我們稱這個(gè)空間為“堆”，每當(dāng)生成一個(gè)串時(shí)，系統(tǒng)就通過(guò)malloc()從這個(gè)空間中動(dòng)態(tài)地分配一個(gè)該串所需的存儲(chǔ)空間，當(dāng)刪除一個(gè)串時(shí)，就利用free()將所占的空間釋放?？臻e區(qū)Data_Structure堆存儲(chǔ)結(jié)構(gòu)在堆存儲(chǔ)結(jié)構(gòu)中，一個(gè)串可以由它在堆中的起始位置和串的長(zhǎng)度唯一確定，因此，串的存儲(chǔ)表示可以描述為：typedefstruct{char*ch;//若非空串,按串長(zhǎng)分配;否則ch=NULL

intlength;//串長(zhǎng)度}//HString若在操作中串值改變，重新按新串長(zhǎng)度分配空間。3、鏈?zhǔn)酱鎯?chǔ)表示串也可以用鏈表來(lái)表示，在鏈?zhǔn)浇Y(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以存放一個(gè)字符，也可存放多個(gè)字符，所以存在一個(gè)“結(jié)點(diǎn)大小”問(wèn)題，當(dāng)結(jié)點(diǎn)的大小大于1時(shí)，因串值不一定是結(jié)點(diǎn)數(shù)據(jù)區(qū)的整數(shù)倍，所以，最后一個(gè)結(jié)點(diǎn)的剩余空間填“#”

，或其它非串值字符。DCBAHGFE^###I(b)結(jié)點(diǎn)大小為4的鏈表AB^I(a)結(jié)點(diǎn)大小為1的鏈表例如：#defineCHUNKSIZE80typedefstructChunk{charch[CHUNKSIZE];//數(shù)據(jù)域

structChunk*next;//指針域}Chunk;//定義結(jié)點(diǎn)類型結(jié)點(diǎn)的定義：typedefstruct{Chunk*head;//頭指針

Chunk*tail;//尾指針

intcurLen;//結(jié)點(diǎn)個(gè)數(shù)

}Lstring;//定義用鏈?zhǔn)酱鎯?chǔ)的串類型鏈串的定義：存儲(chǔ)密度=串之所占的空間/實(shí)際分配的空間。

在鏈?zhǔn)浇Y(jié)構(gòu)中，結(jié)點(diǎn)大小的選擇直接影響到串處理的效率。當(dāng)處理的字符有幾百萬(wàn)個(gè)時(shí)，就要求考慮串值的存儲(chǔ)密度。串的存儲(chǔ)密度4.3串的模式匹配算法

求子串位置的定位操作，稱為串的模式匹配，是串處理系統(tǒng)中最重要的操作之一。算法說(shuō)明：返回t在s中第pos個(gè)字符之后的位置;若不存在，返回0。其中，t非空；1<=pos<=StrLength(s).問(wèn)題：求子串位置的定位算法

intIndex(SStrings,SStringt,intpos)1、傳統(tǒng)匹配算法將主串的第1個(gè)字符和模式的第1個(gè)字符比較，如果相等：繼續(xù)逐個(gè)比較后續(xù)字符。如果不等：從主串的下一字符起，重新與模式的第一個(gè)字符比較；直到主串的一個(gè)連續(xù)子符序列與模式相等。返回值為s中與t匹配的子序列第一個(gè)字符的序號(hào)。即匹配成功。否則，匹配失敗，返回值0；算法思想：例：s=‘a(chǎn)babcabcacbab’pos=1t=‘a(chǎn)bcac’

求：串t在串s中pos個(gè)字符之后的位置。ababcabcacbabababcabcacbabababcabcacbabi=1j=1ai=3j=3abci=2j=2abj=1i=2aj=1i=3aj=1i=4ai=6j=4abcai=5j=3abci=7j=5abcaci=4j=2abj=1i=5aj=1i=6ai=10j=5abcac算法流程圖時(shí)間復(fù)雜度：最好為O(n+m);最差為O(n*m)2、KMP匹配算法算法思想：在匹配過(guò)程中,當(dāng)主串中的字符與模式中的字符不相等時(shí),不回溯i指針,而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn)的一段距離后,繼續(xù)進(jìn)行足字比較.2)模式向右到底應(yīng)該滑多遠(yuǎn)才是高效率的?問(wèn)題:1)模式向右怎么滑動(dòng)?不失一般性，假設(shè)：主串為：S=‘s1s2…sn’模式串為：’p1p2…pm’在匹配過(guò)程中，當(dāng)si與

pj失配后，模式串最多應(yīng)該向右滑動(dòng)多遠(yuǎn)？，即：si應(yīng)該與模式串中哪個(gè)字符比較？假設(shè)應(yīng)該與模式串中第k個(gè)字符進(jìn)行比較，即:s1s2s3s4…si-1si

…snp1p2…

pk-1pk

…s1s2…

si-k+1si-k+2…

si-1si

…snpj-k+1pj-k+2…

pj-1pj

…而所得到的部分“部分匹配結(jié)果”是:模式串中的第j個(gè)字符以前的k-1個(gè)字符和主串中第i個(gè)字符以前的k-1個(gè)字符已經(jīng)匹配,如下圖所示:‘p1p2…pk-1’=‘si-k+1si-1+2…si-1’(1)

‘p1p2…pj-1’=‘si-k+1si-1+2…si-1’

(2)(3)

‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’2.1next函數(shù)的定義定義k=next[j],則next[j]的含義為:當(dāng)模式的第j個(gè)字符與主串中相對(duì)應(yīng)的字符失配時(shí),則將模式中的第next[j]個(gè)字符和主串中該字符進(jìn)行比較,由此可以得出模式串的next函數(shù)的定義:next[j]=0（將模式串向右滑動(dòng)1個(gè)字符）當(dāng)j=1時(shí)1（從模式串第１個(gè)字符開(kāi)始）其它情況Max{k|1<k<j&&‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’}當(dāng)此集合不空時(shí)next[j]函數(shù)越大，則j位置以前與主串匹配的字符數(shù)越多，失配后與模式串中比較的位置就越靠后，移動(dòng)的步伐就越慢，比較次數(shù)就越多，效率就越低。next[j]函數(shù)就是模式串從起始位置往右的‘p1p2…pk-1’與從j的前一位置（j-1位置）往左的pj-k+1pj-k+2…pj-1相匹配的最大子串（除串本身外）的長(zhǎng)度加１。例如：abaabcac1234567801122312jnext[j]模式串2.2next函數(shù)的求法由next函數(shù)的定義可以知道,模式串的next函數(shù)的值只與模式串本身有有關(guān),而與主串無(wú)關(guān),那么如何求模式串的next函數(shù)呢?從next函數(shù)的定義出發(fā),用遞推的方法可以求出,步驟如下:1)next函數(shù)初值next[1]=02)設(shè)next[j]=k,求next[j+1]由next[j]=k可以得到:‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’不存在k’>k滿足上式;反過(guò)來(lái),如果能夠得到上述匹配的串,我們可以求出next[j].為了求出next[j+1],可以分兩種情況進(jìn)行討論:情況1:Pnext[j]=Pj,則有:‘p1p2…pnext[j]’=‘pj-k+1pj-k+2…pj’不存在k’>next[j]滿足上式按照next函數(shù)的定義可以得到:next[j+1]=next[j]+1情況2:Pnext[j]!=Pj,則有:‘p1p2…pnext[j]’!=‘pj-k+1pj-k+2…pj’因此,如果能夠在模式串第j個(gè)字符開(kāi)始,往左找到一個(gè)滿足上式的最大子串,就可以求next[j+1],這又是一個(gè)匹配問(wèn)題:當(dāng)pnext[j]與pj失配時(shí)(此時(shí)將‘pj-k+1pj-k+2…pj’看成主串，‘p1p2…pnext[j]’看為模式串),則應(yīng)該將模式串的第next[next[j]]字符與主串的pj進(jìn)行比較,即：比較‘p1p2…pnext[next[j]]’與‘pj-k+1pj-k+2…pj’‘p1p2…pnext[next[j]]’=‘pj-k+1pj-k+2…pj’如果則:next[j+1]=next[k]+1=next[next[j]]+1…如此進(jìn)行下去，直到pj和模式中某個(gè)字符匹配成功或者不存在任何k’滿足匹配條件,這時(shí),next[j+1]=1,具體算法如下:i=1;j=0next[1]=0i<T[0]j==0||T[i]==T[j]++i;++j;next[j]=j;j=next[j];ENDYYNN算法流程圖例如：求abaabcac模式串的next函數(shù)next[1]=0next[2]=1pnext[1]!=p1next[3]=1pnext[2]!=p2next[4]=2pnext[3]=p3next[5]=2pnext[4]!=p4pnext[next[4]]=p4next[6]=3pnext[5]=p5next[7]=1pnext[6]!=p6pnext[3]!=p6pnext[3]!=p6next[8]=2pnext[7]=p72.3KMP模式匹配算法求出next函數(shù)以后，模式匹配算法可以按如下方法進(jìn)行：1）初始化i和j：i=pos；j=1；2）移動(dòng)i和j，比較Si和Pj；

if（Si==Pj）則i++；j++；

else比較Si和Pnext[j]

如此進(jìn)行下去，直到匹配或者