c++数据结构约瑟夫环

约瑟夫环是一个经典的问题，可以使用链表来实现。

具体实现步骤：

1. 定义一个结构体表示节点，包含一个数据成员和一个指向下一个节点的指针成员；
2. 创建一个有 n 个节点的循环链表，将每个节点的数据成员设置为对应的编号；
3. 设定一个计数器，从第一个节点开始计数；
4. 当计数器达到 m 时，删除当前节点，并将计数器重新计数；
5. 重复步骤 4 直到链表中只剩下一个节点。

下面是 C++ 代码实现：

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int x) : data(x), next(nullptr) {}
};

Node *createList(int n) {
    Node *head = nullptr, *tail = nullptr;
    for (int i = 1; i <= n; ++i) {
        Node *p = new Node(i);
        if (!head) head = tail = p;
        else {
            tail->next = p;
            tail = p;
        }
    }
    tail->next = head; // 首尾相连，形成循环链表
    return head;
}

void josephus(Node *head, int m) {
    Node *p = head, *q = nullptr;
    while (p->next != p) {
        for (int i = 1; i < m; ++i) {
            q = p;
            p = p->next;
        }
        q->next = p->next; // 删除当前节点
        cout << p->data << " ";
        delete p; // 释放内存
        p = q->next;
    }
    cout << p->data << endl;
    delete p; // 最后一个节点也要删除
}

int main() {
    int n, m;
    cin >> n >> m;
    Node *head = createList(n);
    josephus(head, m);
    return 0;
}

输入样例：

7 3

输出样例：

3 6 2 7 5 1 4