《数据结构(第3版)第4章串【专业教育】.ppt》由会员分享，可在线阅读，更多相关《数据结构(第3版)第4章串【专业教育】.ppt（66页珍藏版）》请在三一文库上搜索。
1、第4章 串,4.1 串的基本概念,4.2 串的存储结构,本章小结,4.3 串的模式匹配,1,高等课堂,串（或字符串），是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用表示。 串中所含字符的个数称为该串的长度（或串长）。 通常将一个串表示成“a1a2an”的形式。其中最外边的双引号本身不是串的内容，它们是串的标志，以便将串与标识符（如变量名等）加以区别。每个ai（1in）代表一个字符。,4.1 串的基本概念,2,高等课堂,当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。 一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。例如，“a”、“ab”、
2、“abc”和“abcd”等都是“abcde”的子串（真子串是指不包含自身的所有子串）。,3,高等课堂,思考题： 串和线性表有什么异同？,4,高等课堂,例4.1 问题: “abcde”有多少个真子串?,解:空串数:1 含1个字符的子串数:5 含2个字符的子串数:4 含3个字符的子串数:3 含4个字符的子串数:2 共有1+2+3+4+5=15个子串。,推广：含有n个相互相同字符的串有n(n+1)/2个真子串。,5,高等课堂,串的基本运算如下:,StrAssign( int length; SqString;,其中data域用来存储字符串，length域用来存储字符串的当前长度，MaxSize常量表
3、示允许所存储字符串的最大长度。在C语言中每个字符串以0标志结束。,10,高等课堂,顺序串中实现串的基本运算如下。,（1）StrAssign(s,cstr) 将一个字符串常量赋给串s，即生成一个其值等于cstr的串s。,void StrAssign(SqString ,建立顺序串的算法。,11,高等课堂,（2）StrCopy(s,t) 将串t复制给串s。,void StrCopy(SqString ,12,高等课堂,（3）StrEqual(s,t) 判串相等：若两个串s与t相等返回真（1）；否则返回假（0）。,bool StrEqual(SqString s,SqString t) bool s
4、ame=true; int i; if (s.length!=t.length)/长度不相等时返回0 same=false; else for (i=0;is.length;i+) if (s.datai!=t.datai) same=false; break; return same; ,13,高等课堂,（4）StrLength(s) 求串长：返回串s中字符个数。,int StrLength(SqString s) return s.length; ,14,高等课堂,（5）Concat(s,t) 串连接：返回由两个串s和t连接在一起形成的新串。,SqString Concat(SqStrin
5、g s,SqString t) SqString str; int i; str.length=s.length+t.length; for (i=0;is.length;i+) /s.data0.s.length-1str str.datai=s.datai; for (i=0;it.length;i+) /t.data0.t.length-1str str.datas.length+i=t.datai; return str; ,15,高等课堂,（6）SubStr(s,i,j) 求子串：返回串s中从第i（1iStrLength(s)）个字符开始的、由连续j个字符组成的子串。参数不正确时返回
6、一个空串。,SqString SubStr(SqString s,int i,int j) SqString str; int k; str.length=0; if (is.length | js.length) return str;/参数不正确时返回空串 for (k=i-1;ki+j-1;k+) /s.datai.i+jstr str.datak-i+1=s.datak; str.length=j; return str; ,16,高等课堂,（7）InsStr(s1,i,s2) 将串s2插入到串s1的第i（1iStrLength(s)+1）个字符中，即将s2的第一个字符作为s1的第i个
7、字符，并返回产生的新串。参数不正确时返回一个空串。,SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.length=0; if (is1.length+1) /参数不正确时返回空串 return str; for (j=0;ji-1;j+) /将s1.data0.i-2str str.dataj=s1.dataj; for (j=0;js2.length;j+) /s2.data0.s2.length-1str str.datai+j-1=s2.dataj; for (j=i-1;js1.length
8、;j+) /s1.datai-1.s1.length-1str str.datas2.length+j=s1.dataj; str.length=s1.length+s2.length; return str; ,17,高等课堂,（8）DelStr(s,i,j) 从串s中删去第i（1iStrLength(s)）个字符开始的长度为j的子串，并返回产生的新串。参数不正确时返回一个空串。,SqString DelStr(SqString s,int i,int j) int k; SqString str; str.length=0; if (is.length | i+js.length+1) r
9、eturn str; /参数不正确时返回空串 for (k=0;ki-1;k+) /s.data0.i-2str str.datak=s.datak; for (k=i+j-1;ks.length;k+) /s.datai+j-1.s.length-1str str.datak-j=s.datak; str.length=s.length-j; return str; ,18,高等课堂,（9）RepStr(s,i,j,t) 在串s中，将第i（1iStrLength(s)）个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。参数不正确时返回一个空串。,SqString RepStr(Sq
10、String s,int i,int j,SqString t) int k; SqString str;str.length=0; if (is.length | i+j-1s.length) return str; /参数不正确时返回空串 for (k=0;ki-1;k+)/s.data0.i-2str str.datak=s.datak; for (k=0;kt.length;k+) /t.data0.t.length-1str str.datai+k-1=t.datak; for (k=i+j-1;ks.length;k+) /s.datai+j-1.s.length-1str str
11、.datat.length+k-j=s.datak; str.length=s.length-j+t.length; return str; ,19,高等课堂,（10）DispStr(s) 输出串s的所有元素值。,void DispStr(SqString s) int i; if (s.length0) for (i=0;is.length;i+) printf(%c,s.datai); printf(n); ,20,高等课堂,例4.2 设计顺序串上实现串比较运算Strcmp(s,t)的算法。,解：本例的算法思路如下: （1）比较s和t两个串共同长度范围内的对应字符: 若s的字符t的字符，返
12、回1； 若s的字符t的字符，返回-1； 若s的字符=t的字符,按上述规则继续比较。 （2）当（1）中对应字符均相同时，比较s和t的长度: 两者相等时，返回0； s的长度t的长度，返回1； s的长度t的长度，返回-1。,21,高等课堂,int Strcmp(SqString s,SqString t) int i,comlen; if (s.lengtht.datai) return 1; else if (s.datait.length)/st return 1; else return -1;/st ,22,高等课堂,4.2.2 串的链式存储及其基本操作实现,链串的组织形式与一般的链表类似。
13、主要的区别在于，链串中的一个节点可以存储多个字符。通常将链串中每个节点所存储的字符个数称为节点大小。,23,高等课堂,以下两图分别表示了同一个串ABCDEFGHIJKLMN的节点大小为4（存储密度大）和1（存储密度小）的链式存储结构。,节点大小为4的链串,节点大小为1的链串,24,高等课堂,链串节点大小的选择与顺序串的格式选择类似。节点大小越大，则存储密度越大。但存储密度越大，一些操作（如插入、删除、替换等）有所不便，且可能引起大量字符移动，因此它适合于在串基本保持静态使用方式时采用。节点大小越小（如节点大小为1时），运算处理越方便，但存储密度下降。为简便起见，这里规定链串节点大小均为1。,链
14、串的节点类型定义如下： typedef struct snode char data; struct snode *next; LiString;,25,高等课堂,下面讨论在链串上实现串基本运算的算法。,（1）StrAssign(s,cstr) 将一个字符串常量cstr赋给串s，即生成一个其值等于cstr的串s。以下采用尾插法建立链串s。,void StrAssign(LiString * ,26,高等课堂,（2）StrCopy(s,t) 将串t复制给串s。以下采用尾插法建立复制后的链串s。,void StrCopy(LiString * ,27,高等课堂,（3）StrEqual(s,t) 判
15、串相等：若两个串s与t相等则返回真；否则返回假。,bool StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; while (p!=NULL ,28,高等课堂,（4）StrLength(s) 求串长：返回串s中字符个数。,int StrLength(LiString *s) int i=0; LiString *p=s-next; while (p!=NULL) i+; p=p-next; return i; ,29,高等课堂,（5）Concat(s,t) 串连接：返回由两个串s和t连接在一起形成的新串。以下采用尾插法
16、建立链串str并返回其地址。,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; r-next=q;r=q; p=p-next; p=t-next;,30,高等课堂,while (p!=NULL)/将t的所有节点复制到str q=(LiStr
17、ing *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str; ,31,高等课堂,（6）SubStr(s,i,j) 求子串：返回串s中从第i（1iStrLength(s)）个字符开始的、由连续j个字符组成的子串，参数不正确时返回一个空串。以下采用尾插法建立链串str并返回其地址。,LiString *SubStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)
18、malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建链表的尾节点 if (iStrLength(s) | jStrLength(s) return str;/参数不正确时返回空串 for (k=0;knext;,32,高等课堂,for (k=1;kdata=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str; ,33,高等课堂,（7）InsStr(s1,i,s2) 将串s2插入到串s1的第i（1iStrLength(s)+1）个字符位置，即将s2的第1个字符作为s1的第i个字符，s2
19、的第2个字符作为s1的第i+1个字符，等等，并返回产生的新串, 参数不正确时返回一个空串。以下采用尾插法建立链串str并返回其地址。,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); str-next=NULL; r=str;/r指向新建链表的尾节点 if (iStrLength(s)+1)return str; /参数不正确时返回空串,34,高等课堂,for (k=1;
20、kdata=p-data; r-next=q;r=q; p=p-next; while (p1!=NULL)/将t的所有节点复制到str q=(LiString *)malloc(sizeof(LiString); q-data=p1-data; r-next=q;r=q; p1=p1-next; while (p!=NULL)/将*p及其后的节点复制到str q=(LiString *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str; ,35,高等课堂,（8）Del
21、Str(s,i,j) 从串s中删去从第i（1iStrLength(s)）个字符开始的长度为j的子串，并返回产生的新串, 参数不正确时返回一个空串。以下采用尾插法建立链串str并返回其地址。,LiString *DelStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建链表的尾节点 if (iStrLength(s) | jStrLength(s) return str;/参数不正
22、确时返回空串,36,高等课堂,for (k=0;kdata=p-data; 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; r-next=q;r=q; p=p-next; r-next=NULL; return str; ,37,高等课堂,（9）RepStr(s,i,j,t) 在串s中，将第i（1iStrLength(s)）个字符开始的j个字符构成的子串用串t替换，并返回产生的新串，参数不正确
23、时返回一个空串。以下采用尾插法建立链串str并返回其地址。,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); str-next=NULL; r=str;/r指向新建链表的尾节点 if (iStrLength(s) | jStrLength(s) return str; /参数不正确时返回空串,38,高等课堂,for (k=0;kdata=p-data;q-ne
24、xt=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-nex
25、t=NULL; return str; ,39,高等课堂,（10）DispStr(s) 输出串s的所有元素值。,void DispStr(LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data); p=p-next; printf(n); ,40,高等课堂,例4.3 在链串中,设计一个算法把最先出现的子串ab改为xyz。,解：在串s中找到最先出现的子串“ab”，p指向data域值为a的结点，其后为data域值为b的结点。将它们的data域值分别改为x和z，再创建一个data域值为y的结点，将其插入到*p之后。本例算法如
26、下:,41,高等课堂,void Repl(LiString * ,42,高等课堂,4.3 串的模式匹配,设有主串s和子串t，子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，把子串t称为模式串，因此定位也称作模式匹配。 模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。,43,高等课堂,4.4.1 Brute-Force算法 Brute-Force简称为BF算法，亦称简单匹配算法，其基本思路是: 从目标串s=“s0s1sn-1”的第一个字符开始和模式串t=“t0t1tm-1”中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从
27、目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的第i个字符开始，每个字符依次和目标串t中的对应字符相等，则匹配成功,该算法返回i；否则，匹配失败，函数返回-1。,44,高等课堂,int indexpos(SqString str,SqString substr) int i,j,k,idx=-1; for (i=0;istr.length;i+) for (j=i,k=0;str.dataj=substr.datak; j+,k+); if (k=substr.length) /注意j每次从i开始,有回溯 return(i); return(-1); ,算法
28、1,45,高等课堂,int index(SqString s,SqString t) int i=0,j=0; while (i=t.length) return(i-t.length);/返回匹配的第一个字符的下标 else return(-1);/模式匹配不成功 ,算法2,46,高等课堂,例如，设目标串s=“aaaaab”，模式串t=“aaab”。s的长度为n（n=6），t的长度为m（m=4）。用指针i指示目标串s的当前比较字符位置，用指针j指示模式串t的当前比较字符位置。模式匹配过程如下图所示。,47,高等课堂,这个算法简单，易于理解，但效率不高，主要原因是主串指针i在若干个字符序列比较
29、相等后，若有一个字符比较不相等，仍需回溯（即i=i-j+1）。 该算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符正好等于模式串的m个字符。在最坏情况下的时间复杂度为O(n*m)。,48,高等课堂,4.3.2 KMP算法,KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，简称KMP算法。该算法较BF算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。,49,高等课堂,目标串s=aaaaab，模式串t=aaab。,a a a a a b,0 1 2 3 4 5,a a a b,0 1 2 3,BF算法下一步是从s1开始,其实没
30、有必要从s1开始，为什么？,50,高等课堂,模式串中究竟是什么信息呢？,nexti是指下标为i的字符前有多少个真子串的字符。,51,高等课堂,所谓真子串是指模式串t存在某个k（0kj），使得t0t1tk = tj-ktj-k+1tj 成立。 例如，t= abab, 即t0t1t2t3 也就是说， “ab”是真子串。 真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。,52,高等课堂,模式串t=“abcac”，用next数组存放这些“部分匹配”信息 。,53,高等课堂,归纳起来，定义nextj函数如下: maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合
31、非空时 -1 当j=0时 0 其他情况,nextj=,t=“abab”对应的next数组如下:,54,高等课堂,void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.length-1) if (k=-1 | t.dataj=t.datak) j+;k+; nextj=k; else k=nextk; ,由模式串t求出next值：,55,高等课堂,int KMPIndex(SqString s,SqString t) int nextMaxSize,i=0,j=0; GetNext(t,next); whi
32、le (i=t.length) return(i-t.length);/返回匹配模式串的首字符下标 else return(-1);/返回不匹配标志 ,KMP算法：,56,高等课堂,设主串s的长度为n，子串t长度为m。 在KMP算法中求next数组的时间复杂度为O(m)，在后面的匹配中因主串s的下标不减即不回溯，比较次数可记为n，所以KMP算法总的时间复杂度为O(n+m)。,57,高等课堂,58,高等课堂,上述定义的next在某些情况下尚有缺陷。 例如，模式“aaaab”在和主串“aaabaaaab”匹配时： 当i=3,j=3时，s.data3t.data3,由nextj的指示还需进行i=3、
33、j=2,i=3、j=1,i=3、j=0等3次比较。 实际上，因为模式中的第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式一次向右滑动4个字符的位置直接进行i=4，j=0时的字符比较。,59,高等课堂,这就是说，若按上述定义得到nextj=k，而模式中tj=tk，则为主串中字符si和tj比较不等时，不需要再和tk进行比较，而直接和tnextk进行比较。换句话说，此时的nextj应和nextk相同。 为此将nextj修正为nextvalj： 比较t.dataj和t.datak，若不等，则 nextvalj=nextj；若相等nextvalj=nextvalk
34、。,60,高等课堂,void GetNextval(SqString t,int nextval) int j=0,k=-1; nextval0=-1; while (jt.length) if (k=-1 | t.dataj=t.datak) j+;k+; if (t.dataj!=t.datak) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; ,由模式串t求出nextval值：,61,高等课堂,int KMPIndex1(SqString s,SqString t) int nextvalMaxSize,i=0,j=0; GetNextval(t,nextval); while (i=t.length) return(i-t.length); else return(-1); ,修改后的KMP算法:,62,高等课堂,63,高等课堂,思考题： KMP算法给我们什么启示？,64,高等课堂,本章小结 本章基本学习要点如下: （1）理解串和一般线性表之间的差异。 （2）重点掌握在顺序串上和链串上实现串的基本运算算法。 （3）掌握串的模式匹配算法。 （4）灵活运用串这种数据结构解决一些综合应用问题。,65,高等课堂,练习题4 习题4.1、4.2和4.3。,66,高等课堂,