数据结构课件(部分6)

4.1串类型的定义一、串和基本概念串是零个或多个字符组成的有限序列。一般记作S=‘a1a2a3…an’，S是串名，单引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串。注意：空串和空白串的不同，例如“”和“”分别表示长度为1的空白串和长度为0的空串。

第四章串14.1串类型的定义第四章串1串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如: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。注意:单引号是为字符串区别于变量名而设,它不是字符串的内容称两个串是相等的当且仅当这两个串每个字符对应相等2串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相2二、串的抽象数据定义

串的抽象数据类型定义见书P71ADTString{数据对象：D={ai|ai∈CharacteSet,i=1,2,...n,n>=0}数据关系：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二、串的抽象数据定义33基本操作的功能说明StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个其值等于chars的串T。StrCopy(&T,S)初始条件:字符串S已经存在。操作结果:由串S复制得串T。StrEmpty(S)初始条件:字符串S已经存在。操作结果:若S为空串，则返回TRUE,否则返回FALSE。StrCompare(S,T)初始条件:字符串S和T存在。操作结果:若S>T,则返回值>0;若S=T,则返回值=0;否则返回值<0。4基本操作的功能说明StrAssign(&T,chars)44StrLength(S)初始条件:字符串S已经存在。操作结果:返回串S元素个数，称为串的长度。ClearString(&S)初始条件:字符串S已经存在。操作结果:将串S清为空串。Concat(&T,S1,S2)初始条件:字符串S1,S2已经存在。操作结果:用T返回由串S1和S2联结而成的新串。Substring(&Sub,S,pos,len)初始条件:串S存在,1<=pos<=S的长度,0<=len<=S的长度-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。5StrLength(S)55Index(S,T,pos)初始条件:串S和T存在,T是非空串，1<=pos<=S的长度。操作结果:若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则返回０。Replace(&S,T,V)初始条件:字符串S,T,V已经存在，T是非空串。操作结果:用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(&S,pos,T)初始条件:字符串S,T存在，1<=pos<=S的长度+1。操作结果:在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件:串S存在，1<=pos<=S的长度-len+1。操作结果:从串S中删除第pos个字符起长度为len的子串。DestroyString(&S):把存在的串S销毁。6Index(S,T,pos)66上述13种基本操作中,下面5种操作构成最小操作子集:串赋值StrAssign;串比较StrCompare;求串长StrLength;串联结Concat;求子串Substring;其它操作可以用其实现例如定位函数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种操作构成最小操作子集:int74.2串的表示和实现4.2.1定长顺序存储表示用一组连续的存储单元存储串值的字符序列.在C语言中,用字符“\0”表示串的终结,“\0”不计入串长.另一种方法是定长数组表示一个串:#defineMAXSTRLEN255//串的长度最大为255typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串的长度,其最大值刚好是255.当超出255个字符时,串的多余内容被舍去,叫做“截断”以下用串联结和求子串为例介绍这种存储84.2串的表示和实现4.2.1定长顺序存储表示#def8S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN时S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN时截断部分9S1S2T0maxst91.串联结Concat(&T,S1,S2)的算法statusConcat(SString&T,SStringS1,SStringS2){//用T返回由串S1和S2联结而成的新串。若未被截断,则返回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.串联结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堆分配存储表示

也是用一组连续的存储单元存储串值的字符序列.但存储空间是在程序执行过程中动态分配得到的.在C语言中,用字符“\0”表示串的终结,“\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的元素个数,称为串的长度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联接而成的新串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串的块链存储结构为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小(比如说划分成大小为4的结点)，每一个结点有两个域：data域放4个字符，next域放下一个结点的指针。例如,s='abcdefghk'显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。194.2.3串的块链存储结构为了提高存储密度，可使每个结点存19#definechunksize80typedefstructchunk{charch[chunksize];structchunk*next;}chunktypedefstruct{//串的链表结构Chunk*head,*tail;//串的头和尾指针intcurlen;//串的当前长度}LString;20#definechunksize80typedef204.3串的模式匹配算法4.3.1求子串位置的定位函数Index(S,T,pos)采用定长顺序存储结构,不依赖其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也称为模式，1<=pos<=S的长度。//若主串S中存在和模式T相同的子串，则返回它在主串//S中第pos个字符之后第一次出现的位置；否则返回０。i=pos;j=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;//匹配不成功}214.3串的模式匹配算法4.3.1求子串位置的定位函数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个字符之后第一次出现的位置；否则返回０。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算法的复杂度分析设n=StrLength(S);m=StrLength(T);设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：最好情况的复杂度为O(n+m),如T=“STING”S=“ASTRINGSEARCHINGEXAMPLECONSISTINGOFSIMPLETEXT”34BF算法的复杂度分析设n=StrLength(S);m34最坏情况,T=“00000001”S=“00000000000000000000000000000000000000000000000001”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。而01串是计算机应用中最普遍的一种，所以有必要改进该模式匹配算法。35最坏情况,3535

4.1串类型的定义一、串和基本概念串是零个或多个字符组成的有限序列。一般记作S=‘a1a2a3…an’，S是串名，单引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串。注意：空串和空白串的不同，例如“”和“”分别表示长度为1的空白串和长度为0的空串。

第四章串364.1串类型的定义第四章串36串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如: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。注意:单引号是为字符串区别于变量名而设,它不是字符串的内容称两个串是相等的当且仅当这两个串每个字符对应相等37串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相37二、串的抽象数据定义

串的抽象数据类型定义见书P71ADTString{数据对象：D={ai|ai∈CharacteSet,i=1,2,...n,n>=0}数据关系：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二、串的抽象数据定义338基本操作的功能说明StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个其值等于chars的串T。StrCopy(&T,S)初始条件:字符串S已经存在。操作结果:由串S复制得串T。StrEmpty(S)初始条件:字符串S已经存在。操作结果:若S为空串，则返回TRUE,否则返回FALSE。StrCompare(S,T)初始条件:字符串S和T存在。操作结果:若S>T,则返回值>0;若S=T,则返回值=0;否则返回值<0。39基本操作的功能说明StrAssign(&T,chars)439StrLength(S)初始条件:字符串S已经存在。操作结果:返回串S元素个数，称为串的长度。ClearString(&S)初始条件:字符串S已经存在。操作结果:将串S清为空串。Concat(&T,S1,S2)初始条件:字符串S1,S2已经存在。操作结果:用T返回由串S1和S2联结而成的新串。Substring(&Sub,S,pos,len)初始条件:串S存在,1<=pos<=S的长度,0<=len<=S的长度-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。40StrLength(S)540Index(S,T,pos)初始条件:串S和T存在,T是非空串，1<=pos<=S的长度。操作结果:若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则返回０。Replace(&S,T,V)初始条件:字符串S,T,V已经存在，T是非空串。操作结果:用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(&S,pos,T)初始条件:字符串S,T存在，1<=pos<=S的长度+1。操作结果:在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件:串S存在，1<=pos<=S的长度-len+1。操作结果:从串S中删除第pos个字符起长度为len的子串。DestroyString(&S):把存在的串S销毁。41Index(S,T,pos)641上述13种基本操作中,下面5种操作构成最小操作子集:串赋值StrAssign;串比较StrCompare;求串长StrLength;串联结Concat;求子串Substring;其它操作可以用其实现例如定位函数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种操作构成最小操作子集:int424.2串的表示和实现4.2.1定长顺序存储表示用一组连续的存储单元存储串值的字符序列.在C语言中,用字符“\0”表示串的终结,“\0”不计入串长.另一种方法是定长数组表示一个串:#defineMAXSTRLEN255//串的长度最大为255typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串的长度,其最大值刚好是255.当超出255个字符时,串的多余内容被舍去,叫做“截断”以下用串联结和求子串为例介绍这种存储434.2串的表示和实现4.2.1定长顺序存储表示#def43S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN时S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN时截断部分44S1S2T0maxst441.串联结Concat(&T,S1,S2)的算法statusConcat(SString&T,SStringS1,SStringS2){//用T返回由串S1和S2联结而成的新串。若未被截断,则返回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.串联结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堆分配存储表示

也是用一组连续的存储单元存储串值的字符序列.但存储空间是在程序执行过程中动态分配得到的.在C语言中,用字符“\0”表示串的终结,“\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的元素个数,称为串的长度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联接而成的新串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串的块链存储结构为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小(比如说划分成大小为4的结点)，每一个结点有两个域：data域放4个字符，next域放下一个结点的指针。例如,s='abcdefghk'显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。544.2.3串的块链存储结构为了提高存储密度，可使每个结点存54#definechunksize80typedefstructchunk{charch[chunksize];structchunk*next;}chunktypedefstruct{//串的链表结构Chunk*head,*tail;//串的头和尾指针intcurlen;//串的当前长度}LString;55#definechunksize80typedef554.3串的模式匹配算法4.3.1求子串位置的定位函数Index(S,T,pos)采用定长顺序存储结构,不依赖其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也称为模式，1<=pos<=S的长度。//若主串S中存在和模式T相同的子串，则返回它在主串//S中第pos个字符之后第一次出现的位置；否则返回０。i=pos;j=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;//匹配不成功}564.3串的模式匹配算法4.3.1求子串位置的定位函数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