c++ - 打乱链表

Question

我有一个接受双向链表的函数。 Head 是第一个节点，tail 是最后一个节点。有 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++ 标准库已经具有(几乎)您将永远需要的每个容器类型和逻辑操作的模板实现。这些构建 block 每天在数十亿台计算机中使用，已针对您的编译器的效率进行了优化，并且已经过世界上每一位最专业的程序员的同行评审。简而言之，没有理由考虑写链表(std::list)或写shuffle算法(std::random_shuffle)。

如果您真的想将卡片保存在链表中(您不想， vector 更自然)，您可以重构为:

#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) 并使您的牌组成为 vector ，那就更简单了:

typedef std::vector<Card> deck_of_cards;

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

如果您期待一份有值(value)的 C++ 职业，请花时间彻底学习标准库——许多 C++ 程序员不费心去学习 algorithm 库——这是一个错误。它是优雅、可维护代码的基础。

这里是关于 std::random_shuffle 的文档链接。 http://en.cppreference.com/w/cpp/algorithm/random_shuffle

你会注意到它被标记为从 c++17 的标准中删除，因为它被高级 std::shuffle 取代。然而，出于本次讨论的目的，我认为这可能会分散注意力——鼓励您学习和使用标准库:-)