《数据结构教程》第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(&s,chars):将一个字符串常量赋给串s,即生成一个其值等于chars的串s。(2)StrCopy(&s,t):串复制:将串t赋给串s。(3)StrEqual(s,t):判串相等:若两个串s与t相等则返回真；否则返回假。(4)StrLength(s):求串长:返回串s中字符个数。,(5)Concat(s,t):串连接:返回由两个串s和t连接在一起形成的新串。(6)SubStr(s,i,j):求子串:返回串s中从第i(1iStrLength(s)个字符开始的、由连续j个字符组成的子串。(7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1iStrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。,(8)DelStr(s,i,j):从串s中删去从第i(1iStrLength(s)个字符开始的长度为j的子串,并返回产生的新串。(9)RepStr(s,i,j,t):替换:在串s中,将第i(1iStrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。(10)DispStr(s):串输出:输出串s的所有元素值。,4.2.1 串的顺序存储及其基本操作实现 串是一种特殊的线性表,在非紧缩格式中,它的每个结点仅由一个字符组成,因此存储串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序存储,即把串的字符顺序地存储在内存一片相邻的空间,这称为顺序串。,4.2 串的存储结构,顺序存储采用一般顺序表的存储结构,其类型定义如下:#define MaxSize 100 typedef struct char dataMaxSize;int len;strtype;其中,ch域用来存储字符串,len域用来存储字符串的当前长度,MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以0标志结束。,顺序串中实现串的基本运算如下:(1)StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。void StrAssign(SqString,(2)StrCopy(s,t)将串t复制给串s。void StrCopy(SqString,(3)StrEqual(s,t)判断两个串是否相等:若两个串s与t相等返回真(1)；否则返回假(0)。int StrEqual(SqString s,SqString t)int same=1,i;if(s.len!=t.len)same=0;/*长度不相等时返回0*/else for(i=0;is.len;i+)if(s.datai!=t.datai)/*有一个对应字符不同时返回0*/same=0;break;return same;,(4)StrLength(s)求串长:返回串s中字符个数。int StrLength(SqString s)return s.len;,(5)Concat(s,t)返回由两个串s和t连接在一起形成的新串。SqString Concat(SqString s,SqString t)SqString str;int i;str.len=s.len+t.len;for(i=0;istr*/str.datai=s.datai;for(i=0;istr*/str.datas.len+i=t.datai;return str;,(6)SubStr(s,i,j)返回串s中从第i(1iStrLength(s)个字符开始的、由连续j个字符组成的子串。SqString SubStr(SqString s,int i,int j)SqString str;int k;str.len=0;if(is.len|js.len)printf(参数不正确n);return str;/*参数不正确时返回空串*/for(k=i-1;kstr*/str.datak-i+1=s.datak;str.len=j;return str;,(7)InsStr(s1,i,s2)将串s2插入到串s1的第i个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.len=0;if(is1.len+1)/*参数不正确时返回空串*/printf(参数不正确n);return s1;,for(j=0;jstr*/str.dataj=s1.dataj;for(j=0;jstr*/str.datai+j-1=s2.dataj;for(j=i-1;jstr*/str.datas2.len+j=s1.dataj;str.len=s1.len+s2.len;return str;,(8)DelStr(s,i,j)从串s中删去第i(1iStrLength(s)个字符开始的长度为j的子串,并返回产生的新串。SqString DelStr(SqString s,int i,int j)int k;SqString str;str.len=0;if(is.len|i+js.len+1)/*参数不正确时返回空串*/printf(参数不正确n);return str;,for(k=0;kstr*/str.datak=s.datak;for(k=i+j-1;kstr*/str.datak-j=s.datak;str.len=s.len-j;return str;,(9)RepStr(s,i,j,t)在串s中,将第i(1iStrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。SqString RepStr(SqString s,int i,int j,SqString t)int k;SqString str;str.len=0;if(is.len|i+j-1s.len)/*参数不正确时返回空串*/printf(参数不正确n);return str;,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;return str;,(10)DispStr(s)输出串s的所有元素值。void DispStr(SqString s)int i;if(s.len0)for(i=0;is.len;i+)printf(%c,s.datai);printf(n);,例4.2 设计顺序串上实现串比较运算Strcmp(s,t)的算法。,解:本例的算法思路如下:(1)比较s和t两个串共同长度范围内的对应字符:若s的字符t的字符,返回1；若s的字符t的字符,返回-1；若s的字符=t的字符,按上述规则继续比较。(2)当(1)中对应字符均相同时,比较s1和s2的长度:两者相等时,返回0；s的长度t的长度,返回1；s的长度t的长度,返回-1。,int Strcmp(SqString s,SqString t)int i,comlen;if(s.lent.datai)return 1;if(s.len=t.len)/*s=t*/return 0;else if(s.lent*/,4.2.2 串的链式存储及其基本操作实现 也可以采用链式方式存储串,即用单链表形式存储串。这称为链式串或链串。链串中的结点类型定义:typedef struct snode char data;struct snode*next;LiString;,其中data域用来存储组成字符串的字符,next域用来指向下一个结点。每个字符对应一个结点,一个这样的链表存储一个字符串。下图所示是一个结点大小为1的链串。,链串示意图,下面讨论在链串上实现串基本运算的算法。(1)StrAssign(s,t)将一个字符串常量t赋给串s,即生成一个其值等于t的串s。以下采用尾插法建立链串。void StrAssign(LiString*,(2)StrCopy(s,t)将串t复制给串s。以下采用尾插法建立复制后的链串s。void StrCopy(LiString*,(3)StrEqual(s,t)判断两个串是否相等:若两个串s与t相等则返回真(1)；否则返回假(0)。int StrEqual(LiString*s,LiString*t)LiString*p=s-next,*q=t-next;while(p!=NULL,(4)StrLength(s)求串长:返回串s中字符个数。int StrLength(LiString*s)int i=0;LiString*p=s-next;while(p!=NULL)i+;p=p-next;return i;,(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;return str;,(6)SubStr(s,i,j)返回串s中从第i(1iStrLength(s)个字符开始的、由连续j个字符组成的子串。LiString*SubStr(LiString*s,int i,int j)int k;LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);return str;/*参数不正确时返回空串*/,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;return str;,(7)InsStr(s1,i,s2)将串s2插入到串s1的第i(1iStrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。LiString*InsStr(LiString*s,int i,LiString*t)int k;LiString*str,*p=s-next,*p1=t-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)+1)printf(参数不正确n);return str;/*参数不正确时返回空串*/,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;return str;,(8)DelStr(s,i,j)从串s中删去从第i(1iStrLength(s)个字符开始的长度为j的子串,并返回产生的新串。LiString*DelStr(LiString*s,int i,int j)int k;LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);return str;/*参数不正确时返回空串*/,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;return str;,(9)RepStr(s,i,j,t)在串s中,将第i(1iStrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。LiString*RepStr(LiString*s,int i,int j,LiString*t)int k;LiString*str,*p=s-next,*p1=t-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);return str;/*参数不正确时返回空串*/,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;return str;,(10)DispStr(s)输出串s的所有元素值。void DispStr(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之后。本例算法如下:,void Repl(LiString*,4.3 串的模式匹配 设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。,4.4.1 Brute-Force算法 Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是:从目标串s=s0s1sn-1的第一个字符开始和模式串t=t0t1tm-1中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。,int indexpos(SqString str,SqString substr)int i,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,int index(SqString s,SqString t)int i=0,j=0,k;while(i=t.len)k=i-t.len;/*返回匹配的第一个字符的下标*/else k=-1;/*模式匹配不成功*/return k;,算法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.2 KMP算法 KMP算法是、和共同提出的,简称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-2 tj-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数组如下:,void GetNext(SqString t,int next)int j,k;j=0;k=-1;next0=-1;while(jt.len-1)if(k=-1|t.dataj=t.datak)/*k为-1或比较的字符相等时*/j+;k+;nextj=k;else k=nextk;,由模式串t求出next值的算法,int KMPIndex(SqString s,SqString t)int nextMaxSize,i=0,j=0,v;GetNext(t,next);while(i=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/else v=-1;/*返回不匹配标志*/return v;,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;,void GetNextval(SqString t,int nextval)int j=0,k=-1;nextval0=-1;while(jt.len)if(k=-1|t.dataj=t.datak)j+;k+;if(t.dataj!=t.datak)nextvalj=k;else nextvalj=nextvalk;else k=nextvalk;,由模式串t求出nextval值,int KMPIndex1(SqString s,SqString t)int nextvalMaxSize,i=0,j=0,v;GetNextval(t,nextval);while(i=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/else v=-1;/*返回不匹配标志*/return v;,修改后的KMP算法,本章小结 本章基本学习要点如下:(1)理解串和一般线性表之间的差异。(2)重点掌握在顺序串上和链串上实现串的基本运算算法。(3)掌握串的模式匹配算法。(4)灵活运用串这种数据结构解决一些综合应用问题。,练习题4习题1、2和3。上机实验题题1、2,