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

第四章串⒈教學(xué)內(nèi)容：4.1串及其基本運(yùn)算4.2串的定長順序存儲(chǔ)及基本運(yùn)算4.3串的堆存儲(chǔ)結(jié)構(gòu)⒉教學(xué)目的：⑴了解串的定義；⑵理解和領(lǐng)會(huì)串的存儲(chǔ)方式；⑶掌握常用的串運(yùn)算。⒊教學(xué)重點(diǎn)：⑴串的基本概念、基本運(yùn)算；⑵串的兩種存儲(chǔ)方式。⑶串的模式匹配算法。⒋教學(xué)難點(diǎn)：⑴串的模式匹配算法；⑵串的基本運(yùn)算的綜合應(yīng)用⒌學(xué)時(shí)安排：4學(xué)時(shí)2/5/20231數(shù)據(jù)結(jié)構(gòu)講義4.1串及其基本運(yùn)算串的基本概念串的基本運(yùn)算2/5/20232數(shù)據(jù)結(jié)構(gòu)講義4.1.1串的基本概念串是由零個(gè)或多個(gè)任意字符組成的字符序列。一般記作：s=”s1s2…sn”。

其中s是串名；在本書中，用雙引號(hào)作為串的定界符，引號(hào)引起來的字符序列為串值，引號(hào)本身不屬于串的內(nèi)容；

ai(1<=i<=n)是一個(gè)任意字符，它稱為串的元素，是構(gòu)成串的基本單位，i是它在整個(gè)串中的序號(hào);

n為串的長度，表示串中所包含的字符個(gè)數(shù)，當(dāng)n=0時(shí)，稱為空串，通常記為Ф。2/5/20233數(shù)據(jù)結(jié)構(gòu)講義子串與主串：串中任意連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串。子串的位置：

子串的第一個(gè)字符在主串中的序號(hào)稱為子串的位置。串相等：稱兩個(gè)串是相等的，是指兩個(gè)串的長度相等且對(duì)應(yīng)字符都相等。2/5/20234數(shù)據(jù)結(jié)構(gòu)講義4.1.2串的基本運(yùn)算⒈求串長StrLength(s)

操作結(jié)果是求出串s的長度。⒉串賦值StrAssign(s1,s2)

s1是一個(gè)串變量，s2或者是一個(gè)串常量，或者是一個(gè)串變量（通常s2是一個(gè)串常量時(shí)稱為串賦值，是一個(gè)串變量稱為串拷貝），操作結(jié)果是將s2的串值賦值給s1，s1原來的值被覆蓋掉。⒊連接操作StrConcat(s1,s2,s)

或StrConcat(s1,s2)

兩個(gè)串的連接就是將一個(gè)串的串值緊接著放在另一個(gè)串的后面，連接成一個(gè)串。前者是產(chǎn)生新串s，s1和s2不改變;后者是在s1的后面聯(lián)接s2的串值，s1改變，s2不改變。⒋求子串SubStr(s,i,len)

串s存在并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果是求得從串s的第i個(gè)字符開始的長度為len的子串。len=0得到的是空串。⒌串比較StrCmp(s1,s2)

操作結(jié)果是若s1==s2，操作返回值為0；若s1<s2，返回值<0；若s1>s2，返回值>0。2/5/20235數(shù)據(jù)結(jié)構(gòu)講義⒍子串定位StrIndex(s,t)

s為主串，t為子串，操作結(jié)果是若t∈s，則操作返回t在s中首次出現(xiàn)的位置，否則返回值為0。⒎串插入StrInsert(s,i,t)

串s,t存在，且1≤i≤StrLength(s)+1。操作結(jié)果是將串t插入到串s的第i個(gè)字符位置上，s的串值發(fā)生改變。⒏串刪除StrDelete(s,i,len)

串s存在，并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果是刪除串s中從第i個(gè)字符開始的長度為len的子串，s的串值改變。⒐串替換StrRep(s,t,r)

