串类型的定义串的表示与实现串的模式匹配算法串操作应用举例

串类型的定义串的表示和实现串的模式匹配算法串操作应用举例1、了解串的概念；学习要点2、熟悉串的基本运算的定义及实现方法；3、掌握基本串匹配算法。在较早的程序设计语言中，字符串（简称串）是作为输入或输出的常量（是直接量，不参加运算）出现，而非数值处理的对象基本上是字符串数据。这就要求字符串也能以变量的形式出现，能进行一系列字符串操作（运算）。目前大多数程序设计语言都支持串这种数据类型。1、串2、串长：串中所包含的字符个数。3、空串：长度为零的串，它不包含任何字符。记作“Ø”4、子串：串中任意个连续的字符组成的子序列。5、主串：包含子串的串。4.1串类型的定义基本概念：零个或多个字符组成的有限序列，即数据元素为字符的线性表。一般记为S=‘a1a2...an’，其中，S是串名，单引号括起的字符序列是串值。7、子串在主串中的位置：子串在主串中第一次出现时，子串的第一个字符在主串中的位置。6、字符在串中的位置：字符在序列中的序号。8、两个串相等：两个串的长度相等，并且各个对应位置的字符都相等时才相等。9、空格串：由一个或多个空格组成的串，其长度为串中空格字符的个数。它与空串Ø是不同的概念。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象为字符集。串的基本操作和线性表有很大差别：在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。ADTString{数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：……}ADTStringADT串的定义StrAssign(&T,chars)//串赋值初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)//串复制初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)//串销毁初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)//串判空初始条件：串S存在。操作结果：若S为空串，则返TRUE，否则返回FALSE。StrCompare(S,T)//串比较例如：StrCompare(data,state)0StrCompare(cat,case)0初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0StrLength(S)//求串长初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)//串联接例如：Concate(T,man,kind)求得T=mankind初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)//求子串初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。子串为“串”中的一个字符子序列。SubString(sub,commander,1,9)求得sub=commanderSubString(sub,commander,9,1)求得sub=r例如：SubString(sub,commander,4,3)求得sub=man;SubString(sub,student,5,0)得sub=关于参数len（子串长度）的说明：长度为0的子串为“合法”串—空串。事实上对任何串S和位置pos都有：SubString(sub,commander,4,7)得sub=manderSubString(sub,S,pos,0)得sub=；有时对len放宽到len＞StrLength(S)-pos+1，此时规定SubString(sub,S,pos,len)的值取S的第pos个字符到S的最后一个字符作为子串（长为StrLength(S)-pos+1）。Index(S,T,pos)//(子)串(位置)定位初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。假设S=abcaabcaaabc,T=bcaIndex(S,T,1)=Index(S,T,3)=Index(S,T,8)=“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。2;6;0;Replace(&S,T,V)//串替换初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。例如：假设S=abcaabcaaabca,T=bca若V=x,则经置换后得到S=axaxaax若V=bc,则经置换后得到S=abcabcaabcStrInsert(&S,pos,T)//串插入例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=character初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)//串删除初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)//串清除初始条件：串S存在。操作结果：将S清为空串。在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T)),T)T串T串iposStrLength(S)–StrLength(T)+1算法的基本思想：?=0S串在pos到StrLength(S)–StrLength(T)+1范围内寻求使下式成立的i值T串ipos+1intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的//子串，则返回第一个这样的子串在S中的位置，否则返回0if(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;}}return0;//S中不存在与T相等的子串}//Index利用最小操作子集中的操作也可实现串判空StrEmpty(S)、串替换Replace(&S,T,V)、串删除StrDelete(&S,pos,len)、串插入StrInsert(&S,pos,T)等操作。留作习题若在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2串的表示和实现串有三种机内表示方法:一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示用一组地址连续的存储单元存储串值的字符序列。该结构可用定长数组描述如下：#defineMAXSTRLEN255//可在255以内定义最大串长typedefunsignedcharSstring[MAXSTRLEN+1];//0号单元存放串的长度一、串的定长顺序存储表示对串的长度有两种表示方法:1.以下标为0的数组分量存放串的实际长度(如PASCAL语言),特点是便于进行某些操作；2.在串值后面加不计入串长的结束标记字符(如C语言采用“\0”),此时的串长为隐含值,特点是访问容易,但删除或插入麻烦。说明：串的实际长度可在预定义长度的范围内随意设定，超过预定义长度的串值则被“截断”。对超长部分实施截断操作正是串的定长顺序存储表示的弊端。为克服此弊端，惟有不限定最大串长，即动态分配串值的存储空间。以下以串联接为例进行讨论在这种存储结构表示下如何实现串的操作：假设T,S1,S2都是Sstring型变量,T为S1联结S2后所得之串,则联接运算Concat(&T,S1,S2)是将S1和S2的值分别传送到T的相应位置上,超过MAXSTRLEN的部分截断之。其运算结果可能有三种情况：1)S1[0]+S2[0]≤MAXSTRLEN2)S1[0]+S2[0]＞MAXSTRLEN3)S1[0]＝MAXSTRLEN1)S1[0]+S2[0]≤MAXSTRLEN串S1串S2串TS1[0]S2[0]S1[0]+S2[0]MAXSTRLENMAXSTRLENMAXSTRLEN2)S1[0]+S2[0]＞MAXSTRLEN串S1串S2串TS1[0]S2[0]MAXSTRLENMAXSTRLENMAXSTRLEN截去串S2被全部截去。3)S1[0]＝MAXSTRLEN串S1串S2串TS1[0]S2[0]S1[0]MAXSTRLENMAXSTRLENMAXSTRLENStatusConcat(SString&T,SStringS1,SStringS2){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;}else//截断if(S1[0]MAXSTRSIZE){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;}returnuncut;}//Concat在串的顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于字符序列的长度。二、串的堆分配存储表示堆分配存储类似于线性表的顺序存储结构，仍以一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。在C语言中是由动态分配函数malloc()和free()来管理一个称之为“堆（heap）”的自由存储区的。该存储结构类型描述如下：typedefstruct{char*ch;//若是非空串，则按串长分配存储区，//否则ch为NULLintlength;//串长度}一个串值的确定是通过串在堆中的起始位置和串的长度实现的。HString;这类串操作实现的算法为:先为新生成的串（若该串已存在,则先释放其所占空间）分配一个长度适当的存储空间，然后进行串值的复制。这种存储结构表示时的串操作仍基于“字符序列的复制”进行的。为此，串名与串值之间要建立一个对照表。0123456789HStringa,b;串名基址·ch长度·lengtha20004b20194DataStructureBook……162000＋串插入算法StatusStrInsert(Hstring&S,intpos,HstringT){//在串S的第pos个字符之前插入串TS.ch01pos-1T.lengthif(pos1||posS.length+1)returnERROR；if(T.length