大學(xué)數(shù)據(jù)結(jié)構(gòu)課件-第4章串

1

4.1串類(lèi)型的定義

4.2串的表示和實(shí)現(xiàn)

4.3串的模式匹配算法第4章串2串（字符串）是由零個(gè)或多個(gè)字符組成的有限序列，記為：S=

‘a(chǎn)1a2……an-1an’

（n≥0）串的長(zhǎng)度：串中字符的個(gè)數(shù)；零個(gè)字符的串稱(chēng)為空串，記為串名串值（單引號(hào)內(nèi)的部分，但‘’不屬于串）串的相關(guān)術(shù)語(yǔ)空格串：由一個(gè)或多個(gè)空格組成的串，其長(zhǎng)度為串中空格字符的個(gè)數(shù)子串：串s中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的子串，包含子串的串s相應(yīng)地稱(chēng)為主串。子串位置：字符在序列中的序號(hào)稱(chēng)為該字符在串中的位置。子串在主串中的位置以第一個(gè)字符在主串中的位置來(lái)表示。串相等：兩個(gè)串相等，當(dāng)且僅當(dāng)這兩個(gè)串的值相等。即，只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。4.1

串類(lèi)型的定義3例：現(xiàn)有以下4個(gè)字符串‘’

a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEI□JING’問(wèn)：①4個(gè)字符串的的長(zhǎng)度分別是多少？

②

b是哪個(gè)串的子串？其在主串的位置是多少？

③串c是不是串d的子串，為什么？4.1串類(lèi)型的定義4StrAssign(&T,chars);//串賦值，生成一個(gè)值等于chars的串TStrCompare(S,T);//串比較，若S>T，返回值>0……StrLength(S);//求串長(zhǎng)Concat(&T,S1,S2);//串連接，用T返回S1+S2的新串SubString(&Sub,S,pos,len);//求S中pos位置起長(zhǎng)度為len的子串……Index(S,T,pos);//返回子串T在主串S中pos字符之后首次出現(xiàn)的位置Replace(&S,T,V);//用子串V代替串S中所有的子串TADTstring{}string數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:數(shù)據(jù)操作:串的抽象數(shù)據(jù)類(lèi)型定義4.1串類(lèi)型的定義5例：s=‘I□AM□A□STUDENT’,t=‘GOOD’,q=‘WORKER’求：StrLength(s)=StrLength(t)=SubString(s,8,7)=SubString(t,2,1)=Index(s,’A’)=Index(s,t)=Replace(s,’STUDENT’,q)=Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))=4.1串類(lèi)型的定義6定長(zhǎng)順序存儲(chǔ)表示堆分配存儲(chǔ)表示串的塊鏈存儲(chǔ)表示順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)4.2串的表示和實(shí)現(xiàn)7用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列。一、定長(zhǎng)順序存儲(chǔ)表示#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];按照予定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)，可用定長(zhǎng)數(shù)組描述。注意：①用SString[0]來(lái)存放串長(zhǎng)信息；

②串值后面加一個(gè)不計(jì)入串長(zhǎng)度的標(biāo)識(shí)符‘\0’；

③串的實(shí)際長(zhǎng)度可在予定義長(zhǎng)度的范圍內(nèi)隨意,超過(guò)予定義長(zhǎng)度的串值則被舍去，稱(chēng)為“截?cái)唷薄?.2串的表示和實(shí)現(xiàn)8例：用順序存儲(chǔ)方式實(shí)現(xiàn)求子串函數(shù)SubString(&Sub,s,pos,len)將串S中從第pos個(gè)字符開(kāi)始長(zhǎng)度為len的字符序列復(fù)制到Sub中（注：串Sub的預(yù)留長(zhǎng)度與S一樣）StatusSubString(SString&Sub,SStrings,intpos,intlen)S=‘a(chǎn)1a2……an-1an’poslenS[pos…pos+len-1]=Sub[1…len]Sub[0]=len;{}RetrunOK:If(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)Returnerror;想存放超長(zhǎng)字符串怎么辦？改用動(dòng)態(tài)分配的一維數(shù)組4.2串的表示和實(shí)現(xiàn)9仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得二、堆分配存儲(chǔ)表示malloc()合理預(yù)設(shè)串長(zhǎng)空間；若串長(zhǎng)改變，使用realloc()按新串長(zhǎng)度增加空間Typedefstruct{char*ch;intlength;}HString;//若非空串，按串長(zhǎng)分配空間；否則ch=NULL//串長(zhǎng)度4.2串的表示和實(shí)現(xiàn)10例：用堆分配存儲(chǔ)方式實(shí)現(xiàn)串插入操作(參見(jiàn)教材P75)

