数据结构域算法设计-第5章 数组和广义表教案

《数据结构域算法设计-第5章 数组和广义表教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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的最大公约数p  for(i=0;i

2、i]=temp;  }//for}//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]

3、,A[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、=A[i][0],j=0;j

5、      }  }//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;  for(x=1;x<=

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

7、=x;          C.data[pc].j=A.data[pa].j;          C.data[pc].e=ce;          pa++;pb++;pc++;        }      }//if      elseif(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++;      }   

8、   else      {        C.data[pc].i=x;        C.data[pc].j=A.data[pa].j;