数据结构课件(串).ppt

数据结构第四章串,2019年11月22日星期五,第四章串,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。,4.1串的定义,是由零个或多个字符组成的有限序列，一般记为s=“a1a2an”(n0)其中，s是串名，用单引号（也可以是用双引号括起来的）括起来的字符序列是串的值。ai可以是字母、数字或其他字符；串中字符的个数n成为串的长度。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。注意区分空串与空格串的区别。,4.1串的定义,串的逻辑结构和线性表的区别:,1.串的数据对象约束为字符集。2.线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。对于串可以定义以下运算：1.置串为一个空串；2.判断一个串是否为空串3.求一个串的长度；4.将两个串拼接在一起构成一个新串；5.在一个串中，求从串的第i个字符开始连续j个字符所构成的子串；6.如果串S2是S1的子串，则可求串S2在串S1中第一次出现的位置。,4.1串的定义,串的抽象数据类型的定义,ADTString数据对象：Dai|aiCharacterSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n基本操作：StrAssign(m=StrLength(T);i=pos;while(iT,则返回值0;若S=T返回值=0，若ST返回值0;for(i=0;iS.length,三、串的块链存储表示,三、串的块链存储表示,类C语言描述,#defineCHUNKSIZE80/可由用户定义的块大小typedefstructchunk/结点结构charchCUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构Chunk*head,*tail;/串的头和尾指针intcurlen;/串的当前长度LString;,4.3串的模式匹配算法,模式匹配,模式匹配：子串（又称模式串）在主串中的定位操作。这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)初始条件：串S和T存在,T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,4.3串的模式匹配算法,1.简单算法,设主串S=“ababcabcacbab”,模式串T=“abcac”。则普通算法的匹配过程如下：,4.3串的模式匹配算法,1.简单算法,intIndex(SStringS,SStringT,intpos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。其中，T非空，1posStrLength(S)。i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,4.3串的模式匹配算法,2.首尾匹配算法,先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。abcba主串:ababcabcaaabcbaabc模式串:aa(2次)aaa(1+2次)aaabba(2+4次)aaaa(2+2次)aa(2次)abcba(5次),上述两种算法的时间复杂度为O(mn),4.3串的模式匹配算法,3、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法,设主串S=“ababcabcacbab”,模式串T=“abcac”。则普通算法的匹配过程如下：,改进后的匹配情况：,改进后的模式匹配算法,KMP算法,希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk对准si继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：t1t2tk-1=si-k+1si-k+2si-1(4.1)(4.1)式左边是tk前面的k-1个字符，右边是si前面的k-1个字符。,改进后的模式匹配算法,KMP算法,而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：t1t2tj-1=si-j+1si-j+2si-1(4.2)因为kj，所以有：tj-k+1tj-k+2tj-1=si-k+1si-k+2si-1(4.3)(4.3)式左边是tj前面的k-1个字符，右边是si前面的k-1个字符，通过(4.1)和(4.3)得到关系：t1t2tk-1=tj-k+1tj-k+2tj-1(4.4)结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。,改进后的模式匹配算法,（2）next函数,模式中的每一个tj都对应一个k值，由(4.4)式可知，这个k值仅依赖与模式t本身字符序列的构成，而与主串s无关。我们用nextj表示tj对应的k值，根据以上分析，next函数有如下性质：nextj是一个整数，且0nextjj为了使t的右移不丢失任何匹配成功的可能，当存在多个满足(4.4)式的k值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-nextj个。如果在tj前不存在满足(4.4)式的子串，此时若t1tj，则k=1;若t1=tj，则k=0;这时“滑动”的最远，为j-1个字符即用t1和sj+1继续比较。,改进后的模式匹配算法,（2）next函数,next函数定义如下：,设有模式串：t=abaabcac，则它的next函数值为：,改进后的模式匹配算法,(3)KMP算法,在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中si=tj，则i和j分别增，若sitj匹配失败后，则i不变，j退到nextj位置再比较，若相等，则指针各自增，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增继续进行匹配;另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增，表明从主串的下一个字符起和模式重新开始匹配。,改进后的模式匹配算法,(3)KMP算法,在假设已有next函数情况下，KMP算法如下：intStrIndex_KMP(char*s,char*t,intpos)/*从串s的第pos个字符开始找首次与串t相等的子串*/inti=pos,j=1,slen,tlen;while(it0)returni-t0;/*匹配成功，返回存储位置*/elsereturn1;/StrIndex_KMP,voidget_next(SStringT,int*next)/算法4.7inti=1;next1=0;intj=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;elsej=nextj;,Next函数的缺陷,根据前面定义的Next函数对模式串aaaab和主串aaabaaaab,改进后的模式匹配算法,（2）next函数,nextval函数定义如下：,设有模式串：t=abcaababc，则它的next函数值为：,第一趟第二趟第三趟第四趟,4.4串应用文本编辑软件,文本编辑软件：,基本操作：串的输入、修改、删除（行或子串）、查找、输出；早期多采用静态存储结构，适应性差；现在多采用链式存储结构：按屏幕宽度每个结点设计成存放80个字符;每行的结点（任意多个）构成一个结点链（块链）;头结点中存放行号和该行字符数;各行（任意多个）的头结点自上而下构成链。需要：页表、行表等,4.4串应用文本编辑软件,链式存储结构：,4.4串应用文本编辑软件,链式存储结构（类型定义）：,typedefstructnodechardata80;structnode*next;nodetype;typedefstructhnodeintnum;intlen;structhnode*hnext;nodetype*next;headtype;,4.4串应用文本编辑软件,代码段,main()floata,b,max;scan