將一個鏈表重新排序

Question

我有一個函數需要一個雙向鏈表。頭是第一個節點，尾是最後一個節點。有52個節點（卡牌）我試圖做的是執行一個洗牌，就像你用手洗牌一樣。所以你把甲板砍下一半，從上半部分拿下底牌，將底牌從另一半上取下，並將其放在頂部。

所以。左半部分是1 2 3右半部分是4 5 6後洗牌4 1 5 2 6 3

我知道我的錯誤是在指針中，他們相互覆蓋。我只是不知道如何正確地對這些列表進行排序，並將它們一個接一個地抽出來，然後將它們粘在一起。

bool Shuffle(deck* &head, deck* &tail, int ShuffleAmnt) 

{

deck* temp_tail = nullptr; 
deck* temp_head = head; 
deck* temp_list = new deck; 
for (int i = 1; i < 26; i++) 
    temp_head = temp_head->next; 

temp_tail = temp_head->next; 

temp_tail->previous = nullptr; 

temp_head->next = nullptr; 


while (head->next != NULL) // get to the bottom of head 
    head = head->next; 

temp_head->previous = nullptr; 
temp_tail->next = nullptr; 

for (int i = 1; i < 26; i++) 
{ 
    temp_list->next = temp_head; 
    temp_head = head->previous; 
    temp_list = temp_list->next; 
    temp_list->next = temp_tail; 
} 

head = temp_list; 



return(true); 

}

Answer 1

這個答案可能沒有直接回答這個問題，但它是在這裏指導和教育如果這是所需的。

C++標準庫中已經有（幾乎）每個容器類型和邏輯操作的模板實現你永遠都需要。這些構建塊每天都在數十億臺計算機上使用，並已針對您的編譯器效率進行了優化，並由全球最專業的程序員進行了同行評審。簡而言之，沒有理由考慮編寫一個鏈表（std::list）或編寫一個shuffle算法（std::random_shuffle）。

如果你真的想保持卡鏈表（你不這樣做，一個向量是更自然的），你可以重構，以這樣的：如果你決定做正確的事（

#include <vector> 
#include <list> 
#include <algorithm> 

struct Card {}; 

typedef std::list<Card> deck; // that's it - a complete linked list implementation 

void shuffle_deck(deck& the_deck) { 
    // c++11 takes advantage of efficiently copying by value. 
    std::vector<Card> temp(std::make_move_iterator(the_deck.begin()), 
          std::make_move_iterator(the_deck.end())); 

    // clear out the zombie objects that will have been left by the move 
    the_deck.clear(); 

    // those clever fellows in the standards committee thought of everything... 
    // even shuffling a deck of cards! 
    std::random_shuffle(temp.begin(), temp.end()); 

    // move the cards back into the linked list in the correct order 
    std::move(temp.begin(), temp.end(), back_inserter(the_deck)); 
} 

TM），使您的撲克牌載體，它的更簡單：

typedef std::vector<Card> deck_of_cards; 

void shuffle_deck(deck_of_cards& deck) 
{ 
    std::random_shuffle(deck.begin(), deck.end()); 
} 

如果你正期待着一個有價值的職業寫C++，需要時間來全面掌握了標準庫 - 許多C++程序員不打擾學習algorithm庫 - 這是一個錯誤。它是優雅，可維護代碼的基礎。

以下是有關std::random_shuffle文檔的鏈接。 http://en.cppreference.com/w/cpp/algorithm/random_shuffle

你會注意到，它被標記爲從C++ 17中刪除，因爲它正被上級std::shuffle所取代。然而，爲了討論的目的，我認爲這可能會導致主要問題的分心 - 這是鼓勵你學習和使用標準庫:-)

Answer 2

你可以象下面這樣：

bool Shuffle(deck* &head, deck* &tail, int ShuffleAmnt = 1) 
{ 
    deck* temp_tail = nullptr; 
    deck* temp_head = head; 
    for (int i = 1; i < 26; i++) 
    temp_head = temp_head->next; 

    temp_tail = temp_head->next; 
    temp_tail->previous = nullptr; 

    temp_head->next = nullptr; 
    temp_head = head; 

    temp_head_next = temp_head->next; 
    temp_head_next->previous = temp_head; 

    temp_tail_next->next = temp_tail->next; 
    temp_tail_next->previous = temp_tail; 

    head = temp_tail; 

    for (int i = 1; i < 26; i++) 
{ 
    temp_tail->next = temp_head; 
    temp_head->previous = temp_tail; 
    temp_head->next = temp_tail->next; 

    temp_tail = temp_head_next; 
    temp_head = temp_head_next; 

    temp_head_next = temp_head->next; 
    temp_head_next->previous = temp_head; 

    temp_tail_next->next = temp_tail->next; 
    temp_tail_next->previous = temp_tail; 
    } 
tail = temp_head; 
return(true); 

}