(PAT)BasiclLevel_c++ #1008 数组元素循环右移问题

题目描述：

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A₀​ A₁⋯A_​N−1）变换为（A​_N−M​​ ⋯A​_N−1​​ A​₀​​ A​₁​​ ⋯A​_N−M−1​​）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式：

每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。

输出格式：

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：

6 2
1 2 3 4 5 6

输出样例：

5 6 1 2 3 4

思路：
很显然只要让这些数字组成一个循环，我们输出的时候，从后面指定个数的数字开始输出，循环一遍输出完毕就可以了，因此这里用循环链表作为存储结构

有一个需要注意的小问题就是，我们要移动的个数不一定小于数字总个数，
也就是说，我们又可能会移动超过一个循环的距离

代码实现：

#include <iostream>
#include <string>
#include <math.h>
using namespace std;
typedef class LNode* PtrToNode;
//循环链表
class LNode
{
public:
int data;
PtrToNode next;
public:
LNode()
{
data = 0;
next = NULL;
}
LNode(int data)
{
this->data = data;
next = NULL;
}
};
class List
{
public:
PtrToNode head;
PtrToNode tail;
public:
List()
{
head = tail = new LNode();
head->next = NULL;
}
void append(int data)
{
//尾部追加元素
tail->next = new LNode(data);
//如果为空，
if (head->next == NULL)
{
head->next = tail->next;
}
//尾指针后移
tail = tail->next;
//循环指向首节点
tail->next = head->next;
}
void print()
{
PtrToNode temp = head->next;
while (temp != tail)
{
if (temp != head->next)
{
cout << " ";
}
cout << temp->data;
temp = temp->next;
}
if (head->next == tail)
{
cout << temp->data;
}
else
{
cout << " " << temp->data;
}
}
};
//上面就是循环链表的简单定义和基本操作，没什么难的
//我用的是带头结点的，其实这里不涉及头部的插入删除，用不带头结点的可能会更好理解
int main()
{
int m, n;
cin >> n >> m;
//存入链表
List* list = new List();
for (int i = 0; i < m; i++)
{
int data;
cin >> data;
list->append(data);
}
//循环移位，移动头指针的位置
//这里的循环终止条件要注意，我们是要把指针移动到后面m个的起始处，
//所以并不是简单的移动 （m % n） 个
for (int i = 0; i < n - m % n; i++)
{
list->head->next = list->head->next->next;
list->tail = list->tail->next;
}
list->print();
return 0;
}

最后

以上就是无情荔枝为你收集整理的(PAT)BasiclLevel_c++ #1008 数组元素循环右移问题的全部内容，希望文章能够帮你解决(PAT)BasiclLevel_c++ #1008 数组元素循环右移问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。