- 323.50 KB
- 2022-04-29 14:47:36 发布
- 1、本文档共5页，可阅读全部内容。
- 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
- 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
- 文档侵权举报电话：19940600175。
'第四章串
4.1串的抽象数据类型的定义4.2串的表示和实现4.3串的模式匹配算法
4.1串的抽象数据类型的定义如下：ADTString{数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{|ai-1,ai∈D,i=2,...,n}串是有限长的字符序列，由一对单引号相括，如:astring
基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(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)ClearString(&S)}ADTString
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)初始条件：串S和T存在。操作结果：若ST，则返回值0； 若ST，则返回值0；若ST，则返回值0。例如：StrCompare(data,state)<0StrCompare(cat,case)>0
StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数， 称为串的长度。
Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例如：Concate(T,man,kind)求得T=mankind
SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用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=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串
Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同 的子串,则返回它在主串S中第pos个 字符之后第一次出现的位置； 否则函数值为0。
假设S=abcaabcaaabc,T=bcaIndex(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=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和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=character
StrDelete(&S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。
ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。
对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：
在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。
例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T)),T)?0S串T串T串iposn-m+1算法的基本思想为：
intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0if(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;//S中不存在与T相等的子串}//Index
又如串的置换函数：S串T串V串V串pospossubinews串sub
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。
在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.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]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{}//完整子串returnOK;}//SubString……
Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;
三、串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存储密度=数据元素所占存储位实际分配的存储位
#defineCHUNKSIZE80//可由用户定义的块大小typedefstructChunk{//结点结构charch[CUNKSIZE];structChunk*next;}Chunk;typedefstruct{//串的链表结构Chunk*head,*tail;//串的头和尾指针intcurlen;//串的当前长度}LString;
例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。
这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。4.3串的模式匹配算法
初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)
下面讨论以定长顺序结构表示串时的几种算法。一、简单算法二、首尾匹配算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法
intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。若不存在，//则函数值为0。其中，T非空，1≤pos≤StrLength(S)。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;}//Index一、简单算法
先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。二、首尾匹配算法
intIndex_FL(SStringS,SStringT,intpos){sLength=S[0];tLength=T[0];i=pos;patStartChar=T[1];patEndChar=T[tLength];while(i<=sLength–tLength+1){if(S[i]!=patStartChar)++i;//重新查找匹配起始点elseif(S[i+tLength-1]!=patEndChar)++i;//模式串的“尾字符”不匹配else{}}return0;}//检查中间字符的匹配情况
k=1;j=2;while(jT[j]时，已经得到的结果：S[i-j+1..i-1]==T[1..j-1]若已知T[1..k-1]==T[j-k+1..j-1]则有S[i-k+1..i-1]==T[1..k-1]三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法
定义：模式串的next函数
intIndex_KMP(SStringS,SStringT,intpos){//1≤pos≤StrLength(S)i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j=0||S[i]==T[j]){++i;++j;}//继续比较后继字符elsej=next[j];//模式串向右移动}if(j>T[0])returni-T[0];//匹配成功elsereturn0;}//Index_KMP
这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串求next函数值的过程是一个递推过程，分析如下:已知：next[1]=0；假设：next[j]=k；又T[j]=T[k]则：next[j+1]=k+1若：T[j]T[k]则需往前回朔，检查T[j]=T[？]
voidget_next(SString&T,int&next[]){//求模式串T的next函数值并存入数组nexti=1;next[1]=0;j=0;while(i
您可能关注的文档
微信/支付宝扫码支付下载-
关注微信公众号售出明细实时看