简介以经典约瑟夫生死游戏为驱动案例面向正在学习C语言数据结构、尤其是链表与指针部分的本科或专科学生解决“如何用循环链表高效模拟围圈报数、逐人淘汰与幸存者输出”的算法设计问题。文档从问题建模讲起先定义包含编号与姓名的ElemType结构体再设计LNode结点与LinkList链表类型随后实现创建环形链表、定位并删除第PersonCount个结点、按剩余人数控制循环次数等关键函数完整覆盖了带头结点创建、尾插法成链、释放头结点后连接成环、删除后重新调整头指针等核心细节。循环链表天然契合环形报数场景这份实现正好展示了其遍历删除优势。资源包共1个docx文件整体仅18KB内容紧凑包含可直接运行或移植的C语言源码及逐步思路说明便于课前预习、期末复习或课程设计参考。目前已有3143人学习下载对希望快速理解循环链表增删逻辑和约瑟夫环完整实现的读者来说是一份高性价比的学习资料。1. 约瑟夫死亡游戏是什么一个从小游戏到算法题的经典模型约瑟夫死亡游戏也叫约瑟夫环是C语言学习里绕不开的一道题n个人围成一圈从固定位置开始报数每报到k就淘汰一个人淘汰后从下一个人重新报数直到剩最后一个人。很多读者第一次见到它是在课程设计里要求用C语言模拟整个过程第二次见到它是在数据结构课的链表章节第三次见到它可能是在面试题里要求用O(1)数学解法。这篇文章不讲空泛的“链表删除很简单”而是把数组模拟、循环链表、数学递推三种C语言实现都拆开给出可直接运行的代码、参数怎么设、以及我踩过的几个内存和下标坑。适合正在做课程设计、准备面试、或者想把这个经典问题一次吃透的从业者。2. 三种C语言实现的选型逻辑数组、链表、数学递推约瑟夫环的C语言实现没有唯一标准答案选型直接决定你会不会翻车。我的习惯是先问三个问题要不要输出淘汰顺序n是否可能过万k是否远大于n三个问题的答案组合对应数组模拟、循环链表、数学递推三种不同写法。数组模拟最贴近人的直觉适合n不太大、需要按顺序打印淘汰过程的场景循环链表完美复现“围成一圈删除节点”的游戏过程但动态内存操作很容易埋雷数学递推只求幸存者编号性能最好却无法告诉你中间谁先出局。下面逐个拆开。2.1 数组模拟状态标记与环形下标回绕数组版本是我在新手阶段第一个写对的实现核心思路是用一个长度n的数组保存每个人的存活状态1代表仍在圈内0代表已淘汰。每次报数从当前下标开始向后扫描遇到0就跳过数到k时把该位置置0报数计数器清零然后继续从下一个位置开始下一轮。这个写法的关键点在于环形下标的维护当cur走到数组末尾时必须回到0也就是cur (cur 1) % n。很多初学者在这里直接写cur导致数组越界这是第5章要展开的典型坑。#include stdio.h #include stdlib.h // 数组模拟约瑟夫环n个人报数到k出局 // 返回值为幸存者编号编号从0开始若参数非法返回 -1 int josephus_array(int n, int k) { if (n 0 || k 0) return -1; int *alive (int *)malloc(n * sizeof(int)); if (alive NULL) return -1; for (int i 0; i n; i) alive[i] 1; int remaining n; // 当前还在圈内的人数 int cur 0; // 当前从哪个下标开始报数 int count 0; // 报数累加器 while (remaining 1) { if (alive[cur]) { count; if (count k) { alive[cur] 0; remaining--; count 0; } } cur (cur 1) % n; // 环形下标走到末尾自动回到0 } int survivor -1; for (int i 0; i n; i) { if (alive[i]) { survivor i; break; } } free(alive); return survivor; }这段代码的逻辑是cur每轮无条件向后移动但只有alive[cur]为1时才累加报数所以已淘汰的人不会占报数位置。当count等于k时把当前位置标记为0幸存人数减1计数器归零。注意循环结束后数组里只剩一个位置为1再遍历一遍就能找到它的下标。参数说明n是总人数k是报数阈值两个都必须大于0。返回值使用0基编号如果题目要求从1开始数最终结果加1即可。这个版本的优点是逻辑清晰不需要任何动态删除缺点是每轮都要扫描包括已淘汰者在内的所有元素时间复杂度O(n*k)当n和k都很大时会明显变慢。2.2 循环链表删除节点时的前驱与内存释放链表版本更贴近“圈子里的人一个个离开”的直观感受每次淘汰就是一次节点删除不需要维护存活标记。但要小心C语言动态内存的两个隐藏坑删除节点前必须找到它的前驱尤其当要删除的是头节点时前驱是链表的最后一个节点另外free之后指针不能再被引用否则会触发double free或use-after-free。下面是一个可用的循环单链表实现。我用prev和cur两个指针一前一后走prev始终指向当前报数节点的前驱这样删除节点时可以无缝重接链表。#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; // 创建一个包含 n 个节点的循环链表编号为 0 到 n-1 Node* create_circular_list(int n) { Node *head NULL, *tail NULL; for (int i 0; i n; i) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) return NULL; // 内存不足直接返回 node-id i; node-next NULL; if (head NULL) { head node; tail node; } else { tail-next node; tail node; } } if (tail ! NULL) tail-next head; // 尾节点指向头形成环 return head; } // 链表模拟约瑟夫环返回幸存者编号0基 int josephus_list(int n, int k) { if (n 0 || k 0) return -1; Node *head create_circular_list(n); if (head NULL) return -1; Node *cur head; Node *prev head; // 先把 prev 移动到最后一个节点这样删除头节点时也有前驱 while (prev-next ! head) { prev prev-next; } while (cur-next ! cur) { // 当链表中不止一个节点 for (int i 1; i k; i) { // 当前节点已算报数1所以走k-1步 prev cur; cur cur-next; } // cur 就是要淘汰的人 Node *to_delete cur; prev-next cur-next; cur cur-next; free(to_delete); } int survivor cur-id; free(cur); return survivor; }逻辑说明先让prev指向尾节点是为了保证删除头节点时能通过prev-next cur-next把环重新接好。for循环移动k-1步是因为当前节点本身处于报数1的位置再走k-1步正好落到报数为k的人身上。删除后cur自动指向被删节点的下一个节点而这个节点正是下一轮报数的起点。参数说明k1时循环体不移动也就是说从cur开始数1个人该人立刻被淘汰行为符合定义。这个版本的空间复杂度是O(n)时间复杂度同样是O(n*k)但因为每次移动都要访问malloc出来的节点内存局部性比数组差实际在n很大时反而更慢。2.3 数学递推从淘汰结果反推幸存者编号数学递推是约瑟夫问题的最优解法时间复杂度O(n)空间复杂度O(1)。它不模拟过程只计算最终幸存者的编号核心递推公式是f(1) 0 f(i) (f(i-1) k) % i其中i是当前环的长度f(i)表示长度为i的环中最终幸存者的编号。推导思路是第一轮淘汰后剩下的 n-1 个人组成一个更短的环但这个环的起始点不再是原环的0号位而是被淘汰者的下一位。通过下标映射可以证明长度为 i-1 的环中的答案加上 k 再对 i 取模就得到原环中的答案。// 数学递推法不模拟过程直接返回幸存者编号0基 int josephus_math(int n, int k) { if (n 0 || k 0) return -1; int survivor 0; // 只有1个人时幸存者就是编号0 for (int i 2; i n; i) { survivor (survivor k) % i; } return survivor; }逻辑说明从i2开始向上迭代每一步复用前一步的结果。这里的k不需要预先取模因为C语言的%运算在正数范围内天然处理了survivor k超过i的情况。如果k非常大这个公式依然正确因为它等价于每轮移动k % i步取模由同一个表达式完成。参数说明这个公式默认编号从0开始且最初从编号0的人开始报数1。如果题目要求编号从1开始返回survivor 1即可。它最大的限制是无法输出淘汰顺序所以需要顺序过程时只能回到前两种模拟法。选型到这里已经清晰要过程用数组或链表只要结果用数学递推n很小用数组最简单n很大只能数学解面试时先问清楚输出要求再决定写法能省下大量调试时间。3. 可直接编译运行的C语言完整代码参数怎么配、结果怎么验上一章给的是函数级实现真正要跑起来还需要一个带入口的可执行程序。这一章我给出两种落地方案一种是把三个函数拼进同一个文件通过命令行参数切换另一种是在数组模拟基础上增加淘汰顺序输出适合课程设计需要展示过程。最后再聊一下参数校验避免用户输入非法值让程序直接崩溃。3.1 集成三种算法的完整程序与命令行参数把第2章里三个函数原型放在文件头部然后在main中根据命令行第三个参数调用对应的实现。下面是一个可以直接使用的main函数与第2章三个函数放在同一个.c文件中即可通过gcc编译运行。#include stdio.h #include stdlib.h #include string.h // 三个函数原型实现见第2章josephus_array / josephus_list / josephus_math int josephus_array(int n, int k); int josephus_list(int n, int k); int josephus_math(int n, int k); int main(int argc, char *argv[]) { if (argc 4) { fprintf(stderr, 用法: %s n k array|list|math\n, argv[0]); fprintf(stderr, 示例: %s 10 3 math\n, argv[0]); return 1; } int n atoi(argv[1]); int k atoi(argv[2]); const char *mode argv[3]; if (n 1 || k 1) { fprintf(stderr, 错误n 和 k 都必须大于 0\n); return 1; } int survivor -1; if (strcmp(mode, array) 0) { survivor josephus_array(n, k); } else if (strcmp(mode, list) 0) { survivor josephus_list(n, k); } else if (strcmp(mode, math) 0) { survivor josephus_math(n, k); } else { fprintf(stderr, 未知模式: %s\n, mode); return 1; } if (survivor 0) { fprintf(stderr, 计算失败\n); return 1; } printf(n%d, k%d, survivor(0基)%d\n, n, k, survivor); printf(编号从1开始的话幸存者是 %d\n, survivor 1); return 0; }把这个main和三个函数放进同一个文件后编译命令是gcc -o josephus josephus.c运行示例./josephus 100 7 math会直接输出幸存者的0基和1基编号。逻辑说明先检查命令行参数数量再用atoi转换前两个参数模式字符串用strcmp精确匹配。参数说明n和k使用十进制整数mode只接受三个固定字符串任何拼写错误都会在运行前被拦截。3.2 用数组版输出淘汰顺序过程可观察的改造很多课程设计的要求不仅是算出幸存者还要按顺序打印每一步被淘汰的人。数组模拟做这个改造最省事只需要在上面的while循环里加一个打印。下面是一个完整的josephus_array_verbose函数它在淘汰发生时立刻输出当前淘汰者的编号。#include stdio.h #include stdlib.h // 数组模拟按顺序输出淘汰者编号返回幸存者编号0基 int josephus_array_verbose(int n, int k) { if (n 0 || k 0) return -1; int *alive (int *)malloc(n * sizeof(int)); if (alive NULL) return -1; for (int i 0; i n; i) alive[i] 1; int remaining n; int cur 0; int count 0; printf(淘汰顺序: ); while (remaining 1) { if (alive[cur]) { count; if (count k) { printf(%d , cur); alive[cur] 0; remaining--; count 0; } } cur (cur 1) % n; } int survivor -1; for (int i 0; i n; i) { if (alive[i]) { survivor i; break; } } printf(\n幸存者(0基): %d\n, survivor); free(alive); return survivor; }逻辑说明每次count达到k时在置0前先打印当前cur这样输出顺序就是真实的淘汰顺序。注意打印的是0基编号如果题目要求1基在这个函数里把printf(%d , cur)改成printf(%d , cur 1)即可。参数说明这个函数和原版一样会修改数组内容但由于是局部数组每次调用都会重新分配所以可以反复调用。3.3 用strtol代替atoi参数校验不可省atoi虽然方便但它把非法输入比如abc静默转换成0也不检查是否溢出。如果用户误传n0程序可能在分配内存时直接崩溃。我一般用strtol做严格校验它能识别出非法字符并判断整值范围。#include stdio.h #include stdlib.h #include errno.h #include limits.h // 从命令行参数解析一个正整数失败返回 -1 int parse_positive_int(const char *str) { if (str NULL) return -1; char *end NULL; errno 0; long value strtol(str, end, 10); // 没有任何字符被解析或解析到非数字字符或发生范围错误 if (end str || *end ! \0 || errno ERANGE) { return -1; } if (value 1 || value INT_MAX) { return -1; } return (int)value; } // 用法示例 // int n parse_positive_int(argv[1]); // int k parse_positive_int(argv[2]);逻辑说明strtol会把str中尽可能多的连续数字字符转换为long并通过end指针返回剩余部分的位置。如果end str说明首字符就不是数字如果*end ! \0说明后面还跟着非空白、非数字的字符errno ERANGE说明数值超出long表示范围。三层检查过滤掉绝大多数非法输入。参数说明返回值限定在1到INT_MAX之间正好挡住数组大小为负或过大的情况。4. 约瑟夫死亡游戏的必调参数与边界条件n、k、start怎么选写约瑟夫环最怕的不是算法本身而是参数设定不清导致结果对不上。这一章把n、k、起始位置start三个参数的选型和边界讲透包含一组可以直接查用的典型值以及两个我反复踩过的细节。4.1 n与k的典型取值从课程设计到压测场景不同场景下的参数范围差异很大选错实现会让程序慢到怀疑人生。下面表格是我常用的参数配置参考按使用场景区分。场景典型n典型k推荐实现课程设计演示10 ~ 1003 ~ 10数组模拟带输出淘汰过程数据结构链表作业100 ~ 10001 ~ 100循环链表面试手写任意任意数学递推性能压测100000 ~ 1000000003 ~ 10000数学递推游戏过程模拟100 ~ 100002 ~ 50数组模拟k小注意k2是一个特殊场景它等价于“每隔一人淘汰一人”数学递推公式可以直接化简为survivor与n的二进制位运算关系。但工程上不需要背化简结论直接用通用递推计算即可。k越大模拟法每次报数需要移动的步数越多n越大数组和链表的劣势越明显这也是压测场景必须上数学解的原因。4.2 k大于n时先取模避免无效循环当k n时完整的报数过程会在圈内绕很多圈才淘汰一个人但最终效果等价于从起点移动k % remaining步。这里的remaining是当前存活人数每淘汰一个人都会变化因此不能只用k % n统一处理必须在每轮淘汰前重新取模。模拟链表时可以把第2章的for (int i 1; i k; i)优化为int steps k % remaining; if (steps 0) steps remaining; // 从当前节点走 steps-1 步到达报数为k的节点 for (int i 1; i steps; i) { prev cur; cur cur-next; }逻辑说明remaining是当前圈内还活着的人数。报数k次意味着移动k-1步但k可能很大取模后如果余数为0说明实际上移动了整整remaining圈相当于移动remaining步但我们要用stepsremaining来表示因为移动remaining-1步到达的节点正好是起点前一个不符合实际。参数说明这个优化只对数组和链表模拟有效数学递推公式里已经天然处理了取模无需额外操作。加了这一步之后即使k1000000000、n1000模拟速度也不会明显下降。4.3 起始位置start与返回值编号的关系递推公式默认从编号0的人开始报数1但很多实际问题会指定从某一个任意编号开始。比如游戏说“从3号开始数”这里的3号如果是0基则start3。此时不能直接套用前面的递推结果需要做一个偏移映射。数学递推的正确用法是先用原公式计算出0基起点时的幸存者编号f(n,k)再通过(f(n,k) start) % n得到以start为起点的真实幸存者编号。数组和链表模拟则可以直接把初始cur设为start逻辑天然正确。int josephus_math_with_start(int n, int k, int start) { int base josephus_math(n, k); // 0起点时幸存者编号 return (base start) % n; // 偏移到 start 起点 }逻辑说明start表示第一次报数1的人所在的0基编号。偏移的本质是环的线性变换原0基答案相对于起点的位置不变整体加上start再取模即可。参数说明start必须在0到n-1之间否则先做% n处理。这个细节也是最常见的“为什么数学解和模拟解对不上”的原因很多人在没有统一起点时直接比较结果自然不一致。5. 约瑟夫游戏实现的常见问题排查与避坑这一章把我在实际调试中遇到过的四个顽固问题写成排查记录每一条都按“现象 → 原因 → 解决”展开。如果你正在调代码建议先对照现象再去看原因不要一上来就重写整个逻辑。5.1 链表删除节点后free引发double free现象程序运行到中段经常崩溃报错类似double free or corruption (out)或者没有报错但结果偶尔正确偶尔错误属于典型的未定义行为。血泪经验是链表版本的问题很少出在算法思想上几乎都出在指针管理上。原因常见的错误写法是在free(cur)之后下一轮循环里又通过某个残留指针访问了cur。例如删除节点时先保存了next cur-next但在后续操作中错误地把prev-next重新指向了已释放的cur或者两个指针同时指向同一个节点导致再次进入循环时对同一个节点执行两次free。解决删除节点后只保留两个有效指针prev和新的cur。删除前先用prev-next cur-next接链再cur cur-next最后才free(to_delete)。只要to_delete不再被任何指针引用就不会出现double free。我还会在free后立刻把to_delete NULL方便在调试器里通过指针值判断是否存在悬空引用。Node *to_delete cur; prev-next cur-next; cur cur-next; // cur 先指向下一个有效节点 free(to_delete); // 最后才释放顺序不能反 to_delete NULL; // 习惯性置空调试时能立刻发现问题这段代码的关键是执行顺序接链、移动cur、释放旧节点。如果先free再移动cur那么cur-next本身就是非法访问程序会在下一行崩溃。这个顺序建议直接背下来。5.2 数组下标越界报数计数的逻辑顺序颠倒现象数组版本在n10, k3时输出淘汰顺序从1开始而不是预期的2或0甚至在某些参数下崩溃。用gdb查的时候cur变成了10而数组长度只有10可访问下标是0~9。原因循环体里先执行了cur (cur 1) % n再执行if (alive[cur])报数。这样第一次报数时cur已经从初始位置移动了一次相当于从初始位置的下一个人才开始报数而且最后一次循环移动后没有再次取模直接越界。本质是“报数”和“移动”的顺序没有按语义区分。解决先把当前节点判断完毕再移动cur。正确顺序是while (remaining 1) { if (alive[cur]) { count; if (count k) { alive[cur] 0; remaining--; count 0; } } cur (cur 1) % n; // 判断完成后才移动永远不越界 }这里的关键是cur的更新固定放在本轮处理之后而且更新时一定带% n。不要试图在if内部移动cur那样会让算法逻辑变得极其难读。把这行当成数组版本的“铁律”基本可以永别越界问题。5.3 数学递推结果和模拟结果不一致编号起点没对齐现象我写过一个测试n10, k3数学递推返回3但数组模拟返回2。两个函数单独跑都正确放一起就矛盾当时以为公式背错了查了半天才发现是起点问题。原因数学递推公式基于“编号从0开始从编号0的人最先报数1”而数组模拟里我为了打印方便把人的编号初始化为1~n并让cur0表示第一个人。这样数组里的编号实际是下标1与数学递推的0基编号天然错位1。另一个常见原因是起始位置start被误设成1而不是保持0。解决把两个实现统一为“内部0基编号输出时加1”。具体做法是数组和链表默认编号0~n-1数学递推返回0~n-1只在最后打印用户可见编号时加1。交叉验证时不要直接比较原始返回值而是统一先转成0基再做断言。我把这条规则写在代码文件开头注释里防止下次再看时又踩。5.4 大n时数组和链表直接卡死如何快速定位是死循环还是复杂度问题现象用数组版本跑n1000000, k10000程序像死了一样卡住不动CPU占用却很高。第一反应是while循环没退出在count和cur之间打了半天发现逻辑没问题最后才意识到是复杂度爆炸。原因数组模拟的时间复杂度是O(n*k)。n1000000, k10000时需要执行大约1e10次循环即使每次循环只有几条简单指令也足够让程序卡上几十秒甚至更久。链表的报数移动和内存访问开销更大遇到这种参数直接放弃模拟法才是正解。解决先用最快的方法估算总循环次数再决定要不要继续跑。以n*k大于1000000为警戒线超过就切到数学递推。如果必须看到淘汰过程比如课程设计要求可视化可以把k % remaining优化加上并把n降到1000以内。不要怀疑死循环先看复杂度这是排障的第一步。# 数学递推跑百万级参数是毫秒级时间对比一目了然 time ./josephus 1000000 10000 math # 数组版本的话建议CtrlC这行命令的用途是验证同样的参数数学解几乎瞬间完成模拟法却卡住说明问题在复杂度而不是算法逻辑。用time命令实测能帮你快速确认瓶颈。6. 验证方法用多算法交叉对比、用数学解做压力测试写完代码只是第一步验证方法决定了你敢不敢把它交出去。我的一贯做法是用三种实现互相打架随机参数对拍再用数学解压测极端情况最后把常用封装成一个工具函数。6.1 写一个交叉验证函数随机参数对拍三个版本对拍脚本的思路很简单生成大量随机的(n, k)分别调用数组、链表、数学递推版本断言三者结果一致。下面这个函数可以放在测试文件里跑10000组随机参数。#include stdio.h #include stdlib.h #include assert.h // 三个函数的原型前置 int josephus_array(int n, int k); int josephus_list(int n, int k); int josephus_math(int n, int k); // 随机参数对拍返回是否全部通过 int cross_validate(int tests) { for (int t 0; t tests; t) { int n rand() % 1000 1; // 1 ~ 1000 int k rand() % 1000 1; // 1 ~ 1000 int r1 josephus_array(n, k); int r2 josephus_list(n, k); int r3 josephus_math(n, k); if (r1 ! r2 || r1 ! r3) { fprintf(stderr, 对拍失败 n%d k%d r1%d r2%d r3%d\n, n, k, r1, r2, r3); return 0; } } return 1; }调用cross_validate(10000)如果返回1说明三个实现至少在0基编号、从0开始报数的约定下行为一致。逻辑说明rand()生成的范围经过取模控制在1000以内避免过大的n导致链表版本太慢。参数说明如果你想压测更大范围可以把%1000调高但链表版本在n超过10000后会非常吃力建议对拍时保持小参数。6.2 用数学解压测n1亿时C语言能跑多快对拍通过后我习惯用数学解验证极端情况。下面是实际压测时的命令和预期表现./josephus 100000000 100000000 math这行命令计算1亿个人、报数到1亿的幸存者编号。数学递推只需要做1亿次循环每次循环两条指令加法和取模在普通机器上大约0.1到0.3秒。如果换成数组模拟首先是内存分配alive数组需要400MB1亿个int多数课程设计环境直接失败其次是循环次数约1e16根本跑不完。这个对比说明选型不是玄学而是实实在在的工程决策。6.3 习惯建议把经典模型变成自己的工具箱我现在遇到约瑟夫问题已经不再从零写代码。习惯是先确认三个信息编号是0基还是1基、从哪个人开始报数、k是否可能远大于n。然后把递推公式封装成一个通用函数模拟版本只保留在需要输出淘汰过程的场景里。有一次做某模拟项目X需要计算几百万人的幸存者加上淘汰顺序的后半段我先用数学解得答案再用链表模拟到只剩100人的时候切换到数组整个过程快了很多。这种把多个实现组合使用的习惯比我当年只会一种写法时省下大量时间。希望这些经验能帮你少走弯路。如果你正被困在某个奇怪的约瑟夫变体里先别急着改代码把编号起点、报数起点和k的取模逻辑重新对一遍多半能找到突破口。希望帮到你。本文还有配套的精品资源点击获取