严蔚敏《数据结构(c语言版)习题集》答案第五章 数组和广义表文库

《严蔚敏《数据结构(c语言版)习题集》答案第五章 数组和广义表文库》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表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、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[12]->A[3],A[3]->A[9],A[9]->A[0].第二条

3、链: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][j];//求一行中的最小值for(j=0;j

5、层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志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;for(x=1;x<=A.mu;x++)//对矩阵的每一行进行加法{while(A.data[pa].i

6、.i==x&&B.data[pb].i==x)//行列值都相等的元素{if(A.data[pa].j==B.data[pb].j){ce=A.data[pa].e+B.data[pb].e;if(ce)//和不为0{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=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.dat

7、a[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++;}}//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中剩余的元

8、素(第x行){C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}}//forC.tu=pc;}//TSMatrix_Add5.22voidTSMatrix_Addto(T