将一个链表重新排序

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

}