串s,t,r存在且t不為空，操作結(jié)果是用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串，s的串值改變。串的基本操作中前５個(gè)操作是最為基本的，它們不能用其他的操作來合成，因此通常將這５個(gè)基本操作稱為最小操作集。2/5/20236數(shù)據(jù)結(jié)構(gòu)講義4.2串的定長順序存儲(chǔ)及基本運(yùn)算串的定長順序存儲(chǔ)定長順序串的基本運(yùn)算模式匹配2/5/20237數(shù)據(jù)結(jié)構(gòu)講義4.2.1串的定長順序存儲(chǔ)用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值中的字符序列，所謂定長是指按預(yù)定義的大小，為每一個(gè)串變量分配一個(gè)固定長度的存儲(chǔ)區(qū)，如：#defineMAXSIZE256chars[MAXSIZE];則串的最大長度不能超過256。2/5/20238數(shù)據(jù)結(jié)構(gòu)講義如何標(biāo)識(shí)實(shí)際長度？1.類似順序表，用一個(gè)指針來指向最后一個(gè)字符，這樣表示的串描述如下：typedefstruct

{chardata[MAXSIZE];

intcurlen;}SeqString;定義一個(gè)串變量：SeqStrings;

這種存儲(chǔ)方式可以直接得到串的長度：s.curlen+1。如圖所示。2/5/20239數(shù)據(jù)結(jié)構(gòu)講義2.在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符，以此表示串的結(jié)尾。比如C語言中處理定長串的方法就是這樣的，它是用’\0’來表示串的結(jié)束。這種存儲(chǔ)方法不能直接得到串的長度，是用判斷當(dāng)前字符是否是’\0’來確定串是否結(jié)束，從而求得串的長度。2/5/202310數(shù)據(jù)結(jié)構(gòu)講義3.設(shè)定長串存儲(chǔ)空間：chars[MAXSIZE+1];用s[0]存放串的實(shí)際長度，串值存放在s[1]~s[MAXSIZE]，字符的序號(hào)和存儲(chǔ)位置一致，應(yīng)用更為方便。2/5/202311數(shù)據(jù)結(jié)構(gòu)講義4.2.2定長順序串的基本運(yùn)算主要討論定長串聯(lián)接、求子串、串比較算法，順序串的插入和刪除等運(yùn)算基本與順序表相同，在此不在贅述。設(shè)串結(jié)束用＇\0＇來標(biāo)識(shí)。2/5/202312數(shù)據(jù)結(jié)構(gòu)講義⒈串連接串連接是把兩個(gè)串s1和s2首尾連接成一個(gè)新串s。

intStrConcat1(s1,s2,s)chars1[],s2[],s[];{inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;/*s長度不夠*/

j=0;while(s1[j]!=’\0’)

{s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}s[i]=’\0’;return1;}2/5/202313數(shù)據(jù)結(jié)構(gòu)講義⒉求子串intStrSub(char*t,char*s,inti,intlen)/*用t返回串s中第個(gè)i字符開始的長度為len的子串1≤i≤串長*/{intslen;slen=StrLength(s);if(i<1||i>slen||len<0||len>slen-i+1){printf(＂參數(shù)不對(duì)＂);return0;}for(j=0;j<len;j++)t[j]=s[i+j-1];t[j]=’\0’;return1;}2/5/202314數(shù)據(jù)結(jié)構(gòu)講義⒊串比較

intStrComp(char*s1,char*s2){inti=0;

while(s1[i]==s2[i]&&s1[i]!=’\0’)

i++;return(s1[i]-s2[i]);}2/5/202315數(shù)據(jù)結(jié)構(gòu)講義4.2.3模式匹配串的模式匹配即子串定位是一種重要的串運(yùn)算。設(shè)s和t是給定的兩個(gè)串，在主串s中查找子串t的過程稱為模式匹配，如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲(chǔ)位置(或序號(hào))，否則匹配失敗，返回0。t也稱為模式。為了運(yùn)算方便，設(shè)字符串采用定長存儲(chǔ)，且用第三種方式表示串長，即串的長度存放在0號(hào)單元，串值從1號(hào)單元存放，這樣字符序號(hào)與存儲(chǔ)位置一致。2/5/202316數(shù)據(jù)結(jié)構(gòu)講義算法思想如下：首先將s1與t1進(jìn)行比較，若不同，就將s2與t1進(jìn)行比較，...，直到s的某一個(gè)字符si和t1相同，再將它們之后的字符進(jìn)行比較，若也相同，則如此繼續(xù)往下比較，當(dāng)s的某一個(gè)字符si與t的字符tj不同時(shí)，則s返回到本趟開始字符的下一個(gè)字符，即si-j+2，t返回到t1，繼續(xù)開始下一趟的比較，重復(fù)上述過程。若t中的字符全部比完，則說明本趟匹配成功，本趟的起始位置是i-j+1或i-t[0]，否則，匹配失敗。設(shè)主串s=＂acabaabaabcacaabc＂，模式t=＂abaabcac＂，匹配過程如圖所示。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義依據(jù)這個(gè)思想，算法描述如下:intStrIndex_BF(char*s,char*t)

