实验案例2-2：数组元素循环右移问题

69 阅读 0 评论 46 点赞

我是靠谱客的博主冷艳大炮，最近开发中收集的这篇文章主要介绍实验案例2-2：数组元素循环右移问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.C++方法，利用rotate函数

rotate(beg, mid, end),该函数接受三个迭代器，将迭代器所在的容器的元素循环移动，使得mid元素成为首元素，随后是mid + 1到end之前的元素，
再接着是beg到mid 之间的元素，返回一个迭代器，指向原来在beg位置的元素
rotate_copy(beg, mid, end, dest),即将变换过后的元素保存在目的容器的dest位置

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int N, M, i;
10     vector<int> vec;
11     cin >> N >> M;
12     int mount = N;
13     while (mount--)
14     {
15         cin >> i;
16         vec.push_back(i);
17 
18     }
19     rotate(vec.begin(),  vec.end() - (M % N), vec.end());        //循环右移
20     //rotate(vec.begin(), vec.begin() + (M % N), vec.end());    //循环左移
21     vector<int>::const_iterator iter;
22     for (iter = vec.begin(); iter != vec.end() - 1; ++iter)
23         cout << *iter << " ";
24     cout << *iter << endl;
25     return 0;
26 }

2.C的一般方法：

先写一个循环右移一位的函数，然后调用该函数M次，即可使数组循环右移M位

 1 #include <stdio.h>
 2 #define MAXN 100
 3 
 4 void CircleMove(int *array, int N);
 5 
 6 int main()
 7 {
 8     int Number[MAXN], N, M;
 9     int i;
10     scanf_s("%d %d", &N, &M);
11     for (i = 0; i < N; i++)
12     {
13         scanf_s("%d", &Number[i]);
14     }
15     M %= N;            //当M大于等于N时转化成等价的小于N的数
16     for (i = 0; i < M; i++)            //调用移位函数M次
17         CircleMove(Number, N);
18     for (i = 0; i < N -1; i++)
19         printf("%d ", Number[i]);
20     printf("%d", Number[i]);
21     return 0;
22 }
23 
24 void CircleMove(int *array, int N)
25 {
26     int i, ArrayEnd;
27     ArrayEnd = array[N - 1];        //先最后一个元素记录下来，因为待会会被覆盖掉
28     for (i = N -1; i > 0; i--)
29         array[i] = array[i - 1];
30     array[0] = ArrayEnd;
31 }

3.C的简单解法

先用宏定义define 定义一个两个数相交换的的函数，该函数利用了三次异或运算符

异或运算符有一个性质，假如 a ^ b = c;那么 a ^ c = b; b ^ c = a;

#define Swap(a, b) a^ = b, b ^= a, a ^= b;　　　　//交换两个数的宏定义函数，

对这个函数的解读：

a ^= b 就是 a = a ^ b,此时a 等于上面说的C

b ^= a,就是 b = b ^ a,注意，这里的a 已经变成C了，所以相当于 b = b ^ C ---> b = a;

同理，a ^= b,就是 a = a ^ b,需要注意的是，等式右边的a在第一步变换中变成了C，b 在第二步变换中变成了a, 所以这个等式就相当于a = C ^ a ------> a = b;

所以就完成了交换。

接下来程序中利用三次逆转，实现了循环右移M位，（这种方法很神奇）

第一次：逆转整个数组

第二次：在第一步的基础上逆转数组前M个元素

第三次: 逆转数组后N- M个元素

 1 #include <stdio.h>
 2 #define MAXN 100
 3 #define Swap(a, b) a^= b, b^= a, a ^= b;    //通过连续三次以后运算符交换a与b
 4 
 5 void RightShift(int array[], int N, int M);
 6 
 7 int main()
 8 {
 9     int Number[MAXN], N, M;
10     int i;
11     scanf_s("%d %d", &N, &M);
12     for (i = 0; i < N; i++)
13         scanf_s("%d", &Number[i]);
14     M %= N;
15     RightShift(Number, N);
16     for (i = 0; i < N - 1; i++)
17         printf("%d", Number[i]);
18     printf("%d", Number[N - 1]);
19     return 0;
20 }
21 
22 void RightShift(int array[], int N, int M)
23 {
24     int i, j;
25     if (M > 0 && M < N)
26     {
27         for (i = 0, j < N - 1; i < j; i++, j--)        //逆转N个数据
28             Swap(array[i], array[j]);                
29         for (i = 0, j < M - 1; i < j; i++, j--)        //逆转前M个数据
30             Swap(array[i], array[j]);
31         for (i = M, j = N - 1; i < j; i++, j--)        //逆转后N - M个数据
32             Swap(array[i], array[j]);
33     }
34 }