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

我試圖解決一個相當簡單的問題，但..嗯，看來我不能。 :)

的想法是，我有一個FIFO列表（FIFO隊列）與n個元素和它給的值，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]<<" "; 
}

任何幫助將不勝感激。先謝謝你。

來源

2010-02-03 flowerpowerduck

'用k個元素向左移動元素'是什麼意思？你的意思是「將第k個元素移到隊列的前面？」 – 2010-02-03 17:55:42

男人，那真是一個醜陋的一段代碼，即使codaddict清理了一點點。 -1不是來自我的，但如果是因爲代碼，我不會感到驚訝。我對未來的建議，因爲你似乎在學習：爲你的讀者編寫和格式化你的代碼，而不是爲了你打字時的方便。這會提高你的代碼質量，並且會使人更有可能回答你的問題。現在，請原諒我，我想我會在樓上開源的傢伙，並告訴他C++多麼醜陋，如果他仍然在這個大樓。 – OregonGhost 2010-02-03 17:58:17

對不起...不好意思，我的骯髒的代碼。 – flowerpowerduck 2010-02-03 18:21:32

我我不確定我是否完全理解了你的問題。但看起來你實際上想要旋轉數組的內容。

到陣列內容向左旋轉k倍。您可以執行以下操作：

反轉第一個K元素。
反轉剩餘的N-K元素。
逆向整個陣列。

實施例：

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

來源

2010-02-03 18:23:15 codaddict

謝謝你，codaddict。 :) – flowerpowerduck 2010-02-03 19:03:23

它看起來像你想要一個左旋轉？這應該不是很困難。只是出列第一k元件，（可能通過將它們在一個臨時數組的開頭）轉移剩餘n-k元件到左邊，然後在第一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數據結構;如果情況並非如此，請參閱傑里科芬的答案。

來源

2010-02-03 18:02:59 danben

謝謝，丹本！這是我想要做的。至於STL數據結構，我還沒有學習這些。 :) 謝謝，再次。 – flowerpowerduck 2010-02-03 18:40:29

既然你已經標記這是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); 
    } 
}

如果您想要在另一個方向旋轉，這幾乎是交換正面和背面角色的問題。

來源

2010-02-03 18:03:19

謝謝你的迴應。我真的是一個初學者（很難不注意到），嗯，我從來沒有聽說過std :: deque。但我會研究它。謝謝。 :) – flowerpowerduck 2010-02-03 18:23:30

如果你的意思是「第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; 
}

來源

2010-02-03 18:08:06

我不認爲他的意思。在他的例子中，k是3. – danben 2010-02-03 18:09:23

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

將輸出：

來源

2010-02-03 18:19:37 Notinlist

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

回答

相關問題