C数据结构题目

来源：百度知道 编辑：UC知道 时间：2024/06/05 15:33:41
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 */

一维数组类型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;
}
}
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],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[