串习题及答案

1、第四章串习题及答案、基础知识题简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态 分配的顺序串；目标串和模式串；有效位移和无效位移。假设有如下的串说明：char s130=Stocktom,CA, s230=March 5 1999, s330, *p;(1) 在执行如下的每个语句后 p 的值是什么 ?p=stchr(s1,t); p=strchr(s2,9); p=strchr(s2,6);(2) 在执行下列语句后， s3 的值是什么 ?strcpy(s3,s1); strcat(s3,); strcat(s3,s2);(3) 调用函数strcmp(s1

2、,s2的返回值是什么？(4) 调用函数strcmp(&s15,ton)的返回值是什么？(5) 调用函数stlen(strcat(s1,s2)的返回值是什么？设 T0.n-1=adaabaabcaabaa,P0.m-1=aab当用模式串匹配目标串 T 时，请给出所有的有效位移。算法 NaiveStrMatch(T,P返回的位移是哪一个位 移。二、算法设计题：利用 C 的库函数 strlen,strcpy 和 strcat 写一算法 void StrInsert(char *S,char *T,int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。利用 C 的库函数 str

3、len 和 strcpy(或 strncpy)写一算法 void StrDelete(char *S,inti,int m)删去串S中从位置i开始的连续m个字符。若i strlen(S则没有字符 被删除；若i+mstrlen(S则将S中从位置i开始直至末尾的字符均删去。以 HString 为存储表示，写一个求子串的算法。一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表 为：a b c d e f g h i j k l m n o p q r s t u v w x y zn g z q t c o b m u h e l k p d a w x f y i v r s j则字符

4、串encrypt被加密为tkzwsdf.试写一算法将输入的文本串进行加密 后输出；另写一算法，将输入的已加密的文本串进行解密后输出。写一算法 void StrReplace(char *T, char *P, char *5将 T 中首次出现的子串 P 替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。将 NaveStrMatch 改写为输出目标串中所有也模式串匹配的有效位移。* 利用的结果写一算法 void StrReplaceAll(char *T, char *P, char *S) T 中出 现的所有与P相等的不重叠子串替换为S,这里S和P的长度不一定相等。若S和T是用结

5、点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。答案：简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态 分配的顺序串；目标串和模式串；有效位移和无效位移。答：空串是指不包含任何字符的串，它的长度为零。空白串是指包含一个或多个空格的串，空格也是字符。串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子 串，而包含子串的串就称为主串。静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态 的，在编译时刻就被确定。动态分配的顺序串

6、是在编译时不分配串值空间，在运行过程中用malloc 和free 等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间 )。目标串和模式串 :在串匹配运算过程中，将主串称为目标串，而将需要匹配 的子串称为模式串，两者是相对的。有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位 移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是 有效位移 (也就是从此位置开始的匹配成功 )，反之，若有不相同的字符存在，则 此次位移就是无效位移 (也就是从此位置开始的匹配失败 )。4、2解：(1) stchr(*s,c)函数的功能是查找字符c在串

7、s中的位置，若找到，则返 回该位置，否则返回 NULL。因此:执行p=stchr(s1,t);后p的值是指向字符t的位置 也就是p=&s15。执行p=strchr(s2,9);后p的值是指向s2串中第一个9所在的位置 也就是p=&s29。执行p=strchr(s2,6);之后，p的返回值是NULL。(2) strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以：在执行 strcpy(s3,s1)后，s3 的值是Stocktom,CA在执行 strcat(s3,);后，s3 的值变成Stocktom,Ca,在执行完 strcat(s3,s2)后，s3 的值就成了 Stocktom,C

8、a,March 5,1999(3) 函数strcmp(串1,串2)的功能是串比较，按串的大小进行比较，返回大 于 0，等于 0 或小于 0 的值以表示串 1 比串 2 大，串 1 等于串 2，串 1 小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码 值相比的 )(4) 首先,我们要知道 &s 1 5是一个地址,当放在函数 strcmp 中时,它就表示指向以它为首地址的一个字符串,所以在 strcmp( &s15,ton) 中,前一个字 符串值是tom,CA,用它和ton比较，应该是后者更大，所以返回值是小于0的数。(5)strlen是求串长的函

9、数，我们先将s1,s2联接起来，值是Stocktom,CAMarch5,1999数一数有几个字符？是不是23个(空格也是一个)?所以 返回值是 23。4、3 解：所有的有效位移 i 的值如下： 2, 5, 9。算法NaveStrMatch(T,P的返回值是第一个有效位移，因此是2。二、算法设计题：解：算法如下：void Strln sert(char *S, char *T, i nt i)5char BMaxsize=very cool ;Strlnsert( A,B,7);printf(%s,A);void Strlnsert(char *S, char *T, int i),17;HSt

10、ring B=am,2;printf(%sn,;printf(%sn,;printf(n%s,StringMatch( &A,&B);char* StringMatch( HString *T, HString *P);解：这个算法是具有实用性的，但是做起来比较难，简单的算法应是这样 的，利用的算法在串 T 中找到一个 P 的匹配成功，马上进行串替换，然后从替 换后的下一个位置进行匹配，直到查找完所有的有效位移或者所有合法位移考 查完毕也没有匹配成功。算法如下：void StrReplaceAll(char *T, char *P, char *S)5char B=good;char C=very cool;printf(The original string is: %s,A);printf(n%s-%s,B,C);StrReplaceAll( A,B,C);printf(nThe new String is:%s,A);void StrDelete(char *S, int i ,int m)char Temp