第4章--串

1一、教学内容：1、串的概念；2、串的存储结构；3、串的运算。二、教学要求：1、理解串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法；2、熟练掌握在串的顺序存储结构上实现串的各种操作的方法3、了解串操作的应用方法和特点。第四章串2第四章串串类型的定义串的表示和实现串的模式匹配算法34.1串类型定义串(String)----零个或多个字符组成的有限序列.’‘21naaasL=串名串值串长n空串n=04a=‘BEI’,b=‘JING’c=‘BEIJING’d=‘BEIJING’子串字符位置主串子串位置串相等空格串4.1串类型定义50}n,,,2,1,|{==nietCharacterSaaDiiL串的抽象数据类型数据对象:数据关系:},,2,1,,|,{111niDaaaaRiiiiL==ADTString{6基本操作:(1)StrAssign(&T,chars)//串赋值(2)StrCompare(S,T)//串比较(3)StrLength(S)//求串长(4)Concat(&T,S1,S2)//串联(5)SubString(&Sub,S,pos,len)//求子串串的最小操作子集7(6)StrCopy(&T,S)//串拷贝(7)StrEmpty(S)//串判空(8)ClearString(&S)//清空串(9)Index(S,T,pos)//求子串的位置(11)Replace(&S,T,V)//串替换(12)StrInsert(&S,pos,T)//子串插入(12)StrDelete(&S,pos,len)//子串删除(13)DestroyString(&S)//串销毁}ADTString基本操作:利用上述基本运算还可以组合成字符串的其他有关操作.8串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。94.2串的表示和实现定长顺序表示★★-了解！堆分配存储表示★★★★-重点！串的块链存储表示★-了解！104.2.1定长顺序存储表示-了解！#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串长定长顺序存储表示,也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：SStringT;特点:串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”。按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。114.2.2堆分配存储表示typedefstruct{char*ch;//若串非空,则按串长分配存储区,//否则ch为NULLintlength;//串长度}HString;这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。typedefchar*string;//c中的串库相当于此类型定义注意：在C语言中，下标从0开始，此处与串的定长顺序存储的下标从1~Length不同12通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空操作字符‘\0’为结束符，串长是一个隐含值。这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。13(1)串初始化voidInitString(HString&T){T.length=0;T.ch=NULL;}14StatusClearString(HString&S){//将S清为空串if(S.ch){free(S.ch);S.ch=NULL=0;}S.length=0;returnOK;}//ClearString(2)清空串#defineDestroyStringClearString15StatusStrAssign(HString&T,char*chars){if(T.ch)free(T.ch);//释放T原有空间for(i=0,c=chars;*c!=‘\0’;++i,++c);//求chars的长度iif(!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.length=i;}returnOK;}//StrAssign(3)串赋值(4)串拷贝voidStrCopy(HString&T,HStringS){if(T.ch)free(T.ch);//释放串T原有存储空间T.ch=(char*)malloc(S.length*sizeof(char));//分配存储空间if(!T.ch)//分配串存储空间失败exit(OVERFLOW);for(i=0;iS.length;i++)//从第1个字符到最后一个字符T.ch[i]=S.ch[i];//逐一复制字符T.length=S.length;//复制串长}1617StatusStrEmpty(HStringS){//初始条件：串S存在。操作结果：若串S为空，则返回TRUE；否则返回FALSEif(S.length==0&&S.ch==NULL)//空串标志returnTRUE;elsereturnFALSE;}(5)串判空18intStrLength(HStringS){//返回S的元素个数,称为串的长度returnS.length;}//StrLength（6）求串长19intStrCompare(HStringS,HStringT){//若ST,返回值0;若S=T,返回值=0;若ST,返回值0;for(i=0;iS.length&&iT.length;++i)if(S.ch[i]!=T.ch[i]return(S.ch[i]-T.ch[i]);returnS.length-T.length;}//StrCompare（7）串比较20（8）串插入StatusStringInsert(HString&S,intpos,HStringT){STposS.lengthT.length(pos=1)&&(pos=S.length+1)21（8）串插入StatusStringInsert(HString&S,intpos,HStringT){STposS.length+T.lengthT.lengthfor(i=S.length-1;i=pos-1;--i)S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];pos+T.length-122StatusStringInsert(HString&S,intpos,HStringT){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(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;}returnOK;}//StringInsert算法4.423StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2联接而成的新串if(T.ch)free(T.ch);//释放旧空间if(!(T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char))))exit(OVERFLOW);T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];T.length=S1.length+S2.length;T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];returnOK;}//Concat（9）串联接24HStringSubString(HString&Sub,HStringS,intpos,intlen){if(pos1||posS.length||len0||lenS.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[pos-1..pos+len-2];Sub.length=len;}returnOK;}//SubString（10）求子串25串的堆分配存储表示小结存储空间动态分配(释放旧空间-申请新空间！)实现串操作的方法：字符序列的复制操作的算法时间复杂度：基于串长优点：有顺序存储结构的特点处理方便操作中对串长没有限制264.2.3串的块链存储表示ABCDEFGHI###headABCIhead...也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存储密度=数据元素所占存储位实际分配的存储位特点：以一组存储单元（在程序执行过程中动态分配）存放串值字符序列-串的链表表示。结点大小为1的链表结点大小为4的链表27例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。28串的块链存储表示小结串的块链存储结构-串的链表表示。除了某些特定操作如联接有一定方便之处，总的来说不如另外两种存储结构灵活结点大小为１优点:操作方便；缺点:存储密度较低，占用存储量大。所谓存储密度为：结点大小为４优点：存储密度高；缺点：插入、删除字符时，可能会引起结点之间字符的移动，算法实现比较复杂。存储密度＝串值所占存储位实际分配存储位子串的定位操作intIndex(S,T,pos)称为串的模式匹配4.3串的模式匹配正文串S=s1s2sn模式串T=p1p2pmsisi+1si+m-1=p1p2pm30例：Index操作的实现intIndex(StringS,StringT,intpos){SposTmn31例：Index操作的实现(该操作与存储结构无关)intIndex(StringS,StringT,intpos){STposnmi=posmSub32例：Index操作的实现intIndex(StringS,StringT,intpos){STposnmi=pos+1mSub33例：Index操作的实现intIndex(StringS,StringT,intpos){STposnmi=pos+2mSub34例：Index操作的实现intIndex(StringS,StringT,intpos){STposnmi