《《第4章 串》习题解答》由会员分享，可在线阅读，更多相关《《第4章 串》习题解答（24页珍藏版）》请在金锄头文库上搜索。
1、第 4 章 串存储与基本操作的实现-.0.-第四章 串存储与基本操作的实现本章学习要点熟悉串的相关概念以及串与线性表的关系重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。4.1 串的基本概念4.1.1 串的概念1串的定义串(string) 是由 n
2、 个字符组成的有限序列，记为：S=”a 0a1a2an-1” (n0)。其中，S 是串的名字，字符序列 a0a1a2an-1 是串的值，a i(0in-1)可以是字母、数字或其他字符元素；由于在 C 语言系统中数组元素的下标是从 0 开始的，所以串中所含元素的序号等于该元素的下标值加 1；串中所含字符的个数 n 称为该串的长度，长度为 0 的字符串称为空串（null string） 。从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。例如：（1）A=“X123” (长度为 4 的串)（2）B=“12345654321” (长度为 11 的串)（3）C=“Bei Jing” (长度为
3、8 的串)（4）D=“” (长度为 0 的空串)（5）E=“This is a string” (长度为 16 的串)（6）F=“ is a ” (长度为 6 的串)2子串、主串和位置串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为 n 的字符串具有 n(n+1)/2 个子串。例如：在上例的(6)中串 F 就是(5) 中串 E 的子串，且子串 F 在主串 E 中的位置是 5
4、。由于空格符也是一个字符，所以在串 G=“abc defghne”中包含有子串“c def”,而串 “cdef”不是串 G 的子串。串 G 中第一个字符e的位置是 6，第二个字符e的位置是 11。3串的比较如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串 A、B 的比较过程是：从前往后逐个比较对应位置上的字符的 ASCII 码值，直到不相等或有一个字符第 4 章 串存储与基本操作的实现-.1.-串结束为止，此时的情况有以下几种：（1）两个串同时结束，表示 A 等于 B；（2）A 中字符的 ASCII 码值大于 B 中相应位置上字符的 ASCII 码值或 B 串结束，表示 A
5、大于 B；（3）B 中字符的 ASCII 码值大于 A 中相应位置上字符的 ASCII 码值或 A 串结束，表示 A小于 B。例如：“abc”=“abc”， “abc”“abcdefg”， “132”“123456”， “ABab”“2+3”。4空格串由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。4.1.2 串的基本操作尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串
6、）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。串的基本操作主要有：（1）初始化串 StrAssign(&T,chars) 由字符串常量 chars 生成字符串 T 的操作。（2）串复制 StrCopy(&T,S) 由串 S 复制生成串 T 的操作。（3）串比较 StrCompare(S,T) 若 S=T 返回 0，ST 返回正数，SLength_SS(S)+1) return 0; /*判断位置和长度是否合理*/while(iT 则返回正数,如果 S=T 则返回 0,否则返回负数。int StrCompare_SS(SString S,SString T)i
7、nt i=0;while(Sireturn (int)(Si-Ti);（7）串的替换操作 int Replace_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)第 4 章 串存储与基本操作的实现-.4.-SString S1;int len=Length_SS(T);int i=n-1,j=0,k=n+m-1; /*i 为开始替换位置，j 指
8、向第一个替换字符，k 为剩余字符的开始位置*/if(nLength_SS(S)+1|Length_SS(S)+len-mMAXLEN) return(0);/*判断位置是否合理*/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,
9、n;while(1)coutstr1”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。*/cin.getline(str2,sizeof(str2);StrAssign_SS(s1,str1);StrAssign_SS(s2,str2);l1=Length_SS(s1);l2=Length_SS(s2);cout0)couts2n;else if(n=0)coutposlen;if(SubString_SS(sub,s3,pos,len) coutposlen;coutS.length+1) return(0); /如果位置不合理时返回 0 值Sub.ch=new charlen+
10、1; /动态分配子串的存储空间Sub.length=len;for(i=0;iS.length+1) return 0; /位置不合理返回 0 值S1.length=S.length+H.length;S1.ch=new charS1.length+1; /重新分配空间for(i=0;iS.length+1)return(0); /长度或位置不合理S1.length=S.length+T.length-m;S1.ch=new charS1.length+1; /重新分配储存空间for(i=0;i0) coutS2n;else if(nposlen;if(SubString_HS(sub,S,p
11、os,len) coutpos;cin.get();coutposlen;cin.get();coutLength_SS(S)+1)return(0);while(Si+j&Tj)if(Si+j=Tj)j+; /若字符相等，则继续比较后续字符else i+; j=0; /若不相等，则重新开始新一轮比较if(!Tj) return(i+1); /若匹配成功，则返回 T 首次出现的开始位置else return(0); /若匹配不成功，则返回 0算法分析：在一般情况下，BF 算法的时间复杂度为 O(m+n)，其中 m,n 分别为串 S 和 T 的长度。但是在有些情况下，该算法的效率很低。例如：S=
12、“aaaaaaaaaaab” 共有 52 个a和 1 个b,T=“aaaaaaab”共有 7 个a和 1 个b。由于每趟比较都是在最后一个字符出现不相等，此时需要将初始位置指针 i 回溯到 i+1 的位置上，并从模式的第一个字符开始重新比较。从图 4.2 所示的匹配过程可以直观地算出，初始位置指针 i 一共要回溯 52-7=45 次，总的比较次数为： 8(45+1)=368 次。所以，在最坏的情况下 BF 算法的时间复杂度为 O(mn)。4.3.2 模式匹配的 KMP 算法模式匹配的另一种算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 同时发现的，称之为克努特-莫里
13、斯 -普拉特操作，简称 KMP 算法，他是一种改进的模式匹配算法。此算法可使时间复第 4 章 串存储与基本操作的实现-.12.-杂度在 O(m+n)的数量级上完成串的模式匹配操作。1模式的 next 数组模式匹配的 KMP 算法是，每当一趟匹配比较过程中出现字符不相同的情况时，不需要回溯指针 i,而是利用已经得到的 “部分匹配”的结果将模式 T 向右“滑动”尽可能远的一段距离后，再继续进行比较。为此需要引入一个有关模式串 T 的整型数组 next，其中第 j 个元素 nextj-1表示当模式串 T 中的第 j 个字符与主串 S 中相应字符匹配失败时，在模式 T 中需要重新和主串 S 中该字符进
14、行比较的字符的下标值。next 数组定义为： 10max|T,1,k-Tj,-k1,Tj-jnextjkjLL当 时 且其 它 情 况其中 nextj=k 表明，存在整数 k 满足条件 0n+1) return 0; /位置不合理返回 0 值GetNext(T,next); /计算 nextwhile(i=m) return(i-m+1); /匹配成功else return(0);void main()SString S,T;int pos,n;coutS;coutT;coutpos;if(n=Index_KMP(S,T,pos)coutLength_SS(S) return(0);第 4 章 串存储与基本操作的实现-.15.-while(Si+j&Tj) num+;if(Si+j=Tj)j+; /若字符相等，则继续比较后续字符elsei+; j=0; /若不相等，则重新开始新一轮比较if(!Tj) return(i+1); /若匹配成功，则返回 T 首次出现的开始位置else return(0); /若匹配不成功，则返回 0（2）函数 int IndexKMP(SString S,SString T,int& num)的功能是通过 KMP 算法返回串 T在 S
