串习题及答案

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

2、at(s3,","); strcat(s3,s2);(3) 调用函数strcmp(s1 ,s2的返回值是什么？(4) 调用函数strcmp(&s1,"ton")的返回值是什么？(5) 调用函数stlen(strcat(s1 ,s2)的返回值是什么？设 T0.n-1=,adaabaabcaabaa",P0.m-1="aab"当用模式串匹配目标串 T 时，请 给出所有的有效位移。算法NaiveStrMatch(T,P返回的位移是哪一个位移。二' 算法设计题：利用 C 的库函数 strlen,strcpy 和 st

3、rcat 写一算法 void Strlnsert(char *S,char *T,int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。利用 C 的库函数 strlen 和 strcpy(或 strncpy)写一算法 void StrDelete(char *S,inti,int m)删去串S中从位置i开始的连续m个字符。若i > strlen(S则没有字符 被删 除；若i+m>strlen(S则将S中从位置i开始直至末尾的字符均删去。以HString为存储表示，写一个求子串的算法。一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为:abcde

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

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

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

7、，则此次位移就是无效位移(也 就是从此位置开始的匹配失败)o4、2解：stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位 置，否则返回NULL。因此：执行p=stchr(s1 后p的值是指向字符t的位置 也就是p=&s1。执行p=strchr(s2,9);后p的值是指向s2串中第一个9所在的位置 也就是 p=&s29 o执行p=strchr(s2,'6');之后，p的返回值是NULL。(2) strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以：在执行 strcpy(s3,s1)后，s3 的值是"Stockto

8、in,CA"在执行 strcat(s3,",");后,s3 的值变成"Stocktom,Ca,"在执行完 strcat(s3,s2)后，s3 的值就成了 "Stocktom,Ca,March 5,1999"(3) 函数strcmp(串1,串2)的功能是串比较，按串的大小进行比较，返回大 于0, 等于0或小于0的值以表示串1比串2大，串1等于串2,串1小于串2o因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码 值相 比的)(4) 首先我们要知道&s 1 5是一个地址，当放在函数s

9、trcmp中时,它就表 示指向以它为首地址的一个字符串，所以在strcmp( &s15,"ton")中，前一个字符串值是"tom,CA",用它和"ton"比较，应该是后者更大，所以返回值是小于0的数。(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是 "Stocktom,CAMarch5,1999"数一数有几个字符？是不是23个(空格也是一个)？所以 返 回值是23o4、3解：所有的有效位移i的值如下：2, 5, 9O算法NaveStrMatch(T,P的返回值是第一个有效位移，因此是 2。

10、二、算法设计题：解：算法如下：void Strlnsert(char *S, char *T, int i) char BMaxsize=Hvery coolH;Strlnsert( A,B,7);printf(n%sH,A);void Strlnsert(char *S, char *T, int i),17；HString B=,amn,2;printf(n%snn3;printf(n%snH,;printf(Hn%sH,StringMatch( &A,&B);char* StringMatch( HString *T, HString *P)；解：这个算法是具有实用性的，

11、但是做起来比较难，简单的算法应是这样的，利用 的算法在串T中找到一个P的匹配成功，马上进行串替换，然后从替 换后的下一个位置 进行匹配，直到查找完所有的有效位移或者所有合法位移考查完毕也没有匹配成功。算法如下：void StrReplaceAII(char *T, char *P, char *S) char B=ngoodn;char C=nvery cool”；printf(nThe original string is: %sn,A);printf(Hn%s%sh5B,C);StrReplaceAII( A,B,C);printf("nThe new String is:%s”,A);void StrDelete(char *S, int i ,int m