《数据结构教程》第4章串.ppt

第4章串,4.1串的基本概念,4.2串的存储结构,本章小结,4.3串的模式匹配,串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用表示。串中所含字符的个数称为该串的长度(或串长)。通常将一个串表示成a1a2an的形式。其中,最外边的双引号本身不是串的内容,它们是串的标志,以便将串与标识符(如变量名等)加以区别。每个ai(1in)代表一个字符。,4.1串的基本概念,当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（平凡子串不包括自身）。,例4.1问题:“abcde”有多少个平凡子串?,解:空串数:1含1个字符的子串数:5含2个字符的子串数:4含3个字符的子串数:3含4个字符的子串数:2共有1+2+3+4+5=15个子串。,串的基本运算如下:(1)StrAssign(intlen;strtype;其中,ch域用来存储字符串,len域用来存储字符串的当前长度,MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以0标志结束。,顺序串中实现串的基本运算如下:(1)StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。voidStrAssign(SqString,(2)StrCopy(s,t)将串t复制给串s。voidStrCopy(SqString,(3)StrEqual(s,t)判断两个串是否相等:若两个串s与t相等返回真(1)；否则返回假(0)。intStrEqual(SqStrings,SqStringt)intsame=1,i;if(s.len!=t.len)same=0;/*长度不相等时返回0*/elsefor(i=0;is.len+1)/*参数不正确时返回空串*/printf(参数不正确n);returnstr;,for(k=0;kstr*/str.datak=s.datak;for(k=i+j-1;kstr*/str.datak-j=s.datak;str.len=s.len-j;returnstr;,(9)RepStr(s,i,j,t)在串s中,将第i(1iStrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。SqStringRepStr(SqStrings,inti,intj,SqStringt)intk;SqStringstr;str.len=0;if(is.len|i+j-1s.len)/*参数不正确时返回空串*/printf(参数不正确n);returnstr;,for(k=0;kstr*/str.datak=s.datak;for(k=0;kstr*/str.datai+k-1=t.datak;for(k=i+j-1;kstr*/str.datat.len+k-j=s.datak;str.len=s.len-j+t.len;returnstr;,(10)DispStr(s)输出串s的所有元素值。voidDispStr(SqStrings)inti;if(s.len0)for(i=0;inext,*q=t-next;while(p!=NULL,(4)StrLength(s)求串长:返回串s中字符个数。intStrLength(LiString*s)inti=0;LiString*p=s-next;while(p!=NULL)i+;p=p-next;returni;,(5)Concat(s,t)返回由两个串s和t连接在一起形成的新串。LiString*Concat(LiString*s,LiString*t)LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;while(p!=NULL)/*将s的所有结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;,p=t-next;while(p!=NULL)/*将t的所有结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;returnstr;,(6)SubStr(s,i,j)返回串s中从第i(1iStrLength(s)个字符开始的、由连续j个字符组成的子串。LiString*SubStr(LiString*s,inti,intj)intk;LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);returnstr;/*参数不正确时返回空串*/,for(k=0;knext;for(k=1;kstr*/q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;returnstr;,(7)InsStr(s1,i,s2)将串s2插入到串s1的第i(1iStrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。LiString*InsStr(LiString*s,inti,LiString*t)intk;LiString*str,*p=s-next,*p1=t-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)+1)printf(参数不正确n);returnstr;/*参数不正确时返回空串*/,for(k=1;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;while(p1!=NULL)/*将t的所有结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p1-data;q-next=NULL;r-next=q;r=q;p1=p1-next;while(p!=NULL)/*将*p及其后的结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;returnstr;,(8)DelStr(s,i,j)从串s中删去从第i(1iStrLength(s)个字符开始的长度为j的子串,并返回产生的新串。LiString*DelStr(LiString*s,inti,intj)intk;LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);returnstr;/*参数不正确时返回空串*/,for(k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;for(k=0;knext;while(p!=NULL)/*将*p及其后的结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;returnstr;,(9)RepStr(s,i,j,t)在串s中,将第i(1iStrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。LiString*RepStr(LiString*s,inti,intj,LiString*t)intk;LiString*str,*p=s-next,*p1=t-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);returnstr;/*参数不正确时返回空串*/,for(k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;for(k=0;knext;while(p1!=NULL)/*将t的所有结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p1-data;q-next=NULL;r-next=q;r=q;p1=p1-next;,while(p!=NULL)/*将*p及其后的结点复制到str*/q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;returnstr;,(10)DispStr(s)输出串s的所有元素值。voidDispStr(LiString*s)LiString*p=s-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);,例4.3在链串中,设计一个算法把最先出现的子串ab改为xyz。,解:在串s中找到最先出现的子串ab,p指向data域值为a的结点,其后为data域值为b的结点。将它们的data域值分别改为x和z,再创建一个data域值为y的结点,将其插入到*p之后。本例算法如下:,voidRepl(LiString*,4.3串的模式匹配设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。,4.4.1Brute-Force算法Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是:从目标串s=s0s1sn-1的第一个字符开始和模式串t=t0t1tm-1中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。,intindexpos(SqStringstr,SqStringsubstr)inti,j,k,idx=-1;for(i=0;istr.len;i+)for(j=i,k=0;str.dataj=substr.datak;j+,k+);if(k=substr.len)/注意j每次从i开始,有回溯return(i);return(-1);,算法1,intindex(SqStrings,SqStringt)inti=0,j=0,k;while(i=t.len)k=i-t.len;/*返回匹配的第一个字符的下标*/elsek=-1;/*模式匹配不成功*/returnk;,算法2,这个算法简单,易于理解,但效率不高,主要原因是:主串指针i在若干个字符序列比较相等后,若有一个字符比较不相等,仍需回溯(即i=i-j+1)。该算法在最好情况下的时间复杂度为O(m),即主串的前m个字符正好等于模式串的m个字符。在最坏情况下的时间复杂度为O(n*m)。,例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为n(n=6),t的长度为m(m=3)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。BF模式匹配过程如下所示。,4.3.2KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。,所谓真子串是指模式串t存在某个k(0kj)，使得t0t1tk=tj-ktj-k+1tj成立。例如，t=abab,即t0t1t2t3也就是说，“ab”是真子串。真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。,一般情况:设主串s=s0s1sn-1,模式t=t0t1tm-1,在进行第i趟匹配时，出现以下情况：这时，应有t0t1tj-1=si-jsi-j+1si-1(4.1)如果在模式t中，t0t1tj-1t1t2tj(4.2),则回溯到si-j+1开始与t匹配，必然“失配”，理由很简单：由(4.1)式和(4.2)式综合可知：t0t1tj-1si-j+1si-j+2si既然如此，回溯到si-j+1开始与t匹配可以不做。那么，回溯到si-j+2开始与t匹配又怎么样？从上面推理可知，如果t0t1tj-2t2t3tj仍然有t0t1tj-2si-j+2si-j+3si,这样的比较仍然“失配”。依此类推，直到对于某一个值k，使得：t0t1tk-2tj-k+1tj-k+2tj-1且t0t1tk-1=tj-ktj-k+1tj-1“才有tj-ktj-k+1tj-1=si-ksi-k+1si-1=t0t1tk-1,说明下一次可直接比较si和tk，这样，我们可以直接把第i趟比较“失配”时的模式t从当前位置直接右滑j-k位。而这里的k即为nextj。,例如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开始。,为此,定义nextj函数如下:maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1”当此集合非空时-1当j=0时0其他情况,nextj=,t=“abab”对应的next数组如下:,voidGetNext(SqStringt,intnext)intj,k;j=0;k=-1;next0=-1;while(jt.len-1)if(k=-1|t.dataj=t.datak)/*k为-1或比较的字符相等时*/j+;k+;nextj=k;elsek=nextk;,由模式串t求出next值的算法,intKMPIndex(SqStrings,SqStringt)intnextMaxSize,i=0,j=0,v;GetNext(t,next);while(i=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/elsev=-1;/*返回不匹配标志*/returnv;,KMP算法,设主串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.data3t.data3,由nextj的指示还需进行i=3、j=2,i=3、j=1,i=3、j=0等三次比较。实际上,因为模式中的第1、2、3个字符和第4个字符都相等,因此,不需要再和主串中第4个字符相比较,而可以将模式一次向右滑动4个字符的位置直接进行i=4,j=0时的字符比较。,这就是说,若按上述定义得到nextj=k,而模式中pj=pk,则为主串中字符si和pj比较不等时,不需要再和pk进行比较,而直接和pnextk进行比较,换句话说,此时的nextj应和nextk相同。为此将nextj修正为nextvalj：比较t.dataj和t.datak，若不等，则nextvalj=nextj;若相等nextvalj=nextvalk;,voidGetNextval(SqStringt,intnextval)intj=0,k=-1;nextval0=-1;while(jt.len)if(k=-1|t.dataj=t.datak)j+;k+;if(t.dataj!=t.datak)nextvalj=k;elsenextvalj=nextvalk;elsek=nextvalk;,由模式串t求出nextval值,intKMPIndex1(SqStrings,SqStringt)intnextvalMaxSize,i=0,j=0,v;GetNextval(t,nextval);while(i=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/elsev=-1;/*返回不匹配标志*/returnv;,修改后的KMP算法,本章小结本章基本学习要点如下:(1)理解串和一般线性表之间的差异。(2)重点掌握在顺序串上和链串上实现串的基本运算算法。(3)掌握串的模式匹配算法。(4)灵活运用串这种数据结构解决一些综合应用问题。,练习题4习题1、2和3。上机实验题题1、2,