约瑟夫环（Josephus problem）是一个经典的数学问题，其大意是：N 个人围成一圈，每次数到第 M 个人被淘汰，直到最后剩下一个人。该问题在计算机科学、密码学等领域有广泛应用，例如进程调度、游戏规则设计等。
数据结构选择：使用循环链表模拟环形队列，每个节点包含编号（code）和指向下一节点的指针（next）。
createlist函数创建包含 N 个节点的循环链表。
关键步骤：
1.动态分配内存并初始化节点。
2.通过尾插法构建链表，最后将尾节点指向头节点形成环。
3.打印链表前 5 个节点（方便验证链表正确性）。
yuesefu函数模拟约瑟夫环淘汰过程。
关键步骤：
1.使用双指针（p和pre）遍历链表，找到第 M 个节点。
2.删除被淘汰节点，并处理头节点的特殊情况。
3.循环直到只剩一个节点，输出最后存活者。
#include <stdio.h>
#include <stdlib.h>typedef int elemtype;// 定义循环链表节点结构体
typedef struct node {elemtype code; // 节点编号struct node *next; // 指向下一个节点的指针
} node;// 创建循环链表并返回头节点
node *createlist(int n) {if (n == 0) return NULL; // 处理非法输入node *p, *head, *last; // 临时指针变量for (int i = 1; i <= n; i++) {// 分配新节点内存并检查是否成功p = (node *)malloc(sizeof(node));if (p == NULL) {fprintf(stderr, "内存分配失败\n");exit(EXIT_FAILURE);}p->code = i; // 设置节点编号if (i == 1) { // 处理第一个节点head = last = p; // 头节点和尾节点均指向第一个节点} else { // 处理后续节点last->next = p; // 将新节点链接到链表末尾last = p; // 更新尾节点}}last->next = head; // 尾节点指向头节点，形成循环链表// 打印链表前5个节点和第6个节点（假设n>=6）p = head;for (int i = 0; i < 5; i++) {printf("%d->", p->code);p = p->next;}printf("%d\n", p->code);return head; // 返回头节点
}// 约瑟夫环问题求解
void yuesefu(node *L, int m) {node *p = L; // 当前节点指针node *pre = NULL; // 当前节点的前驱指针while (p->next != p) { // 循环直到只剩一个节点// 移动m-1次，找到第m个节点for (int i = 1; i < m; i++) {pre = p;p = p->next;}printf("%d ", p->code); // 输出被淘汰者编号// 删除当前节点pif (pre == NULL) { // 当p是头节点且pre未初始化时// 找到最后一个节点node *last = p;while (last->next != p) {last = last->next;}last->next = p->next; // 断开头节点free(p); // 释放内存p = last->next; // 更新当前节点为头节点的下一个节点L = p; // 更新头节点指针} else {pre->next = p->next; // 前驱节点跳过当前节点free(p); // 释放内存p = pre->next; // 更新当前节点为前驱的下一个节点}}printf("\n最后幸存者编号是：%d\n", p->code); // 输出最后存活者
}int main() {const int n = 6; // 总人数const int m = 3; // 数到第3个人淘汰node *head = createlist(n); // 创建循环链表yuesefu(head, m); // 求解约瑟夫环问题return 0;
}运行结果：
