第4章串1.字符串的替换操作replace(String&s,String&t,String&v)是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为"aabbabcbaabaaacbab"，串t为"bab"，串v为"abdc"，则执行replace操作后，串s中的结果为"aababdccbaabaaacabdc"。试利用字符串的基本运算实现这个替换操作。【解答】Replace(String&t,String&v){if((intid=Find(t))==-1)//没有找到，当前字符串不改，返回{printf("The(replace)operationfailed.\n";return;}Stringtemp(ch);//用当前串建立一个空的临时字符串ch[0]='\0';curLen=0;//当前串作为结果串，初始为空intj,k=0,l;//存放结果串的指针while(id!=-1){for(j=0;j<id;j++)ch[k++]=temp.ch[j];//摘取temp.ch中匹配位置if(curLen+id+v.curLen<=maxLen)l=v.curLen;//确定替换串v传送字符数lelsel=maxLen-curLen-id;for(j=0;j<l;j++)ch[k++]=v.ch[j];//连接替换串v到结果串ch后面curLen+=id+l;//修改结果串连接后的长度if(curLen==maxLen)break;//字符串超出范围for(j=id+t.curLen;j<temp.curLen;j++)temp.ch[j-id-t.curLen]=temp.ch[j];//删改原来的字符串temp.curLen-=id+t.curLen;id=temp.Find(t);}return;}2.编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。【解答】include<iostream.h>include"string.h"voidfrequency(String&s,charA[],intC[],int&k){//s是输入字符串，数组A[]中记录字符串中有多少种不同的字符，C[]中记录每//一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。inti,j,len=s.length();if(!len){printf("Thestringisempty.\n");k=0;return;}else{A[0]=s[0];C[0]=1;k=1;/*语句s[i]是串的重载操作*/for(i=1;i<len;i++)C[i]=0;/*初始化*/for(i=1;i<len;i++){/*检测串中所有字符*/j=0;while(j<k&&A[j]!=s[i])j++;/*检查s[i]是否已在A[]中*/if(j==k){A[k]=s[i];C[k]++;k++}/*s[i]从未检测过*/elseC[j]++;/*s[i]已经检测过*/}}}测试数据s="castcastsatatatasa\0"【另一解答】include<iostream.h>include"string.h"constintcharnumber=128;/*ASCII码字符集的大小*/voidfrequency(Strings,int&C[]){//s是输入字符串，数组C[]中记录每一种字符的出现次数。for(inti=0;i<charnumber;i++)C[i]=0;/*初始化*/for(i=0;i<s.length();i++)/*检测串中所有字符*/C[atoi(s[i])]++；/*出现次数累加*/for(i=0;i<charnumber;i++)/*输出出现字符的出现次数*/if(C[i]>0)cout<<"("<<i<<"):\t"<<C[i]<<"\t";}3.设串s为"aaab"，串t为"abcabaa"，串r为"abcaabbabcabaacbacba"，试分别计算它们的失效函数f(j)的值。【解答】4.设定整数数组B[m+1][n+1]的数据在行、列方向上都按从小到大的顺序排序，且整型变量x中的数据在B中存在。试设计一个算法，找出一对满足B[i][j]==x的i,j值。要求比较次数不超过m+n。【解答】算法的思想是逐次二维数组右上角的元素进行比较。每次比较有三种可能的结果：若相等，则比较结束；若右上角的元素小于x，则可断定二维数组的最上面一行肯定没有与x相等的数据，下次比较时搜索范围可减少一行；若右上角的元素大于x，则可断定二维数组的最右面一列肯定不包含与x相等的数据，下次比