解决约瑟夫问题c++循环链表

约瑟夫问题是经典的循环链表问题，可以使用C++的循环链表来解决。

下面是一个简单的C++程序来解决约瑟夫问题：

#include <iostream>
#include <stdlib.h>

using namespace std;

struct Node {
    int data;
    Node *next;
};

Node *createList(int n) {
    Node *head, *p, *pre;
    head = (Node *) malloc(sizeof(Node));
    head->data = 1;
    pre = head;
    for (int i = 2; i <= n; i++) {
        p = (Node *) malloc(sizeof(Node));
        p->data = i;
        pre->next = p;
        pre = p;
    }
    pre->next = head;
    return head;
}

void josephus(int n, int m) {
    Node *p, *q;
    p = createList(n);
    q = p;
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            q = p;
            p = p->next;
        }
        q->next = p->next;
        cout << p->data << " ";
        free(p);
        p = q->next;
    }
    cout << p->data << endl;
}

int main() {
    int n, m;
    cout << "请输入参加游戏的人数n和报数的数m：";
    cin >> n >> m;
    josephus(n, m);
    return 0;
}

在这个程序中，我们首先定义了一个结构体Node，表示链表中的节点。然后，我们定义了一个函数createList，用于创建一个长度为n的循环链表。在createList函数中，我们首先创建头节点head，然后创建n-1个节点，并将它们依次插入到链表中。最后，我们将最后一个节点的next指向头节点，形成一个循环链表，并将头节点返回。

接着，我们定义了一个函数josephus，用于解决约瑟夫问题。在josephus函数中，我们首先调用createList函数创建一个长度为n的循环链表，并将p和q指向头节点。然后，我们进入一个while循环，直到链表中只剩下一个节点。在每次循环中，我们先从p开始遍历链表，找到第m个节点，并将q指向它的前一个节点。然后，我们删除第m个节点，并输出它的值。最后，我们将q的next指向p的下一个节点，并将p指向q的下一个节点，继续循环，直到只剩一个节点为止。

最后，我们在main函数中读入参加游戏的人数n和报数的数m，并调用josephus函数解决约瑟夫问题。