约瑟夫环问题：实现所有出列的人形成新队列

约瑟夫环问题是一个经典的算法问题，描述了n个人围成一个圈，从第一个人开始报数，报到m的人出列，然后从下一个开始继续报数，直到剩下最后一个人。

实现所有出列的人形成新队列

要实现所有出列的人形成新队列，可以创建一个新的链表，在每次游戏结束后，将出列的人依次插入新链表的末尾。以下是修改后的代码：

#include <iostream>
using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
} LNode, * Linklist;

void creatlist(Linklist& head, int n) {
    head = new LNode;
    head->next = NULL;
    LNode* r = head;
    for (int i = 1; i <= n; i++) {
        LNode* p = new LNode;
        p->data = i;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    r->next = head->next;
}

Linklist josephus(Linklist& head, int n, int m) {
    Linklist newHead = NULL;
    Linklist newTail = NULL;
    LNode* cur = head->next;
    LNode* prev = head;
    int num = 0;
    while (num < n) {
        for (int i = 1; i < m; i++) {
            prev = cur;
            cur = cur->next;
        }
        if (newHead == NULL) {
            newHead = cur;
            newTail = cur;
        }
        else {
            newTail->next = cur;
            newTail = newTail->next;
        }
        prev->next = cur->next;
        cur->next = NULL;
        cur = prev->next;
        num++;
    }
    newTail->next = newHead;
    return newHead;
}

int main() {
    int n, m;
    cout << '请输入n，回车输入：';
    cin >> n;
    Linklist head = NULL;
    creatlist(head, n);
    int numPasswords;
    cout << '请输入游戏遍数：' << endl;
    cin >> numPasswords;
    cout << '请输入m，回车输入：';
    cin >> m;
    for (int i = 0; i < numPasswords; i++) {
        head = josephus(head, n, m);
    }
    cout << '新队列次序：' << endl;
    Linklist cur = head;
    for (int i = 0; i < n; i++) {
        cout << cur->data << ' ';
        cur = cur->next;
    }
    return 0;
}

这个修改后的代码中，新增了一个josephus函数，它返回一个新队列的头节点。在每次游戏结束后，将出列的人依次插入新队列的末尾，最后返回新队列的头节点。在main函数中，根据输入的游戏遍数，多次调用josephus函数，将每次游戏的新队列作为下一次游戏的输入。最后，输出新队列的次序。

代码解析

josephus函数：该函数接受原始队列的头节点head，人数n，报数间隔m作为参数，并返回一个新队列的头节点。
创建新队列：函数内部首先创建两个指针newHead和newTail，分别指向新队列的头节点和尾节点。
模拟游戏过程：使用一个while循环模拟游戏过程，循环条件是num小于n，表示还没有所有的人出列。循环内部，使用一个for循环模拟报数，每次报数到m时，就将当前节点cur从原始队列中删除，并插入到新队列的末尾。
插入新节点：将当前节点cur插入到新队列的末尾时，需要根据新队列是否为空进行判断。如果新队列为空，则将newHead和newTail都指向cur；否则，将newTail->next指向cur，并将newTail指向cur。
返回新队列的头节点：当所有的人出列后，将newTail->next指向newHead，形成一个环形链表，并返回newHead。

总结

通过修改代码，我们实现了所有出列的人形成新队列的功能。这个修改方法简单易懂，且代码易于理解和维护。希望这篇文章能够帮助你更好地理解和解决约瑟夫环问题。

如果你有任何问题，请随时提问。