数据结构Ch4串.ppt

,1,数 据 结 构 Ch.4 串,计 算 机 学 院 肖明军Email:http:/,2,Ch.4 串,字符串是一种特殊的线性表，它的每个结点仅有一个字符组成早期，串只能出现在输入输出中，以直接量形式出现，不参与运算,3,4.1 串定义及运算,基本概念串：零个或多个字符组成的有限序列记为s=“a1a2an”(n0)s为串名，引号中为串值ai：字母，数字等字符串长度：n，n=0为空串空白串：“”和“”之差别,4,4.1 串定义及运算,子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的的串称为主串特别地：空串是任意串的子串 任意串是其自身的子串串常量：只能引用，不能改变，一般用直接量表示有的语言允许对其命名，如C+；const char path=“dir/bin/appl”串变量：可读写，一般有名字,5,4.1 串定义和运算,基本运算求串长 复制 拼接 比较 子串定位 C中比较相等：长度相等，且各对应位置上字符亦 相等大小：字典序“axy”“ba”,6,4.1 串定义及运算,子串定位子串在主串中首次出现时，该子串首字符对应主串中的位置序号A=“This is a string”B=“is”序号为3 3 6其它复杂操作：均可用基本操作构成 C中有丰富的函数,7,4.2 串的存储结构,单个字符，故有特殊技巧静态存储分配的顺序串直接用定长字符向量来表示，上界预先给定#define MaxStrSize 256/用户定义 Typedef char SeqStringMaxStrSize;SeqString S;/S是可容纳255个字符的顺序串终结符：0是串终结符，放在串值尾部串长属性：若不设终结符typedef struct char chMaxStrSize;/可容纳256字符int length;SeqString,8,4.2 串的存储结构,动态存储分配的顺序串用C的malloc和free动态申请和释放向量空间，有两种形式：typedef char*string;/C中串库相当于使用此类/似定义 typedef struct char*ch;/若串非空，则按串实际长度分配，否则为NULL int length；Hstring,9,4.2 串的存储结构,链串块链存储结点大小大小为1：大小为3：存储密度dd=数据大小/结点大小,10,4.3 串的模式匹配算法（串定位运算）,朴素的定位算法（串匹配）主串：目标串（正文串Target，Text）子串：模式（串）（子串，Pattern）设T=“t0t1tn-1”P=“p0p1pm-1”（0mn）通常mn应用：文本编辑，基因匹配等,11,4.3 串的模式匹配算法,思想：对合法的位置0in-m（合法位移），依次将目标串中的子串Ti.i+m-1和模式串P0.m-1进行比较若T i.i+m-1=P0.m-1(即：“titi+1ti+m-1”=“p0p1pm-1”)则称从位置i开始的匹配成功；否则，存在某个0jm-1，使ti+jpj，则称从位置i开始的匹配失败,12,4.3 串的模式匹配算法,有效位移：若Ti.i+m-1=P0.m-1，则i称为有效 位移无效位移：若Ti.i+m-1P0.m-1，则i称为无效 位移总结：朴素的串匹配算法是对合法位移检查其是否 为有效位移 有时需在T中找到所有有效位移 通常找首次出现的有效位移,13,4.3 串的模式匹配算法,int NaiveStrMatch(SeqString T,SeqString P)/顺序串上实现 int i,j,k;int m=P.length,n=T.length;for(i=0;i=n-m;i+)/i为合法位移，检查其是否为有效位移 j=0;k=i;/j指向模式，k指向目标 while(jm/匹配失败，所有合法位移均不是有效位移,14,4.3 串的模式匹配算法,该算法是将模式串看作是在目标串上向右滑动的模板,15,4.3 串的模式匹配算法,时间：最坏情况：对所有合法位移，均要比较到模式的最后一个字符，才能确定位移无效即：O(n-m+1)m)O(n*m)/nm最坏情况发生在：目标串是 an-1b模式串是 am-1b/最后一次成功用链串表示时定位运算类似,16,4.3 串的模式匹配算法,KMP算法（不带回溯）下标仍从1算原因分析P右移1位T：ti-j+1ti ti-j+1ti-j+2 titi+1P：p1pj p1pj-1pj原因：没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快,回溯,比较点,17,4.3 模式匹配算法,T:a b b a b aP:a b a失败时有：p1=t1，p2=t2，p3t3若将P右移1位，则p1？t2，因为 p1p2，p2=t2 p1t2，故右移1位后仍失败若将P右移2位，则p1？t3，因为 p1=p3，p3t3 p1t3，故右移2位后仍失败结论：上图比较失败时应直接将P右移3位（即i=1，2，3均为无效位移），即直接比较p1和t4，比较点不回溯。Note：上述观察告诉我们，分析模式本身，就可知道潜在的有效位移,18,4.3 模式匹配算法,若使比较点不回溯（i不回溯），则当tipj（Ti-j+1.i-1=P1.j-1，即P的前j-1个字符与相应T上字符相等：ti-j+1ti-1=p1pj-1）时，P中哪个字符应与ti继续比较？因为i不动时，必定是将模式右移一段距离，所以不妨设pk（kj）应与ti 继续比较。Knuth发现，k值仅依赖于P的前j个字符的构成，与目标T无关。采用next1.m数组，用nextj=k表示当tipj时，下一 个应与ti比较的是pk若P中任何字符均无需与ti比较，则将p1与ti+1比较，此时令nextj=0。P右移最大,19,4.3 模式匹配算法,P的右移位数为：j-nextjti-j+1 ti ti-j+1ti-k+1ti p1pj p1pkpj,j-k,右移j-k,？,右移i-k+1-(i-j+1)=j-k,20,算法若已知next1m,则匹配算法如下：int KMPMatch(char T,char P)/T0和P0分别表示长度 n=T0;m=P0;/长度 i=j=1;/开始 t1p1 while(i0)j=k;/比较ti和pk:tipkelse j=1;i+;/比较ti+1和p1:ti+1p1/endif，endwhile,4.3 模式匹配算法,21,算法if(jm)/匹配成功 return i-m;/注意成功时，i和j均多加了1 else return 0;/匹配失败时间：循环主要取决于i只增不减，因为nm，所以时间为O(n),4.3 模式匹配算法,22,next数组的性质整数数组：0nextj0，则比较ti和pk，此时有:T i-k+1.i-1=P 1.k-1/长度为k-1T i-j+1.i-1=P 1.j-1/失败前部分匹配，长度为j-1P j-k+1.j-1=P1.k-1/“p1pk-1”=“pj-k+1pj-1”当tipj时，k的值应等于串P1j-1中前后缀相等的子串的长度加1T：ti-j+1 ti-k+1 ti-1 ti p1pj-k+1pj-1pj/前j-1个字符相等P右移j-k位：p1pk-1pk/前k-1个字符相等,4.3 模式匹配算法,？,23,当满足性质2的k有多个（即前后缀相等的子串有多个）时，应取最大的k值。原因：k最大，模式P右移j-k最少，不丢失任何匹配机会。例:j 1 2 3 4 T a a a a b b b b P a a a b在P1.3中，k=3最大，j-k=1位右移最少，k=2，k=1时失去匹配机会即P1.3中，前后缀相等的最大真子串为P1.2=P2.3，长度+1=3=k,4.3 模式匹配算法,P右移1位，匹配成功P右移2位、3位均失败,24,4.3 模式匹配算法,真子串不包括自身，但包括空串真子串：”aa”,“a”,“”长度：2 1 0 k：3 2 1,25,4.3 模式匹配算法,若P1j-1不存在首尾相同的字符串，或者说仅存在长度为零的相同前后缀（空串）子串，则k=1，即p1与ti继续比较特别地，若j=1（即tip1），则P中任何字符无法与ti继续比较，P右移1位，将p1和ti+1继续比较。按next定义，可取next1=0（对任何P成立）。综上所述，当ti pj时 0 j=1 P1j-1中前后缀相等的最大真子串的长度加1(包括空串),即：Maxk|1kj 且”p1pk-1”=“pj-k+1pj-1”/k=1时,为空串例：j 1 2 3 4 5 6 7 8 P a b a a b c a c nextj 0 1 1 2 2 3 1 2,nextj=,26,4.3 模式匹配算法,next数组生成（递推法）设nexti=j已知，求nexti+1(i1)由性质4告知我们，对任何模式P，总有next1=0成立，给出了递推基础next1nexti已知，且已知nexti=jP1i-1中有：“p1pj-1”=“pi-j+1pi-1”/最大真子串长度为j-1 扩充一个字符pi后，比较pjpi 若pi=pj，则P1j=Pi-j+1i即P1i中前后缀的最大真子串长度为j，故nexti+1=j+1 或者 nexti+1=nexti+1,27,4.3 模式匹配算法,若pipj，则将求next值的问题看成是模式匹配问题，即P既为主串又为模式串,将P右移，用nextj=k作下标，比较pkpi即：令jnextj，如此反复比较pipj至pi=pj（情况）或者 j=0，令nexti+1=1为止/没有一个字符与pi比较例子自己分析,？,目标串：p1pi-j+1pi-k+1pi-1 pi模式串：p1pj-k+1pj-1 pj p1pk-1 pk,28,4.3 模式匹配算法,void GetNext(char p,int next)/求模式串P的next数组（递推法）i-主串指针i=1;j=0;next1=0;m=P0;/模式串长度while(i0if(Pi=Pj)next+i=+j;/nexti+1=j+1else/pipjj=nextj;/可改进为书上一样的算法,29,4.3 模式匹配算法,时间：O(m)KMP算法的时间加上求next数组后为O(n+m)当nm时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时但当nm时，朴素匹配可能更好next数组的改进 next性质5：若tipj时，设nextj=k0，应比较tipk 若已知pk=pj，则必有ti pk，此时应使用nextk=k(k0)为下标继续比较：tipk,30,4.3 模式匹配算法,即可用下述方式节省时间：当pj=pk时，将nextj置为nextk此过程可重复！例：j 1 2 3 4 5 j P nextj nextvalj P a a a a b 1 a 0 0 nextj 0 1 2 3 4 2 a 1 0改进 nextvalj 0 0 0 0 4 3 a 2 0 pj p2 p3 p4 p5 4 a 3 0 pk p1p2 p3 p4 5 b 4 4,tip2,比较tipnext2 p2=p1,next2 next1,ti p3,tipnext3,p3=p2next3next2,31,4.3 模式匹配算法,求nextval算法与书上不一样的算法，请比较void GetNextVal(char P,int nextval)/求nextvali=1;j=0;nextval1=0;m=P0;while(i0/nextvali+1=j+1时间仍为O(m),