《数据结构 串的基本概念; 串的存储结构》由会员分享，可在线阅读，更多相关《数据结构 串的基本概念; 串的存储结构（47页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 主讲人：张云雷主讲人：张云雷信息工程学院信息工程学院授课内容授课内容 串的基本概念串的基本概念串的存储结构串的存储结构教学目标教学目标理解掌握串的定义与特性理解掌握串的定义与特性理解掌握串的存储结构理解掌握串的存储结构教学重点教学重点串的存储结构串的存储结构教学难点教学难点串的存储结构串的存储结构 串串( (或或字字符符串串),),是是由由零零个个或或多多个个字字符符组组成成的的有有穷穷序序列列。含零个字符的串称为空串。含零个字符的串称为空串, ,用用表示。表示。 串中所含字符的个数称为该串的长度串中所含字符的个数称为该串的长度( (或串长或串长) )。 通通常常将将一一个个
2、串串表表示示成成 a a1 1a a2 2aan n 的的形形式式。其其中中, ,最最外外边边的的双双引引号号本本身身不不是是串串的的内内容容, ,它它们们是是串串的的标标志志, ,以以便便将将串串与与标标识识符符( (如如变变量量名名等等) )加加以以区区别别。每每个个a ai i(1in)(1in)代表一个字符。代表一个字符。4.1 4.1 串的基本概念串的基本概念 当当且且仅仅当当两两个个串串的的长长度度相相等等并并且且各各个个对对应应位位置置上上的的字符都相同时字符都相同时, ,这两个串才是相等的这两个串才是相等的。 一一个个串串中中任任意意个个连连续续字字符符组组成成的的子子序序列列
3、( (含含空空串串, ,但但不不含含串串本本身身) )称称为为该该串串的的子子串串。例例如如,“a”,“a”、“ab”“ab”、“abc”“abc”和和“abcd”“abcd”等等都都是是“abcde”“abcde”的的子子串串（有有的的教教科上将本身作为子串）。科上将本身作为子串）。例例4.1 4.1 问问题题: : “abcde”“abcde”有有多多少少个个子子串串? ?解解: :空串数空串数:1:1含含1 1个字符的子串数个字符的子串数:5:5含含2 2个字符的子串数个字符的子串数:4:4含含3 3个字符的子串数个字符的子串数:3:3含含4 4个字符的子串数个字符的子串数:2:2共有共
4、有1+2+3+4+5=151+2+3+4+5=15个子串。个子串。 串的基本运算如下串的基本运算如下: : (1) (1) StrAssign(&s,chars):StrAssign(&s,chars):将将一一个个字字符符串串常常量量赋赋给给串串s,s,即生成一个其值等于即生成一个其值等于charschars的串的串s s。 (2) StrCopy(&s,t):(2) StrCopy(&s,t):串复制串复制: :将串将串t t赋给串赋给串s s。 (3) (3) StrEqual(s,t):StrEqual(s,t):判判串串相相等等: :若若两两个个串串s s与与t t相相等等则则返回真
5、；否则返回假。返回真；否则返回假。 (4) StrLength(s):(4) StrLength(s):求串长求串长: :返回串返回串s s中字符个数。中字符个数。 (5) (5) Concat(s,t):Concat(s,t):串串连连接接: :返返回回由由两两个个串串s s和和t t连连接在一起形成的新串。接在一起形成的新串。 (6)SubStr(s,i,j):(6)SubStr(s,i,j):求求 子子 串串 : :返返 回回 串串 s s中中 从从 第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的、由由连连续续j j个个字符组成的子串。字符组
6、成的子串。 (7)InsStr(s1,i,s2):(7)InsStr(s1,i,s2):将将 串串 s2s2插插 入入 到到 串串 s1s1的的 第第i(1iStrLength(s)+1)i(1iStrLength(s)+1)个个字字符符中中, ,即即将将s2s2的的第第一一个字符作为个字符作为s1s1的第的第i i个字符个字符, ,并返回产生的新串。并返回产生的新串。 (8)DelStr(s,i,j):(8)DelStr(s,i,j):从从 串串 s s中中 删删 去去 从从 第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的长长度度为为j j的的子
7、子串串, ,并返回产生的新串。并返回产生的新串。 (9)RepStr(s,i,j,t):(9)RepStr(s,i,j,t):替替 换换 : :在在 串串 s s中中 , ,将将 第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的j j个个字字符符构构成成的子串用串的子串用串t t替换替换, ,并返回产生的新串。并返回产生的新串。 (10) DispStr(s):(10) DispStr(s):串输出串输出: :输出串输出串s s的所有元素值。的所有元素值。 4.2.1 4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 串串是是一一
8、种种特特殊殊的的线线性性表表, ,在在非非紧紧缩缩格格式式中中, ,它它的的每每个个结结点点仅仅由由一一个个字字符符组组成成, ,因因此此存存储储串串的的方方法法也也就就是是存存储储线线性性表表的的一一般般方方法法。存存储储串串最最常常用用的的方方式式是是采采用用顺顺序序存存储储, ,即即把把串串的的字字符符顺顺序序地地存存储储在在内内存存一一片片相相邻邻的的空空间间, ,这称为顺序串。这称为顺序串。4.2 4.2 串的存储结构串的存储结构 顺顺序序存存储储采采用用一一般般顺顺序序表表的的存存储储结结构构, ,其其类类型型定定义义如下如下: : #define MaxSize 100#defi
9、ne MaxSize 100 typedef structtypedef struct char dataMaxSize; char dataMaxSize; int len; int len; SqString; SqString; 其其中中,data,data域域用用来来存存储储字字符符串串,len,len域域用用来来存存储储字字符符串串的的当当前前长长度度,MaxSize,MaxSize常常量量表表示示允允许许所所存存储储字字符符串串的的最大长度。在最大长度。在C C语言中每个字符串以语言中每个字符串以00 标志结束。标志结束。 顺序串中实现串的基本运算如下顺序串中实现串的基本运算如下:
10、 : (1) StrAssign(str,cstr) (1) StrAssign(str,cstr) 将将一一个个字字符符串串常常量量赋赋给给串串str,str,即即生生成成一一个个其其值值等等于于cstrcstr的串的串s s。 void StrAssign(SqString &str,char cstr) void StrAssign(SqString &str,char cstr) int i; int i; for (i=0;cstri!=0;i+) for (i=0;cstri!=0;i+) str.datai=cstri; str.datai=cstri; =i; =i; (2)
11、StrCopy(s,t)(2) StrCopy(s,t) 将串将串t t复制给串复制给串s s。void void StrCopy(SqString StrCopy(SqString & &s,SqString s,SqString t) t) /*/*引引用用型型参参数数*/*/ int i; int i; for (i=0;it.len;i+) for (i=0;it.len;i+) s.datai=t.datai; s.datai=t.datai; =; =; (3) StrEqual(s,t)(3) StrEqual(s,t) 判判断断两两个个串串是是否否相相等等: :若若两两个个串串
12、s s与与t t相相等等返返回回真真(1)(1)；否则返回假否则返回假(0)(0)。 int StrEqual(SqString s,SqString t)int StrEqual(SqString s,SqString t) int same=1,i; int same=1,i; if (!=)if (!=) same=0; same=0; /*/*长度不相等时返回长度不相等时返回0*/0*/ else else for (i=0;is.len;i+) for (i=0;is.len;i+) if (s.datai!=t.datai) if (s.datai!=t.datai) /*/*有一
13、个对应字符不同时返回有一个对应字符不同时返回0*/0*/ same=0; break; same=0; break; return same; return same; (4) StrLength(s)(4) StrLength(s) 求串长求串长: :返回串返回串s s中字符个数。中字符个数。 int StrLength(SqString s)int StrLength(SqString s) return ; return ; (5) Concat(s,t)(5) Concat(s,t) 返回由两个串返回由两个串s s和和t t连接在一起形成的新串。连接在一起形成的新串。 SqString
14、 Concat(SqString s,SqString t) SqString Concat(SqString s,SqString t) SqString str; int i; SqString str; int i; =; =; for (i=0;is.len;i+) for (i=0;is.len;i+) str.datai=s.datai; str.datai=s.datai; for(i=0;it.len;i+) for(i=0;it.len;i+) str.datas.len+i=t.datai;str.datas.len+i=t.datai; return str; retur
15、n str; (6) SubStr(s,i,j)(6) SubStr(s,i,j) 返返回回串串s s中中从从第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的、由连续的、由连续j j个字符组成的子串。个字符组成的子串。 SqString SubStr(SqString s,int i,int j)SqString SubStr(SqString s,int i,int j) SqString str;int =0;SqString str;int =0; if (i | j)if (i | j) printf( printf(参数不正确参数不正确n);
16、n); return str; /* return str; /*参数不正确时返回空串参数不正确时返回空串*/*/ for(k=i-1;ki+j-1;k+)for(k=i-1;ki+j-1;k+) str.datak-i+1=s.datak;str.datak-i+1=s.datak; =j;=j; return str;return str; (7) InsStr(s1,i,s2)(7) InsStr(s1,i,s2) 将将串串s2s2插插入入到到串串s1s1的的第第i i个个字字符符中中, ,即即将将s2s2的的第第一一个个字符作为字符作为s1s1的第的第i i个字符个字符, ,并返回产生
17、的新串。并返回产生的新串。 SqStringSqString InsStr(SqString s1,int i,SqString s2)InsStr(SqString s1,int i,SqString s2) int j; int j; SqString str; =0;SqString str; =0; if if (i=0 (is1.len+1)/*is1.len+1)/*参参数数不不正正确确时时返返回回空空串串*/*/ printf( printf(参数不正确参数不正确n);return s1;n);return s1; for (j=0;ji-1;j+)for (j=0;ji-1;j
18、+) str.dataj=s1.dataj;str.dataj=s1.dataj; for(j=0;js2.len;j+) for(j=0;js2.len;j+) str.datai+j-1=s2.dataj;str.datai+j-1=s2.dataj; for (j=i-1;js1.len;j+) for (j=i-1;js1.len;j+) str.datas2.len+j=s1.dataj;str.datas2.len+j=s1.dataj; =s1.len+s2.len;=s1.len+s2.len; return str;return str; (8) DelStr(s,i,j)(
19、8) DelStr(s,i,j) 从从串串s s中中删删去去第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的长度为长度为j j的子串的子串, ,并返回产生的新串。并返回产生的新串。 SqString DelStr(SqString s,int i,int j)SqString DelStr(SqString s,int i,int j) int k;SqString str;int k;SqString str; =0;=0; if if (i=0 (i i | | i+js.len+1) i+js.len+1) /*/*参参数数不不正正确确时时返返
20、回回空串空串*/*/ printf( printf(参数不正确参数不正确n);return str;n);return str; for (k=0;ki-1;k+)for (k=0;ki-1;k+) str.datak=s.datak; str.datak=s.datak; for (k=i+j-1;ks.len;k+) for (k=i+j-1;ks.len;k+) str.datak-j=s.datak; str.datak-j=s.datak; =; =; return str; return str; (9) RepStr(s,i,j,t) (9) RepStr(s,i,j,t) 在在
21、串串s s中中, ,将将第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的j j个字符构成的子串用串个字符构成的子串用串t t替换替换, ,并返回产生的新串。并返回产生的新串。 SqString SqString RepStr(SqString RepStr(SqString s,int s,int i,int i,int j,SqString t)j,SqString t) i int k;SqString str;nt k;SqString str; =0;=0; if if (i=0 (i i | | i+j-1) i+j-1) /*/*参参数数
22、不不正正确确时时返返回空串回空串*/*/ printf( printf(参数不正确参数不正确n); return str;n); return str; for (k=0;ki-1;k+) for (k=0;ki-1;k+) str.datak=s.datak;str.datak=s.datak; for (k=0;kt.len;k+) for (k=0;kt.len;k+) str.datai+k-1=t.datak; str.datai+k-1=t.datak; for (k=i+j-1;ks.len;k+) for (k=i+j-1;k0) if (0) for (i=0;is.len;
23、i+) for (i=0;is.len;i+) printf(%c,s.datai); printf(%c,s.datai); printf(n); printf(n); 例例4.2 4.2 设设计计顺顺序序串串上上实实现现串串比比较较运运算算Strcmp(s,t)Strcmp(s,t)的算法。的算法。 解解: :本例的算法思路如下本例的算法思路如下: : (1) (1)比较比较s s和和t t两个串共同长度范围内的对应字符两个串共同长度范围内的对应字符: : 若若s s的字符的字符t t的字符的字符, ,返回返回1 1； 若若s s的字符的字符t t的字符的字符, ,返回返回-1-1； 若若
24、s s的字符的字符=t=t的字符的字符, ,按上述规则继续比较。按上述规则继续比较。 (2) (2)当当(1)(1)中对应字符均相同时中对应字符均相同时, ,比较比较s1s1和和s2s2的长度的长度: : 两者相等时两者相等时, ,返回返回0 0； s s的长度的长度t t的长度的长度, ,返回返回1 1； s s的长度的长度t t的长度的长度, ,返回返回-1-1。 int Strcmp(SqString s,SqString t)int Strcmp(SqString s,SqString t) int i,comlen;int i,comlen; if ()if () comlen=;/
25、* comlen=;/*求求s s和和t t的共同长度的共同长度*/*/ else comlen=;else comlen=; for (i=0;icomlen;i+) /*for (i=0;icomlen;i+) /*逐个字符比较逐个字符比较*/*/ if(s.datait.datai) return -1;if(s.datait.datai)return 1;if (s.datait.datai)return 1; if (=) return 0;if (=) return 0; /*s=t*/*s=t*/ else if () else if ()/*st*/*st*/*st*/ 4.2
26、.2 4.2.2 串串的的链链式式存存储储及及其其基基本本操操作作实现实现 也也可可以以采采用用链链式式方方式式存存储储串串, ,即即用用单单链链表表形形式式存存储储串。这称为链式串或链串。串。这称为链式串或链串。 链串中的结点类型定义链串中的结点类型定义: : typedef struct snode typedef struct snode char data; char data; struct snode *next; struct snode *next; LiString; LiString; 其其中中datadata域域用用来来存存储储组组成成字字符符串串的的字字符符,next,
27、next域域用用来来指指向向下下一一个个结结点点。每每个个字字符符对对应应一一个个结结点点, ,一一个个这这样样的的链链表表存存储储一一个个字字符符串串。下下图图所所示示是是一一个个结结点大小为点大小为1 1的链串。的链串。链串示意图链串示意图 (1) StrAssign(s,t)(1) StrAssign(s,t) 将将一一个个字字符符串串常常量量t t赋赋给给串串s,s,即即生生成成一一个个其其值值等等于于t t的串的串s s。以下采用尾插法建立链串。以下采用尾插法建立链串。 void StrAssign(LiString *&s,char t)void StrAssign(LiStrin
28、g *&s,char t) int i; int i; LiString *r,*p;LiString *r,*p; /*r/*r始终指向尾结点始终指向尾结点*/*/ s=(LiString *)malloc(sizeof(LiString);s=(LiString *)malloc(sizeof(LiString); r=s;r=s; for (i=0;ti!=0;i+) for (i=0;ti!=0;i+) p=(LiString *)malloc(sizeof(LiString); p=(LiString *)malloc(sizeof(LiString); p-data=ti;r-ne
29、xt=p;r=p; p-data=ti;r-next=p;r=p; r-next=NULL;r-next=NULL; (2) StrCopy(s,t)(2) StrCopy(s,t) 将将串串t t复复制制给给串串s s。以以下下采采用用尾尾插插法法建建立立复复制制后后的的链链串串s s。 void StrCopy(LiString *&s,LiString *t)void StrCopy(LiString *&s,LiString *t) LiString *p=t-next,*q,*r; LiString *p=t-next,*q,*r; s=(LiString *)malloc(size
30、of(LiString);s=(LiString *)malloc(sizeof(LiString);r=s;r=s;/*r/*r始终指向尾结点始终指向尾结点*/*/ while (p!=NULL)while (p!=NULL) /*/*将将t t的所有结点复制到的所有结点复制到s*/s*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p-data;r-next=q;r=q; q-data=p-data;r-next=q;r=q; p=p-next; p=p-next;
31、 r-next=NULL;r-next=NULL; (3) StrEqual(s,t)(3) StrEqual(s,t) 判判断断两两个个串串是是否否相相等等: :若若两两个个串串s s与与t t相相等等则则返返回回真真(1)(1)；否则返回假；否则返回假(0)(0)。 int StrEqual(LiString *s,LiString *t)int StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; LiString *p=s-next,*q=t-next; while(p!=NULL&q!=NULL&p-data=
32、q-data) while(p!=NULL&q!=NULL&p-data=q-data) p=p-next;q=q-next; p=p-next;q=q-next; if (p=NULL & q=NULL) return 1;if (p=NULL & q=NULL) return 1; else return 0;else return 0; (4) StrLength(s)(4) StrLength(s)求串长求串长: :返回串返回串s s中字符个数。中字符个数。 int StrLength(LiString *s)int StrLength(LiString *s) int i=0; in
33、t i=0; LiString *p=s-next; LiString *p=s-next; while (p!=NULL) while (p!=NULL) i+; i+; p=p-next;p=p-next; return i; return i; (5) Concat(s,t)(5) Concat(s,t) 返回由两个串返回由两个串s s和和t t连接在一起形成的新串。连接在一起形成的新串。 LiString *Concat(LiString *s,LiString *t) LiString *Concat(LiString *s,LiString *t) LiString *str,*p
34、=s-next,*q,*r;LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString);str=(LiString *)malloc(sizeof(LiString); r=str;r=str; while(p!=NULL)/*while(p!=NULL)/*将将s s的所有结点复制到的所有结点复制到str*/str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p-data; q-da
35、ta=p-data; r-next=q;r=q; r-next=q;r=q; p=p-next; p=p-next; p=t-next;p=t-next; while(p!=NULL)/* while(p!=NULL)/*将将t t的所有结点复制到的所有结点复制到s str*/tr*/ q q=(LiString *)malloc(sizeof(LiString);=(LiString *)malloc(sizeof(LiString); q-data=p-data; q-data=p-data; r-next=q;r=q; r-next=q;r=q; p=p-next; p=p-next;
36、r-next=NULL; r-next=NULL; return str;return str; (6) SubStr(s,i,j)(6) SubStr(s,i,j) 返返回回串串s s中中从从第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的、由连续由连续j j个字符组成的子串。个字符组成的子串。 LiString *SubStr(LiString *s,int i,int j)LiString *SubStr(LiString *s,int i,int j) int k; int k; LiString *str,*p=s-next,*q,*r;L
37、iString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str=(LiString *)malloc(sizeof(LiString); r=str; r=str; if(iStrLength(s)|j0|i+j-if(iStrLength(s)|jStrLength(s)1StrLength(s) printf( printf(参数不正确参数不正确n);n); return str;/* return str;/*参数不正确时返回空串参数不正确时返回空串*/*/ for (k=0;ki-1;k+) /*fo
38、r (k=0;knext; p=p-next; for (k=1;k=j;k+) /*sifor (k=1;kstr*/=str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; q-data=p-data;q-next=NULL; r-next=q;r=q;r-next=q;r=q; p=p-next;p=p-next; r-next=NULL; r-next=NULL; return str;return str; (7) In
39、sStr(s1,i,s2)(7) InsStr(s1,i,s2) 将将串串s2s2插插入入到到串串s1s1的的第第i(1iStrLength(s)+1)i(1iStrLength(s)+1)个个字字符符中中, ,即即将将s2s2的的第第一一个个字字符符作作为为s1s1的的第第i i个个字字符符, ,并并返回产生的新串。返回产生的新串。 LiString *InsStr(LiString *s,int i,LiString *t)LiString *InsStr(LiString *s,int i,LiString *t) int k;int k; LiString *str,*p=s-next
40、,*p1=t-next,*q,*r;LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString);str=(LiString *)malloc(sizeof(LiString); r=str;r=str; if (iStrLength(s)+1) if (iStrLength(s)+1) printf( printf(参数不正确参数不正确n);n); return str; return str; /*/*参数不正确时返回空串参数不正确时返回空串*/*/ for(k=1;ki;k+)/*for
41、(k=1;kdata=p-data;q-next=NULL; q-data=p-data;q-next=NULL; r-next=q;r=q;p=p-next; r-next=q;r=q;p=p-next; while (p1!=NULL) /*while (p1!=NULL) /*将将t t的所有结点复制到的所有结点复制到str*/str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p1-data;q-next=NULL;q-data=p1-data;q-next
42、=NULL; r-next=q;r=q; p1=p1-next;r-next=q;r=q; p1=p1-next; while(p!=NULL)/*while(p!=NULL)/*将将*p*p及其后的结点复制到及其后的结点复制到str*/str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; r-next=q;r=q; p=p-n
43、ext; r-next=NULL; r-next=NULL;return str;return str; (8) DelStr(s,i,j)(8) DelStr(s,i,j) 从从串串s s中中删删去去从从第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的长度为的长度为j j的子串的子串, ,并返回产生的新串。并返回产生的新串。 LiString *DelStr(LiString *s,int i,int j)LiString *DelStr(LiString *s,int i,int j) int k; int k; LiString *str,*p=
44、s-next,*q,*r;LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString);str=(LiString *)malloc(sizeof(LiString); r=str;r=str; if(iStrLength(s) | jStrLength(s)if(iStrLength(s) | jStrLength(s) printf( printf(参数不正确参数不正确n);n); return str; return str; /*/*参数不正确时返回空串参数不正确时返回空串*/*/ for(k=0;ki-1
45、;k+)/*for(k=0;kdata=p-data;q-next=NULL; q-data=p-data;q-next=NULL; r-next=q;r=q;p=p-next; r-next=q;r=q;p=p-next; for (k=0;kj;k+) /*for (k=0;knext; p=p-next; while(p!=NULL)/*while(p!=NULL)/*将将*p*p及其后的结点复制到及其后的结点复制到str*/str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString)
46、; q-data=p-data;q-next=NULL; q-data=p-data;q-next=NULL; r-next=q;r=q;p=p-next; r-next=q;r=q;p=p-next; r-next=NULL; r-next=NULL;return str;return str; (9) RepStr(s,i,j,t) (9) RepStr(s,i,j,t) 在在串串s s中中, ,将将第第i(1iStrLength(s)i(1iStrLength(s)个个字字符符开开始始的的j j个字符构成的子串用串个字符构成的子串用串t t替换替换, ,并返回产生的新串。并返回产生的新串
47、。 LiString *RepStr(LiString *s,int i,int j,LiString *t)LiString *RepStr(LiString *s,int i,int j,LiString *t) int k; int k; LiString *str,*p=s-next,*p1=t-next,*q,*r;LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString);str=(LiString *)malloc(sizeof(LiString); r=str;r=str;
48、if(iStrLength(s) | jStrLength(s)if(iStrLength(s) | jStrLength(s) printf( printf(参数不正确参数不正确n);n); return str; /* return str; /*参数不正确时返回空串参数不正确时返回空串*/*/ for (k=0;ki-1;k+) /*for (k=0;kdata=p-data;q-next=NULL; q-data=p-data;q-next=NULL; r-next=q;r=q;p=p-next; r-next=q;r=q;p=p-next; for (k=0;kj;k+) /*for
49、 (k=0;knext; p=p-next; while (p1!=NULL) /*while (p1!=NULL) /*将将t t的所有结点复制到的所有结点复制到str*/str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p1-data;q-next=NULL; q-data=p1-data;q-next=NULL; r-next=q;r=q;p1=p1-next; r-next=q;r=q;p1=p1-next; while (p!=NULL) /*while
50、 (p!=NULL) /*将将*p*p及其后的结点复制到及其后的结点复制到str*/str*/ q=(LiString *)malloc(sizeof(LiString); q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL;q-data=p-data;q-next=NULL; r-next=q;r=q;r-next=q;r=q; p=p-next;p=p-next; r-next=NULL; r-next=NULL;return str;return str; (10) DispStr(s) (10) DispSt
51、r(s) 输出串输出串s s的所有元素值。的所有元素值。 void DispStr(LiString *s)void DispStr(LiString *s) LiString *p=s-next;LiString *p=s-next; while (p!=NULL) while (p!=NULL) printf(%c,p-data); printf(%c,p-data); p=p-next; p=p-next; printf(n);printf(n); 例例4.3 4.3 在在链链串串中中, ,设设计计一一个个算算法法把把最最先先出出现现的的子串子串abab改为改为xyzxyz。 解解: :
52、在在串串s s中中找找到到最最先先出出现现的的子子串串ab,pab,p指指向向datadata域域值值为为aa的的结结点点, ,其其后后为为datadata域域值值为为bb的的结结点点。将将它它们们的的datadata域域值值分分别别改改为为xx和和z,z,再再创创建建一一个个datadata域域值值为为yy的的结结点点, ,将将其其插插入入到到*p*p之之后后。本本例例算算法法如如下下: : void Repl(LiString *&s)void Repl(LiString *&s) LiString *p=s-next,*q;int find=0;LiString *p=s-next,*q
53、;int find=0; while (p-next!=NULL & find=0) while (p-next!=NULL & find=0) if(p-data=a& p-next-data=b) /* if(p-data=a& p-next-data=b) /*找到找到*/*/ p-data=x;p-next-data=z; p-data=x;p-next-data=z; /* /*替换为替换为xyz*/xyz*/ q=(lstring *)malloc(sizeof(lstring);q=(lstring *)malloc(sizeof(lstring); q-data=y;q-next=p-next;q-data=y;q-next=p-next; p-next=q;p-next=q; find=1;find=1; else p=p-next; else p=p-next; 小结小结 (1) (1) 理解串和一般线性表之间的差异。理解串和一般线性表之间的差异。 (2)(2)重重点点掌掌握握在在顺顺序序串串上上和和链链串串上上实实现现串串的的基基本本运算算法。运算算法。
