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

1

4.1串類型的定義

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

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

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

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

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

a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEI□JING’問：①4個字符串的的長度分別是多少？

②

b是哪個串的子串？其在主串的位置是多少？

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

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

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

StatusStrInsert(HString&S,intpos,HStringT){//在串S的第pos個字符之前（包括尾部）插入串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);//若開不了新空間，則退出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串長度4.2串的表示和實(shí)現(xiàn)11三、串的塊鏈存儲表示headABI^C…例：S=‘ABCDEFGHI’①

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

鏈表結(jié)點(diǎn)大小為4^headABCDEFGHI###法1存儲密度為1/2；法2存儲密度為9/15=3/5存儲密度=串值所占的存儲位實(shí)際分配的存儲位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個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0注：串S稱為被匹配的串，T稱為模式串。若S包含T，則稱

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

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

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

若不等，從主串的下一字符（pos+1）起，重新與第1個字符比較直到主串的一個連續(xù)子串字符序列與模式相等。返回值為S中與T匹配的子序列第1個字符的序號，即匹配成功，否則匹配失敗，返回值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能否利用已部分匹配過的信息而加快模式串的滑動速度？KMP算法4.3串的模式匹配算法15當(dāng)主串S中第i個字符與模式串P中第j個字符“失配”時(Si≠Pj)，主串中第i個字母應(yīng)與模式中哪個字符再比較呢？假設(shè)此時與模式串中第k個字符繼續(xù)比較，則模式串P中前k-1個字符的子串必滿足下列的關(guān)系（1<K<j）

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