5.18.c

来自「部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)」· C语言 代码 · 共 36 行

5.18⑤  试设计一个算法，将数组A中的元素
A[0..n-1]循环右移k位，并要求只用一个元素
大小的附加存储，元素移动或交换次数为O(n)。

要求实现以下函数：
void Rotate(Array1D &a, int n, int k);

一维数组类型Array1D的定义：
typedef ElemType Array1D[MAXLEN];
void Rotate(Array1D &a, int n, int k)
/* a[n] contains the elements,          */
/* rotate them right circlely by k sits */
{  
 int round,pos1,pos2,i,temp;
 for(i=1;i<=k;i++)
   if(k%i==0&&n%i==0) round=i;
 for(i=0;i<round;i++)
    {
     pos1=pos2=(n+(i-k)%n)%n;
     temp=a[pos1];
     for(;;)
       {
       if(pos1!=i)
         {
          pos1=(n+(pos1-k)%n)%n;
          a[pos2]=a[pos1];     //a[pos1]存放即将替换a[pos2]的数值
          pos2=pos1;
           }
       else break;
       }
     a[pos1]=temp;
      }

}