《数据结构》-第五章 数组和广义表

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

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、要把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[12]->A[3],A[3]->A[9],A[9]->A[0].第二条链:A[1]->A[7]

3、,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、;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、=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++;        }      }//if      elseif(A.data[pa].j>B.data[pb].j) 

7、     {        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;