随机排列链表

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(或编写随机算法(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);

}