StatusStrInsert(HString&S,intpos,HStringT){//在串S的第pos個(gè)字符之前（包括尾部）插入串T}//StrInsertif(pos<1||pos>S.length+1)ReturnERROR;//pos不合法則警告if(T.length){//只要串T不空，就需要重新分配S空間，以便插入T

}returnOK;if(!(S.ch=(char)*realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);//若開(kāi)不了新空間，則退出for(i=S.length-1;i>=pos-1;--i)//為插入T而騰出pos之后的位置，即從S的pos位置起全部字符均后移

S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入TS.length+=T.length;//刷新S串長(zhǎng)度4.2串的表示和實(shí)現(xiàn)11三、串的塊鏈存儲(chǔ)表示headABI^C…例：S=‘ABCDEFGHI’①

鏈表結(jié)點(diǎn)大小為1②

鏈表結(jié)點(diǎn)大小為4^headABCDEFGHI###法1存儲(chǔ)密度為1/2；法2存儲(chǔ)密度為9/15=3/5存儲(chǔ)密度=串值所占的存儲(chǔ)位實(shí)際分配的存儲(chǔ)位4.2串的表示和實(shí)現(xiàn)12模式匹配：即子串定位運(yùn)算（Index函數(shù)）算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）

——即如何實(shí)現(xiàn)Index(S,T,pos)函數(shù)初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(s)操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0注：串S稱(chēng)為被匹配的串，T稱(chēng)為模式串。若S包含T，則稱(chēng)

“匹配成功”，否則稱(chēng)“匹配不成功”。4.3串的模式匹配算法13①基本設(shè)計(jì)思想：

將主串的第pos個(gè)字符和模式的第1個(gè)字符比較，(pos=1)

若相等，繼續(xù)比較后續(xù)字符;

若不等，從主串的下一字符（pos+1）起，重新與第1個(gè)字符比較直到主串的一個(gè)連續(xù)子串字符序列與模式相等。返回值為S中與T匹配的子序列第1個(gè)字符的序號(hào)，即匹配成功，否則匹配失敗，返回值04.3串的模式匹配算法14主串S=‘a(chǎn)babcabcacbab’，模式串T=‘a(chǎn)bcac’第1趟匹配：ababcabcacbab

abc

第2趟匹配：ababcabcacbab

a

第3趟匹配：ababcabcacbab

abcac第4趟匹配：ababcabcacbab

a第5趟匹配：ababcabcacbab

a第6趟匹配：ababcabcacbab

abcac能否利用已部分匹配過(guò)的信息而加快模式串的滑動(dòng)速度？KMP算法4.3串的模式匹配算法15當(dāng)主串S中第i個(gè)字符與模式串P中第j個(gè)字符“失配”時(shí)(Si≠Pj)，主串中第i個(gè)字母應(yīng)與模式中哪個(gè)字符再比較呢？假設(shè)此時(shí)與模式串中第k個(gè)字符繼續(xù)比較，則模式串P中前k-1個(gè)字符的子串必滿(mǎn)足下列的關(guān)系（1<K<j）

‘P1P2…Pk-1’=‘Si-k+1Si-k+2…Si-1’而得到的部分匹配的結(jié)果是（Si和Pj失配時(shí)的結(jié)果）

‘P1P2…Pj-1’=‘Si-j+1Si-j+2…Si-1’兩式聯(lián)立可得：‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’結(jié)論：K的選擇與主串無(wú)關(guān)，只與模式串的結(jié)構(gòu)有關(guān)。同理可得：‘Pj-k+1Pj-k+2…Pj-1’=‘Si-k+1Si-k+2…Si-1’已知：主串S1S2…Si…Sm

子串P1P2…Pk…Pj…Pn4.3串的模式匹配算法16

j12345tabcacnext[j]根據(jù)‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’，求next[j]第1趟匹配：ababcabcacbab

abc第2趟匹配：ababcabcacbab

abcac第3趟匹配：ababcabcacbab

abcac改進(jìn)的主串S=‘a(chǎn)babcabcacbab’和子串T=‘a(chǎn)bcac’的匹配過(guò)程01112令next[j]=k=0j=1Max{k|1<k<j且‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’

}1其它4.3串的模式匹配算法17令next[j]=k，根據(jù)‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’，求j12345678910111213141516模式串a(chǎn)bcdabcdabcdaabcnext[j]01111234567891023Nextval[j]

011101110111010114.3串的模式匹配算法18Nextval[j]0000006第1趟匹配：aaaaabaaaaaaab

aaaaaa第2趟匹配：aaaaabaaaaaaab

aaaa

a第3趟匹配：aaaaabaaaaaaab

aaa

a

j1234567模式串

aaaaaabnext[j]0123456第4趟匹配：aaaaabaaaaaaab

aa

a

第5趟匹配：aaaaabaaaaaaab

a

a

第6趟匹配：aaaaabaaaaaaab

a

第7趟匹配：aaaaabaaaaaaab

aaaaaa

b

第1趟匹配：aaaaabaaaaaaab

aaaaaa第2趟匹配：aaaaabaaaaaaab

aaaaaab第3趟匹配：aaaaabaaaaaaab

aaaaaab4.3串的模式匹配算法19設(shè)主串S=‘S1S2……Sm’

子串P=‘P1P2……Pn’當(dāng)Si和Pj不相等（失配）時(shí)，求出next[j]=K，表示下一次比較時(shí)讓Si和Pk相比較。如果Pk和Pj相等，Si和Pk肯定不相等，所以，必然需要再繼續(xù)比較下去，即next[j]的值需要修正。如果Pk和Pj不相等，則Si和Pk有可能相等，有比較的必要，即next[j]的值不需要修正。再下一次比較的時(shí)候，是判斷Pk所對(duì)應(yīng)的next[j]所代表的字符是否與Pk相等，即Pk是否等于Pnext[k]，如果相等則繼續(xù)比較，否則即可得到next[j]的修正值。4.3串的模式匹配算法201、試問(wèn)執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果？voiddemonstrate(){StrAssign(s,‘THISISABOOK’);Replace(s,SubString(s,3,7),‘ESEARE’);StrAssign(t,Conca