數(shù)據(jù)結(jié)構(gòu)課件(部分6)

4.1串類型的定義一、串和基本概念串是零個(gè)或多個(gè)字符組成的有限序列。一般記作S=‘a(chǎn)1a2a3…an’，S是串名，單引號(hào)括起來(lái)的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。長(zhǎng)度為零的串稱為空串，它不包含任何字符。通常將僅由一個(gè)或多個(gè)空格組成的串稱為空白串。注意：空串和空白串的不同，例如“”和“”分別表示長(zhǎng)度為1的空白串和長(zhǎng)度為0的空串。

第四章串14.1串類型的定義第四章串1串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的序號(hào)（或位置）。例如:a,b,c,d四個(gè)字符串為a=‘BEI’,b=‘JING’c=‘BEIJING’,d=‘BEIJING’它們的長(zhǎng)度分別為3,4,7,8；a和b都是c和d的子串。a在c和d中的位置都是1，b在c中的位置是4,而b在d中的位置是5。注意:單引號(hào)是為字符串區(qū)別于變量名而設(shè),它不是字符串的內(nèi)容稱兩個(gè)串是相等的當(dāng)且僅當(dāng)這兩個(gè)串每個(gè)字符對(duì)應(yīng)相等2串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相2二、串的抽象數(shù)據(jù)定義

