FIFO 列表（移动元素）[C++]

Question

晚上好，人们！

我正在尝试解决一个相当简单的问题，但是……好吧，似乎我不能。:)

这个想法是我有一个包含 n 个元素的 FIFO 列表（FIFO 队列），它被赋予一个值 k (k < n)。我的小程序必须将元素向左移动 k 个元素。（例如，对于 n=4, k=3, a[]=(1, 2, 3, 4)，结果是 4 1 2 3）。

但好吧，我离那很远。

这是我到目前为止所写的：

#include <iostream>
using namespace std;

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=0; i<=n-1; i++) t[i]=a[i];
        for (i=0; i<=k-1; i++) a[i]=a[i+k-1];
        for (i=k; i<=n-1; i++) a[i]=t[i+1];
}

int main () {
        int a[100];
        unsigned k, n, i;
        cout<<"n; k= "; cin>>n>>k;
        for (i=0; i<=n-1; i++) cin>>a[i];
        move (a, n, k);
        for (i=0; i<=n-1; i++) cout<<a[i]<<" ";
}

任何帮助将不胜感激。先感谢您。

Answer 1

我不确定我是否完全理解你的问题。但看起来您实际上想要旋转数组的内容。

将数组内容向左旋转 k 次。您可以执行以下操作：

• 反转前 K 个元素。
• 反转剩余的 NK 元素。
• 反转整个数组。

例子：

N = 5，K = 3，数组 = [1 2 3 4 5]

• 步骤1：反转前3个元素：[3 2 1 4 5]
• 步骤2：反转剩余2个元素：[3 2 1 5 4]
• 步骤3：反转整个数组：[4 5 1 2 3]

C++ 函数执行相同操作：

void move (int a[100], int n, int k) {
        int t[100];
        int i,j;
        for (i=k-1,j=0; i>=0; i--,j++) t[j]=a[i];
        for (i=n-1; i>=k; i--,j++) t[j]=a[i];
        for (i=n-1,j=0; i>=0; i--,j++) a[j]=t[i];
}

在恒定空间中执行此操作的更好方法是就地进行反转：

void arr_rev(int a[100], int start, int end) {
        int temp;

        for(;start<end;start++,end--) {
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
        }
}

void move2 (int a[100], int n, int k) {
        arr_rev(a,0,k-1);
        arr_rev(a,k,n-1);
        arr_rev(a,0,n-1);
}