数据结构-第四章ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构课程的内容,1,数据结构课程的内容1,第4章 串（String）,4.2,串的表示和实现,4.3,串的模式匹配算法,1. 定义,2. 逻辑结构,3. 存储结构,4. 运算规则,5. 实现方式,4.1,串类型的定义,2,第4章 串（String）4.2 串的表示和实现1.,串,即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,记为：,s = a,1, a,2, . , a,n, (n0 ),串名,串值（用 括起来）,隐含结束符0 ，即ASCII码NULL,说明：串是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符（字母、数字或其他字符），所以，人们经常这样定义串：串是一个有穷字符序列。,3,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单,若干术语：,串长：,空白串：,子串：,子串位置：,字符位置：,串相等：,串中字符个数（n0）. n=0 时称为空串,。,由一个或多个空格符组成的串。,串s中任意个连续的字符序列叫s的子串; S叫,主串,。,子串的第一个字符的序号。,字符在串中的序号。,串长度相等，且对应位置上字符相等。,注：空串是任意串的子串。任意串是其自身的子串。,4,若干术语：串中字符个数（n0）. n=0 时称为空串 ,串常量和串变量,通常在程序中使用的串可分为：串常量和串变量。,串变量：串变量和其它类型的变量一样，其值是可以改变的。,串常量：串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。,串常量由直接量来表示的： 【例】Error（“overflow”）中“overflow”是直接量。串常量命名 有的语言允许对串常量命名，以使程序易读、易写。 【例】C+中，可定义串常量pathconst char path=dir/bin/appl;,5,串常量和串变量5,练1：,串是由,字符组成的序列，一般记为,。,练2：,现有以下4个字符串：,a =BEI b =JING c = BEIJING d = BEI JING,问： 他们各自的长度？, a是哪个串的子串？在主串中的位置是多少？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c和d中的位置都是1,练3：,空串和空白串有无区别？,答：,有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串.,0个或多个,S=a,1,a,2,a,n,6,练1：串是由,ADT Sting,Objects:,D=ai | aiCharacterSet, i=1, 2,，n, n0,Relations:,R1= | a,i-1,a,i,D, i=2, ，n,functions:,/,有13种之多,StrAssign(,&,T, chars),/,串赋值，生成值为chars的串T,StrCompare(S,T),/,串比较，若,ST,，返回值大于0,StrLength(S),/,求串长，即返回S的元素个数,Concat(,&,T, S1, S2),/,串连接，用T返回S1S2的新串,SubString(,&,Sub, S, pos, len),/,求S中pos起长度为len的子串,Index(S, T, pos),/,返回子串T在pos之后的位置,Replace(&S, T,V),/,用子串V替换子串T,ADT Sting,串的抽象数据类型定义（,参见教材P71,）,最小操作子集,7,ADT Sting串的抽象数据类型定义（参见教材P71）最,设 s =I AM A STUDENT, t =GOOD, q=WORKER。求：,练习：,StrLength(,s,) ,StrLength(,t,) ,SubString(,s, 8, 7)=,SubString,(t, 2, 1)=,Index(,s, A)=,Index(,s, t,)=,Replace(,s, STUDENT,q,)=,14,4,STUDENT,O,3,0 （ s中没有t！）,I AM A WORKER,再问：,Concat(SubString(,s,6,2), Concat(,t,SubString(,s,7,8) ？,8,设 s =I AM A ST,4.2串的表示和实现,定长顺序存储表示,用一组地址连续的存储单元存储串值的字符序列,堆分配存储表示,用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。,串的块链存储表示,链式方式存储,首先强调：,串与线性表的运算有所不同，是以“,串的整体,”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有三种机内表示方法：,顺序存储,链式存储,9,4.2串的表示和实现定长顺序存储表示首先强调：串与线性表的,定长顺序存储特点：,用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的,上界预先给出,，故称为静态存储分配。,例如：,#define Maxstrlen 255 /用户可用的最大串长,typedef unsigned char SString Maxstrlen1 ;,SString s; /s是一个可容纳255个字符的顺序串。,注：,一般用SString0来存放串长信息；,C语言约定在串尾加结束符 0，以利操作加速，但不计入串长；,若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。,讨论：想存放超长字符串怎么办？静态数组有缺陷！,实现方式：参见教材P73编程两例，两串连接和,求子串,改用动态分配的一维数组,“堆”！,10,定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长,例：,用顺序存储方式实现求子串函数SubString(,&,Sub, S, pos, len),Status SubString(SString &sub, SString S, int pos, int len ), if(posS0 | lenS0-pos+1),return ERROR;,/pos不合法则告警,Sub1len=Spospos+len-1;,Sub0=len; return OK;,将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中,（注：串Sub的预留长度与S一样）,s = a,1, a,2, . , a,n,n,串长,pos,len,11,例：用顺序存储方式实现求子串函数SubString(&Sub,思路：,利用malloc函数合理预设串长空间。,特点：,若在操作中串值改变，还可以利用,realloc,函数按新串长度,增加(堆砌),空间。,Typedef struct ,char,*ch,;,/ 若非空串,按串长分配空间; 否则 ch = NULL,int length;,/串长度,HString,堆分配存储特点：,仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,约定：,所有按堆存储的串，其关键信息放置在：,12,思路：利用malloc函数合理预设串长空间。Typedef,Status StrInsert ( HString &S, int pos, HString T ),/在串S的第pos个字符之前（包括尾部）插入串T,if (posS.length+1) return ERROR;,/pos不合法则告警,if(T.length),/只要串T不空，就需要重新分配S空间，以便插入T,if (!（S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char),) exit(OVERFLOW);,for ( i=S.length-1; i=pos-1; -i ),/为插入T而腾出pos之后的位置,S.chi+T.length = S.chi;,/从S的pos位置起全部字符均后移,S.chpos-1pos+T.length-2 = T.ch0T.length-1;,/插入T，略0,S.length + = T.length;,/刷新S串长度,return OK;,/StrInsert,例：,用“堆”实现串插入操作,(,教材P75,),13,Status StrInsert ( HString &S,Status StrAssign(HString &T, char *chars),if (T.ch) free(T.ch);,for (i=0, c=chars; c; +i, +c);,/求串长度,if (!i) T.ch = NULL; T.length = 0;,else,if (!(T.ch = (char*)malloc(i*sizeof(char),exit(OVERFLOW);,T.ch0.i-1 = chars0.i-1;,T.length =i;,Return OK;,/StrAssign,指针变量C也可以自增！意即每次后移一个数据单元。,附：堆分配存储表示,直到终值为“假”停止，串尾特征是,0NULL=0,14,Status StrAssign(HString &T, c,显然，若,数据元素很多，用法2存储更优称为,块链结构,链式存储特点 ：,用链表存储串值，易插入和删除。,法1：,链表结点（数据域）大小取1,法2：,链表结点（数据域）大小取n(例如n=4),A,B,C,I,NULL,head,head,A B C D,E F G H,I # # # NULL,15,显然，若数据元素很多，用法2存储更优称为块链结构链式存储特,head,A B C D,E F G H,I J # # NULL,head,A B C,X,F G H I,Y,Z,D E,J # # # NULL,虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。,16,headA B C D E F G H ,#define CHUNKSIZE 80,/可由用户定义的块大小,typedef struct Chunk ,/首先定义结点类型,char ch CHUNKSIZE ;,/结点中的数据域,struct Chunk * next ;,/结点中的指针域,Chunk;,块链类型定义：,例略,typedef struct ,/其次定义用链式存储的串类型,Chunk *head;,/头指针,Chunk *tail;,/尾指针,int curLen;,/结点个数, Lstring;,17,#define CHUNKSIZE 80 /可,再次强调：,串与线性表的运算有所不同，是以“,串的整体,”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,这类操作中均涉及到,定位问题,，称为,串的模式匹配,。它是串处理系统中最重要的操作之一。,18,再次强调：串与线性表的运算有所不同，是以“串的整体”作为操作,4.3 串的模式匹配算法,模式匹配(Pattern Matching) 即,子串定位运算（Index函数）,。,算法目的：,确定主串中所含子串第一次出现的位置（定位）,即如何实现 Index(S,T,pos)函数（见教材P72）,初始条件：,串S和T存在，T是非空串，1posStrLength(s),操作结果：,若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”。否则称 “匹配不成功” 。,19,4.3 串的模式匹配算法模式匹配(Pattern Ma, BF算法设计思想：,将主串的第pos个字符和模式的第1个字符比较，,若,相等,，继续逐个比较后续字符；,若,不等,，从主串的下一字符（pos+1）起，重新与第一个字符比较。,BF算法,（又称古典或经典的、朴素的、穷举的）,KMP算法,（特点：速度快）,算法种类：,直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列,第一个字符的序号,，即匹配成功。,否则，匹配失败，返回值 0 .,S=a b a b c a b c a c b a b,T=,a b c a c,pos=5,20, BF算法设计思想： BF算法 （又称古典或经典的、朴素,Int Index(SString S, SString T, int pos) ,i=pos; j=1;,while ( i=S0 & jT0) return i-T0;,/子串结束，说明匹配成功,else return 0;,/Index, BF算法的实现,即,Index（）操作的实现,（见教材P79）,S=a b a b,c,a b c a c b a b,T=,a b c a c,pos=5,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,i,j,21,Int Index(SString S, SString T,例,： S=,ababcabcacbab,，T=,abcac,，pos=1，,求：串T在串S中第pos个字符之后的位置。,解：,此题的BF算法：,int IndexBF(Sstring S,Sstring T),i=1;j=1;,while(i=s0 &jT0),return i-T0;,else return 0;,讨论：,若,n,为主串长度，,m,为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为,(n-m+1)*mO(n*m),最恶劣情况是：,主串前面n-m个位置都,部分匹配,到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！,BF匹配算法的最坏时间复杂度,但一般情况下BF算法的时间复杂度为O(n+m),22,例： S=ababcabcacbab，T=abcac,KMP算法,（特点：速度快）,KMP算法设计思想,KMP算法的推导过程,KMP算法的实现,（关键技术:计算nextj）,KMP算法的,时间复杂度,23,KMP算法（特点：速度快） KMP算法设计思想23,能否利用已经部分匹配的结果而加快模式串的滑动速度？,能！而且主串S的指针i不必回溯！可提速到O(n+m)！,例：, KMP算法设计思想：,(参见教材P80-84）,S=a b a b c a b c a c b a b,T=,a b c a c,S=,a b,a,b c a,b,c a c b a b,T=,a,b c a,c,S=,a b,a b c a,b,c a c,b a b,T=,a,b,c a c,Index_kmp的返回值应为,i=6,需要讨论两个问题：, 如何“记忆”部分匹配结果？, 如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点,k,.,i,i,i,k,k,a,b,a,a,b,c,24,能否利用已经部分匹配的结果而加快模式串的滑动速度？ KMP, KMP算法的推导过程：,（见教材P81）,抓住部分匹配结果的两个特征：,两式联立可得：T,1,T,k-1,=T,j-(k-1),T,j-1,注意：j 为当前已知的失配位置，我们的目标是计算新起点 k，,仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,则S前,i-1i-(k-1),位T的,j-1j-(k-1),位,即(4-3）式含义,S=,a b a b c,a,b,c a c b a b,T=,a,b,c a c,i,k,则T的,k-11,位S前,i-1i-(k-1),位,即(4-2）式含义,i,k,j,S=,a b a b c,a,b,c a c b a b,T=,a b c,a,c,刚才肯定是在S的i,处和,T的第j字符 处失配,设目前应与T的第k字符开始比较,25, KMP算法的推导过程：（见教材P81）抓住部分匹配结果的, KMP算法的推导过程(续）：,根据模式串T的规律： T,1,T,k-1,=T,j-(k-1),T,j-1,和已知的当前失配位置j ，可以归纳出计算新起点 k的表达式。,令k = next j ，则,next j ,0 当j1时,max k |1kj 且T,1,T,k-1,=T,j-(k-1),T,j-1, ,1 其他情况,讨论：, next j 有何意义？,一旦失配，应从模式串T中第next j 个字符开始与S的失配点i 重新匹配!, next j 怎么求？,后面会举例（参见教材P81）,26, KMP算法的推导过程(续）：根据模式串T的规律： ,第一步，先,把模式T所有可能的失配点j所对应的nextj计算出来,；,第二步：执行定位函数index_kmp （与BF算法模块非常相似）, KMP算法的实现即,Index( )操作的实现,（见教材P82）,Int Index_KMP(SString S, SString T, int pos) ,i=pos; j=1;,while ( i=S0 & jT0) return i-T0;,/子串结束，说明匹配成功,else return0;,/Index_KMP,27,第一步，先把模式T所有可能的失配点j所对应的nextj计,怎样计算模式T所有可能的失配点 j 所对应的 nextj？,例： 模 式 串 T： a b a a b c a c,可能失配位,j,： 1 2 3 4 5 6 7 8,新匹配位,nextj,:,next j ,0 当j1时,max k |1kj 且T,1,T,k-1,=T,j-(k-1),T,j-1, ,1 其他情况,0,1,1,2,2,3,1,2,讨论：,j=1,时, next j =,0；,因为属于“,j=1,”;,j=2,时, next j =,1；,因为属于,“其他情况”,；,刚才已归纳：,j=3,时,k=2,，只需查看T,1,=T,2,；,j=4,时,k=2，3,，要查看T,1,=T,3, 和T,1,T,2,=T,2,T,3,j=5,时,k=2，3，4,，要查看T,1,=T,4, 、T,1,T,2,=T,3,T,4, 和,T,1,T,2,T,3,=T,2,T,3,T,4,以此类推，可得后续nextj值。,28,怎样计算模式T所有可能的失配点 j 所对应的 nextj,讨论两个有关next j 的问题：, 怎样简捷计算nextj？,可用递推法编程实现！,（参见P83简捷算法）,计算nextj的时间为O(m),void get_next(SString T, int &next ),/next函数值存入数组next,i=1; next1=0; j=0;,while(iT0 ),if(j= = 0|Ti= = Tj)+i;+j;nexti=j;,else j=nextj;,/ get_next,void get_nextval(SString T, int &nextval ),/next函数修正值存入数组nextval,i=1; nextval1=0; j=0;,while(iT0 ),if(j= = 0|Ti= =Tj ) +i;+j;,If(Ti!=Tj ) nextvali=j;,else nextvali=nextvalj; ,else j=nextvalj; ,/ get_nextval, next j 是否完美无缺？,答：未必，例如当,S=a b a a a a b,T=a a a a b时,仍有多余动作,（参见P84改进算法,称为nextval j ）,29,讨论两个有关next j 的问题： 怎样简捷计算ne,i=1; j=0,next1=0,iT0,j=0 | Ti=Tj,+i; +j;,nextj=j;,j=nextj;,END,Y,Y,N,N,附：求解nextj 算法流程图:,30,i=1; j=0iT0j=0 | Ti=T,例如：求abaabcac模式串的next函数,next1=0,next2=1 p,next1,!= p,1,next3=1 p,next2,!= p,2,next4=2 p,next3,= p,3,next5=2 p,next4,!= p,4,p,nextnext4,= p,4,next6=3 p,next5,= p,5,next7=1 p,next6,!= p,6,p,next3,!=p,6,p,next3,!=p,6,next8=2 p,next7,= p,7,31,例如：求abaabcac模式串的next函数next1=,next函数的改进算法,前面定义的next函数在某些情况下还是有缺陷,例如：模式aaaab与主串aaabaaaab匹配情况：,模式： a a a a b,j：1 2 3 4 5,nextj： 0 1 2 3 4,S: a a a b a a a a b,T: a a a a b,i: 1 2 3 4 5 6 7 8 9,a a a a b,a a a a b,a a a a b,a a a a b,32,next函数的改进算法前面定义的next函数在某些情况下还是,当P,j,=P,nextj,时，则,如果S,i,!= P,j,，= S,i,!= P,nextj,因此，S,i,没有必要继续与 P,nextj,进行比较，,而应该直接和P,nextj,的下一个字符P,nextnextj,进行比较。,因此，在计算next函数时，,如果出现P,j,=P,nextj,=,P,k,则nextj=nextk=nextnextj,修改算法见教材P84 算法4.8,此时效率不高的原因为：,33,当Pj=Pnextj时，则如果Si != Pj，=, KMP算法的,时间复杂度,注意：,由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被采用。,而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算nextj时所用的比较次数m，比较总次数也仅为n+m=,O(nm)，,大大快于BF算法。,回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为：,(n-m+1)*mO(n*m),因为主串指针,i,不必回溯，所以从外存输入文件时可以做到边读入边查找，“流式”作业！,KMP算法的用途：,本章结束,34, KMP算法的时间复杂度注意：由于BF算法在一般情况下的时,