数据结构电子课件教案-第4章 串.ppt

1,第四章串,2,主要内容,4.1串的定义和操作（自学）4.2串的表示和实现定长顺序存储表示堆分配存储表示块链存储表示4.3串的模式匹配算法4.4串的应用（自学）,3,4.1串的定义的操作,自学提示从本质上讲，串就是一个线性表。区别如下：与一般线性表的区别在于：串这种线性表的数据元素是“字符”一般线性表的操作是以单个元素为处理对象，而串的操作一般是以串整体或串的一个子集为处理对象。即串的操作具有集合性特点。,4,注意串的几个基本操作函数：串赋值StrAssign串复制Strcopy、串比较StrCompare求串长StrLength、串联接Concat求子串SubString这六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。,5,对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。要注意不同语言中串处理函数命名的不同，如C语言函数库中提供下列串处理函数,gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；,串的存储结构,顺序串：用数组来存储串中的字符序列。,特殊线性表串,如何改造数组实现串的顺序存储？,（1）非压缩形式。,串的存储结构,顺序串：用数组来存储串中的字符序列。,特殊线性表串,如何改造数组实现串的顺序存储？,（1）非压缩形式。,（2）压缩形式。,启示：时空权衡！,方案1：用一个变量来表示串的实际长度。,特殊线性表串,如何表示串的长度？,串的存储结构,特殊线性表串,方案1：用一个变量来表示串的实际长度。,串的存储结构,如何表示串的长度？,方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。,特殊线性表串,方案3：用数组的0号单元存放串的长度，从1号单元开始存放串值。,串的存储结构,如何表示串的长度？,方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。,方案1：用一个变量来表示串的实际长度。,链接串：用链接存储结构来存储串。,（1）非压缩形式,特殊线性表串,串的存储结构,如何改造链表实现串的链接存储？,链接串：用链接存储结构来存储串。,（1）非压缩形式,（2）压缩形式,特殊线性表串,串的存储结构,如何改造链表实现串的链接存储？,启示：时空权衡！,13,4.3串的模式匹配,串的模式匹配是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项=查找过程就是一个模式匹配过程,初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0,回忆一下串匹配(查找)的定义:,INDEX(S,T,pos),定义：在一个主串中查找一个子串的操作就称为串的模式匹配,14,4.3串的模式匹配,目标（串）和模式（串）,在串匹配中，一般将主串称为目标（串），子串称为模式（串）。假设S为目标串，P为模式串，且不妨设：S=s1s2sn-1snP=t1t2tm-1tm(0mn),15,4.3串的模式匹配,串匹配串匹配就是对于合法的位置（又称合法的位移）1in-m+1，依次将目标串中的子串“SiSi+1Si+m-1”和模式串“P1P2Pm”进行比较：若“SiSi+1Si+m-1”“P1P2Pm”，则称从位置i开始的匹配成功，或称i为有效位移。若“SiSi+1Si+m-1”“P1P2Pm”，则称从位置i开始的匹配失败，或称i为无效位移。因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。,注意：有些应用中要求求出P在S中所有出现的有效位移。,16,4.3串的模式匹配,讨论以定长顺序结构表示串时的几种算法串的定长顺序存储表示:#definemaxstrlen255unsignedcharsstringmaxstrlen+1;/0号单元存放串的实际长度利用基本串函数实现匹配算法简单匹配算法KMP(D.E.Knuth,J.H.Morris,V.R.Pratt)算法,17,利用基本串函数实现匹配算法,intIndex(StringS,StringT,intpos)/T为非空串。若主串S中第pos个字符之后存在与T相等的子串，/则返回第一个这样的子串在S中的位置，否则返回-1if(pos0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)i+;elsereturni;/while/ifreturn-1;/S中不存在与T相等的子串,18,主串Sababcabcacbab模式串P=abcac,简单匹配算法,intIndex(SStringS,SStringT,intpos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，/则函数值为0。其中，T非空，1posStrLength(S)。i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,19,主串Sababcabcacbab,模式串P=abcac,算法的时间复杂性:T(n)=?,T(n)=O(m*n),20,KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法,简单模式匹配算法的问题,回溯,21,S=ababcabcacbab,P=abcac,第一趟匹配结果：i=3S1=P1；S2=P2；S3P3因P2P1；可以肯定S2P1第二趟比较没有必要,第三趟匹配结果：i=7S3=P1；S4=P2；S5=P3；s6=P4因P2P1；可以肯定S4P1第四趟比较没有必要因P3P1；可以肯定S5P1第五趟比较没有必要因P4=P1；可以肯定S6=P1第六趟比较也没有必要,可以直接从S7与P2开始比较,22,S=ababcabcacbab,P=abcac,在第二趟匹配的基础上，第三趟匹配时，i=7,源串不必回溯；模式串也不是从j=1开始，而是向右滑动一个字符的距离；即S7与P2开始比较,一般情况如何？,23,设S=“s1s2sn-1snP=“p1p2pm-1pm(0mn),讨论一般情况,KMP算法需要解决的问题,当匹配不成功(SiPj)时，模式串应该向右滑动多远的距离？即主串的第i个字符(i不回溯)应该与模式串的哪一个字符比较？,假设此时主串的第i个字符应该与模式串的第k(kj)个字符比较，则必有下面的关系成立,24,已经得到的部分匹配结果,因此,前缀串子串,前缀串的子串,25,如何求一个串的前缀子串？,在模式匹配中，k的值只与上一趟匹配时失配时模式串的位置j有关。令nextj=k,称nextj为模式串的前缀，前缀串的长度nextj-1用nextj表示当模式串中第j个字符与主串中第i个字符失配时，下一次模式串中第nextj个字符与主串的第i个字符比较,例1：,26,KMP模式匹配算法,intIndex_KMP(SStringS,SStringT,intpos)/KMP算法：利用模式串T的前缀串nextj,i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,/简单模式匹配关键代码while(i=S0,27,如何求模式串的nextj值？,这实际上也是一个模式串自已与自己匹配的过程，主串和模式串是同一个串=使用KMP算法,求next函数值的过程是一个递推过程，分析如下:,已知：next1=0；,假设：nextj=k；,则：nextj+1=k+1,(2)若PkPj则:需往前回朔，检查Pj=