《《数据结构教程》串》由会员分享，可在线阅读，更多相关《《数据结构教程》串（70页珍藏版）》请在金锄头文库上搜索。
1、第4章 串 4.1 串的基本概念4.2 串的存储结构 本章小结4.3 串的模式匹配 串(或字符串),是由零个或多个字符组成的有穷序 列。含零个字符的串称为空串,用表示。串中所含字符的个数称为该串的长度(或串长)。通常将一个串表示成“a1a2an“的形式。其中,最 外边的双引号本身不是串的内容,它们是串的标志,以 便将串与标识符(如变量名等)加以区别。每个 ai(1in)代表一个字符。4.1 串的基本概念当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“ab
2、cd”等都是“abcde”的子串（平凡子串不包括自身）。例4.1 问题: “abcde”有多少个平凡子串?解:空串数:1含1个字符的子串数:5含2个字符的子串数:4含3个字符的子串数:3含4个字符的子串数:2共有1+2+3+4+5=15个子串。串的基本运算如下:(1) StrAssign(int len; strtype;其中,ch域用来存储字符串,len域用来存储字符串的 当前长度,MaxSize常量表示允许所存储字符串的最大 长度。在C语言中每个字符串以0标志结束。顺序串中实现串的基本运算如下:(1) StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于
3、cstr的串s。void StrAssign(SqString for (i=0;cstri!=0;i+)str.datai=cstri;str.len=i;(2) StrCopy(s,t)将串t复制给串s。void StrCopy(SqString 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,in
4、t 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;
5、 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(SqSt
6、ring 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
7、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(
8、s) 输出串s的所有元素值。void DispStr(SqString s) int i;if (s.len0) for (i=0;it.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域 用来指向下一个结点。每个字
9、符对应一个结点,一个 这样的链表存储一个字符串。下图所示是一个结点 大小为1的链串。链串示意图下面讨论在链串上实现串基本运算的算法。(1) StrAssign(s,t)将一个字符串常量t赋给串s,即生成一个其值等于t的 串s。以下采用尾插法建立链串。void StrAssign(LiString *LiString *r,*p;/*r始终指向尾结点*/s=(LiString *)malloc(sizeof(LiString);r=s;for (i=0;ti!=0;i+) p=(LiString *)malloc(sizeof(LiString);p-data=ti;r-next=p;r=p;
10、r-next=NULL;(2) StrCopy(s,t)将串t复制给串s。以下采用尾插法建立复制后的链串s。void StrCopy(LiString *s=(LiString *)malloc(sizeof(LiString); r=s;/*r始终指向尾结点*/while (p!=NULL) /*将t的所有结点复制到s*/ q=(LiString *)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next; r-next=NULL;(3) StrEqual(s,t)判断两个串是否相等:若两个串s与t相等则返回真(1) ；否则返回
11、假(0)。int StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next;while (p!=NULL q=q-next; if (p=NULL else return 0;(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(LiS
12、tring *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
13、-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“);retur
14、n 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
15、 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=
