数据结构习题及答案

				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				   if(k%i==0&&n%i==0) round=i;
				 for(i=0;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;
				      }
				
				}