《New数据结构》PPT课件.pptVIP

,第四章串,4.1串的抽象数据类型的定义,4.2串的表示和实现,4.3串的模式匹配算法,4.1串的抽象数据类型的定义1、名词术语串(String)(字符串):由零个或多个字符组成的有限序列。串的长度串中字符的数目n。,例如:S=a1a2a3an，其中S是串名，单引号(双引号)括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；,子串:串中任意个连续的字符组成的子序列称为该串的子串。主串:包含子串的串。子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=IloveyouB=loveB是A的子串，A为主串。B在A中的序号为3，注意空格也是字符。,空串(Nullstring)：零个字符的串，它的长度为零。空串是任意串的子串，任意串是其自身的子串。空格串(blankstring)：由一个或多个空格组成的串。注意：空串和空格串的不同。例如:“”表示长度为1的空格串;“”长度为0的空串。,两个串的比较相等：长度相等，对应位置的字符相等。大小：字符根据ASCII码字符串：从起始位置开始，比较对应位置的字符不相等则比较结果即为字符串比较结果如果相等则继续比较下一个,通常在程序中使用的串可分为两种：串常量和串变量。串常量在程序中只能被引用，不能改变其值，即只能读不能写。通常串常量是由直接量来表示。例如:printf(overflow);有的语言允许对串常量命名，以使程序易读、易写。如C+中，可定义constcharcity=Tianjin;city是一个串常量，对它只能读不能写。串变量其取值是可以改变的。,串的抽象数据类型的定义如下：,ADTString,数据对象：,Dai|aiCharacterSet,i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,基本操作：,StrAssign(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串,pos,pos,sub,i,news串,sub,S串,继续置换,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。,在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.2串的表示和实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,#defineMAXSTRLEN255/用户可在255以内定义最大串长typedefunsignedcharSstringMAXSTRLEN+1;,一、串的定长顺序存储表示,按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”。,特点:,StatusConcat(SStringS1,SStringS2,SString/Concat,例如：串的联接算法中需分三种情况处理：,T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;,if(S10+S200；若S=T，则返回值=0；/若ST，则返回值0。for(i=0;iS.length,StatusConcat(HString/Concat,StatusSubString(HString/SubString,Sub.ch=(char*)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2;Sub.length=len;,三、串的块链存储表示,也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度=,数据元素所占存储位,实际分配的存储位,#defineCHUNKSIZE80/可由用户定义的块大小typedefstructChunk/结点结构charchCUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构Chunk*head,*tail;/串的头和尾指针intcurlen;/串的当前长度LString;,例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。,4.3串的模式匹配算法,初始条件：串S和T存在，T是非空串，1posStrLength(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非空，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/重新开始下一次的匹配检测,现在讨论一般情况。假设主串：s:s(1)s(2)s(3)s(n);模式串：p:p(1)p(2)p(3).p(m)现在我们假设主串第i个字符与模式串的第j(j=m)个字符失配后，主串第i个字符与模式串的第k(kk满足下列关系式：(kj),p(1)p(2)p(3).p(k-1)=s(i-k+1)s(i-k+2)s(i-1)即：主串：S(1)s(i-k+1)s(i-k+2)s(i-1)s(i).|(相配)|?(有待比较)匹配串：p(1)p(2)p(k-1)p(k),三、KMP算法(3),现在我们把前面总结的关系综合一下，有：S(1)s(i-j+1)s(i-k+1)s(i-k+2)s(i-1)s(i)|(相配)|(失配)P(1)p(j-k+1)p(j-k+2).p(j-1)p(j)|(相配)|?(有待比较)P(1)p(2).p(k-1)p(k)由上，我们得到关系：p(1)p(2)p(3).p(k-1)=s(j-k+1)s(j-k+2)s(j-1),定义：模式串的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(SString/get_next,还有一种特殊情况需要考虑：例如：S=aaabaaabaaabaaabaaabT=aaaab,nextvalj=00004,nextj=01234,voidget_nextval(SString/get_n