数据结构(严蔚敏)精第4章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,第四章,串,.,【课前思考】,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=a,1,a,2,a,n,，其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的引号不算串值，不包含在串中。a,i,(1in)可以是字母、数字或其它字符。,n为串中字符的个数，称为串的长度。,2空串,不含任何字符的串称为空串，它的长度n=0，记为s=。,3空格串,含有一个或多个空格的串，称为空格串，它的长度n为空格的个数，一般用符号“,”表示空串。,串是有限长的字符序列，由一对单引号相括，如:,a string,.,4子串、主串,通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。,若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。,另外，空串是任意串的子串，任意串是自身的子串。若一个串的长度为n，则它的子串数目为 +1，真子串个数为 (除串本身以外的子串都称为真子串)。,当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。,.,二、串的抽象数据类型的定义如下：,ADT String,数据对象,：,D,a,i,|a,i,CharacterSet,i=1,2,.,n,n0,数据关系,：,R,1,|a,i-1,a,i,D,i=2,.,n,.,基本操作,：,StrAssign(&,T,chars,),StrCopy,(,&,T,S),DestroyString,(,&,S),StrEmpty,(S),StrCompare,(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。,表示空串，空串的长度为零。,.,StrCompare(S,T),初始条件：,串 S 和 T 存在,。,操作结果：,若S,T，则返回值,0；若S,T，则返回值,0；若S,T，则返回值,0。,例如：,StrCompare(,data,state)0,.,StrLength,(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),且,0,lenStrLength(S)-pos+1,。,操作结果：,用 Sub 返回串 S 的第 pos 个字符起,长度为 len 的子串。,.,例如：,SubString(sub,commander,4,3),求得 sub=man；,SubString(sub,commander,1,9),求得 sub=commander；,SubString(sub,commander,9,1),求得 sub=r；,子串为“串”中的一个字符子序列,.,SubString(sub,commander,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=,a,bca,a,bca,aa,bca,，T=bca,若 V=,x,，则经置换后得到,S=a,x,a,x,aa,x,若,V=,bc,，则经置换后得到,S=a,bc,a,bc,aa,bc,.,StrInsert,(,&,S,pos,T),初始条件：,串S和T存在，,1posStrLength(S)1。,操作结果：,在串S的第pos个字符之前,插入串T。,例如：,S=,chater，T=,rac,，,则执行 StrInsert(S,4,T)之后得到,S=cha,rac,ter,.,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、,串比较StrCompare、求串长StrLength、,串联接Concat以及求子串SubString,等六种操作构成串类型的最小操作子集,。,即：这些操作不可能利用其他串操作来实现，,反之，其他串操作（除串清除ClearString和串,销毁DestroyString外）可在这个最小操作子,集上实现。,.,例如，可利用,串比较,、求串长和求子串等操作实现定位函数Index(S,T,pos)。,StrCompare(SubString(S,i,StrLength(T),T),?,0,S 串,T 串,T 串,i,pos,n-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,(StrCompare(sub,T),!=,0)+i;,else,return,i;,/while,/if,return,0;,/S中不存在与T相等的子串,/Index,.,又如串的置换函数,：,Replace,(,&,S,T,V),S 串,T 串,V 串,V 串,pos,pos,sub,i,news 串,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 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)串比较函数。,StrCompare(s,t)/*若串s和t相等,则返回0；若st，则返回1；若st，则返 回-1*/,SString s,t;,int i;,for(i=0;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(,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),使得“t,0,t,1,t,k,”=“t,j-k,t,j-k+1,t,j,”成立。,例如t=cdc就是这样的模式串。在图4.6中的第一次回溯,当s,0,=t,0,s,1,=t,1,s,2,t,2,时,算法中取i=1,j=0,使主串指针回溯一个位置,比较s,1,和t,0,。因t,0,t,1,所以一定有s,1,t,0,。另外,因有t,0,=t,2,s,0,=t,0,s,2,t,2,则一定可推出s,2,t,0,所以也不必取i=2,j=0去比较s,2,和t,0,。可直接在第二次比较时取i=3,j=0,比较s,3,和t,0,。这样,模式匹配过程主串指针i就可不必回溯。,.,(2)模式串中存在真子串,例如t=“abab”,由于“t,0,t,1,”=“t,2,t,3,”(这里k=1,j=3),则存在真子串。设s=“abacabab”,t=“abab”,第一次匹配过程如下所示。,此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹配。因t,0,t,1,s,1,=t,1,必有s,1,t,0,又因t,0,=t,2,s,2,=t,2,所以必有s,2,=t,0,。因此,第二次匹配可直接从i=3,j=1开始。,.,现在我们讨论一般情况。,设s=s,0,s,1,s,n-1,t=t,0,t,1,t,m-1,当s,i,t,j,(0in-m,0jm)时,存在:,t,0,t,1,t,j-1,=s,i-j,s,i-j+1,s,i-1,(4.1),若模式串中存在的真子串满足:,t,0,t,1,t,k,=t,j-k,t,j-k+1,t,j,(0kj),(4.2),由(4.1)式说明模式串中的子串t,0,t,1,t,k-1,已和主串s,i-k,s,i-k+1,s,i-1,匹配,下一次可直接比较s,i,和t,k,若不存在(4.2)式,则结合(4.1)式说明在t,0,t,1,t,j-1,中不存在任何以t,0,为首字符子串与s,i-j+1,s,i-j+2,s,i-1,中以s,i-1,为末字符的匹配子串,下一次可直接比较s,i,和t,0,。,.,为此,定义nextj函数如下:,maxk|0kj,且“t,0,t,1,t,k-1,”=“t,j-k,t,j-k+1,t,j-1,”,当此集合非空时,-1 当j=0时,0 其他情况,nextj=,t=“abab”对应的next数组如下,:,.,由模式串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模式匹配过程如下所示。,.,.,上述定义的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,而模式中p,j,=p,k,则为主串中字符s,i,和p,j,比较不等时,不需要再和p,k,进行比较,而直接和p,nextk,进行比较,换句话说,此时的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=s,1,s,2,s,n,，T=t,1,t,2,t,m,，且0m=n。用简单和KMP模式匹配算法判断模式串T是否在主串S中，若在，则输出模式串在主串的第一匹配位置，否则，匹配失败，返回零值。,三、实验要点及说明,简单模式匹配算法和KMP模式匹配算法的主要区别在于后者将有效利用已有的匹配结果，省去不必要的匹配过程，提高匹配性能。,利用串的顺序存储结构实现实验内容。,四、思考题,能否用串的块链存储结构实现KMP算法？,.,The end.,thank you for,listening,重庆工商大学,计算机与信息工程学院,.,