严蔚敏数据结构第四章PPT课件

.,1,第四章串,.,2,4.1串的抽象数据类型的定义,4.2串的表示和实现,4.3串的模式匹配算法,.,3,4.1串的抽象数据类型的定义如下：,ADTString,数据对象：,Dai|aiCharacterSet,i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,串是有限长的字符序列，由一对双引号相括，如:astring,.,4,基本操作：,StrAssign(,SubString(sub,commander,1,9),SubString(sub,commander,9,1),求得sub=r,求得sub=commander,.,15,SubString(sub,commander,4,7)sub=?,SubString(sub,beijing,7,2)=?sub=?,SubString(student,5,0)=,起始位置和子串长度之间存在约束关系,长度为0的子串为“合法”串,.,16,Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,.,17,假设S=abcaabcaaabc,T=bca,Index(S,T,1)=2;,Index(S,T,3)=6;,Index(S,T,8)=0;,“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。,.,18,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;,.,27,又如串的置换函数：,S串,T串,V串,V串,pos,pos,sub,i,news串,sub,=i+m,pos,n-pos+1,.,28,voidreplace(String/剩余串Concat(S,news,sub);,n=StrLength(S);m=StrLength(T);pos=1;StrAssign(news,NullStr);i=1;,.,29,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。,.,30,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.2串的表示和实现,.,31,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,.,32,#defineMAXSTRLEN255/用户可在255以内定义最大串长typedefunsignedcharSstringMAXSTRLEN+1;/0号单元存放串的长度,一、串的定长顺序存储表示,.,33,按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”,特点:,.,34,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,.,41,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;i0)n=StrLength(S);m=StrLength(T);i=pos;while(im,T串,一、简单算法,.,50,intIndex(SStringS,SStringT,intpos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。/其中，T非空，1posStrLength(S)。i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,.,51,先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。,二、首尾匹配算法,.,52,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;,检查中间字符的匹配情况,.,53,k=1;j=2;while(jtLength/重新开始下一次的匹配检测,.,54,KMP算法的时间复杂度可以达到O(m+n),当SiTj时，假设此时应与模式中第k（kj）个字符继续比较，则模式中前k-1个字符的子串必须满足：T1.k-1=Si-k+1.i-1已经得到的结果:Si-j+1.i-1=T1.j-1在上式中取任意多个从右到左的子串仍然相等，取k-1个，有Si-k+1.i-1=Tj-k+1.j-1则有Tj-k+1.j-1=T1.k-1,三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法,.,55,能向右滑动多远？,显然应有：sik+1si1=t1tk1。,而由前次的比较应有：sik+1si1=tjk+1tj1。,于是得到这样的结果：t1tk1=tjk+1tj1。,.,56,一个模式的next(j),j：123456789模式：abaabaaabnextj：,0,没有相应的k，next(j)为1。,1,1,k=2，下次从第二个元素开始比较。,2,2,依次以此类推可得其余元素的next(j)。,3,4,5,2,.,57,滑动不会造成遗漏,引理1：正文S和模式P比较时，若sipj，则S没有以sik0+1(nextj1时，假设结论不成立，即存在这样的k0，那么有p1p2pk01=sik0+1sik0+2si1。从而有，p1p2pk01=pjk0+1pjk0+2pj1(7.3)由假设有nextjk0i。这与nextj是满足(7.3)式的最大值相矛盾；所以结论成立。,.,58,定义：模式串的next函数,.,59,intIndex_KMP(SStringS,SStringT,intpos)/1posStrLength(S)i=pos;j=1;while(iT0)returni-T0;/匹配成功elsereturn0;/Index_KMP,.,60,这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,求next函数值的过程是一个递推过程，分析如下:,已知：next1=0；,假设：nextj=k；又Tj=Tk,则：nextj+1=k+1,若：TjTk则需往前回朔，检查Tj=T？,.,61,next(j)的计算,如何来计算模式P的next(j)?首先，我们由定义可知next(1)=0；其次，显然有next(2)=1；现在我们来考虑next(j+1)。由next(j)=k可知模式中有：p1pk1=pjk+1pj1。现在存在两种情况：pk=pj或者pkpj。如果pk=pj，于是p1pk1pk=pjk+1pj1pj。从而有next(j+1)=next(j)+1。,.,62,next(j)的计算,如果pkpj，显然next(j+1)next(j)。这实际是在将p1pk1pk与pjk+1pj1pj相匹配时，出现了pj与pk失佩。,下一步拿p1pk1pk中哪个元素和pj相比较呢？,滑动多远？,向右滑动next(k)，即比较pnext(k)和pj。,若这时有pnext(k)=pj，则next(j+1)=next(k)+1；若这时有pnext(k)pj，则再重复以上的做法，直至k=1。,.,63,next(j)的计算,intnextMaxStrLen;voidget_next(SStringP)j=1;next1=0;k=0；while(j=P0)if(k=0Pk=Pj)+k;+j;nextj=k;/next(j+1)=k+1elsek=nextk;,初始化,.,64,一个模式的next(j),j：123456789模式：abaabaaabnextj：,初始化：j=1;next1=0;k=0；,1,0,第一趟：j=1;k=0；,k=0+k;+j;nextj=k;即，k=1;j=2;next(2)=1。,第二趟：j=2;k=1,P1P2k=nextk=0,k=0+k;+j;nextj=k;即，k=1;j=3;next(3)=1。,1,第三趟：j=3;k=1。,P1=P3+k;+j;nextj=k;即，k=2;j=4;next(4)=2。,2,第四趟：j=4;k=2。,P2P4k=next2=1,P1=P4/k=1+k;+j;nextj=k;即，k=2;j=5;next(5)=2。,2,第五趟：j=5;k=2。,P2=P5+k;+j;nextj=k;即，k=3;j=6;next(6)=3。,3,第六趟：j=6;k=3。,P3=P6+k;+j;nextj=k;即，k=4;j=7;next(7)=4。,4,第七趟：j=7;k=4。,P4=P7+k;+j;nextj=k;即，k=5;j=8;next(8)=5。,5,第八趟：j=8;k=5。,P5P8k=nextk=next5=2。,P2P8k=nextk=next2=1。,P1=P8/k=1+k;+j;nextj=k;即，k=2;j=9;next(9)=2,2,至此循环结束，求出了所有元素的next(j)。,.,65,还有一种特殊情况需要考虑：例如：S=aaabaaabaaabaaabaaabT=aaaabnextj=01234,nextvalj=00004,.,66,voidget_nextval(SString/ge