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

本文将介绍如何使用 C 语言和循环链表解决约瑟夫环问题，并提供完整的代码示例。

问题描述

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

n 个人围成一圈，从第 s 个人开始报数，报到 m 的人出列，然后从出列者的下一位继续报数，直到所有人出列。求出列者的顺序。

解决方案

我们可以使用带尾指针的循环链表来模拟约瑟夫环。每个节点代表一个人，存储其序号和指向下一个人的指针。

以下是使用 C 语言编写的约瑟夫环问题的实现：c#include <stdio.h>#include <stdlib.h>

typedef struct Node { int password; int index; struct Node* next;} Node;

Node* createNode(int password, int index) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->password = password; newNode->index = index; newNode->next = NULL; return newNode;}

void josephus(int n, int m, int s) { Node* head = createNode(1, 1); Node* tail = head; for (int i = 2; i <= n; i++) { Node* newNode = createNode(i, i); tail->next = newNode; tail = newNode; } tail->next = head; // 将尾节点的 next 指针指向头节点，形成循环链表

Node* current = head;    // 找到从第s个人开始报数的人    for (int i = 1; i < s; i++) {        current = current->next;    }

while (n > 0) {        // 找到要出列的人        for (int i = 1; i < m - 1; i++) {            current = current->next;        }                Node* eliminated = current->next;        printf('出列者序号：%d

', eliminated->index); current->next = eliminated->next; current = current->next;

    free(eliminated);        n--;    }    printf('未出列人序号：');    for (int i = 0; i < n; i++) {        printf('%d ', current->index);        current = current->next;    }    printf('

');}

int main() { int n, m, s; printf('请输入 n、m 和 s 的值：'); scanf('%d %d %d', &n, &m, &s); josephus(n, m, s); return 0;}

代码解释：

createNode 函数：创建一个新的节点，并初始化其密码、序号和指向下一个节点的指针。2. josephus 函数：解决约瑟夫环问题的主要函数。 - 首先创建一个包含 n 个节点的循环链表。 - 然后找到从第 s 个人开始报数的节点。 - 循环遍历链表，每次找到报到 m 的节点，将其从链表中删除，并输出其序号。 - 最后输出剩余节点的序号。3. main 函数：读取用户输入的 n、m 和 s 的值，并调用 josephus 函数解决问题。

程序运行示例：

请输入 n、m 和 s 的值：5 2 1出列者序号：2出列者序号：4出列者序号：1出列者序号：5出列者序号：3未出列人序号：

希望本文能够帮助您理解如何使用 C 语言和循环链表解决约瑟夫环问题。