数据结构课后答案

《数据结构课后答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题答案网http://www.jiexi360.cn第五章数组和广义表5.18voidRSh(intA[n],intk)//把数组A的元素循环右移k位,只用一个辅助存储空间{for(i=1;i<=k;i++)if(n%i==0&&k%i==0)p=i;//求n和k的最大公约数pfor(i=0;i

2、}//RSh分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:n=15,k=6,则p=3.第一条链:A[0]->A[6],A[6]->A[12],A[

3、12]->A[3],A[3]->A[9],A[9]->A[0].第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.5.19voidGet_Saddle(intA[m][n])//求矩阵A中的马鞍点{for(i=0;i

4、in=A[i][0],j=0;j

5、j,A[i][j]);}}//for}//Get_Saddle5.20本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复.5.21voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&C)//三元组表示的稀疏矩阵加法{C.mu=A.mu;C.nu=A.nu;C.tu=0;pa=1;pb=1;pc=1;f

6、or(x=1;x<=A.mu;x++)//对矩阵的每一行进行加法{while(A.data[pa].i

7、=ce;pa++;pb++;pc++;}}//ifelseif(A.data[pa].j>B.data[pb].j){C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}else{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].epa++;pc++;习题答案网http://www.jiexi360.cn习题答案网http://www.j

8、iexi360.cn}}//whilewhile(A.data[pa]==x)//插入A中剩余的元素(第x行){C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].epa++;pc++;}while(B.data[pb]==x)//插入B中剩余的元素(第