约瑟夫环问题：C语言循环链表实现

1) 题目描述

有编号为 1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第 s 个人按顺时针方向自 1 开始报数，报到 m 者出列，不再参加报数，这时将出列者的密码作为 m，从出列者顺时针方向的下一人开始重新自 1 开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列和未出列人的序号。

2) 实验要求

采用链式存储结构实现，可以用循环链表。(提示可以用带尾指针的循环链表)

3) C语言实现

以下是使用 C 语言实现约瑟夫环问题的代码，采用带尾指针的循环链表：

#include <stdio.h>
#include <stdlib.h>

// 循环链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建循环链表
Node* createCircularLinkedList(int n) {
    Node* head = NULL;
    Node* tail = NULL;

    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
        } else {
            tail->next = newNode;
        }
        tail = newNode;
    }

    tail->next = head;  // 将尾节点的 next 指针指向头节点，形成循环链表

    return head;
}

// 在指定位置之后插入节点
void insertAfter(Node* current, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = current->next;
    current->next = newNode;
}

// 删除指定位置之后的节点
void deleteAfter(Node* current) {
    Node* temp = current->next;
    current->next = temp->next;
    free(temp);
}

// 约瑟夫环问题求解
void josephus(int n, int m) {
    Node* head = createCircularLinkedList(n);
    Node* current = head;

    // 移动到第 s 个人
    int s = 1;
    while (s != 1) {
        current = current->next;
        s++;
    }

    printf("出列者的序列: ");

    // 开始报数并出列
    while (n > 0) {
        for (int i = 1; i < m; i++) {
            current = current->next;
        }

        printf("%d ", current->next->data);

        Node* temp = current->next;
        deleteAfter(current);
        current = temp;

        n--;
    }

    printf("\n未出列人的序号: ");

    // 输出未出列的人的序号
    current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");

    // 释放链表内存
    current = head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
}

int main() {
    int n, m;
    printf("请输入人数 n：");
    scanf("%d", &n);
    printf("请输入报数的正整数 m：");
    scanf("%d", &m);

    josephus(n, m);

    return 0;
}

4) 代码解析

循环链表的创建: 使用 createCircularLinkedList(n) 函数创建包含 n 个节点的循环链表，每个节点包含一个数据值 data 和指向下一个节点的指针 next。
插入和删除节点: 使用 insertAfter(current, data) 函数在指定节点 current 后插入数据为 data 的新节点，使用 deleteAfter(current) 函数删除指定节点 current 后的节点。
约瑟夫环问题求解: 使用 josephus(n, m) 函数模拟约瑟夫环问题，通过循环链表的节点遍历和删除操作，实现报数出列的过程。
输出结果: 函数将输出出列者的序列和未出列人的序号。

5) 代码运行示例

输入：

请输入人数 n： 5
请输入报数的正整数 m： 3

输出：

出列者的序列: 3 1 5 2 4
未出列人的序号:

6) 总结

本文介绍了使用 C 语言和循环链表实现约瑟夫环问题的方法，并提供完整的代码示例，帮助读者理解和应用相关知识。循环链表在处理需要循环访问节点的场景中非常有效，它可以有效地避免在链表末尾处理特殊情况。在实际应用中，可以根据具体情况选择合适的数据结构和算法来解决问题。