《数据结构(第3版)第4章 串.ppt》由会员分享，可在线阅读，更多相关《数据结构(第3版)第4章 串.ppt（66页珍藏版）》请在金锄头文库上搜索。
1、第4章 串,4.1 串的基本概念,4.2 串的存储结构,本章小结,4.3 串的模式匹配,串（或字符串），是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用表示。 串中所含字符的个数称为该串的长度（或串长）。 通常将一个串表示成“a1a2an”的形式。其中最外边的双引号本身不是串的内容，它们是串的标志，以便将串与标识符（如变量名等）加以区别。每个ai（1in）代表一个字符。,4.1 串的基本概念,当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。 一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。例如，“a”、“ab”、“abc”和“abcd”等都
2、是“abcde”的子串（真子串是指不包含自身的所有子串）。,思考题： 串和线性表有什么异同？,例4.1 问题: “abcde”有多少个真子串?,解:空串数:1 含1个字符的子串数:5 含2个字符的子串数:4 含3个字符的子串数:3 含4个字符的子串数:2 共有1+2+3+4+5=15个子串。,推广：含有n个相互相同字符的串有n(n+1)/2个真子串。,串的基本运算如下:,StrAssign( int length; SqString;,其中data域用来存储字符串，length域用来存储字符串的当前长度，MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以0标志结束。,顺序
3、串中实现串的基本运算如下。,（1）StrAssign(s,cstr) 将一个字符串常量赋给串s，即生成一个其值等于cstr的串s。,void StrAssign(SqString ,建立顺序串的算法。,（2）StrCopy(s,t) 将串t复制给串s。,void StrCopy(SqString ,（3）StrEqual(s,t) 判串相等：若两个串s与t相等返回真（1）；否则返回假（0）。,bool StrEqual(SqString s,SqString t) bool same=true; int i; if (s.length!=t.length)/长度不相等时返回0 same=fal
4、se; else for (i=0;is.length;i+) if (s.datai!=t.datai) same=false; break; return same; ,（4）StrLength(s) 求串长：返回串s中字符个数。,int StrLength(SqString s) return s.length; ,（5）Concat(s,t) 串连接：返回由两个串s和t连接在一起形成的新串。,SqString Concat(SqString s,SqString t) SqString str; int i; str.length=s.length+t.length; for (i=0
5、;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; ,（6）SubStr(s,i,j) 求子串：返回串s中从第i（1iStrLength(s)）个字符开始的、由连续j个字符组成的子串。参数不正确时返回一个空串。,SqString SubStr(SqString s,int i,int j) SqString str; int k; str.length=0; if
6、 (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; ,（7）InsStr(s1,i,s2) 将串s2插入到串s1的第i（1iStrLength(s)+1）个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。参数不正确时返回一个空串。,SqString InsStr(SqString s1,int i,SqString s2) int j; SqString st
7、r; 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;j+) /s1.datai-1.s1.length-1str str.datas2.length+j=s1.dataj; str.length=s1.length+s2.lengt
8、h; 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.length=0; if (is.length | i+js.length+1) return str; /参数不正确时返回空串 for (k=0;ki-1;k+) /s.data0.i-2str str.datak=s.datak; for (k=i+j-1;ks.length;
9、k+) /s.datai+j-1.s.length-1str str.datak-j=s.datak; str.length=s.length-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.length=0; if (is.length | i+j-1s.length) return st
10、r; /参数不正确时返回空串 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.datat.length+k-j=s.datak; str.length=s.length-j+t.length; return str; ,（10）DispStr(s) 输出串s的所有元素值。,void Dis
11、pStr(SqString s) int i; if (s.length0) for (i=0;is.length;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）中对应字符均相同时，比较s和t的长度: 两者相等时，返回0； s的长度t的长度，返回1； s的长度t的长度，返回-1。,int Strcmp(SqS
12、tring s,SqString t) int i,comlen; if (s.lengtht.datai) return 1; else if (s.datait.length)/st return 1; else return -1;/st ,4.2.2 串的链式存储及其基本操作实现,链串的组织形式与一般的链表类似。主要的区别在于，链串中的一个节点可以存储多个字符。通常将链串中每个节点所存储的字符个数称为节点大小。,以下两图分别表示了同一个串ABCDEFGHIJKLMN的节点大小为4（存储密度大）和1（存储密度小）的链式存储结构。,节点大小为4的链串,节点大小为1的链串,链串节点大小的选择
13、与顺序串的格式选择类似。节点大小越大，则存储密度越大。但存储密度越大，一些操作（如插入、删除、替换等）有所不便，且可能引起大量字符移动，因此它适合于在串基本保持静态使用方式时采用。节点大小越小（如节点大小为1时），运算处理越方便，但存储密度下降。为简便起见，这里规定链串节点大小均为1。,链串的节点类型定义如下： typedef struct snode char data; struct snode *next; LiString;,下面讨论在链串上实现串基本运算的算法。,（1）StrAssign(s,cstr) 将一个字符串常量cstr赋给串s，即生成一个其值等于cstr的串s。以下采用尾插
14、法建立链串s。,void StrAssign(LiString * ,（2）StrCopy(s,t) 将串t复制给串s。以下采用尾插法建立复制后的链串s。,void StrCopy(LiString * ,（3）StrEqual(s,t) 判串相等：若两个串s与t相等则返回真；否则返回假。,bool 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; Li
15、String *p=s-next; while (p!=NULL) i+; p=p-next; return i; ,（5）Concat(s,t) 串连接：返回由两个串s和t连接在一起形成的新串。以下采用尾插法建立链串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(L
16、iString); q-data=p-data; 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; r-next=q;r=q; p=p-next; r-next=NULL; return str; ,（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 *)ma
