中南大学数据结构与算法第4章串课后作业答案中南大学数据结构与算法第4章串课后作业答案.doc

第4章串习题练习答案 4.1 简述下列每对术语的区别：　　空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。答：　●空串是指不包含任何字符的串，它的长度为零。　　空白串是指包含一个或多个空格的串，空格也是字符。　●串常量是指在程序中只可引用但不可改变其值的串。　　串变量是可以在运行中改变其值的。　●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。　●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。　　动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。　●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。　●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 4.2 假设有如下的串说明：　　char s1[30]=Stocktom,CA, s2[30]=March 5 1999, s3[30], *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,s2)的返回值是什么?　(4)调用函数strcmp(s1[5],ton)的返回值是什么?　(5)调用函数stlen(strcat(s1,s2))的返回值是什么?解：　(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。　因此:　　执行p=stchr(s1,t);后p的值是指向第一个字符t的位置, 也就是p==s1[1]。　　执行p=strchr(s2,9);后p的值是指向s2串中第一个9所在的位置,也就是p==s2[9]。` 　执行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,Ca,March 5,1999　(3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)　(4)首先，我们要知道s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( s1[5],ton)中，前一个字符串值是tom,CA,用它和ton比较，应该是后者更大，所以返回值是小于0的数。　(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是Stocktom,CAMarch 5,1999,数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。 4.3 设T[0..n-1]=adaabaabcaabaa,P[0..m-1]=aab.当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。解：　　所有的有效位移i的值为：2，5，9。　　算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。 4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。解：　　算法如下：　void StrInsert(char *S, char *T, int i)　　{//将串T插入到串S的第i个位置上　　　char *Temp;　　　if(i=strlen(S))　　　　{　　　　　Temp