/*從串s的第一個(gè)字符開始找首次與串t相等的子串*/{inti=1,j=1;

while(i<=s[0]&&j<=t[0])/*都沒遇到結(jié)束符*/

if(s[i]==t[j])

{i++;j++;}/*繼續(xù)*/

else{i=i-j+2;j=1;}/*回溯*/

if(j>t[0])

return(i-t[0]);/*匹配成功，返回存儲(chǔ)位置*/

elsereturn0;}2/5/202318數(shù)據(jù)結(jié)構(gòu)講義下面分析它的時(shí)間復(fù)雜度，設(shè)串s長度為n，串t長度為m。匹配成功的情況下，考慮兩種極端情況：在最好情況下，每趟不成功的匹配都發(fā)生在第一對(duì)字符比較時(shí)：例如：s=”aaaaaaaaaabc”，t=”bc”

設(shè)匹配成功發(fā)生在si處，則字符比較次數(shù)在前面i-1趟匹配中共比較了i-1次，第i趟成功的匹配共比較了m次，所以總共比較了i-1+m次，所有匹配成功的可能共有n-m+1種，設(shè)從si開始與t串匹配成功的概率為pi，等概率情況下pi=1/(n-m+1)，因此最好情況下平均比較的次數(shù)是：

即最好情況下的時(shí)間復(fù)雜度是O(n+m)。2/5/202319數(shù)據(jù)結(jié)構(gòu)講義在最壞情況下，每趟不成功的匹配都發(fā)生在t的最后一個(gè)字符：例如：s=”aaaaaaaaaaab”，t=”aaab”

設(shè)匹配成功發(fā)生在si處，則在前面i-1趟匹配中共比較了(i-1)*m次，第i趟成功的匹配共比較了m次，所以總共比較了i*m次，因此最壞情況下平均比較的次數(shù)是：

即最壞情況下的時(shí)間復(fù)雜度是O(n*m)。2/5/202320數(shù)據(jù)結(jié)構(gòu)講義上述算法中匹配是從s串的第一個(gè)字符開始的，有時(shí)算法要求從指定位置開始，這時(shí)算法的參數(shù)表中要加一個(gè)位置參數(shù)pos：StrIndex(shar*s,intpos,char*t)，比較的初始位置定位在pos處。算法4.4是pos=1的情況。2/5/202321數(shù)據(jù)結(jié)構(gòu)講義4.3串的堆存儲(chǔ)結(jié)構(gòu)

串名的存儲(chǔ)映象堆存儲(chǔ)結(jié)構(gòu)基于堆結(jié)構(gòu)的基本運(yùn)算2/5/202322數(shù)據(jù)結(jié)構(gòu)講義4.3.1串名的存儲(chǔ)映象串名的存儲(chǔ)映象是串名－串值內(nèi)存分配對(duì)照表，也稱為索引表。表的形式有多種表示，常見的串名－串值存儲(chǔ)映象索引表有如下幾種：帶串長度的索引表末尾指針的索引表帶特征位的索引表2/5/202323數(shù)據(jù)結(jié)構(gòu)講義1.帶串長度的索引表如圖所示，索引項(xiàng)的結(jié)點(diǎn)類型為：typedefstruct

{charname[MAXNAME];/*串名*/

intlength;/*串長*/

char*stradr;/*起始地址*/}LNode;2/5/202324數(shù)據(jù)結(jié)構(gòu)講義2.末尾指針的索引表如圖所示，索引項(xiàng)的結(jié)點(diǎn)類型為：

