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);
}

Answer 2

由于您已将其标记为 C++，因此我假设这就是您正在使用的。在这种情况下，您几乎肯定应该使用 std::deque 而不是数组来存储数据。此外，队列通常有“前”和“后”，因此“左”并没有多大意义。

假设（只是为了论证）你想要的是从队列后面取出 k 个元素并将它们移动到前面，你可以这样做：

typedef std::deque<your_type> data;

void push_to_front(data &d, int k) { 
    if (k > d.size())
        return;
    for (int i=0; i<k; i++) {
        data::value_type v = d.pop_back();
        d.erase(d.back());
        d.push_front(v);
    }
}      

如果你想向另一个方向旋转，那几乎是交换前面和后面的角色的问题。

Answer 3

看起来你想要左旋转？那应该不是很困难。只需将前 k 元素出列，将剩余的 nk 元素向左移动（可能将它们放在临时数组的开头），然后添加第一个 < code>k 按顺序放在最后。

以这种方式修改代码可能如下所示：

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

由于这仍然很难看，您可以重写它以使逻辑更清晰，但我将把它作为练习。

这还假设您不被允许使用 STL 数据结构；如果情况并非如此，请参阅杰里·科芬的回答。

Answer 4

如果您的意思是“将第 k 个元素移动到队列的前面”，那么这是一种方法：

void move( int *a, unsigned n, unsigned k )
{ 
    int t; // To store the temporary for the k'th element 

    t = a[ k ];

    // Shift all the elements to the right by one.
    for( unsigned i = k; i > 0; --i )
        a[ i ] = a[ i - 1 ];

    // Put the k'th element at the left of the queue.
    a[ 0 ] = t;
}

Answer 5

#include <iostream>
#include <list>
template <typename T>
void Rotate(std::list<T>& list, int k){
    for(int i=0; i<k; ++i){
        T tmp(list.back());
        list.pop_back();
        list.push_front(tmp);
    }
}
int main(){
    std::list<int> ints;
    ints.push_back(1); ints.push_back(2);
    ints.push_back(3); ints.push_back(4);
    Rotate(ints,2);
    for(std::list<int>::const_iterator i = ints.begin(); i!=ints.end(); ++i)
        std::cout << *i << std::endl;
    return 0;
}

将输出：

3
4
1
2

Answer 6

这个问题很老了，但现在看来最简单的解决方案是依赖 std::旋转。复杂度是线性的，但取决于第一个和最后一个之间的距离。因此，如果需要旋转 1 个元素，复杂度为 O(1)，对于 3 个元素，复杂度为 O(3)。