串的抽象数据类型的定义(精).ppt

,第四章串,4.1串的抽象数据类型的定义,4.2串的表示和实现,4.3串的模式匹配算法,4.1串的抽象数据类型的定义如下：,ADTString,数据对象：,Dai|aiCharacterSet,i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,串是有限长的字符序列，由一对双引号相括，如:astring,基本操作：,StrAssign(,SubString(sub,commander,1,9),SubString(sub,commander,9,1),求得sub=r,求得sub=commander,SubString(sub,commander,4,7)sub=?,SubString(sub,beijing,7,2)=?sub=?,SubString(student,5,0)=,起始位置和子串长度之间存在约束关系,长度为0的子串为“合法”串,Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,假设S=abcaabcaaabc,T=bca,Index(S,T,1)=2;,Index(S,T,3)=6;,Index(S,T,8)=0;,“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。,Replace(/S中不存在与T相等的子串/Index,n=StrLength(S);m=StrLength(T);i=pos;,while(i=n-m+1)/while,SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;elsereturni;,又如串的置换函数：,S串,T串,V串,V串,pos,pos,sub,i,news串,sub,=i+m,pos,n-pos+1,voidreplace(String/剩余串Concat(S,news,sub);,n=StrLength(S);m=StrLength(T);pos=1;StrAssign(news,NullStr);i=1;,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.2串的表示和实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,#defineMAXSTRLEN255/用户可在255以内定义最大串长typedefunsignedcharSStringMAXSTRLEN+1;/0号单元存放串的长度,一、串的定长顺序存储表示,按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”,串的实际长度在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”,特点:,StatusConcat(SStringS1,SStringS2,SString/Concat,例如：串的联接算法中需分三种情况处理：,T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;,if(S10+S20=MAXSTRLEN)/未截断,elseif(S100)/T非空，则为S重新分配空间并插入T/StrInsert_HSq,S.ch=newcharslen+tlen;/为S重新分配空间for(i=0,k=0;ipos-1;i+)S.chk+=S1.chi;/保留插入位置之前的子串for(i=0;itlen;i+)S.chk+=T.chi;/插入Tfor(i=pos-1;i0)n=StrLength(S);m=StrLength(T);i=pos;while(im,T串,一、简单算法,intIndex(SStringS,SStringT,intpos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。/其中，T非空，1posStrLength(S)。i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。,二、首尾匹配算法,intIndex_FL(SStringS,SStringT,intpos)sLength=S0;tLength=T0;i=pos;patStartChar=T1;patEndChar=TtLength;while(i=sLengthtLength+1)if(Si!=patStartChar)+i;/重新查找匹配起始点elseif(Si+tLength-1!=patEndChar)+i;/模式串的“尾字符”不匹配elsereturn0;,检查中间字符的匹配情况,k=1;j=2;while(jtLength/重新开始下一次的匹配检测,KMP算法的时间复杂度可以达到O(m+n),当SiTj时，已经得到的结果:Si-j+1.i-1=T1.j-1若已知T1.k-1=Tj-k+1.j-1则有Si-k+1.i-1=T1.k-1,三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法,定义：模式串的next函数,intIndex_KMP(SStringS,SStringT,intpos)/1posStrLength(S)i=pos;j=1;while(iT0)returni-T0;/匹配成功elsereturn0;/Index_KMP,这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,求next函数值的过程是一个递推过程，分析如下:,已知：next1=0；,假设：nextj=k；又Tj=Tk,则：nextj+1=k+1,若：TjTk则需往前回溯，检查Tj=T？,voidget_next(SStringT,int/get_next,还有一种特殊情况需要考虑：例如：S=aaabaaaabT=aaaabnextj=01234,nextvalj=00004,voidget_nextval(SStringT,int/get_nextval,1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆存储结