数据结构串的性质和基本操作本

第四章串的性质和基本操作为什么要学习字符串？计算机在处理非数值数据时基本是字符串。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大的差别。串操作中，通常以“串的整体”作为操作对象。也就是说，串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。串是一种内容受限的线性表。本章内容4.1串的定义4.2串的表示和实现4.3串的模式匹配算法1.串的顺序存储结构2.串的链式存储结构1.朴素的模式匹配算法2.KMP算法串的定义和相关概念串（String）:由零个或多个字符组成的有限序列。记为：s=’a1a2…an’（n≥0）1.串的定义2.相关概念s为串名，’a1a2…an’为串值，n为串的长度。ai，约束为字符集中的字符。空串（NullString）：n=0，记为：Ф。空格串(blankstring)：串中仅包含空格字符。子串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串被称为主串。子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。串相等：当且仅当两个串的串值相等（两个串的长度相等，并且各个对应的字符也都相等）。串的抽象数据类型定义ADTString{数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：……}串是有限长的字符序列，由一对单引号相括，如:astring串的操作串赋值：StrAssign(&S,chars)求串长：StrLength(S)串判等：StrCompare(S,T)串联接：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)（其中，前5个操作为基本操作构成最小操作子集。）对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：例如，可利用串判等、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,pos,StrLength(T)),T)?0S串T串T串iposn-m+1算法的基本思想为：intIndex(StringS,StringT,intpos){if(pos0){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;//S中不存在与T相等的子串}//IndexT为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0。又如串的置换函数：S串T串V串V串pospossubinews串subS串串运算举例1.求子串SubString(&sub,S,pos,len)SubString(sub,commander,4,3)求得sub=；？manSubString(sub,commander,1,9)求得sub=；？commanderSubString(sub,commander,9,1)求得sub=；？r串运算举例起始位置和子串长度之间存在约束关系SubString(sub,commander,4,7)求得sub=；？manderSubString(sub,beijing,7,2)求得sub=；？gSubString(sub,student,5,0)求得sub=；？串运算举例2.子串定位Index(S,T,pos)假设S=abcaabcaaabc,T=bca求得Index(S,T,1)=；？2求得Index(S,T,3)=；？6求得Index(S,T,8)=；？0串运算举例3.替换子串Replace(&S,T,V)假设S=abcaabcaaabca，T=bca，若V=x，则经置换后得到S=；？axaxaax若V=bc，则经置换后得到S=；？abcabcaabc串运算举例4.插入子串StrInsert(&S,pos,T)例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=；？character5.删除子串StrDelete(&S,pos,len)例如：S=WelcometoBeijing，则执行StrDelete(S,8,4)之后得到S=；？WelcomeBeijing串的表示和实现1.串的顺序存储结构用一组连续的存储单元依次存储串中的字符序列。①定长顺序存储②堆分配存储2.串的链式存储结构每个结点一个字符的单链表表示每个结点多个字符的块链存储表示串的定长顺序存储表示#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串的长度预先定义字符数组大小静态存储按这种串的表示方法实现串的运算时，其基本操作为“字符序列的复制”。串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”。特点StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。returnuncut;}//Concat例如：串的联接算法中需分三种情况处理：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;}if(S1[0]+S2[0]=MAXSTRLEN){//未截断elseif(S1[0]MAXSTRSIZE){//截断else{//截断(仅取S1)T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;}串的堆分配存储表示typedefstruct{char*ch;intlength;}HString;在程序执行过程中，利用标准函数malloc和free动态分配或释放存储字符串的存储单元，并以一个特殊的字符（’\0’）作为字符串的结束标志。从堆区分配，故得名堆分配存储。按串长分配存储区，动态存储通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符(‘\0’)为结束符，串长是一个隐含值。这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。串的堆分配存储的操作实现串连接intStringConcat(HString&T,HStringS1,HStringS2){∥T返回S1和S2联接的新串if(T.ch)free(T.ch);∥释放T原来占据的空间if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW);∥重新为T分配空间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;}∥StringConcat串的链式存储表示串作为一种特殊的线性表（数据元素为字符），使用顺序表示时，做插入和删除运算，运算量很大，不方便，效率低。采用链式存储结构spring^SSspring####^？直接采用第一种链表存储串值，进行操作时效率太低。用链表存储串值，每个结点可以存放一个字符，也可以存放多个字符。由于串长不一定是结点大小的整数倍，则链表中最后一个结点不一定完全被串值占满，补上’#’。串的块链存储表示块的结构定义串的链表结构定义#defineCHUNKSIZE80∥可由用户定义的块大小typedefstructChunk{∥结点结构charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{∥串的链表结构Chunk*head,*tail;∥串的头和尾指针intcurlen;∥串的当前长度}LString;