数据结构(c语言版)第4章串.

第4章串第4章串4.1串的定义4.2抽象数据类型串的实现4.3串的模式匹配算法4.4串的应用举例：文本编辑第4章串4.1串的定义串(String)是零个或多个字符组成的有限序列。一般记为：S=‘a1a2...an’(n≥0)其中S是串的名字，用单引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度，n=0时的串称为空串(NullString)。第4章串串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。假如有串A=‘ChinaBeijing’，B=‘Beijing’，C=‘China’，则它们的长度分别为13、7和5。B和C是A的子串，B在A中的位置是7，C在A中的位置是1。当且仅当两个串的值相等时，称这两个串是相等的，即只有当两个串的长度相等，并且每个对应位置的字符都相等时才相等。第4章串串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其它字符中间。由一个或多个空格组成的串‘’称为空格串（blankstring，请注意此处不是空串）。它的长度为串中空格字符的个数。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。第4章串串的抽象数据类型定义如下:ADTString{数据对象:D={ai|ai∈CharacterSet,i=1,2,…,n;n≥0}数据关系:R={ai-1,ai|ai-1,ai∈D,i=2,…,n;n≥0}基本操作:(1)StrAssign（&T,chars）初始条件：chars是字符串常量。操作结果：生成一个其值等于chars的串T。第4章串(2)Strcopy（&T,S）初始条件：串S存在。操作结果：由串S复制得串T。(3)StrEmpty（S）初始条件：串S存在。操作结果：若S为空串，则返回TURE，否则返回FALSE(4)StrCompare（S，T）初始条件：串S和T存在。操作结果：若ST，则返回值0；若S=T,则返回值＝0；若ST,则返回值0。第4章串(5)StrLength(S)初始条件:串S存在。操作结果:返回串S的长度,即串S中的元素个数。(6)ClearString（&S）初始条件：串S存在。操作结果：将S清为空串。(7)Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。第4章串(8)SubString(&Sub,S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。(9)Index（S，T，pos）初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。(10)Replace（&S,T,V）初始条件：串S，T和V存在，T是非空串。操作结果：用V替换主串S的第pos个字符之前插入串T。第4章串(11)StrInsert（&S,pos,T）初始条件：串S和T存在，1≤pos≤StrLength(S)。操作结果:在串S的第pos个字符起长度为len的子串。(12)StrDelete（&S,pos,len）初始条件：串S存在，1≤pos≤StrLength(S)–len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。。(13)DestroyString（&S）初始条件：串S存在。操作结果：串S被销毁。第4章串对于串的基本操作集可以有不同的定义方法，读者在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串比较StrCompare、求串长StrLengt、串联接Concat以及求子串SubString等五种操作构成的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）均可在这个最小操作子集上实现。例如：可利用判等、求串长和求子串等操作作为实现定位函数Index（S，T，pos）。算法的基本思想为：在主串S中取从第i（i的初值为pos）个字符起、长度和T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止。如算法4.1所示。第4章串intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，//则返回第一个这样的子串在S中的位置，否则返回0if(pos0)n=StrLength(T);m=StrLength(T);i=pos;while(i＝n-m+1){SubString(Sub,S,i,m);iIf(StrCompare(Sub,T)!=0)++i;elsereturnI;}//while}//ifreturn0;//S中不存在与T相等的子串}//Index第4章串4.2抽象数据类型串的实现4.2.1定长顺序串类似于线形表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述之。#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串的长度第4章串串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。对串长有两种表示方法：一个是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言中的串类型采用这种表示方法；二是在串值后面加一个不计入串长的结束标记字符，如在C语言中以“\0”表示串值的终结。此时的串长为隐含值，显然不便于进行某些串操作。第4章串1.串联接Concat(&T,S1,S2)假设S1、S2和T都是SString型的串变量，且串T是由串S1联接串S2得到的，即串T的值的前一段和串S1的值相等，串T的值的后一段和串S2的值相等，则只要进行相应的“串值复制”操作即可，只是需要按前述约定，对超长部分实施“截断”操作。基于串S1和S2长度的不同情况，串T的产生可能有如下三种情况：1）S1[0]+S2[0]=MAXSTRLEN，如图4.10(a)所示，得到的串T是正确的结果；2）S1[0]MAXSTRLEN而S1[0]+S2[0]MAXSTRLEN，则将串S2的一部分截断，得到的串T只包含串S2的一个子串，如图4.1(b)所示；3）S1[0]=MAXSTRLEN，则得到的串T并非联接结果，而和串S1相等。上述算法描述如算法4.2所示。第4章串StatusConcat(SString&T,SStringS1,SStringS2){//用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE,否则FALSE。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=TRUE;}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=FALSE;}else{//截取（仅取S1）T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];Uncut=FALSE;}returnuncut;}//Concat第4章串2.求子串SubString(&Sub,S,pos,len)求子串的过程即为复制字符串的过程。将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。显然，本操作不会有需截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回ERROR。其算法描述如算法4.3所示。StatusSubString(SString&Sub,SStringS,intpos.intlen){//用Sub返回串是S的第pos个字符起长度为len的字串。//其中，1=pos=Strlength(S)0=len=Strlength(S)–pos+1。if(pos1||len0||lenS[0]–pos+1)returnERROR;Sub[1..len]=S[pos..pos+len–1];Sub[0]=len;returnOK;}//SubString第4章串综上两个操作可见，在顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于复制的字符序列的长度。另一操作特点是，如果在操作中出现串值序列的长度超过上界MAXSTRLRN时，约定用结尾法处理，这种情况不仅在求联接串时可能发生，在串的其他操作中，如插入、置换等也可能发生。克服这个弊病惟有不限定串长的最大长度，即动态分配串的存储空间。第4章串4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新产生的串分配一块实际串长所需要的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结果的一部分。typedefstruct{char*ch;//若是非空串，则按串长分配存储区，否则ch为NULLintlength;//串长度}HString;第4章串（1）串插入操作StrInsert(&S,pos,T)为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值复制。StatusStrInsert(HString&S,intpos,HStringT){//1=pos=Strlength(S)+1.在串S的第pos个字符之前插入串T。if(pos1||posS.length+1)returnERROR;//pos不合法if(T.length){//T非空，则重新分配，插入Tif(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLIW);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;}returnOK;}//StrInsert第4章串StatusStrAssing(HString&T,char*chars){//生成一个其值等于串常量chars的串Tif(T.ch)free(T.ch);//释放T原有的空间for(i=0,c=chars;*c;++i,++c);//求chars的长度if(!i){T.ch=NULL;T.length=0;}else{if(!(T.ch=(char*)malloc(i*sizeof(char))))exit(OVERFLOW);T.ch[0..i–1]=chars[0..i–1];T.l