约瑟夫环游戏：单链表实现及优化

约瑟夫环游戏是一个经典的算法问题，描述了 N 个人围成一圈，从第一个人开始报数，报到 M 的人出局，然后从出局人下一个开始继续报数，直到只剩下一个人。

本文将使用单链表数据结构来实现约瑟夫环游戏，并提供代码示例和优化方案。

单链表实现

1. 构建单链表

首先，我们需要创建一个包含 N 个节点的循环单链表，每个节点代表一个人，节点中的数据为人的编号。cpp#include using namespace std;

struct ListNode { int data; ListNode* next; ListNode(int x) : data(x), next(NULL) {}};

ListNode* createList(int N) { ListNode* head = new ListNode(1); ListNode* prev = head; for (int i = 2; i <= N; i++) { ListNode* cur = new ListNode(i); prev->next = cur; prev = cur; } prev->next = head; // 连接成循环链表 return head;}

2. 模拟游戏过程

接下来，我们需要模拟游戏的过程，即从第一个节点开始报数，报到 M 的节点出局，并将链表中的下一个节点连接到出局节点的下一个节点，直到链表只剩下一个节点。cppvoid josephus(ListNode* head, int M) { ListNode* cur = head; while (cur->next != cur) { // 当链表只剩下一个节点时，循环结束 for (int i = 1; i < M; i++) { cur = cur->next; } ListNode* temp = cur->next; // 出局节点 cur->next = temp->next; // 连接链表 cout << ' ' << temp->data; // 输出出局节点编号 delete temp; // 释放出局节点内存 cur = cur->next; // 指针指向下一个节点 } cout << ' ' << cur->data << endl; // 输出最后留下的节点编号}

3. 多次游戏

如果需要进行多次游戏，可以使用一个循环来控制游戏次数，每次游戏开始前，需要将链表恢复到初始状态。cppvoid playJosephusGame(int N, int* passwords, int numPasswords) { ListNode* head = createList(N); for (int i = 0; i < numPasswords; i++) { josephus(head, passwords[i]); // 恢复链表状态 head = createList(N); }}

优化方案

1. 减少内存分配

在每次游戏开始前，不需要重新创建链表，可以使用一个指针来记录链表的起点，每次游戏结束后将指针重置到起点即可。cppvoid playJosephusGame(int N, int* passwords, int numPasswords) { ListNode* head = createList(N); ListNode* start = head; // 记录链表起点 for (int i = 0; i < numPasswords; i++) { josephus(head, passwords[i]); head = start; // 重置链表指针 }}

2. 优化报数过程

使用循环报数的方式效率较低，可以采用以下方式优化：cppvoid josephus(ListNode* head, int M) { ListNode* prev = head; ListNode* cur = head->next; int count = 1; while (cur != head) { if (count == M) { prev->next = cur->next; cout << ' ' << cur->data; delete cur; cur = prev->next; // 指针指向下一个节点 count = 1; // 重置计数器 } else { prev = cur; cur = cur->next; count++; } } cout << ' ' << cur->data << endl; delete cur;}

代码示例cpp#include using namespace std;

struct ListNode { int data; ListNode* next; ListNode(int x) : data(x), next(NULL) {}};

void josephus(ListNode* head, int M) { ListNode* prev = head; ListNode* cur = head->next; int count = 1; while (cur != head) { if (count == M) { prev->next = cur->next; cout << ' ' << cur->data; delete cur; cur = prev->next; count = 1; } else { prev = cur; cur = cur->next; count++; } } cout << ' ' << cur->data << endl; delete cur;}

void playJosephusGame(int N, int* passwords, int numPasswords) { ListNode* head = createList(N); ListNode* start = head; for (int i = 0; i < numPasswords; i++) { josephus(head, passwords[i]); head = start; }}

int main() { int N, numPasswords; cin >> N >> numPasswords; int* passwords = new int[numPasswords]; for (int i = 0; i < numPasswords; i++) { cin >> passwords[i]; } playJosephusGame(N, passwords, numPasswords); delete[] passwords; return 0