typedefstruct

{charname[MAXNAME];/*串名*/

char*stradr,*enadr;/*起始地址，末尾地址*/}ENode;2/5/202325數(shù)據(jù)結(jié)構(gòu)講義

3.

帶特征位的索引表當(dāng)一個(gè)串的存儲(chǔ)空間不超過一個(gè)指針的存儲(chǔ)空間時(shí)，可以直接將該串存在索引項(xiàng)的指針域，這樣既節(jié)約了存儲(chǔ)空間，又提高查找速度，但這時(shí)要加一個(gè)特征位tag以指出指針域存放的是指針還是串。如圖所示，索引項(xiàng)的結(jié)點(diǎn)類型為：typedefstruct

{charname[MAXNAME];

inttag;/*特征位*/

union/*起始地址或串值*/{char*stradr;charvalue[4];}uval;}TNode;2/5/202326數(shù)據(jù)結(jié)構(gòu)講義4.3.2堆存儲(chǔ)結(jié)構(gòu)在應(yīng)用程序中，參與運(yùn)算的串變量之間的長度相差較大，并且操作中串值的長度變化也較大，因此為串變量預(yù)分配固定大小的空間不盡合理。堆存儲(chǔ)結(jié)構(gòu)的基本思想是：在內(nèi)存中開辟能存儲(chǔ)足夠多的串、地址連續(xù)的存儲(chǔ)空間作為應(yīng)用程序中所有串的可利用存儲(chǔ)空間，稱為堆空間，如設(shè)store[SMAX+1];根據(jù)每個(gè)串的長度，動(dòng)態(tài)的為每個(gè)串在堆空間里申請相應(yīng)大小的存儲(chǔ)區(qū)域，這個(gè)串順序存儲(chǔ)在所申請的存儲(chǔ)區(qū)域中，當(dāng)操作過程中若原空間不夠了，可以根據(jù)串的實(shí)際長度重新申請，拷貝原串值后再釋放原空間。2/5/202327數(shù)據(jù)結(jié)構(gòu)講義如圖所示，是一個(gè)堆結(jié)構(gòu)示意圖。陰影部分是已經(jīng)為存在的串分配過的，free為未分配部分的起始地址，每當(dāng)向store中存放一個(gè)串時(shí)，要填上該串的索引項(xiàng)。2/5/202328數(shù)據(jù)結(jié)構(gòu)講義4.3.3基于堆結(jié)構(gòu)的基本運(yùn)算堆結(jié)構(gòu)上的串運(yùn)算仍然基于字符序列的復(fù)制進(jìn)行，基本思想是：當(dāng)需要產(chǎn)生一個(gè)新串時(shí)，要判斷堆空間中是否還有存儲(chǔ)空間，若有，則從free指針開始劃出相應(yīng)大小的區(qū)域?yàn)樵摯拇鎯?chǔ)區(qū)，然后根據(jù)運(yùn)算求出串值，最后建立該串存儲(chǔ)映象索引信息，并修改free指針。設(shè)堆空間為：charstore[SMAX+1];自由區(qū)指針：intfree;

串的存儲(chǔ)映象類型如下：typedefstruct

{intlength;/*串長*/

intstradr;/*起始地址*/

}HString;2/5/202329數(shù)據(jù)結(jié)構(gòu)講義1.

串常量賦值voidStrAssign(HString*s1,char*s2)/*將一個(gè)字符型數(shù)組s2中的字符串送入堆store中,free是自由區(qū)的指針*/{inti=0,len;len=StrLength(s2);if(len<0||free+len-1＞SMAX)return0;else{for(i=0;i<len;i++)store[free+i]=s2[i];s1.stradr=free;s1.length=len;free=free+len;

}}2/5/202330數(shù)據(jù)結(jié)構(gòu)講義2.

賦值一個(gè)串voidStrCopy(Hstring*s1,Hstrings2)

/*該運(yùn)算將堆store中的一個(gè)串s2復(fù)制到一個(gè)新串s1中*/{inti;

if(free+s2.length-1>SMAX)returnerror;else

{for(i=0;i<s2.lengt