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

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

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

串的抽象數(shù)據(jù)類型定義見書P71ADTString{數(shù)據(jù)對象：D={ai|ai∈CharacteSet,i=1,2,...n,n>=0}數(shù)據(jù)關(guān)系：R1={＜ai-1.,ai＞|ai∈D,i=2,...n}?；静僮鳎篠trAssign(&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é)果:生成一個其值等于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元素個數(shù)，稱為串的長度。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的長度,0<=len<=S的長度-pos+1。操作結(jié)果:用Sub返回串S的第pos個字符起長度為len的子串。5StrLength(S)55Index(S,T,pos)初始條件:串S和T存在,T是非空串，1<=pos<=S的長度。操作結(jié)果:若主串S中存在和串T相同的子串，則返回它在主串S中第pos個字符之后第一次出現(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的長度+1。操作結(jié)果:在串S的第pos個字符之前插入串T。StrDelete(&S,pos,len)初始條件:串S存在，1<=pos<=S的長度-len+1。操作結(jié)果:從串S中刪除第pos個字符起長度為len的子串。DestroyString(&S):把存在的串S銷毀。6Index(S,T,pos)66上述13種基本操作中,下面5種操作構(gòu)成最小操作子集:串賦值StrAssign;串比較StrCompare;求串長StrLength;串聯(lián)結(jié)Concat;求子串Substring;其它操作可以用其實現(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串的表示和實現(xiàn)4.2.1定長順序存儲表示用一組連續(xù)的存儲單元存儲串值的字符序列.在C語言中,用字符“\0”表示串的終結(jié),“\0”不計入串長.另一種方法是定長數(shù)組表示一個串:#defineMAXSTRLEN255//串的長度最大為255typedefunsignedcharSString[MAXSTRLEN+1];//0號單元存放串的長度,其最大值剛好是255.當超出255個字符時,串的多余內(nèi)容被舍去,叫做“截斷”以下用串聯(lián)結(jié)和求子串為例介紹這種存儲84.2串的表示和實現(xiàn)4.2.1定長順序存儲表示#def8S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN時S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN時截斷部分9S1S2T0maxst91.串聯(lián)結(jié)Concat(&T,S1,S2)的算法statusConcat(SString&T,SStringS1,SStringS2){//用T返回由串S1和S2聯(lián)結(jié)而成的新串。若未被截斷,則返回1;否則返回0。if(S1[0]+S2[0]<=MAXSTRLEN){//未被截斷T[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){//截斷T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=0;}else{//截斷(僅取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個字符起長度為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堆分配存儲表示

也是用一組連續(xù)的存儲單元存儲串值的字符序列.但存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的.在C語言中,用字符“\0”表示串的終結(jié),“\0”不計入串長.typedefstruct{char*ch;//若是非空串,則按實際長度分配,否則為NULL;intlength;//串長度}HString;以下用串插入操作StrInsert(&S,pos,T)為例介紹這種存儲124.2.2堆分配存儲表示typedefstruct{以12串插入StrInsert(&S,pos,T)的算法statusStrInsert(HString&S,intpos,HStringT){//1<=pos<=StrLength(S)+1。在串S的第pos個字符之前插入串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){//生成一個其值等于串常量chars的串Tif(T.ch)free(T.ch);//釋放T原有空間i=strlen(chars);//求chars的長度iif(!i){T.ch=NULL;T.length=0;}else{//chars的長度不為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的元素個數(shù),稱為串的長度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個字符起長度為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串的塊鏈存儲結(jié)構(gòu)為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放的字符個數(shù)定義為結(jié)點的大小(比如說劃分成大小為4的結(jié)點)，每一個結(jié)點有兩個域：data域放4個字符，next域放下一個結(jié)點的指針。例如,s='abcdefghk'顯然，當結(jié)點大小大于1時，串的長度不一定正好是結(jié)點的整數(shù)倍，因此要用特殊字符來填充最后一個結(jié)點，以表示串的終結(jié)。194.2.3串的塊鏈存儲結(jié)構(gòu)為了提高存儲密度，可使每個結(jié)點存19#definechunksize80typedefstructchunk{charch[chunksize];structchunk*next;}chunktypedefstruct{//串的鏈表結(jié)構(gòu)Chunk*head,*tail;//串的頭和尾指針intcurlen;//串的當前長度}LString;20#definechunksize80typedef204.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)Index(S,T,pos)采用定長順序存儲結(jié)構(gòu),不依賴其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也稱為模式，1<=pos<=S的長度。//若主串S中存在和模式T相同的子串，則返回它在主串//S中第pos個字符之后第一次出現(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簡單匹配算法（BF算法）的匹配過程示例例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ijijij第1趟abcac

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

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

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

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

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

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

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

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

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

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

i=11，j=6，T中全部字符都比較完畢，匹配成功。第6趟ijijijijij簡單匹配算法（BF算法）的匹配過程示例32例：主串S="ababcabcacbab"，模式T="abc32intIndex(SStringS,SStringT,intpos){//T是非空串,也稱為模式，1<=pos<=S的長度。//若主串S中存在和模式T相同的子串，則返回它在主串//S中第pos個字符之后第一次出現(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ù)是：即最壞情況下的時間復(fù)雜度是O(n*m)。而01串是計算機應(yīng)用中最普遍的一種，所以有必要改進該模式匹配算法。35最壞情況,3535

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

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

串的抽象數(shù)據(jù)類型定義見書P71ADTString{數(shù)據(jù)對象：D={ai|ai∈CharacteSet,i=1,2,...n,n>=0}數(shù)據(jù)關(guān)系：R1={＜ai-1.,ai＞|ai∈D,i=2,...n}?；静僮鳎篠trAssign(&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é)果:生成一個其值等于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元素個數(shù)，稱為串的長度。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的長度,0<=len<=S的長度-pos+1。操作結(jié)果:用Sub返回串S的第pos個字符起長度為len的子串。40StrLength(S)540Index(S,T,pos)初始條件:串S和T存在,T是非空串，1<=pos<=S的長度。操作結(jié)果:若主串S中存在和串T相同的子串，則返回它在主串S中第pos個字符之后第一次出現(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的長度+1。操作結(jié)果:在串S的第pos個字符之前插入串T。StrDelete(&S,pos,len)初始條件:串S存在，1<=pos<=S的長度-len+1。操作結(jié)果:從串S中刪除第pos個字符起長度為len的子串。DestroyString(&S):把存在的串S銷毀。41Index(S,T,pos)641上述13種基本操作中,下面5種操作構(gòu)成最小操作子集:串賦值StrAssign;串比較StrCompare;求串長StrLength;串聯(lián)結(jié)Concat;求子串Substring;其它操作可以用其實現(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串的表示和實現(xiàn)4.2.1定長順序存儲表示用一組連續(xù)的存儲單元存儲串值的字符序列.在C語言中,用字符“\0”表示串的終結(jié),“\0”不計入串長.另一種方法是定長數(shù)組表示一個串:#defineMAXSTRLEN255//串的長度最大為255typedefunsignedcharSString[MAXSTRLEN+1];//0號單元存放串的長度,其最大值剛好是255.當超出255個字符時,串的多余內(nèi)容被舍去,叫做“截斷”以下用串聯(lián)結(jié)和求子串為例介紹這種存儲434.2串的表示和實現(xiàn)4.2.1定長順序存儲表示#def43S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN時S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN時截斷部分44S1S2T0maxst441.串聯(lián)結(jié)Concat(&T,S1,S2)的算法statusConcat(SString&T,SStringS1,SStringS2){//用T返回由串S1和S2聯(lián)結(jié)而成的新串。若未被截斷,則返回1;否則返回0。if(S1[0]+S2[0]<=MAXSTRLEN){//未被截斷T[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){//截斷T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=0;}else{//截斷(僅取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個字符起長度為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堆分配存儲表示

也是用一組連續(xù)的存儲單元存儲串值的字符序列.但存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的.在C語言中,用字符“\0”表示串的終結(jié),“\0”不計入串長.typedefstruct{char*ch;//若是非空串,則按實際長度分配,否則為NULL;intlength;//串長度}HString;以下用串插入操作StrInsert(&S,pos,T)為例介紹這種存儲474.2.2堆分配存儲表示typedefstruct{以47串插入StrInsert(&S,pos,T)的算法statusStrInsert(HString&S,intpos,HStringT){//1<=pos<=StrLength(S)+1。在串S的第pos個字符之前插入串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){//生成一個其值等于串常量chars的串Tif(T.ch)free(T.ch);//釋放T原有空間i=strlen(chars);//求chars的長度iif(!i){T.ch=NULL;T.length=0;}else{//chars的長度不為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的元素個數(shù),稱為串的長度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個字符起長度為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串的塊鏈存儲結(jié)構(gòu)為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放的字符個數(shù)定義為結(jié)點的大小(比如說劃分成大小為4的結(jié)點)，每一個結(jié)點有兩個域：data域放4個字符，next域放下一個結(jié)點的指針。例如,s='abcdefghk'顯然，當結(jié)點大小大于1時，串的長度不一定正好是結(jié)點的整數(shù)倍，因此要用特殊字符來填充最后一個結(jié)點，以表示串的終結(jié)。544.2.3串的塊鏈存儲結(jié)構(gòu)為了提高存儲密度，可使每個結(jié)點存54#definechunksize80typedefstructchunk{charch[chunksize];structchunk*next;}chunktypedefstruct{//串的鏈表結(jié)構(gòu)Chunk*head,*tail;//串的頭和尾指針intcurlen;//串的當前長度}LString;55#definechunksize80typedef554.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)Index(S,T,pos)采用定長順序存儲結(jié)構(gòu),不依賴其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也稱為模式，1<=pos<=S的長度。//若主串S中存在和模式T相同的子串，則返回它在主串//S中第pos個字符之后第一次出現(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簡單匹配算法（BF算法）的匹配過程示例例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失敗；i回溯到2，j回溯到1ijijij第1趟abcac

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

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

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

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

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