使用链式存储结构实现约瑟夫环

使用链式存储结构实现约瑟夫环的基本思路是创建一个循环链表，并按照约瑟夫环的规则进行操作。下面是具体的步骤：

1. 定义一个节点结构体，包含两个成员变量：数据域和指针域。
2. 创建一个头节点，并将其指针域指向自身，形成一个空的循环链表。
3. 根据约瑟夫环的规则，确定起始位置和报数的间隔。
4. 从头节点开始，按照报数的间隔遍历链表，直到找到要删除的节点。
5. 删除该节点，并将其前一个节点的指针域指向下一个节点，实现节点的删除操作。
6. 重复步骤4和步骤5，直到只剩下一个节点为止。

下面是一个使用链式存储结构实现约瑟夫环的示例代码：

#include <iostream>

using namespace std;

// 节点结构体
struct Node {
    int data;
    Node* next;
};

// 创建循环链表
Node* createCircularLinkedList(int n) {
    Node* head = new Node;
    head->next = head; // 头节点的指针域指向自身

    Node* tail = head;  // 尾指针

    for (int i = 1; i <= n; i++) {
        Node* newNode = new Node;
        newNode->data = i;
        newNode->next = head;  // 新节点的指针域指向头节点

        tail->next = newNode;  // 尾节点的指针域指向新节点
        tail = newNode;  // 更新尾指针
    }

    return head;
}

// 删除节点
void deleteNode(Node* preNode, Node* curNode) {
    preNode->next = curNode->next;
    delete curNode;
}

// 约瑟夫环问题
void josephusCircle(Node* head, int m) {
    Node* curNode = head;
    Node* preNode = nullptr;

    while (curNode->next != curNode) {
        for (int i = 1; i < m; i++) {
            preNode = curNode;
            curNode = curNode->next;
        }

        deleteNode(preNode, curNode);
        curNode = preNode->next;
    }

    cout << "最后剩下的节点是：" << curNode->data << endl;
}

int main() {
    int n, m;
    cout << "请输入总人数n：";
    cin >> n;
    cout << "请输入报数间隔m：";
    cin >> m;

    Node* head = createCircularLinkedList(n);
    josephusCircle(head, m);

    return 0;
}