PTA（顺序表）2-12 线性表循环右移

zhangzhang2025-10-142025-10-14

2-12 线性表循环右移

分数 8

作者陈越

单位浙江大学

给定顺序表 A=(a1,a2,⋯,a**n)，请设计一个时间和空间上尽可能高效的算法将该线性表循环右移指定的 m 位。例如，(1,2,5,7,3,4,6,8) 循环右移 3 位（m=3) 后的结果是 (4,6,8,1,2,5,7,3)。

输入格式：

第一行输入 n ( 1≤n≤105)、m（m≥0）；第二行输入 n 个整数。所有数字在 int 型整数范围内，同行数字间以空格分隔。

输出格式：

输出循环右移 m 位以后的整数序列。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

1 2	6 2 1 2 3 4 5 6

输出样例：

1	5 6 1 2 3 4

答案

#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int n) {
    L.data = new int[n];
    L.length = 0;
}

// 将下标为left到right元素的顺序颠倒
void reverseElem(sqList &L, int left, int right) {
    while (left < right) {
        int temp = L.data[left];
        L.data[left] = L.data[right];
        L.data[right] = temp;
        left++;
        right--;
    }
}

// 三次反转法右移
void rightMove(sqList &L, int m, int n) {
    if (m == 0) { // 不需要移动
        return;
    }
    reverseElem(L, 0, n-1); // 整体反转
    reverseElem(L, 0, m-1);
    reverseElem(L, m, n-1);
}


int main() {
    int n, m;
    cin >> n >> m;
    sqList L;
    initList(L, n);
    // 读取数据进入顺序表
    for (int i = 0; i < n; ++i) {
        cin >> L.data[i];
        L.length++;
    }
    // 开始三次反转法
    m = m % n;
    rightMove(L, m, n);

    // 输出移动后的结果
    for (int i = 0; i < L.length; ++i) {
        if (i != 0) {
            cout << " ";
        }
        cout << L.data[i];
    }
}