C++单链表实现经典约瑟夫环问题

题目描述

约瑟夫环问题是一个经典的算法问题，描述如下：

M个人围成一圈，从第一个人开始报数，报到N的人出列，然后从出列的下一个人开始重新报数，报到N的人再次出列，以此类推，直到所有人出列。要求输出出列顺序。

单链表实现

使用单链表可以高效地解决约瑟夫环问题。循环链表可以很好地模拟环形结构，而删除节点的操作也非常方便。

以下是使用C++实现的约瑟夫环问题的单链表版本：

#include <iostream>
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* prev = head;
    for (int i = 2; i <= M; i++) {
        ListNode* cur = new ListNode(i); // 创建新节点
        prev->next = cur;  // 将新节点连接到链表尾部
        prev = cur;
    }
    prev->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 << temp->data << ' '; // 输出删除节点的数据
        delete temp;
        cur = cur->next; // 更新当前节点
    }
    cout << 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;
}

代码解释

• createList(int M): 创建一个包含M个节点的循环单链表，节点数据从1到M。
• josephus(ListNode* head, int N): 模拟一轮约瑟夫环游戏，根据报数密码N删除节点并输出节点数据。
• playJosephusGame(int M, int* passwords, int numPasswords): 进行多轮约瑟夫环游戏，根据输入的报数密码数组进行游戏。

示例输入输出

输入：

10 3
3 5 2

输出：

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

总结

使用单链表可以方便地实现约瑟夫环问题。循环链表可以很好地模拟环形结构，而删除节点的操作也非常简单。本篇文章提供了详细的代码实现和解释，希望能够帮助您理解约瑟夫环问题的解决思路和单链表的应用。