C++单链表实现约瑟夫环问题：详解与代码示例

约瑟夫环问题是一个经典的算法问题，描述为：编号为 1 到 M 的 M 个人围成一圈，从编号为 1 的人开始报数，报到 N 的人出列，然后从出列的下一个人开始重新报数，报到 N 的人再出列，以此类推，直到所有人都出列为止。要求输出出列顺序。

本文将介绍如何使用 C++ 的单链表数据结构来解决约瑟夫环问题，并提供详细的代码实现和解释。

1. 问题分析

解决约瑟夫环问题的关键在于如何模拟'出列'操作以及如何找到下一轮报数的起始位置。使用单链表可以很方便地解决这两个问题：

出列操作: 可以直接删除链表中对应节点，并将前一个节点的指针指向下一个节点。* 找到下一轮报数的起始位置: 可以通过遍历链表，找到被删除节点的下一个节点。

2. 代码实现cpp#include #include using namespace std;

// 定义单链表节点结构体struct ListNode { int data; // 节点数据，代表人的编号 ListNode* next; // 指向下一个节点的指针 ListNode(int x) : data(x), next(NULL) {} // 构造函数};

// 创建包含 M 个节点的循环单链表ListNode* createList(int M) { ListNode* head = new ListNode(1); // 创建头节点 ListNode* cur = head; for (int i = 2; i <= M; i++) { ListNode* newNode = new ListNode(i); // 创建新节点 cur->next = newNode; // 将新节点连接到当前节点后面 cur = newNode; // 更新当前节点 } cur->next = head; // 将尾节点指向头节点，形成循环链表 return head;}

// 模拟约瑟夫环游戏void josephus(ListNode* head, int N) { ListNode* cur = head; while (cur->next != cur) { // 当链表中至少有两个节点时循环 for (int i = 1; i < N - 1; i++) { cur = cur->next; // 移动到要删除节点的前一个节点 } ListNode* temp = cur->next; // 临时保存要删除的节点 cur->next = temp->next; // 删除节点 cout << setw(4) << setfill(' ') << temp->data; // 输出出列的人的编号 delete temp; // 释放内存 cur = cur->next; // 更新当前节点 } cout << setw(4) << setfill(' ') << cur->data; // 输出最后一个出列的人的编号}

// 进行多轮约瑟夫环游戏void playJosephusGame(int M, int* passwords, int numPasswords) { ListNode* head = createList(M); // 创建循环单链表 for (int i = 0; i < numPasswords; i++) { // 遍历每一轮游戏的报数密码 josephus(head, passwords[i]); // 进行一轮游戏 cout << endl; // 每轮游戏结束后换行 }}

int main() { int M; // 游戏人数 cin >> M;

int numPasswords;                        // 游戏轮数    cin >> numPasswords;

int* passwords = new int[numPasswords];    // 存储每一轮游戏的报数密码    for (int i = 0; i < numPasswords; i++) {        cin >> passwords[i];    }

playJosephusGame(M, passwords, numPasswords); // 进行游戏

delete[] passwords;                        // 释放内存    return 0;}

3. 代码解释

ListNode 结构体：定义了单链表的节点结构，包含数据域 data 和指针域 next。2. createList(int M) 函数：创建包含 M 个节点的循环单链表，并返回头节点。3. josephus(ListNode* head, int N) 函数：模拟一轮约瑟夫环游戏，输出出列顺序。4. playJosephusGame(int M, int* passwords, int numPasswords) 函数：进行多轮游戏，根据输入的报数密码数组 passwords 进行游戏。5. main() 函数：读取输入数据，调用 playJosephusGame() 函数进行游戏，最后释放内存。

4. 示例

输入：

10 33 5 2

输出：

3 6 9 2 7 1 8 5 10 4 2 5 8 1 6 9 4 10 7 3 7 3 1 6 10 5 2 9 4 8

5. 总结

本文介绍了如何使用 C++ 单链表实现约瑟夫环问题，并提供了详细的代码实现和解释。通过学习本文，您可以了解如何使用单链表解决实际问题，并加深对数据结构和算法的理解。