数据结构课程第二章部分习题解答

中央电大开放教育（）数据结构课程第二章部分习题解答第二章数组2-1设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。【解答】出局人的顺序为5,1,7,4,3,6,9,2,8。2-2试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5，以及n=9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。【解答】函数源程序清单如下：voidJosephus(intA[],intn,s,m){inti,j,k,tmp;if(m==0){coutm=0是无效的参数！endl;return;}for(i=0;in;i++)A[i]=i+1;/*初始化，执行n次*/i=s-1;/*报名起始位置*/for(k=n;k1;i--){/*逐个出局，执行n-1次*/if(i==k)i=0;i=(i+m-1)%k;/*寻找出局位置*/if(i!=k-1){tmp=A[i];/*出局者交换到第k-1位置*/for(j=i;jk-1;j++)A[j]=A[j+1];A[k-1]=tmp;}}for(k=0;kn/2;k++){/*全部逆置,得到出局序列*/tmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp;}}例：n=9,s=1,m=5012345678k=9123456789第5人出局,i=4k=8123467895第1人出局,i=0k=7234678915第7人出局,i=4k=6234689715第4人出局,i=2k=5236894715第3人出局,i=1k=4268934715第6人出局,i=1k=3289634715第9人出局,i=2中央电大开放教育（）k=2289634715第2人出局,i=0829634715第8人出局,i=0逆置517436928最终出局顺序例：n=9,s=1,m=0报错信息m=0是无效的参数！例：n=9,s=1,m=10012345678k=9123456789第1人出局,i=0k=8234567891第3人出局,i=1k=7245678931第6人出局,i=3k=6245789631第2人出局,i=0k=5457892631第9人出局,i=4k=4457892631第5人出局,i=1k=3478592631第7人出局,i=1k=2487592631第4人出局,i=0847592631第8人出局,i=0逆置136295748最终出局顺序当m=1时，时间代价最大。达到(n-1)+(n-2)+∙∙∙∙∙∙+1=n(n-1)/2O(n2)。2-3设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(en-1,en-2,…,e1,e0)。【解答】templateclassTypevoidinverse(TypeA[],intn){Typetmp;for(inti=0;i=(n-1)/2;i++){tmp=A[i];A[i]=A[n-i-1];A[n-i-1]=tmp;}}2-7设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。【解答】设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.2-9设有一个nn的对称矩阵A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。(3)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只中央电大开放教育（）存下三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。【解答】(1)数组B共有n+(n-1)++1=n*(n+1)/2个元素。(2)只存上三角部分时，若ij，则数组元素A[i][j]前面有i-1行（1i-1，第0行第0列不算)，第1行有n个元素，第2行有n-1个元素，，第i-1行有n-i+2个元素。在第i行中，从对角线算起，第j号元素排在第j-i+1个元素位置（从1开始），因此，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+2)+j-i+1=(2n-i+2)*(i-1)/2+j-i+1=(2n-i)*(i-1)/2+j若ij，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第(2n-j)*(j-1)/2+i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为当ij时，=(2n-i+1)*i/2+j-i=(2n-i-1)*i/2+j当ij时，=(2n-j-1)*j/2+i(3)只存下三角部分时，若ij，则数组元素A[i][j]前面有i-1行（1i-1，第0行第0列不算)，第1行有1个元素，第2行有2个元素，，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为1+2++(i-1)+j=(i-1)*i/2+j若ij，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第(j-1)*j/2+i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为当ij时，=i*(i+1)/2+j当ij时，=j*(j+1)/2+i2-10设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。【解答】111110111000nnnnaaaaaaA111110111000nnnnbbbbbbB中央电大开放教育（）计算公式2-14字符串的替换操作replace(String&s,String&t,String&v)是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。【解答】String&String::Replace(String&t,String&v){if((intid=Find(t))==-1)//没有找到，当前字符串不改，返回{coutThe(replace)operationfailed.endl;return*this;}Stringtemp(ch);//用当前串建立一个空的临时字符串ch[0]='\0';curLen=0;//当前串作为结果串，初始为空intj,k=0,l;//存放结果串的指针while(id!=-1){for(j=0;jid;j++)ch[k++]=temp.ch[j];//摘取temp.ch中匹配位置id前面的元素到结果串ch。curLen+=id+v.curLen;//修改结果串连接后的长度if(curLen=maxLen)l=v.curLen;//确定替换串v传送字符数lelse{l=curLen-maxLen;curLen=maxLen;}for(j=0;jl;j++)ch[k++]=v.ch[j];//连接替换串v到结果串ch后面if(curLen==maxLen)break;//字符串超出范围for(j=id+t.curLen;jtemp.curLen;j++)temp.ch[j-id-t.curLen]=temp.ch[j];//删改原来的字符串temp.curLen-=(id+t.curLen);id=temp.Find(t);}return*this;}2-15编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。【解答】1111121110122222212011211111101020100000nnnnnnnnnnnnnbaaaabbaaabbbaabbbbaC时当时当],][[],][[]][[jiijCjijiCjiA时当时当],1][[],1][[]][[jijiCjiijCjiB中央电大开放教育（）统计算法includeiostream.hincludestring.hvoidfrequency(String&s,char&A[],int&C[],int&k){//s是输入字符串，数组A[]中记录字符串中有多少种不同的字符，C[]中记录每//一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。inti,j,len=s.length();if(!len){coutThestringisempty.endl;k=0;return;}else{A[0]=s[0];C[0]=1;k=1;/*语句s[i]是串的重载操作*/for(i=1;ilen;i++)C[i]=0;/*初始化*/for(i=1;ilen;i++){/*检测串中所有字符*/j=0;while(jk&&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\0AcastbC27455【另一解答】includeiostream.hincludestring.hconstintcharnumber=128;/*ASCII码字符集的大小*/voidfrequen