《第4章串》习题解答解读.docx

1、第4章串习题解答解读第四章 串存储与基本操作的实现本章学习要点熟悉串的相关概念以及串与线性表的关系重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。4.1串的基本概念4.1.1串的概念1串的定义串(string) 是由n个字符组成的有限序列，记为：S

2、=”a0a1a2an-1” (n0)。其中，S是串的名字，字符序列a0a1a2an-1是串的值，ai(0in-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。例如：（1）A=“X123” (长度为4的串)（2）B=“12345654321” (长度为11的串)（3）C=“Bei Jing” (长度为8的串)（4）D=“” (长度为0的空串)（5）E=“This is a

3、 string” (长度为16的串)（6）F=“ is a ” (长度为6的串)2子串、主串和位置串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n的字符串具有n(n+1)/2个子串。例如：在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一个字符，所以在串G=“abc defghne”中包含有子串“c def”,而串 “cdef”不是

4、串G的子串。串G中第一个字符e的位置是6，第二个字符e的位置是11。3串的比较如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B的比较过程是：从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种：（1）两个串同时结束，表示A等于B；（2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B；（3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。例如：“abc”=“abc”，“abc”“abcdefg”，“132”“123456”，“ABab”“2

5、+3”。4空格串由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。4.1.2串的基本操作尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。串的基本操作主要有：（1）初始化串StrAssign(&T,chars) 由字符串常量chars生成字符串T的操作。（2）串复制StrCopy(&T,S)

6、由串S复制生成串T的操作。（3）串比较StrCompare(S,T) 若S=T返回0，ST返回正数，ST返回负数。（4）求串长度StrLength(S) 返回串S的长度。（5）串连接Concat(&T,S1,S2) 将串S1和S2连接起来生成串T的操作。（6）求子串SubString(&Sub,S,pos,len) 以串S中pos位置开始的len个字符生成子串Sub的操作。（7）串查找Index(S,T,pos) 返回子串T在S中pos个字符以后出现的位置。（8）串替换Replace(&S,T,V) 将串S中所有不重叠子串T替换为串V的操作。（9）串插入StrInsert(&S,pos,T)

7、在串S中第pos个字符前插入串T的操作。（10）删除子串StrDelete(&S,pos,len) 删除串S中第pos个字符开始的len个字符的操作。4.2串的存储表示与实现既然串是线性表的特例，所以线性表的两种存储结构对于串也是适用的。在应用中具体选用何种存储结构与串的操作有关，比如对串进行插入和删除操作运算时选用链存储结构较好，对串进行查找和求子串运算时选用顺序存储结构较好。本章主要介绍串的3种存储表示方法：（1）串的定长顺序存储表示法（2）串的堆分配存储表示法（3）串的块链式存储表示法4.2.1串的定长顺序存储表示串的定长顺序存储表示是用一组地址连续的存储单元来存储串中的字符序列。在串的

8、定长顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区，所以可以用定长字符数组来表示。1定长顺序存储结构在C+运行环境中，定长顺序结构定义为：#includeiostream.h#includestdio.h#define MAXLEN 255 /定义串的最大长度为255typedef char SStringMAXLEN+1; /定义定长顺序存储类型SString2基本操作的C+程序实现（1）求串长度操作int Length_SS(SString S)操作返回串S中所含字符的个数，即串的长度；如果S为空串则返回0。int Length_SS(SString S) i

9、nt i=0; while(Si)i+; return(i);（2）串连接操作int Concat_SS(SString &T,SString S1,SString S2)该操作将串S1、S2连接生成串T，如果在连接过程中产生了截断（即S1的长度加上S2的长度大于MAXLEN）则返回0，否则返回1。int Concat_SS(SString &T,SString S1,SString S2) int i,j,k; i=j=k=0; while(Ti+=S1j+); i-; while(iMAXLEN&(Ti=S2k) i+;k+; Ti=0; if(i=MAXLEN)&S2k) return(

10、0); /*判断是否产生截断*/ else return(1);（3）求子串操作int SubString_SS(SString &Sub,SString S,int pos,int len)该操作截取串S中从第pos个字符开始的连续的len个字符生成子串Sub，如果位置pos和长度len合理则返回1，否则返回0.int SubString_SS(SString &Sub,SString S,int pos,int len) int i=0; if(pos1|lenLength_SS(S)+1) return 0; /*判断位置和长度是否合理*/ while(ilen) Subi=Si+pos

11、-1; i+; Subi=0; return 1; （4）初始化串操作int StrAssign_SS(SString &T,char *s)该操作用字符数组s，初始化定长顺序串T。如果不产生截断（长度合理）返回1，否则返回0。int StrAssign_SS(SString &T,char *s) int i=0; while(iT则返回正数,如果S=T则返回0,否则返回负数。int StrCompare_SS(SString S,SString T) int i=0; while(Si&Ti&(Si=Ti)i+; return (int)(Si-Ti);（7）串的替换操作int Repla

12、ce_SS(SString &S,int n,int m,SString T)该操作将串S中从第n个字符开始的连续的m个字符替换成串T中的字符，如果n和m的选取合理则返回1，否则返回0。int Replace_SS(SString &S,int n,int m,SString T) SString S1; int len=Length_SS(T); int i=n-1,j=0,k=n+m-1; /*i为开始替换位置，j指向第一个替换字符，k为剩余字符的开始位置*/ if(n1|mLength_SS(S)+1|Length_SS(S)+len-mMAXLEN) return(0);/*判断位置是

13、否合理*/ StrCopy_SS(S1,S); /*将剩余部分复制到S1中*/ while(Si+=Tj+); /*替换S中指定部分的字符*/ i-; while(Si+=S1k+); /*将剩余部分复制到S中*/ return(1);（8）主函数演示程序main()void main_SS() SString s1,s2,s3,sub,T; char str1100,str2100; int l1,l2,l3,pos,len,n; while(1) coutstr1”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。*/ cin.getline(str2,sizeof(str2);

14、 StrAssign_SS(s1,str1); StrAssign_SS(s2,str2); l1=Length_SS(s1); l2=Length_SS(s2); cout(2)求串长操作：ns1的长度=l1，s2的长度=l2endl; n=StrCompare_SS(s1,s2); cout0)couts2n; else if(n=0)couts1=s2n; else couts1s2n; Concat_SS(s3,s1,s2); cout(4)串连接操作：ns1+s2=s3endl; l3=Length_SS(s3); couts1+s2的长度=l3endl;coutposlen; if

15、(SubString_SS(sub,s3,pos,len) coutsub=subendl; else cout位置不正确n; coutposlen; cout输入替换串:n; cin.get(); cin.getline(str1,sizeof(str1); StrAssign_SS(T,str1); if(Replace_SS(s3,pos,len,T) cout替换结果为:ns3=s3endl; else cout替换不成功!n; （程序运行过程略）3定长顺序存储的特点对于定长顺序存储的串在基本操作方面主要有以下特点：（1）对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度；

16、（2）在串删除和串插入操作时必须移动大量的字符；（3）如果在串输入、串连接、串插入和串替换操作中串值的长度超过MAXLEN，则按约定采取“截尾”法处理，这将导致操作结果的不合理。4.2.2串的堆分配存储表示由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且在操作中串值长度的变化也比较大。因此，事先为串变量设置固定大小空间的数组不尽合理。用堆分配存储表示串的方法是：在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间资源。1串的堆分配存储结构在C+运行环境中，堆分配存

17、储结构定义为struct HString char *ch; /串变量中字符数组的首地址 int length; /串的长度;2在堆分配存储结构中串基本操作的C+程序实现（1）串的赋值操作void StrAssign_HS(HString &T,char str)该操作由字符串常量str生成一个HString型串T。void StrAssign_HS(HString &T,char str) int len=0,i; while(strlen)len+; /计算串的长度 T.length=len; if(!len)T.ch=NULL; /对空串进行初始化 else T.ch=new charl

18、en+1; /在堆内存中分配相应大小的存储空间 for(i=0;T.chi=stri;i+); /将数据从str复制到T.ch中 （2）求串长的操作int Length_HS(HString S)该操作返回串S的长度，如果S为空串则返回0。int Length_HS(HString S)return(S.length); （3）串的比较操作int StrComp_HS(HString S,HString T)该操作比较串S、T的大小。int StrComp_HS(HString S,HString T) int i; for(i=0;iT.length&iS.length;i+) if(S.c

19、hi!=T.chi)break; return(int)(S.chi-T.chi); （4）串的清空操作void ClearString_HS(HString &S)该操作清空串S所占的堆空间。void ClearString_HS(HString &S) if(S.ch) deleteS.ch; S.ch=NULL; S.length=0; （5）串的连接操作void Concat_HS(HString &T,HString S1,HString S2)该操作计算串S1、S2的连接串T。void Concat_HS(HString &T,HString S1,HString S2) int

20、i,j,k; T.length=S1.length+S2.length; i=j=k=0; T.ch=new charT.length+1; /分配链接串的储存空间 while(T.chi+=S1.chj+); /将S1复制到T i-; while(T.chi+=S2.chk+); /将S2连接到T的末尾（6）求子串的算法int SubString_HS(HString &Sub,HString S,int pos,int len)该操作求串S中pos个字符开始的len个字符组成的子串Sub，如果位置合理返回1否则返回0。int SubString_HS(HString &Sub,HStrin

21、g S,int pos,int len) int i; if(pos1|lenS.length+1) return(0); /如果位置不合理时返回0值 Sub.ch=new charlen+1; /动态分配子串的存储空间 Sub.length=len; for(i=0;ilen;i+) Sub.chi=S.chpos+i-1; /将子串复制到Sub中 Sub.chi=0; return(1);（7）串插入操作的算法int StrInsert_HS(HString &S,int pos,HString H)该操作在串S的第pos个字符前面插入字符串H，如果位置合理返回1，否则返回0。int St

22、rInsert_HS(HString &S,int pos,HString H) int i,j,k; HString S1; if(posS.length+1) return 0; /位置不合理返回0值 S1.length=S.length+H.length; S1.ch=new charS1.length+1; /重新分配空间 for(i=0;ipos-1;i+)S1.chi=S.chi; /取S中pos前段内容 k=i; for(j=0;j H.length;j+)S1.chi+=H.chj; /将H插入 while(S1.chi+=S.chk+); /取S中剩余的内容 deleteS.

23、ch; S=S1; return 1;（8）串替换操作的算法int Replace_HS(HString &S,int n,int m,HString T)该操作将串S中第n个字符开始的m个字符替换为串T，如果位置n和字符数m合理返回1否则返回0。int Replace_HS(HString &S,int n,int m,HString T) int i,j,k=n+m-1; HString S1; if(n1|mS.length+1)return(0); /长度或位置不合理 S1.length=S.length+T.length-m; S1.ch=new charS1.length+1; /

24、重新分配储存空间 for(i=0;in-1;i+)S1.chi=S.chi; /取S中前面的部分 for(j=0;jT.length;j+)S1.chi+=T.chj; /取T中的内容 while(S1.chi+=S.chk+); /取S中剩余的部分 deleteS.ch; S=S1; return(1);（9）主函数演示程序main()void main_HS() HString S1,S2,S,sub,V,T; SString ss1,ss2; int n,pos,len; while(1) cout(1)串初始化操作：n输入两个字符串:n; cin.getline(ss1,sizeof(

25、ss1); cin.getline(ss2,sizeof(ss2); StrAssign_HS(S1,ss1); StrAssign_HS(S2,ss2);cout(2)求串长操作：nlen1=Length_HS(S1)endl;coutlen2=Length_HS(S2)endl; cout0) coutS2n; else if(n0)coutS1S2n; else coutS1=S2n; Concat_HS(S,S1,S2); cout(4)串连接操作：n:s1+s2=S.chendl; coutlength=Length_HS(S)endl; coutposlen; if(SubStri

26、ng_HS(sub,S,pos,len) coutsub=sub.chendl; else cout位置不对!n; coutpos;cin.get(); cout输入要插入的子串V:n; cin.getline(ss1,sizeof(ss1); StrAssign_HS(V,ss1); if(StrInsert_HS(S,pos,V) cout插入结果为 s=S.chendl; else cout位置不对!n; coutposlen;cin.get(); cout输入替换串T:n; cin.getline(ss1,sizeof(ss1); StrAssign_HS(T,ss1); if(Replace_HS(S,pos,len,T) cout结果为 s=S.chendl; else cout位置不对!n; 3堆分配存储表示的特点从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处理方便，同时在操作中对串的长度又没有任何限制，更显灵活，因此该存储结构在有关字符串处理的应用程序中常被采用。4.2.3串的块链式存储表示1块链式存储的概念和线性表的链式存储结构类似，可以采用链表方式存储串。由于串中