阵列旋转反转算法的C程序-yiteyi-C++库

编写一个函数rotate（arr[]，d，n），将大小为n的arr[]旋转d个元素。

null

例子：

Input:  arr[] = [1, 2, 3, 4, 5, 6, 7]
         d = 2
Output: arr[] = [3, 4, 5, 6, 7, 1, 2]

Array

将上述阵列旋转2将生成阵列

ArrayRotation1

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

算法：

rotate(arr[], d, n)
  reverse(arr[], 1, d) ;
  reverse(arr[], d + 1, n);
  reverse(arr[], 1, n);

设AB是输入数组的两部分，其中A=arr[0..d-1]和B=arr[d..n-1]。该算法的思想是：

反转A得到ArB，其中Ar是A的反转。
反转B以获得ArBr，其中Br是B的反转。
全部反转以获得（ArBr）r=BA。

例子： 让数组arr[]=[1,2,3,4,5,6,7]，d=2，n=7 A=[1,2]和B=[3,4,5,6,7]

反过来，我们得到ArB=[2,1,3,4,5,6,7]
反向B，我们得到ArBr=[2,1,7,6,5,4,3]
全部倒转，我们得到（ArBr）r=[3,4,5,6,7,1,2]

下面是上述方法的C实现：

                       // C/C++ program for reversal algorithm of array rotation                     
                       #include <stdio.h>                     
                                
                       /*Utility function to print an array */                     
                       void                                  printArray(                                  int                                  arr[],                                  int                                  size);                     
                                
                       /* Utility function to reverse arr[] from start to end */                     
                       void                                  rvereseArray(                                  int                                  arr[],                                  int                                  start,                                  int                                  end);                     
                                
                       /* Function to left rotate arr[] of size n by d */                     
                       void                                  leftRotate(                                  int                                  arr[],                                  int                                  d,                                  int                                  n)                     
                       {                     
                                             rvereseArray(arr, 0, d - 1);                     
                                             rvereseArray(arr, d, n - 1);                     
                                             rvereseArray(arr, 0, n - 1);                     
                       }                     
                                
                       /*UTILITY FUNCTIONS*/                     
                       /* function to print an array */                     
                       void                                  printArray(                                  int                                  arr[],                                  int                                  size)                     
                       {                     
                                             int                                  i;                     
                                             for                                  (i = 0; i < size; i++)                     
                                             printf                                  (                                  "%d "                                  , arr[i]);                     
                       }                     
                                
                       /*Function to reverse arr[] from index start to end*/                     
                       void                                  rvereseArray(                                  int                                  arr[],                                  int                                  start,                                  int                                  end)                     
                       {                     
                                             int                                  temp;                     
                                             while                                  (start < end) {                     
                                             temp = arr[start];                     
                                             arr[start] = arr[end];                     
                                             arr[end] = temp;                     
                                             start++;                     
                                             end--;                     
                                             }                     
                       }                     
                                
                       /* Driver program to test above functions */                     
                       int                                  main()                     
                       {                     
                                             int                                  arr[] = { 1, 2, 3, 4, 5, 6, 7 };                     
                                             int                                  n =                                  sizeof                                  (arr) /                                  sizeof                                  (arr[0]);                     
                                             int                                  d = 2;                     
                                             leftRotate(arr, d, n);                     
                                             printArray(arr, n);                     
                                             return                                  0;                     
                       }                     

输出：

3 4 5 6 7 1 2

时间复杂性： O（n）

请参阅完整的文章阵列旋转的反转算法更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章