第四章-串-习题及答案

第四章串习题及答案一、基础知识题4.1简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。4.2假设有如下的串说明：chars1[30]=Stocktom,CA,s2[30]=March51999,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))的返回值是什么?4.3设T[0..n-1]=adaabaabcaabaa,P[0..m-1]=aab.当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。二、算法设计题：4.4利用C的库函数strlen,strcpy和strcat写一算法voidStrInsert(char*S,char*T,inti),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。4.5利用C的库函数strlen和strcpy(或strncpy)写一算法voidStrDelete(char*S,inti,intm)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。4.6以HString为存储表示，写一个求子串的算法。4.7一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj则字符串encrypt被加密为tkzwsdf.试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。4.8写一算法voidStrReplace(char*T,char*P,char*S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。4.9将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。*4.10利用4.9的结果写一算法voidStrReplaceAll(char*T,char*P,char*S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。4.11若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。答案：4.1简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。答：空串是指不包含任何字符的串，它的长度为零。空白串是指包含一个或多个空格的串，空格也是字符。串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。4、2解：(1)stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。因此:执行p=stchr(s1,'t');后p的值是指向字符t的位置,也就是p==&s1[5]。执行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,March5,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,CAMarch5,1999,数一数有几个字符?是不是23个(空格也是一个)?所以返回值是23。4、3解：所有的有效位移i的值如下：2，5，9。算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。二、算法设计题：4.4解：算法如下：voidStrInsert(char*S,char*T,inti){//将串T插入到串S的第i个位置上char*Temp;Temp=(char*)malloc(sizeof(char[Maxsize]));//设置一个临时串if(i=strlen(S)){strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中strcpy(&S[i],T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符strcat(S,Temp);//把临时串中的字符联接到串S后面free(Temp);}}//以下提供验证程序#includestring.h#includestdio.h#includemalloc.h#defineMaxsize50//假设静态顺序串的空间长度为100voidStrInsert(char*S,char*T,inti);voidmain(){charA[Maxsize]=Iamaboy.;charB[Maxsize]=verycool;StrInsert(A,B,7);printf(%s,A);}voidStrInsert(char*S,char*T,inti){//将串T插入到串S的第i个位置上char*Temp;Temp=(char*)malloc(sizeof(char[Maxsize]));//设置一个临时串if(i=strlen(S)){strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中strcpy(&S[i],T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符strcat(S,Temp);//把临时串中的字符联接到串S后面}free(Temp);}//程序结束4.5解：算法如下：voidStrDelete(char*S,inti,intm){//串删除charTemp[Maxsize];//定义一个临时串if(i+mstrlen(S)){strcpy(Temp,&S[i+m]);//把删除的字符以后的字符保存到临时串中strcpy(&S[i],Temp);//用临时串中的字符覆盖位置i之后的字符}elseif(i+m=strlen(S)&&istrlen(S)){strcpy(&S[i],\0);//把位置i的元素置为'\0'，表示串结束}}//以下是验证程序#includestring.h#includestdio.h#defineMaxsize40voidStrDelete(char*S,inti,intm);voidmain(){charA[Maxsize]=Areyouaverybeautifulgirl?;StrDelete(A,40,10);printf(\n%s,A);StrDelete(A,10,15);printf(\n%s,A);StrDelete(A,7,50);printf(\n%s\n,A);}voidStrDelete(char*S,inti,intm){charTemp[Maxsize];//定义一个临时串if(i+mstrlen(S)){strcpy(Temp,&S[i+m]);//把删除的字符以后的字符保存到临时串中strcpy(&S[i],Temp);//用临时串中的字符覆盖位置i之后的字符}elseif(i+m=strlen(S)&&istrlen(S)){strcpy(&S[i],\0);//把位置i的元素置为'\0'，表示串结束}}4.6解：HString是指以动态分配顺序串为存储表示，其定义为：typedefstruct{char*ch;intlength;}HString/*要进行这个算法设计，我们考虑到字符串是以指针的形式表示的，匹配时，用双重循环来实现，外循环用于进行合法位移(即令一指针沿目标串的元素向右移位)内循环进行字符匹配(即令两指针同时沿着目标串和模式串的元素进行移动并比较。直到第一次匹配成功或最终匹配失败。*/char*StringMatch(HString*T,HString*P){//串匹配char*t,*p;intm,n;for(m=0;m=T-length-P-length;m++)//进行合法位移{t=&(T-ch[m]);//指针t指向目标串的当前字符p=&(P-ch[0]);//指针q指向模式串的第一个字符for(n=0;nP-length&&p[n]==t[n];n++);//进行匹配,若有不同字符则进行下一次位移if(n==P-length){return&(T-ch[m]);}//返回第一次有效位移的地址}returnNULL;//匹配失败}//以下是验证程序#includestdio.h#includestring.htypedefstruct{char*ch;intlength;}HString;char*StringMatch(HString*T,HString*P);voidmain(){HStringA={Iamyourfriend.,17};HStringB={am,2};printf(%s\n,A.ch);printf(%s\n,B.ch);printf(\n%s,StringMatch(&A,&B));}char*StringMatch(HString*T,HString*P){//串匹配char*t,*p;intm,n;for(m=0;mT-length-P-length;m++)//进行合法位移{t=&(T-ch[m]);//指针t指向目标串的当前字符p=&(P-ch[0]);//指针q指向模式串的第一个字符for(n=0;nP-length&&p[n]==t[n];n++);//进行匹配,若有不同字符则进行下一次位移if(n==P-length){return&(T-ch[m]);}//返回第一次有效位移的地址}returnNULL;//匹配失败}4.7解：加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串1中查找其位置，然后