数据结构-第四章-串PPT课件

.,1,第四章串,学习要点掌握串的基本操作以及串操作在不同存储结构下的实现。理解串的模式匹配算法。,.,2,4.1串类型的定义,1串的定义串(string)是由零个或多个字符组成的有限序列，一般记作S=“a1a2a3an”，其中S为串的名字，用双引号括起来的字符序列是串值，但两边的双引号不算作串值，不包含在串中。ai(1in)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2空串长度为零的串称为空串(EmptyString)，它不包含任何字符，记为s=“”。通常将仅由一个或多个空格组成的串称为空白串(BlankString)。注意：空串和空白串的不同，例如“”和“”分别表示长度为1的空白串和长度为0的空串。,一、串和基本概念,.,3,3子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如,串s1=“abcd”，s2=“fabcdef”，则s1为s2的子串，s2相对于s1为主串。再如,串s1=“is”，s2=“Thisisastring”，则s1为s2的子串，s2相对于s1为主串。s1在s2中出现了两次，其中首次出现所对应的主串位置是3。因此，称s1在s2中的序号为3。另外:空串是任意串的子串，任意串是其自身的子串。,.,4,二、串的基本操作,1.串赋值StrAssign(s,t)表示将字符序列t赋给名为s串。2.求子串SubStr(sub,s,i,len)用sub返回串s的第i个字符起长度为len的子串。3.求串长度StrLength(s)求s串的长度，即返回串s中元素的个数。4.串联接StrConcat(s,t)表示将s串和t串联接起来，使t串接入s串的后面。5.串的比较StrCmp(s,t)例如：result=StrCmp(“baker”,”Baker”)result0result=StrCmp(“12”,”12”);result=0result=StrCmp(“Joe”,”Joseph”);resultMAXLEN-1)printf(“长度不够!n);elsefor(i=0;islen|islen|lenMAXLEN-1)printf(Error!n);elsefor(k=slen;k=i-1;k-)stlen+k=sk;for(k=0;kslen)printf(Error!n);elsefor(k=i+j-1;sk!=0;k+)sk-j=sk;sk-j=0;,.,14,思考：假设串采用顺序存储，设计以下算法。（1）把串R中所有字符按反序存放在R。（2）从R中删除其值等于ch的所有字符。,.,15,一堆分配存储堆式存储结构仍然用一组地址连续的存储单元存放串值，但它们的存储空间是在程序执行的过程中动态分配而得的。堆存储结构的基本思想是：系统中将一个容量很大、地址连续的存储空间作为串值的可利用空间，称为堆空间。每当建立一个新串时，系统就从这个可利用空间中分配一个大小和串长相同的空间存储新串的串值。系统根据每个串的长度，动态的为每个串在堆空间里申请相应大小的存储区域，这个串顺序存储在所申请的存储区域中，当操作过程中若原空间不够了，可以根据串的实际长度重新申请，拷贝原串值后再释放原空间。,4.3串的堆式存储结构,.,16,设堆空间：charstoreMAXSIZE;自由区指针：intfree;类型定义：typedefstructintstraddr;intlength;HString其串操作仍是基于“字符序列的复制”进行的,.,17,1.串赋值,voidStrAssign(HString*s1,HString*s2)inti=0,len=s2-length;if(lenMAXSIZE)print(“错误，不能赋值！”)elsefor(i=0;istraddr=free;s1-length=len;free=free+len;,.,18,2.求子串,voidSubStr(HString*sub,HStrings,inti,intlen)if(lens.length-i+1)print(“参数错误，不能求子串！”)elsesub-straddr=s.straddr+i-1;sub-length=len;,.,19,HeapString*Concat(HeapString*S1,HeapString*S2)HeapString*T;intn;n=S1-length+S2-length;if(!(T-straddr=(char*)malloc(n*sizeof(char)printf(ERROR!);elsestrcpy(T-straddr,S1-straddr);strcat(T-straddr,S2-straddr);T-length=n;free(S1-straddr);free(S2-straddr);return(T);,可以将整个内存看作一个堆空间，需要时，从内存分配串长大小的空间。例：实现两个串的连接,typedefstructchar*straddr;intlength;HeapString,.,20,4.4串的块链存储表示,一结点大小为1的链式存储和前面介绍到的单链表一样，每个结点为一个字符，链表也可以带头结点。S=abcde的存储结构具体形式见下图。,S串的链式存储示意图,.,21,二结点大小为K的链式存储在单链表中，如果每个结点仅存放一个字符，那么结点的指针域会很多，造成系统空间浪费。因此采用了一种每个结点可存放多个字符的结构以提高链表的存储密度。这种结构称为块链。,head,当链表中的最后一个节点未被串值占满，通常补上0或其他的非串值字符。,结点大小为3的块链,.,22,串的块链式存储形式定义:,#defineblocksize10/*用户自定义块的大小*/typedefstructBlocknodecharchblocksize;structBlocknode*next;BlockNode;typedefstructBlockNode*head;/*串的头指针*/BlockNode*tail;/*串的尾指针*/intcurlen;/*串的当前长度*/LString;,.,23,LString*concat(LString*s1，LString*s2)BlockNode*p，*q;p=s1-tail;q=s2-head;p-next=q;s1-tail=s2-tail;s1-curlen+=s2-curlen;return(s1);,例：实现两个串的连接（块链大小为1）,注：若块链大小超过1，则在串连接时，还应处理最后一个串中无效字符。,.,24,串的链式存储结构的特性：串的链接存储结构有时称为链串。链串的存储形式与一般的链表类似，是将存储区分成许多结点，每个结点有一个存放字符的数据域和一个存放指向下一个结点的指针域。链串中的一个存储结点可以存储1个或多个字符，通常将链串中每个存储结点所存储的字符个数称为结点大小。串值的存储密度=串值所占的存储位/实际分配的存储位存储密度小，运算处理方便，如结点大小为1时，各种操作同单链表，但存储空间占用量大；存储密度大时，运算处理不方便。,.,25,一模式匹配子串的定位运算通常称为串的模式匹配，是串处理中最重要的运算之一。设串S=“a1a2an”，串T=“b1b2bm”(mn)，子串定位是要在主串S中找出一个与子串T相同的子串。通常把主串S称为目标串，把子串T称为模式串，把从目标串S中查找模式为T的子串的过程称为“模式匹配”。匹配有两种结果出现：若S中有模式为T的子串，就返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可，这种情况称为匹配成功；若S中无模式为T的子串，返回值为-1，称为匹配失败。串匹配的算法很多，这里我们先讨论一种最简单的称为朴素的串匹配算法。,4.2.3串的模式匹配,.,26,基本思想：从主串S的第p个字符起和模式串T的第一个字符比较，若相等，则继续比较；否则从S中的下一个字符起，再重新和T的第一个字符开始比较。如果确能在S中找到T则返回模式串T在主串S中第p个字符后第一次出现的位置。此时称为匹配成功，否则匹配失败。,模式串T=ABAC与目标串S的匹配过程,1朴素的模式匹配算法,演示,.,27,匹配过程:,第一趟匹配,第三趟匹配,第四趟匹配,第五趟匹配,第六趟匹配,第二趟匹配,.,28,朴素的模式匹配算法,intStrIndex(char*S,char*T,intp)inti=p-1,j=0;/i,j指示当前参与比较的字符下标intSlen=StrLength(S),Tlen=StrLength(T);while(istringj)+i;+j;elsej=nextj;if(j=tlen)returni-tlen;elsereturn-1;,KMP算法,nextj表示当匹配失败时，j右滑的位置，即在下一趟匹配时，从目标串s的第i个字符与模式串t的第j个字符开始进行比较。,/为了便于理解，我们假设数组下标从1开始,.,38,不妨设位置为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个字符。而本趟匹配失败是在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),现在问题的关键是串t“滑动”到哪个位置上？,.,39,i,j,t1t2tj-1=si-j+1si-j+2si-1,i,k,t1t2tk-1=si-k+1si-k+2si-1,t1t2tk-1=tj-k+1tj-k+2tj-1,.,40,结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4.4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。“滑动”的位置与主串没有关系。,怎样确定需要滑动的位置呢？,.,41,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个字符，即用t1和si+1继续比较。,.,42,next函数定义如下：,0当j=1maxk|1kj且t1t2tk-1=tj-k+1tj-k+2tj-1若不存在上面的k，且t1tj0若不存在上面的k，且t1=tj,nextj=,设有模式串：t=abcaababc，则它的next函数值为：,如何求next函数？由以上讨论知，next函数值仅取决于模式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。由定义知：next1=0(4.5)设nextj=k，即有：t1t2tk-1=tj-k+1tj-k+2tj-1(4.6)nextj+1=?可能有两种情况：第一种情况：若tktj则表明在模式串中t1t2tk=tj-k+1tj-k+2tj(4.7)这就是说nextj+1=k+1，即nextj+1=nextj+1(4.8)第二种情况：若tktj则表明在模式串中t1t2tktj-k+1tj-k+2tj,.,44,此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tktj时应将模式向右滑动，使得第nextk个字符和“主串”中的第j个字符相比较。若nextk=k，且tktj，则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得t1t2tk=tj-k+1tj-k+2tj(4.10)因此：nextj+1=nextk+1(4.11)同理若tktj，则将模式继续向右滑动至使第nextk个字符和tj对齐，依此类推，直至tj和模式中的某个字符匹配成功或者不存在任何k(1kkj)满足(4.10)，此时若t1tj+1，则有：nextj+1=1(4.12)否则若t1=tj+1，则有：nextj+1=0(4.13),.,45,voidGetNext(char*t,intnext)intj=1,k=0,tlen=StrLength(t);next1=0;while(jtlen)if(k=0|tj=tk)+j;+k;nextj=k;elsek=nextk;,求滑动值算法（相当于自己与自己匹配）,/初始化,.,46,由此可见，next算法的时间复杂度是O(m)；KMP算法的时间复杂度是O(n*m)，但在一般情况下，实际的执行时间是O(n+m)。,.,47,4.5串操作应用,一、文本编辑文本编辑程序是一个面向用户的系统服务程序，以用于源程序的输