一，问题描述
在现实生活以及计算机科学的一些场景中，我们常常会遇到类似这样的问题：有编号为 1，2，…，n 的 n 个人按顺时针方向围坐成一圈，每个人手中持有一个密码（正整数）。此时给定一个随机生成的正整数 m > 0，游戏从编号为 1 的人开始，按照顺时针方向，大家依次从 1 开始顺序报数。当某个人报到 m 时，报数停止，该报 m 的人就要出圈离开。并且，此人出圈时留下他所持有的密码作为新的 m 值。然后，从他在顺时针方向上的下一个人开始，重新从 1 开始报数，如此不断重复这个过程，直到所有的人都全部出列为止。我们的任务就是在计算机上通过编程模拟这个 Josephus 问题的完整求解过程，以便更好地理解和分析其中的规律和逻辑。
二，基本要求
（1）为了准确地模拟 Josephus 环，我们需要使用循环单链表这种数据结构。在这个循环单链表中，每个结点都应该包含三个重要成员：一个用于记录该结点对应人的序号（方便识别是哪个人），一个用于存储该人持有的密码（影响后续报数的 m 值），还有一个指针成员，用于指向下一个结点，从而将所有结点连接成一个环形结构。
（2）设计一个专门的算法来建立一个不带附加表头结点的循环单链表（即 Josephus 环）。这个算法要能够根据输入的人数 n 和每个人的密码，正确地构建出符合要求的循环单链表结构。
（3）精心设计 Josephus 问题的求解算法。该算法要能够按照问题描述的规则，从初始的 m 值开始，通过报数、出圈、更新 m 值等一系列操作，最终实现所有人的出列，并输出相应的出圈顺序。
（4）认真仔细地阅读、理解参考程序中已有的代码逻辑和功能。对于程序中可能存在的不完整部分，要根据前面的要求和算法设计思路，完善相关的代码语句，使其能够正确地实现整个 Josephus 问题的求解过程。
（5）设计一系列合理且全面的测试用例。这些测试用例要涵盖不同的人数 n、不同的初始 m 值以及各种不同的密码组合情况。通过上机运行程序，输入测试用例进行验证，记录下每次运行的测试结果。然后，对这些测试结果进行深入分析，检查程序是否能够正确地处理各种情况，是否存在逻辑错误或者异常情况，以便对程序进行进一步的优化和改进。
三，算法设计
（1）存储结构设计
typedef struct LNode { // 循环单链表结点类型
int no; // 序号，用于标识该结点对应的是第几个人
int pass; // 密码，会在报数过程中影响 m 值的更新
struct LNode *next; // 指针，用于指向下一个结点，形成循环链表结构
}LNode, *LinkList;
（2）算法设计
① 创建一个不带附加表头结点的循环单链表（Josephus 环）：
首先，根据输入的人数 n，使用循环依次为每个人创建一个链表结点。在创建每个结点时，为其分配内存空间，并正确地设置结点的序号和密码。然后，将新创建的结点依次连接到已有的链表中，形成一个循环结构。具体来说，让最后一个结点的指针指向第一个结点，完成循环单链表的构建。
② 令 m 取初始密码、k 计数、p 指向第一个结点、pre 始终指向 p 的前驱，初始时令 pre 指向最后一个结点（表尾指针）：
初始化时，将 m 设置为最初给定的随机数（或者根据具体规则确定的初始值）。创建一个变量 k 用于记录当前报数的数值，初始化为 1。设置指针 p 指向循环单链表的第一个结点，作为当前报数的起始位置。同时，设置指针 pre 指向链表的最后一个结点，这样 pre 就始终是 p 的前驱结点，方便在删除结点时进行操作。
③ 用 p 控制循环，每循环到 m 时，输出 p 结点的序号，将 p 结点的密码赋给 m，删除 p 结点，再从 p 的下一结点开始继续循环：
在循环过程中，每次 p 指向一个结点时，k 的值加 1。当 k 的值等于 m 时，说明当前报数到了 m，此时输出 p 结点的序号，表示该人出圈。然后，将 p 结点的密码赋值给 m，更新下一轮报数的终止值。接着，通过修改 pre 的指针，使其指向 p 的下一结点，实现删除 p 结点的操作。最后，将 p 指向 p 的下一结点，重新开始下一轮的报数循环。
④ 重复第 3 步，直至循环链表空为止：
不断重复上述第 3 步的操作，每次都让一个人出圈并更新相关的参数。随着循环的进行，链表中的结点逐渐减少，直到链表为空，即所有人都已经出圈，此时整个 Josephus 问题的求解过程结束。
四，示例代码
#define OK 1
#define ERROR 0
#include <stdio.h>
#include <malloc.h>
typedef int Status;
typedef struct LNode {
int no;
int pass;
struct LNode* next;
} LNode, * LinkList;
Status CreatJosephus(LinkList& Tail, int n, int M[]) // 创建 Josephus 环（循环单链表）
{
int i;
LinkList p, head = NULL; // 初始化 head 为 NULL
for (i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(LNode));
if (p == NULL) {
return ERROR;
}
p->no = i; // 号码从 1 开始
p->pass = M[i - 1];
if (i == 1) { // 第 1 个结点
head = p;
Tail = p;
}
else { // 其余结点
Tail->next = p;
}
Tail = p;
}
if (head != NULL) { // 确保 head 已初始化
Tail->next = head; // 令最后一个结点的指针指向第 1 个结点构成循环链表
}
return OK;
}
Status Josephus(LinkList& Tail, int m) // 求解 Josephus 环问题
{
LinkList q, p, pre;
int k; // 用于报数计数器
if (Tail == NULL || m < 1) { // 检查链表是否为空和 m 是否合法
return ERROR;
}
p = Tail->next;
pre = Tail;
while (p->next != p) { // 若还有未出列者循环，只剩一个节点时结束
for (k = 1; k < m; k++) { // 报数
pre = p;
p = p->next;
}
printf("%4d", p->no); // 出列
q = p;
m = q->pass; // 将出列者密码重新赋值给 m
p = p->next; // 从出列者下一人开始继续报数
pre->next = p; // 修改链指针，从环中删除出列者
free(q);
}
printf("%4d\n", p->no); // 输出最后一个出列者
free(p);
Tail = NULL;
return OK;
}
void OutputJosephus(LinkList Tail) // 输出 Josephus 环
{
if (Tail == NULL) { // 检查链表是否为空
return;
}
LinkList p = Tail;
do {
p = p->next;
printf("%d(%d)，", p->no, p->pass);
} while (p != Tail); // 循环条件为未搜索到表尾
printf("\n");
}
int main() {
int M[] = { 4, 7, 14, 3, 22, 1, 5, 9, 11, 6, 8, 2 }; // 初始化密码数组
int n = 12; // 定义 Josephus 环的长度
int m = 0; // 初始密码初始化
LinkList tail = NULL;
printf("（1）创建 Josephus 环......\n");
if (CreatJosephus(tail, n, M)) {
printf("（2）当前 Josephus 环为：");
OutputJosephus(tail);
printf("请输入初始密码：");
while (m <= 0) {
scanf("%d", &m); // 密码必须为正数
}
printf("（3）Josephus 环求解结果为：");
if (!Josephus(tail, m)) {
printf("求解失败！\n");
}
}
else {
printf("创建 Josephus 环失败！\n");
}
return 0;
}
五，运行效果
1.根据要求调试程序。
2.运行结果
