数据结构ppt.pptx

数据结构严蔚敏数据结构严蔚敏【课前思考课前思考】1.串就是线性表串就是线性表的结论是否正确？的结论是否正确？从数据结构得观点来说,串就是一种特殊得线性表;但就数据类型而言,串不就是线性表。2.串和线性表的主要差别是什么？串和线性表的主要差别是什么？希望您带着这个问题开始这一章得学习,并能在学完这一章得内容之后能得出正确得结论。【学习目标学习目标】1、理解“串”类型定义中各基本操作得特点,并能正确利用它们进行串得其它操作。2、理解串类型得各种存储表示方法。3、理解串匹配得各种算法。【重点与难点重点与难点】相对于其它各个知识点而言,本章非整个课程得重点,鉴于串已就是多数高级语言中已经实现得数据类型,因此本章重点仅在于了解串类型定义中各基本操作得定义以及串得实现方法,并学会利用这些基本操作来实现串得其它操作。本章得难点难点就是理解实现串匹配得串匹配得KMP算法算法得思想,但它不属本章学习得基本要求,更不就是重点学习内容。【知识点知识点】串得类型定义、串得存储表示、串匹配、KMP算法【学习指南学习指南】虽然目前各常用得高级语言中都已经实现了串类型,但由于它就是通过软件实现得,因此作为一个软件工作者还就是应该了解串得实现方法。本章没有必须完成得算法设计题,如果有兴趣可以试试以下几个题:4、10,4、11,4、13,4、17,4、18,4、23,4、28,4、30。其中前6个就是练习串得基本操作得应用,后2个就是与KMP算法相关得练习。4、1 串类型得定义串类型得定义4、2 串得表示与实现串得表示与实现4、3串得模式匹配算法串得模式匹配算法4、1串得类型定义串得类型定义一、一、基本概念基本概念 1、串得定义、串得定义串串(string)就就是是由由零零个个或或多多个个字字符符组组成成得得有有限限序序列列,记记作作s=a1a2an,其其中中s为为串串得得名名字字,用用成成对对得得单单引引号号括括起起来来得得字字符符序序列列为为串串得得值值,但但两两边边得得引引号号不不算算串串值值,不不包包含含在在串串中。中。ai(1in)可以就是字母、数字或其它字符。可以就是字母、数字或其它字符。n为串中字符得个数为串中字符得个数,称为串得长度。称为串得长度。2、空串、空串不含任何字符得串称为空串不含任何字符得串称为空串,它得长度它得长度n=0,记为记为s=。3、空格串、空格串含含有有一一个个或或多多个个空空格格得得串串,称称为为空空格格串串,它它得得长长度度n为为空空格得个数格得个数,一般用符号一般用符号“”表示空串。表示空串。串就是有限长得字符串就是有限长得字符序列序列,由一对单引号由一对单引号相括相括,如如:a string 4、子串、主串、子串、主串 通通常常将将字字符符在在串串中中得得序序号号称称为为该该字字符符在在串串中中得得位位置置。子子串串在在主主串串中中得得位位置置则则以以子子串串得得第第一一个个字字符符在在主主串串中中得得位置来表示。位置来表示。若若一一个个串串就就是是另另一一个个串串中中连连续续得得一一段段,则则这这个个串串称称为为另另一一个个串串得得子子串串,而而另另一一个个串串相相对对于于该该串串称称为为主主串串。例例如如,串串s1=“abcdefg”,s2=“fabcdefghxyz”,则则s1为为s2得得子子串串,s2相相对对于于s1为主串。为主串。另另外外,空空串串就就是是任任意意串串得得子子串串,任任意意串串就就是是自自身身得得子子串串。若若一一个个串串得得长长度度为为n,则则它它得得子子串串数数目目为为 +1,真真子子串串个个数数为为 (除串本身以外得子串都称为真子串除串本身以外得子串都称为真子串)。当且仅当两个串得值相等时当且仅当两个串得值相等时,称这两个串就是相等得称这两个串就是相等得,即只有当两个串得长度相等即只有当两个串得长度相等,并且每个对应位置得字符都并且每个对应位置得字符都相等时才相等。相等时才相等。二、串得抽象数据类型得定义如下二、串得抽象数据类型得定义如下:ADT String 数据对象数据对象:D ai|aiCharacterSet,i=1,2,、,n,n0 数据关系数据关系:R1|ai-1,ai D,i=2,、,n 基本操作基本操作:StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)Strpare(S,T)StrLength(S)Concat(&T,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String StrAssign(&T,chars)初始条件:chars 就是字符串常量。操作结果:把 chars 赋为 T 得值。StrCopy(&T,S)初始条件:串 S 存在。操作结果:由串 S 复制得串 T。DestroyString(&S)初始条件:串 S 存在。操作结果:串 S 被销毁。StrEmpty(S)初始条件:串S存在。操作结果:若 S 为空串,则返回TRUE,否则返回 FALSE。表示空串,空串得长度为零。Strpare(S,T)初始条件初始条件:串 S 与 T 存在。操作结果操作结果:若S T,则返回值 0;若S T,则返回值 0;若S T,则返回值 0。例如例如:Strpare(data,state)0StrLength(S)初始条件:串 S 存在。操作结果:返回 S 得元素个数,称为串得长度。Concat(&;T,S1,S2)初始条件:串 S1 与 S2 存在。操作结果:用 T 返回由 S1 与 S2 联接而成得新串。例如例如:Concate(T,man,kind)求得 T=mankind SubString(&Sub,S,pos,len)初始条件:串 S 存在,1posStrLength(S)且0lenStrLength(S)-pos+1。操作结果:用 Sub 返回串 S 得第 pos 个字符起 长度为 len 得子串。例如例如:SubString(sub,mander,4,3)求得 sub=man;SubString(sub,mander,1,9)求得 sub=mander;SubString(sub,mander,9,1)求得 sub=r;子串为子串为“串串”中得一个字符子序列中得一个字符子序列SubString(sub,mander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置与子串长度之间存在约束关系起始位置与子串长度之间存在约束关系长度为长度为 0 得子串为得子串为“合法合法”串串 Index(S,T,pos)初始初始条件条件:串S与T存在,T就是非空串,1posStrLength(S)。操作结果操作结果:若主串 S 中存在与串 T 值相同 得子串,则返回它在主串 S 中第pos个字符之后第一次出现得位置;否则函数值为0。假设 S=abcaabcaaabc,T=bca Index(S,T,1)=2;Index(S,T,2)=6;Index(S,T,8)=0;“子串在主串中得位置子串在主串中得位置”意指子串中得第一个字符在主串中得位序位序。Replace(&S,T,V)初始条件:串S,T与 V 均已存在,且 T 就是非空串。操作结果:用V替换主串S中出现 得所有与(模式串)T 相等得不重叠得子串。例如:假设 S=abcaabcaaabca,T=bca若 V=x,则经置换后得到 S=axaxaax若 V=bc,则经置换后得到 S=abcabcaabc StrInsert(&S,pos,T)初始条件:串S与T存在,1posStrLength(S)1。操作结果:在串S得第pos个字符之前 插入串T。例如例如:S=chater,T=rac,则执行 StrInsert(S,4,T)之后得到 S=character StrDelete(&S,pos,len)初始条件:串S存在 1posStrLength(S)-len+1。操作结果:从串S中删除第pos个字符 起长度为len得子串。ClearString(&S)初始条件:串S存在。操作结果:将S清为空串。对于串得基本操作集可以有不同得定义方法,在使用高级程序设计语言中得串类型时,应以该语言得参考手册为准以该语言得参考手册为准。gets(str)输入一个串;puts(str)输出一个串;strcat(str1,str2)串联接函数;strcpy(str1,str2,k)串复制函数;strcmp(str1,str2)串比较函数;strlen(str)求串长函数;例如:C语言函数库中提供下列串处理函数:在上述抽象数据类型定义得13种操作中,串赋值串赋值StrAssign、串复制、串复制Strcopy、串比较串比较Strpare、求串长、求串长StrLength、串联接串联接Concat以及求子串以及求子串SubString 等六种操作构成串类型得最小操作子集等六种操作构成串类型得最小操作子集。即:这些操作不可能利用其她串操作来实现,反之,其她串操作(除串清除ClearString与串 销毁DestroyString外)可在这个最小操作子 集上实现。例如,可利用串比较、求串长与求子串等操作实现定位函数Index(S,T,pos)。Strpare(SubString(S,i,StrLength(T),T)?0 S 串 T 串 T 串iposn-m+1算法得基本思想为算法得基本思想为:int Index(String S,String T,int pos)/T为非空串。若主串S中第pos个字符之后存在与 T相等得子串,则返回第一个 这样得子串在S中得位置,否则返回0 if(pos 0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(sub,S,i,m);if(Strpare(sub,T)!=0)+i;else return i;/while /if return 0;/S中不存在与T相等得子串/Index又如串得置换函数:Replace(&S,T,V)S 串 T 串 V 串 V 串pospos subinews 串sub 串得逻辑结构与线性表极为相似,区别区别仅在于串得数据对象约束为字符集。串得基本操作与线性表有很大差别。串得基本操作与线性表有很大差别。在线性表得基本操作中,大多以大多以“单个元单个元素素”作为操作对象作为操作对象;在串得基本操作中,通常以通常以“串得整体串得整体”作为操作对象作为操作对象。在程序设计语言中,串只就是作为输入或输出得常量出现,则只需存储此串得串值,即字符序列即可。但在多数非数值处理得程序中,串也以变量得形式出现。4、2 串得表示与实现串得表示与实现一、串得定长顺序存储表示一、串得定长顺序存储表示二、串得堆分配存储表示二、串得堆分配存储表示三、串得块链存储表示三、串得块链存储表示一、串得定长顺序存储表示一、串得定长顺序存储表示 与与前前面面所所讲讲得得线线性性表表得得顺顺序序存存储储结结构构类类似似,用用一一组组地地址址连连续续得得存存储储单单元元存存储储串串得得字字符符序序列列。常常常常将将定定长长顺顺序序串串设设计计成成一一种种结结构构类类型型,串串得得存存储储分分配就是在编译时完成得。配就是在编译时完成得。#define MAXSTRLEN 255 /用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN+1;/0号单元存放串得长度或或:typedef struct /*串结构定串结构定义义*/char chMAXLEN;int len;SString;按这种串得表示方法实现得串得运算时,其基本操作为“字符序列字符序列得复制得复制”。串串得实际长度可在这个予定义长度得范围内随意设定,超过予定义长度得串值则被舍去,称之为“截断截断”。特点特点:Status Concat(SString S1,SString S2,SString&T)/用T返回由S1与S2联接而成得新串。若未截断,则返回TRUE,否则FALSE。return uncut;/Concat例如例如:串得联接算法中需分三种情况处理:T1、S10=S11、S10;TS10+1、S10+S20=S21、S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断 else if(S10 MAXSTRSIZE)/截断 else /截断(仅取S1)T1、S10=S11、S10;TS10+1、MAXSTRLEN=S21、MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;T0、MAXSTRLEN=S10、MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;(1)串插入函数。串插入函数。StrInsert(s,pos,t)/*在串在串s中序号为中序号为pos得字符之前插入串得字符之前插入串t*/SString*s,t;int pos;int i;if(poss-len)return(0);/*插入位置不合法插入位置不合法*/if(s-len+t、lenlen+t、len-1;i=t、len+pos;i-)s-chi=s-chi-t、len;for(i=0;ichi+pos=t、chi;s-len=s-len+t、len;定长顺序存储得操作实施定长顺序存储得操作实施:【算法算法 串插入函数串插入函数】else if(pos+t、lenMAXLEN,但串但串t得字符序列可以全部插入得字符序列可以全部插入*/for(i=MAXSTRLEN-1;it、len+pos-1;i-)s-chi=s-chi-t、len;for(i=0;ichi+pos=t、chi;s-len=MAXLEN;else /*串串t得部分字符序列要舍弃得部分字符序列要舍弃*/for(i=0;ichi+pos=t、chi;s-len=MAXSTRLEN;return(1);(2)串删除函数。StrDelete(s,pos,len)/*在串s中删除从序号pos起len个字符*/SString*s;int pos,len;int i;if(pos(s-len-len)return(0);for(i=pos+len;ilen;i+)s-chi-len=s-chi;s-len=s-len-len;return(1);【算法算法 串删除函数串删除函数】(3)串复制函数。串复制函数。StrCopy(s,t)/*将串将串t得值复制到串得值复制到串s中中*/SString*s,t;int i;for(i=0;ichi=t、chi;s-len=t、len;【算法算法 串复制函数串复制函数】(4)判空函数。判空函数。StrEmpty(s)/*若串若串s为空为空(即串长为即串长为0),则返回则返回1,否则返回否则返回0*/SString s;if(s、len=0)return(1);else return(0);【算法算法 判空函数判空函数】(5)串比较函数。串比较函数。Strpare(s,t)/*若若串串s与与t相相等等,则则返返回回0;若若st,则则返返回回1;若若st,则则返返 回回-1*/SString s,t;int i;for(i=0;is、len&ilen=0;return(1);【算法算法 清空函数清空函数】(8)连接函数。连接函数。Concat(s,t)/*将串将串t连接在串连接在串s得后面得后面*/SString*s,t;int i,flag;if(s-len+t、lenlen;ilen+t、len;i+)s-chi=t、chi-s-len;s-len+=t、len;flag=1;else if(s-lenlen;ichi=t、chi-s-len;s-len=MAXSTRLEN;flag=0;else flag=0;/*串串s得长度等于得长度等于MAXLEN,串串t不被连接不被连接*/return(flag);【算法算法 连接函数连接函数】(9)求子串函数。求子串函数。SubString(sub,s,pos,len)/*将串将串s中序号中序号pos起起len个字符复制到个字符复制到sub中中*/SString*sub,s;int pos,len;int i;if(poss、len|lens、len-pos)sub-len=0;return(0);else for(i=0;ichi=s、chi+pos;sub-len=len;return(1);【算法算法 求子串函数求子串函数】(10)定位函数。定位函数。StrIndex(s,pos,t)/*求串求串t在串在串s中得位置中得位置*/SString s,t;int pos;int i,j;if(t、len=0)return(0);i=pos;j=0;while(is、len&j=t、len)return(i-t、len);else return(0);【算法算法 定位函数定位函数】typedef struct char*ch;/若就是非空串,则按串长分配存储区,/否则ch为NULL int length;/串长度 HString;二、串得堆分配存储表示二、串得堆分配存储表示特点:仍用一组地址连续得存储单元存储串得字符序列,但其存储空间就是在程序执行过程中动态分配而得。通常,C语言中提供得串类型就就是以这种存储方式实现得。系统利用函数malloc()与free()进行串值空间得动态管理,为每一个新产生得串分配一个存储区,称串值共享得存储空间为“堆堆”。C语言中得串以一个空字符为结束符,串长就是一个隐含值。这类串操作实现得算法为:先为新生成得串分配一个存储空间,然后 进行串值得复制。Status Concat(HString&T,HString S1,HString S2)/用T返回由S1与S2联接而成得新串 if(T、ch)free(T、ch);/释放旧空间 if(!(T、ch=(char*)malloc(S1、length+S2、length)*sizeof(char)exit(OVERFLOW);T、ch0、S1、length-1=S1、ch0、S1、length-1;T、length=S1、length+S2、length;T、chS1、length、T、length-1=S2、ch0、S2、length-1;return OK;/Concat Status SubString(HString&Sub,HString S,int pos,int len)/用Sub返回串S得第pos个字符起长度为len得子串 if(pos S、length|len S、length-pos+1)return ERROR;if(Sub、ch)free(Sub、ch);/释放旧空间 if(!len)Sub、ch=NULL;Sub、length=0;/空子串 else /完整子串 return OK;/SubString Sub、ch=(char*)malloc(len*sizeof(char);Sub、ch0、len-1=Spos-1、pos+len-2;Sub、length=len;三、串得块链存储表示三、串得块链存储表示也可用链表来存储串值,由于串得数据元素就是一个字符,它只有 8 位二进制数,因此用链表存储时,通常一个结点中存放得不就是一个字符,而就是一个子串。存储密度存储密度=数据元素所占存储位实际分配得存储位#define CHUNKSIZE 80 /可由用户定义得块大小 typedef struct Chunk /结点结构 char chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct /串得链表结构 Chunk*head,*tail;/串得头与尾指针 int curlen;/串得当前长度 LString;例如:在编辑系统中,整个文本编辑区可以瞧成就是一个串,每一行就是一个子串,构成一个结点。即:同一行得串用定长结构(80个字符),行与行之间用指针相联接。实际应用时,可以根据问题所需来设置结点得大小。这就是串得一种重要操作,很多 软件,若有“编辑编辑”菜单项得话,则其中必有“查找查找”子菜单项。4、3 串得模式匹配算法串得模式匹配算法 子串得定位操作通常称为串得模式匹配模式匹配,就是各种串处理系统中最重要得操作之一。初始条件:串S与T存在,T就是非空串,1posStrLength(S)。操作结果:若主串S中存在与串T值相 同得子串返回它在主串S中 第pos个字符之后第一次出 现得位置;否则函数值为0。首先,回忆一下串匹配(查找)得定义:INDEX(S,T,pos)下面讨论以定长顺序结构表示串时得几种算法。一、简单算法一、简单算法二、首尾匹配算法首尾匹配算法三、三、KMP(KMP(D、E、Knuth,V、R、Pratt,J、H、Morris)算法算法一、简单算法一、简单算法Brute-Force算法算法 例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。s得长得长度为度为n(n=6),t得长度为得长度为m(m=3)。用指针。用指针i指示目标串指示目标串s得当前比较字符位置得当前比较字符位置,用指针用指针j指示模式串指示模式串t得当前比得当前比较字符位置。较字符位置。BF模式匹配过程如下所示。模式匹配过程如下所示。这个算法简单这个算法简单,易于理解易于理解,但效率不高但效率不高,主要原因就主要原因就是是:主串指针主串指针i在若干个字符序列比较相等后在若干个字符序列比较相等后,若有一个若有一个字符比较不相等字符比较不相等,仍需回溯仍需回溯(即即i=i-j+1)。该算法在最好。该算法在最好情况下得时间复杂度为情况下得时间复杂度为O(m),即主串得前即主串得前m个字符正个字符正好等于模式串得好等于模式串得m个字符。在最坏情况下得时间复杂个字符。在最坏情况下得时间复杂度为度为O(n*m)。int index(SqString s,SqString t)int i=0,j=0,k;while(is、len&j=t、len)k=i-t、len;/*返返回回匹匹配配得得第第一一个个字字符符得得下标下标*/else k=-1;/*模式匹配不成功模式匹配不成功*/return k;先比较模式串得第一个字符,再比较模式串得最后一个字符,最后比较模式串中从第二个到 第n-1个字符。二、首尾匹配算法首尾匹配算法 int Index_FL(SString S,SString T,int pos)sLength=S0;tLength=T0;i=pos;patStartChar=T1;patEndChar=TtLength;while(i=sLength tLength+1)if(Si!=patStartChar)+i;/重新查找匹配起始点 else if(Si+tLength-1!=patEndChar)+i;/模式串得“尾字符”不匹配 else return 0;/检查中间字符得匹配情况检查中间字符得匹配情况 k=1;j=2;while(j tLength&Si+k=Tj)+k;+j;if(j=tLength)return i;else +i;/重新开始下一次得匹配检测三、模式匹配得改进算法三、模式匹配得改进算法(KMP算法算法)此方法由克努特(D、E、Knuth)莫里斯(J、H、Morris)普拉特(V、R、Pratt)同时发现。1、基本思想基本思想:每当一趟匹配过程中出现字符不等时每当一趟匹配过程中出现字符不等时,不不需回溯需回溯i指针指针,而就是利用已得到得部分匹配结果而就是利用已得到得部分匹配结果,将模式将模式串向右滑动尽可能远得一段距离后继续进行比较。串向右滑动尽可能远得一段距离后继续进行比较。避免多余得、不必要得比较避免多余得、不必要得比较,从而提高算法性能。算法从而提高算法性能。算法总在总在0(n+m)得时间数量级上完成匹配操作。得时间数量级上完成匹配操作。2、KMP算法匹配实例算法匹配实例:(1)模式串模式串t中没有真子串中没有真子串 真真子子串串就就是是指指模模式式串串t存存在在某某个个k(0kj),使使得得“t0t1tk”=“tj-ktj-k+1tj”成立。成立。例例如如t=cdc就就就就是是这这样样得得模模式式串串。在在图图4、6中中得得第第一一次次回回溯溯,当当s0=t0,s1=t1,s2t2时时,算算法法中中取取i=1,j=0,使使主主串串指指针针回回溯溯一一个个位位置置,比比较较s1与与t0。因因t0t1,所所以以一一定定有有s1t0。另另外外,因因有有t0=t2,s0=t0,s2t2,则则一一定定可可推推出出s2t0,所所以以也也不不必必取取i=2,j=0去去比比较较s2与与t0。可可直直接接在在第第二二次次比比较较时时取取i=3,j=0,比比较较s3与与t0。这这样样,模模式式匹匹配配过过程程主主串串指指针针i就就可不必回溯。可不必回溯。(2)模式串中存在真子串模式串中存在真子串 例如例如t=“abab”,由于由于“t0t1”=“t2t3”(这里这里k=1,j=3),则则存在真子串。设存在真子串。设s=“abacabab”,t=“abab”,第一次匹配第一次匹配过程如下所示。过程如下所示。此时不必从此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹重新开始第二次匹配。因配。因t0t1,s1=t1,必有必有s1t0,又因又因t0=t2,s2=t2,所以必有所以必有s2=t0。因此。因此,第二次匹配可直接从第二次匹配可直接从i=3,j=1开始。开始。现在我们讨论一般情况。现在我们讨论一般情况。设设s=s0s1sn-1,t=t0t1tm-1,当当sitj (0in-m,0jm)时时,存在存在:t0t1tj-1=si-jsi-j+1si-1 (4、1)若模式串中存在得真子串满足若模式串中存在得真子串满足:t0t1tk=tj-ktj-k+1tj(0kj)(4、2)由由(4、1)式式说说明明模模式式串串中中得得子子串串t0t1tk-1已已与与主主串串si-ksi-k+1si-1匹匹配配,下下一一次次可可直直接接比比较较si与与tk,若若不不存存在在(4、2)式式,则则结结合合(4、1)式式说说明明在在t0t1tj-1中中不不存存在在任任何何以以t0为为首首字字符符子子串串与与si-j+1si-j+2si-1中中以以si-1为为末末字字符符得得匹匹配配子子串串,下一次可直接比较下一次可直接比较si与与t0。为此为此,定义定义nextj函数如下函数如下:maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1”当此集合非空时当此集合非空时 -1 当当j=0时时 0 其她情况其她情况nextj=j0123tjababnextj-1001t=t=“abababab”对应得对应得nextnext数组如下数组如下:由模式串由模式串t求出求出next值得算法如下值得算法如下:void GetNext(SqString t,int next)int j,k;j=0;k=-1;next0=-1;while(jt、len-1)if(k=-1|t、chj=t、chk)/*k为为-1或比较得字符相等时或比较得字符相等时*/j+;k+;nextj=k;else k=nextk;int KMPIndex(SqString s,SqString t)/*KMP算法算法*/int nextMaxSize,i=0,j=0,v;GetNext(t,next);while(is、len&j=t、len)v=i-t、len;/*返返回回匹匹配配模模式式串串得得首首字字符符下下标标*/else v=-1;/*返回不匹配标志返回不匹配标志*/return v;设设主主串串s得得长长度度为为n,子子串串t长长度度为为m,在在KMP算算法法中中求求next数数组组得得时时间间复复杂杂度度为为O(m),在在后后面面得得匹匹配配中中因因主主串串s得得下下标标不不减减即即不不回回溯溯,比比较较次次数数可可记记为为n,所所以以KMP算法总得时间复杂度为算法总得时间复杂度为O(n+m)。例如例如,设目标串设目标串s=“aaabaaaab”,模式串模式串t=“aaaab”。s得长度为得长度为n(n=9),t得长度为得长度为m(m=5)。用指针。用指针i指示目指示目标串标串s得当前比较字符位置得当前比较字符位置,用指针用指针j指示模式串指示模式串t得当得当前比较字符位置。前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。j01234tjaaaabnextj-10123 上述定义得上述定义得next在某些情况下尚有缺陷。例如在某些情况下尚有缺陷。例如,模式模式“aaaab”在与主串在与主串“aaabaaaab”匹配时匹配时,当当i=3,j=3时时,s、ch3t、ch3,由由nextj得指示还需进行得指示还需进行i=3、j=2,i=3、j=1,i=3、j=0等三次比较。实际上等三次比较。实际上,因为因为模式中得第模式中得第1、2、3个字符与第个字符与第4个字符都相等个字符都相等,因此因此,不需要再与主串中第不需要再与主串中第4个字符相比较个字符相比较,而可以将模式一而可以将模式一次向右滑动次向右滑动4个字符得位置直接进行个字符得位置直接进行i=4,j=0时得字符时得字符比较。比较。KMP算法得改进算法得改进:这就就是说这就就是说,若按上述定义得到若按上述定义得到nextj=k,而模而模式中式中pj=pk,则为主串中字符则为主串中字符si与与pj比较不等时比较不等时,不需不需要再与要再与pk进行比较进行比较,而直接与而直接与pnextk进行比较进行比较,换句换句话说话说,此时得此时得nextj应与应与nextk相同。为此将相同。为此将nextj修正为修正为nextvalj。由模式串由模式串t求出求出nextval值值:void GetNextval(SqString t,int nextval)int j=0,k=-1;nextval0=-1;while(jnext,再设一个对尾指针再设一个对尾指针q-rear指向链队列尾部。指向链队列尾部。队列得链式存储结构可定义如下队列得链式存储结构可定义如下:typedef struct node typedef struct char data;slnode*h;struct node*next;slnode;slnode *rear;lqtype;四、思考题四、思考题 1、比较链队列与链栈得相同点与不同点。比较链队列与链栈得相同点与不同点。2、在链队列中、在链队列中,q-rear指针能否省指针能否省去？若能？若能,怎样才能找到队尾？怎样才能找到队尾？实验六实验六 串得模式匹配串得模式匹配 一、实验目得一、实验目得 熟悉串得有关概念,掌握串得存储结构及串得模式匹配算法。二、实验内容二、实验内容 由用户随意输入两个串:主串S与模式串T,设S=s1s2sn,T=t1t2tm,且0m=n。用简单与KMP模式匹配算法判断模式串T就是否在主串S中,若在,则输出模式串在主串得第一匹配位置,否则,匹配失败,返回零值。三、实验要点及说明三、实验要点及说明 简单模式匹配算法与KMP模式匹配算法得主要区别在于后者将有效利用已有得匹配结果,省去不必要得匹配过程,提高匹配性能。利用串得顺序存储结构实现实验内容。四、思考题四、思考题 能否用串得块链存储结构实现KMP算法？