串的抽象數(shù)據(jù)類型定義見書P71ADTString{數(shù)據(jù)對(duì)象：D={ai|ai∈CharacteSet,i=1,2,...n,n>=0}數(shù)據(jù)關(guān)系：R1={＜ai-1.,ai＞|ai∈D,i=2,...n}。基本操作：StrAssign(&T,chars);StrCopy(&T,S);StrEmpty(S);StrCompare(S,T);StrLength(S);ClearString(&S);Concat(&T,S1,S2);Substring(&Sub,S,pos,len);Index(S,T,pos);Replace(&S,T,V);StrInsert(&S,pos,T);StrDelete(&S,pos,len);DestroyString(&S)}ADTString3二、串的抽象數(shù)據(jù)定義33基本操作的功能說明StrAssign(&T,chars)初始條件:chars是字符串常量。操作結(jié)果:生成一個(gè)其值等于chars的串T。StrCopy(&T,S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:由串S復(fù)制得串T。StrEmpty(S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:若S為空串，則返回TRUE,否則返回FALSE。StrCompare(S,T)初始條件:字符串S和T存在。操作結(jié)果:若S>T,則返回值>0;若S=T,則返回值=0;否則返回值<0。4基本操作的功能說明StrAssign(&T,chars)44StrLength(S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:返回串S元素個(gè)數(shù)，稱為串的長(zhǎng)度。ClearString(&S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:將串S清為空串。Concat(&T,S1,S2)初始條件:字符串S1,S2已經(jīng)存在。操作結(jié)果:用T返回由串S1和S2聯(lián)結(jié)而成的新串。Substring(&Sub,S,pos,len)初始條件:串S存在,1<=pos<=S的長(zhǎng)度,0<=len<=S的長(zhǎng)度-pos+1。操作結(jié)果:用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。5StrLength(S)55Index(S,T,pos)初始條件:串S和T存在,T是非空串，1<=pos<=S的長(zhǎng)度。操作結(jié)果:若主串S中存在和串T相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則返回０。Replace(&S,T,V)初始條件:字符串S,T,V已經(jīng)存在，T是非空串。操作結(jié)果:用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。StrInsert(&S,pos,T)初始條件:字符串S,T存在，1<=pos<=S的長(zhǎng)度+1。操作結(jié)果:在串S的第pos個(gè)字符之前插入串T。StrDelete(&S,pos,len)初始條件:串S存在，1<=pos<=S的長(zhǎng)度-len+1。操作結(jié)果:從串S中刪除第pos個(gè)字符起長(zhǎng)度為len的子串。DestroyString(&S):把存在的串S銷毀。6Index(S,T,pos)66上述13種基本操作中,下面5種操作構(gòu)成最小操作子集:串賦值StrAssign;串比較StrCompare;求串長(zhǎng)StrLength;串聯(lián)結(jié)Concat;求子串Substring;其它操作可以用其實(shí)現(xiàn)例如定位函數(shù)Index(S,T,pos)的算法如右:intIndex(StringS,StringT,intpos){inti,n,m;Stringsub;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;}//while}//ifreturn0;}//Index7上述13種基本操作中,下面5種操作構(gòu)成最小操作子集:int74.2串的表示和實(shí)現(xiàn)4.2.1定長(zhǎng)順序存儲(chǔ)表示用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列.在C語(yǔ)言中,用字符“\0”表示串的終結(jié),“\0”不計(jì)入串長(zhǎng).另一種方法是定長(zhǎng)數(shù)組表示一個(gè)串:#defineMAXSTRLEN255//串的長(zhǎng)度最大為255typedefunsignedcharSString[MAXSTRLEN+1];//0號(hào)單元存放串的長(zhǎng)度,其最大值剛好是255.當(dāng)超出255個(gè)字符時(shí),串的多余內(nèi)容被舍去,叫做“截?cái)唷币韵掠么?lián)結(jié)和求子串為例介紹這種存儲(chǔ)84.2串的表示和實(shí)現(xiàn)4.2.1定長(zhǎng)順序存儲(chǔ)表示#def8S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN時(shí)S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN時(shí)截?cái)嗖糠?S1S2T0maxst91.串聯(lián)結(jié)Concat(&T,S1,S2)的算法statusConcat(SString&T,SStringS1,SStringS2){//用T返回由串S1和S2聯(lián)結(jié)而成的新串。若未被截?cái)?則返回1;否則返回0。if(S1[0]+S2[0]<=MAXSTRLEN){//未被截?cái)郥[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=1;}elseif(S1[0]<MAXSTRLEN){//截?cái)郥[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=0;}else{//截?cái)?僅取S1)T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=0;}//ifreturnuncut;}//Concat101.串聯(lián)結(jié)Concat(&T,S1,S2)的算法statu102.求子串SubString(&Sub,S,pos,len)的算法statusSubString(SString&Sub,SStringS,intpos,intlen){//用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。其中,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1。if(pos<1||pos>s[0]||len<0||len>s[0]-pos+1) returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}//SubStringSSub1poslen112.求子串SubString(&Sub,S,pos,len)114.2.2堆分配存儲(chǔ)表示

也是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列.但存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的.在C語(yǔ)言中,用字符“\0”表示串的終結(jié),“\0”不計(jì)入串長(zhǎng).typedefstruct{char*ch;//若是非空串,則按實(shí)際長(zhǎng)度分配,否則為NULL;intlength;//串長(zhǎng)度}HString;以下用串插入操作StrInsert(&S,pos,T)為例介紹這種存儲(chǔ)124.2.2堆分配存儲(chǔ)表示typedefstruct{以12串插入StrInsert(&S,pos,T)的算法statusStrInsert(HString&S,intpos,HStringT){//1<=pos<=StrLength(S)+1。在串S的第pos個(gè)字符之前插入串T。

if(pos<1||pos>S.length+1)returnERROR;//pos不合法if(T.length){//T非空,則要重新分配S空間,插入Tif(!(S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char))))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)//為插入T而騰出位置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;}//ifreturnOK;}//StrInsert13串插入StrInsert(&S,pos,T)的算法statu13Hstring串類基本操作的算法描述StatusStrAssign(HString&T,char*chars){//生成一個(gè)其值等于串常量chars的串Tif(T.ch)free(T.ch);//釋放T原有空間i=strlen(chars);//求chars的長(zhǎng)度iif(!i){T.ch=NULL;T.length=0;}else{//chars的長(zhǎng)度不為0T.ch=(char*)malloc(i*sizeof(char));//分配串空間if(!T.ch)//分配串空間失敗exit(OVERFLOW);T.ch[0..i-1]=chars[0..i-1];T.length=i;}returnOK;}14Hstring串類基本操作的算法描述1414intStrLength(HStringS){//返回S的元素個(gè)數(shù),稱為串的長(zhǎng)度returnS.length;}intStrCompare(HStringS,HStringT){//若S>T,則返回值>0;若S=T,則返回值=0;若S<T,則返回值<0inti;for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}15intStrLength(HStringS)int15StatusClearString(HString&S){//將S清為空串if(S.ch){free(S.ch);S.ch=NULL;}S.length=0;returnOK;}16StatusClearString(HString&S16StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2聯(lián)接而成的新串if(T.ch)free(T.ch);//釋放舊空間T.length=S1.length+S2.length;T.ch=(char*)malloc(T.length*sizeof(char));if(!T.ch)exit(OVERFLOW);for(i=0;i<S1.length;i++)T.ch[i]=S1.ch[i];for(i=0;i<S2.length;i++)T.ch[S1.length+i]=S2.ch[i];returnOK;}17StatusConcat(HString&T,HStr17StatusSubString(HString&Sub,HStringS,intpos,intlen){//用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。//其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);//釋放舊空間if(!len){Sub.ch=NULL;Sub.length=0;}//空子串else{//完整子串Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2];Sub.length=len;}returnOK;}18StatusSubString(HString&Sub184.2.3串的塊鏈存儲(chǔ)結(jié)構(gòu)為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小(比如說劃分成大小為4的結(jié)點(diǎn))，每一個(gè)結(jié)點(diǎn)有兩個(gè)域：data域放4個(gè)字符，next域放下一個(gè)結(jié)點(diǎn)的指針。例如,s='abcdefghk'顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來(lái)填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。194.2.3串的塊鏈存儲(chǔ)結(jié)構(gòu)為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存19#definechunksize80typedefstructchunk{charch[chunksize];structchunk*next;}chunktypedefstruct{//串的鏈表結(jié)構(gòu)Chunk*head,*tail;//串的頭和尾指針intcurlen;//串的當(dāng)前長(zhǎng)度}LString;20#definechunksize80typedef204.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)Index(S,T,pos)采用定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu),不依賴其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也稱為模式，1<=pos<=S的長(zhǎng)度。//若主串S中存在和模式T相同的子串，則返回它在主串//S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則返回０。i=pos;j=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后續(xù)字符

else{i=i-j+2;j=1;}//指針后退重新開始匹配}

if(j>T[0])returni-T[0];//匹配成功

elsereturn0;//匹配不成功}214.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)In21簡(jiǎn)單匹配算法（BF算法）的匹配過程示例例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ijijij第1趟abcac

22簡(jiǎn)單匹配算法（BF算法）的匹配過程示例例：主串S="abab22例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失?。籭回溯到2，j回溯到1ji第1趟abcac

簡(jiǎn)單匹配算法（BF算法）的匹配過程示例23例：主串S="ababcabcacbab"，模式T="abc23例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第2趟ijabcac

簡(jiǎn)單匹配算法（BF算法）的匹配過程示例24例：主串S="ababcabcacbab"，模式T="abc24例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第2趟ijabcac

簡(jiǎn)單匹配算法（BF算法）的匹配過程示例25例：主串S="ababcabcacbab"，模式T="abc25例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第3趟ijijijijij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例26例：主串S="ababcabcacbab"，模式T="abc26例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第3趟ij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例27例：主串S="ababcabcacbab"，模式T="abc27例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=4，j=1失敗i回溯到5，j回溯到1第4趟ij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例28例：主串S="ababcabcacbab"，模式T="abc28例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=4，j=1失敗i回溯到5，j回溯到1第4趟ij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例29例：主串S="ababcabcacbab"，模式T="abc29例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=5，j=1失敗i回溯到6，j回溯到1第5趟ij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例30例：主串S="ababcabcacbab"，模式T="abc30例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=5，j=1失敗i回溯到6，j回溯到1第5趟ij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例31例：主串S="ababcabcacbab"，模式T="abc31例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=11，j=6，T中全部字符都比較完畢，匹配成功。第6趟ijijijijij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例32例：主串S="ababcabcacbab"，模式T="abc32intIndex(SStringS,SStringT,intpos){//T是非空串,也稱為模式，1<=pos<=S的長(zhǎng)度。//若主串S中存在和模式T相同的子串，則返回它在主串//S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則返回０。i=pos;j=1;start=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;//匹配不成功}start++;i=start;j=1;33intIndex(SStringS,SStringT33BF算法的復(fù)雜度分析設(shè)n=StrLength(S);m=StrLength(T);設(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ù)是：最好情況的復(fù)雜度為O(n+m),如T=“STING”S=“ASTRINGSEARCHINGEXAMPLECONSISTINGOFSIMPLETEXT”34BF算法的復(fù)雜度分析設(shè)n=StrLength(S);m34最壞情況,T=“00000001”S=“00000000000000000000000000000000000000000000000001”設(shè)匹配成功發(fā)生在si處，則在前面i-1趟匹配中共比較了(i-1)*m次，第i趟成功的匹配共比較了m次，所以總共比較了i*m次，因此最壞情況下平均比較的次數(shù)是：即最壞情況下的時(shí)間復(fù)雜度是O(n*m)。而01串是計(jì)算機(jī)應(yīng)用中最普遍的一種，所以有必要改進(jìn)該模式匹配算法。35最壞情況,3535

4.1串類型的定義一、串和基本概念串是零個(gè)或多個(gè)字符組成的有限序列。一般記作S=‘a(chǎn)1a2a3…an’，S是串名，單引號(hào)括起來(lái)的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。長(zhǎng)度為零的串稱為空串，它不包含任何字符。通常將僅由一個(gè)或多個(gè)空格組成的串稱為空白串。注意：空串和空白串的不同，例如“”和“”分別表示長(zhǎng)度為1的空白串和長(zhǎng)度為0的空串。

第四章串364.1串類型的定義第四章串36串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的序號(hào)（或位置）。例如:a,b,c,d四個(gè)字符串為a=‘BEI’,b=‘JING’c=‘BEIJING’,d=‘BEIJING’它們的長(zhǎng)度分別為3,4,7,8；a和b都是c和d的子串。a在c和d中的位置都是1，b在c中的位置是4,而b在d中的位置是5。注意:單引號(hào)是為字符串區(qū)別于變量名而設(shè),它不是字符串的內(nèi)容稱兩個(gè)串是相等的當(dāng)且僅當(dāng)這兩個(gè)串每個(gè)字符對(duì)應(yīng)相等37串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相37二、串的抽象數(shù)據(jù)定義

串的抽象數(shù)據(jù)類型定義見書P71ADTString{數(shù)據(jù)對(duì)象：D={ai|ai∈CharacteSet,i=1,2,...n,n>=0}數(shù)據(jù)關(guān)系：R1={＜ai-1.,ai＞|ai∈D,i=2,...n}。基本操作：StrAssign(&T,chars);StrCopy(&T,S);StrEmpty(S);StrCompare(S,T);StrLength(S);ClearString(&S);Concat(&T,S1,S2);Substring(&Sub,S,pos,len);Index(S,T,pos);Replace(&S,T,V);StrInsert(&S,pos,T);StrDelete(&S,pos,len);DestroyString(&S)}ADTString38二、串的抽象數(shù)據(jù)定義338基本操作的功能說明StrAssign(&T,chars)初始條件:chars是字符串常量。操作結(jié)果:生成一個(gè)其值等于chars的串T。StrCopy(&T,S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:由串S復(fù)制得串T。StrEmpty(S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:若S為空串，則返回TRUE,否則返回FALSE。StrCompare(S,T)初始條件:字符串S和T存在。操作結(jié)果:若S>T,則返回值>0;若S=T,則返回值=0;否則返回值<0。39基本操作的功能說明StrAssign(&T,chars)439StrLength(S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:返回串S元素個(gè)數(shù)，稱為串的長(zhǎng)度。ClearString(&S)初始條件:字符串S已經(jīng)存在。操作結(jié)果:將串S清為空串。Concat(&T,S1,S2)初始條件:字符串S1,S2已經(jīng)存在。操作結(jié)果:用T返回由串S1和S2聯(lián)結(jié)而成的新串。Substring(&Sub,S,pos,len)初始條件:串S存在,1<=pos<=S的長(zhǎng)度,0<=len<=S的長(zhǎng)度-pos+1。操作結(jié)果:用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。40StrLength(S)540Index(S,T,pos)初始條件:串S和T存在,T是非空串，1<=pos<=S的長(zhǎng)度。操作結(jié)果:若主串S中存在和串T相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則返回０。Replace(&S,T,V)初始條件:字符串S,T,V已經(jīng)存在，T是非空串。操作結(jié)果:用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。StrInsert(&S,pos,T)初始條件:字符串S,T存在，1<=pos<=S的長(zhǎng)度+1。操作結(jié)果:在串S的第pos個(gè)字符之前插入串T。StrDelete(&S,pos,len)初始條件:串S存在，1<=pos<=S的長(zhǎng)度-len+1。操作結(jié)果:從串S中刪除第pos個(gè)字符起長(zhǎng)度為len的子串。DestroyString(&S):把存在的串S銷毀。41Index(S,T,pos)641上述13種基本操作中,下面5種操作構(gòu)成最小操作子集:串賦值StrAssign;串比較StrCompare;求串長(zhǎng)StrLength;串聯(lián)結(jié)Concat;求子串Substring;其它操作可以用其實(shí)現(xiàn)例如定位函數(shù)Index(S,T,pos)的算法如右:intIndex(StringS,StringT,intpos){inti,n,m;Stringsub;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;}//while}//ifreturn0;}//Index42上述13種基本操作中,下面5種操作構(gòu)成最小操作子集:int424.2串的表示和實(shí)現(xiàn)4.2.1定長(zhǎng)順序存儲(chǔ)表示用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列.在C語(yǔ)言中,用字符“\0”表示串的終結(jié),“\0”不計(jì)入串長(zhǎng).另一種方法是定長(zhǎng)數(shù)組表示一個(gè)串:#defineMAXSTRLEN255//串的長(zhǎng)度最大為255typedefunsignedcharSString[MAXSTRLEN+1];//0號(hào)單元存放串的長(zhǎng)度,其最大值剛好是255.當(dāng)超出255個(gè)字符時(shí),串的多余內(nèi)容被舍去,叫做“截?cái)唷币韵掠么?lián)結(jié)和求子串為例介紹這種存儲(chǔ)434.2串的表示和實(shí)現(xiàn)4.2.1定長(zhǎng)順序存儲(chǔ)表示#def43S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN時(shí)S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN時(shí)截?cái)嗖糠?4S1S2T0maxst441.串聯(lián)結(jié)Concat(&T,S1,S2)的算法statusConcat(SString&T,SStringS1,SStringS2){//用T返回由串S1和S2聯(lián)結(jié)而成的新串。若未被截?cái)?則返回1;否則返回0。if(S1[0]+S2[0]<=MAXSTRLEN){//未被截?cái)郥[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=1;}elseif(S1[0]<MAXSTRLEN){//截?cái)郥[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=0;}else{//截?cái)?僅取S1)T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=0;}//ifreturnuncut;}//Concat451.串聯(lián)結(jié)Concat(&T,S1,S2)的算法statu452.求子串SubString(&Sub,S,pos,len)的算法statusSubString(SString&Sub,SStringS,intpos,intlen){//用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。其中,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1。if(pos<1||pos>s[0]||len<0||len>s[0]-pos+1) returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}//SubStringSSub1poslen462.求子串SubString(&Sub,S,pos,len)464.2.2堆分配存儲(chǔ)表示

也是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列.但存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的.在C語(yǔ)言中,用字符“\0”表示串的終結(jié),“\0”不計(jì)入串長(zhǎng).typedefstruct{char*ch;//若是非空串,則按實(shí)際長(zhǎng)度分配,否則為NULL;intlength;//串長(zhǎng)度}HString;以下用串插入操作StrInsert(&S,pos,T)為例介紹這種存儲(chǔ)474.2.2堆分配存儲(chǔ)表示typedefstruct{以47串插入StrInsert(&S,pos,T)的算法statusStrInsert(HString&S,intpos,HStringT){//1<=pos<=StrLength(S)+1。在串S的第pos個(gè)字符之前插入串T。

if(pos<1||pos>S.length+1)returnERROR;//pos不合法if(T.length){//T非空,則要重新分配S空間,插入Tif(!(S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char))))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)//為插入T而騰出位置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;}//ifreturnOK;}//StrInsert48串插入StrInsert(&S,pos,T)的算法statu48Hstring串類基本操作的算法描述StatusStrAssign(HString&T,char*chars){//生成一個(gè)其值等于串常量chars的串Tif(T.ch)free(T.ch);//釋放T原有空間i=strlen(chars);//求chars的長(zhǎng)度iif(!i){T.ch=NULL;T.length=0;}else{//chars的長(zhǎng)度不為0T.ch=(char*)malloc(i*sizeof(char));//分配串空間if(!T.ch)//分配串空間失敗exit(OVERFLOW);T.ch[0..i-1]=chars[0..i-1];T.length=i;}returnOK;}49Hstring串類基本操作的算法描述1449intStrLength(HStringS){//返回S的元素個(gè)數(shù),稱為串的長(zhǎng)度returnS.length;}intStrCompare(HStringS,HStringT){//若S>T,則返回值>0;若S=T,則返回值=0;若S<T,則返回值<0inti;for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}50intStrLength(HStringS)int50StatusClearString(HString&S){//將S清為空串if(S.ch){free(S.ch);S.ch=NULL;}S.length=0;returnOK;}51StatusClearString(HString&S51StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2聯(lián)接而成的新串if(T.ch)free(T.ch);//釋放舊空間T.length=S1.length+S2.length;T.ch=(char*)malloc(T.length*sizeof(char));if(!T.ch)exit(OVERFLOW);for(i=0;i<S1.length;i++)T.ch[i]=S1.ch[i];for(i=0;i<S2.length;i++)T.ch[S1.length+i]=S2.ch[i];returnOK;}52StatusConcat(HString&T,HStr52StatusSubString(HString&Sub,HStringS,intpos,intlen){//用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。//其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);//釋放舊空間if(!len){Sub.ch=NULL;Sub.length=0;}//空子串else{//完整子串Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2];Sub.length=len;}returnOK;}53StatusSubString(HString&Sub534.2.3串的塊鏈存儲(chǔ)結(jié)構(gòu)為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小(比如說劃分成大小為4的結(jié)點(diǎn))，每一個(gè)結(jié)點(diǎn)有兩個(gè)域：data域放4個(gè)字符，next域放下一個(gè)結(jié)點(diǎn)的指針。例如,s='abcdefghk'顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來(lái)填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。544.2.3串的塊鏈存儲(chǔ)結(jié)構(gòu)為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存54#definechunksize80typedefstructchunk{charch[chunksize];structchunk*next;}chunktypedefstruct{//串的鏈表結(jié)構(gòu)Chunk*head,*tail;//串的頭和尾指針intcurlen;//串的當(dāng)前長(zhǎng)度}LString;55#definechunksize80typedef554.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)Index(S,T,pos)采用定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu),不依賴其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也稱為模式，1<=pos<=S的長(zhǎng)度。//若主串S中存在和模式T相同的子串，則返回它在主串//S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則返回０。i=pos;j=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后續(xù)字符

else{i=i-j+2;j=1;}//指針后退重新開始匹配}

if(j>T[0])returni-T[0];//匹配成功

elsereturn0;//匹配不成功}564.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)In56簡(jiǎn)單匹配算法（BF算法）的匹配過程示例例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ijijij第1趟abcac

57簡(jiǎn)單匹配算法（BF算法）的匹配過程示例例：主串S="abab57例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失?。籭回溯到2，j回溯到1ji第1趟abcac

簡(jiǎn)單匹配算法（BF算法）的匹配過程示例58例：主串S="ababcabcacbab"，模式T="abc58例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第2趟ijabcac

簡(jiǎn)單匹配算法（BF算法）的匹配過程示例59例：主串S="ababcabcacbab"，模式T="abc59例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=1失敗i回溯到3，j回溯到1第2趟ijabcac

簡(jiǎn)單匹配算法（BF算法）的匹配過程示例60例：主串S="ababcabcacbab"，模式T="abc60例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=7，j=5失敗i回溯到4，j回溯到1第3趟ijijijijij簡(jiǎn)單匹配算法（BF算法）的匹配過程示例61例：主串S="ababcabcacbab"，模式T="a