题目

设将n（n>1)个整数存放到一堆一维数组R中，设计一个算法，将R中的序列循环左移P(0<P<n)个位置，即将R中的数据由 $\{X_0,X_1,...,X_{n-1}\}$ 变换为 $\{X_p,X_{p+1},...,X_{n-1},X_0,X_1,...,X_{p-1}\}$。要求：写出本题的算法描述。

分析

要实现R中序列循环左移P个位置，只需先将R中前P个元素逆置，再将剩下的元素逆置，最后将R中所有的元素再整体做一次逆置操作即可。

例如：

$Array[5]=\{A,B,C,D,E\} \\\Rightarrow Array[5]=\{B,A,C,D,E\} \\\Rightarrow Array[5]=\{B,A,E,D,C\} \\\Rightarrow Array[5]=\{C,D,E,A,B\}$

算法描述

void Reverse(int R[], int l, int r)
{
    int i, j;
    int temp;
    for (i = l, j = r; i < j; ++i, --j)
    {
        temp = R[i];
        R[i] = R[j];
        R[j] = temp;
    }
}
void RCR(int R[], int n, int p)
{
    if (p <= 0 || p >= n)
        cout << "ERROR" << endl;
    else
    {
        Reverse(R, 0, p - 1);
        Reverse(R, p, n - 1);
        Reverse(R, 0, n - 1);
    }
}

完整写法(C++)

#include <iostream>
#define N 50
using namespace std;
void Reverse(int R[], int l, int r)
{
    int i, j;
    int temp;
    for (i = l, j = r; i < j; ++i, --j)
    {
        temp = R[i];
        R[i] = R[j];
        R[j] = temp;
    }
}
void RCR(int R[], int n, int p)
{
    if (p <= 0 || p >= n)
        cout << "ERROR" << endl;
    else
    {
        Reverse(R, 0, p - 1);
        Reverse(R, p, n - 1);
        Reverse(R, 0, n - 1);
    }
}
int main()
{
    int L, i;
    int R[N], n;
    cout << "请输入左移个数"<<endl;
    cin >> L;
    cout << "请输入数组长度"<<endl;
    cin >> n;
    cout << "请输入数组元素"<<endl;
    for (i = 0; i <= n - 1; ++i)
        cin >> R[i];
    RCR(R, n, L);
    cout << "原数组左移"<<L<<"个位置的结果为："<<endl;
    for (i = 0; i <= n - 1; ++i)
        cout << R[i] << " ";
    cout << endl;
    return 0;
}

扩展

问题

若需要将数组元素循环右移P个位置，请写出算法。

分析

要实现R中序列循环右移P个位置，只需先将R中所有的元素再整体做一次逆置操作，再将R中前P个元素逆置，最好将剩下的元素逆置即可。

算法描述

void Reverse(int R[], int l, int r)
{
    int i, j;
    int temp;
    for (i = l, j = r; i < j; ++i, --j)
    {
        temp = R[i];
        R[i] = R[j];
        R[j] = temp;
    }
}
void RCR(int R[], int n, int p)
{
    if (p <= 0 || p >= n)
        cout << "ERROR" << endl;
    else
    {
        Reverse(R, 0, n - 1);
        Reverse(R, 0, p - 1);
        Reverse(R, p, n - 1);
    }
}