简介这份资源围绕经典的约瑟夫死亡游戏展开面向正在学习C语言数据结构与算法、需要理解循环链表实际应用的初学者和进阶者帮助其把抽象的链表操作落到一个完整可运行的小项目上。压缩包内共1个docx文档约18KB以设计思路与代码讲解为主涵盖元素类型与结点类型的结构体定义、带头结点循环链表的创建、按指定计数删除结点、以及最终输出剩余人员名单等完整流程并附有可直接参考的C语言源码。内容从ElemType、LNode到LinkList逐层展开配合CreateLinkList、DeleteLinkList、DieLinkList等函数说明便于读者对照理解指针移动、尾指针维护与环形连接的关键细节。目前已有3145人学习适合用来巩固循环链表算法思想、完成课程设计或课后练习时参考借鉴。1. 约瑟夫死亡游戏一份能直接跑起来的 C 语言循环链表实现第一次看到「约瑟夫死亡游戏」这个标题很多人以为是某个恐怖小游戏点进来才发现是一道经典的数据结构题一群人围成圈从某个位置开始报数数到指定数字的人出列剩下的人继续从下一个位置报数直到圈里只剩指定人数为止。这份 C 语言代码把它做成了一个可交互的控制台程序输入总人数、报数上限、需要剩余的人数程序就会打印出被「抛入大海」的人员名单和最终幸存者名单。它适合两类人正在学循环链表、想找一个能跑通的完整案例的初学者以及需要一份结构清晰、方便改造成其他淘汰规则比如报数间隔变化、多人同时出列的参考实现的开发者。代码不长但把带头结点建表、环形连接、按位置删除、头指针重设这几个循环链表的核心动作都串起来了拿来当模板改比从零写省事得多。2. 项目结构与技术选型为什么是循环链表而不是数组2.1 三个类型定义撑起整个数据模型这份代码的类型设计很克制只用了三个 typedef但层次分明。ElemType描述「一个人」——位置编号加姓名LNode描述「链表结点」——数据域加指针域LinkList直接就是LNode *也就是指向结点的指针。这种写法在数据结构教材里很常见好处是函数签名里写LinkList L一眼就知道传的是链表头指针的引用C 语言里用引用需要.cpp后缀编译或者改成二级指针LinkList *L这是第一个要注意的编译细节。typedef struct ElemType { // 元素类型一个人 int position; // 位置编号从 1 开始 char name[8]; // 姓名最多 7 个字符 结束符 } ElemType; typedef struct LNode { // 链表结点 ElemType data; // 数据域 struct LNode *next; // 指针域指向下一个结点 } LNode; typedef LNode *LinkList; // 链表类型就是结点指针name[8]这个长度是硬编码的输入超过 7 个字符的姓名会越界写内存实际用的时候要么改大要么在scanf里加宽度限制%7s。position用int存编号人数上万也没问题但如果要做超大规摸模拟可以换成long。2.2 带头结点建表再断头是这份代码的关键手法CreateLinkList的思路是先建一个头结点当「占位符」尾指针r始终指向最后一个结点每读一个人就新建结点挂到尾部全部挂完后让尾结点的next指向第一个真实结点L-next形成环最后free(L)释放头结点把L挪到第一个真实结点上。这个「先带头、后断头」的套路比直接建不带头结点的环少了很多边界判断尤其是空表和单结点的情况。void CreateLinkList(LinkList L, int n) { LinkList r, p; int i; L (LinkList)malloc(sizeof(LNode)); // 头结点 L-next NULL; r L; // r 永远指向尾结点 for (i 1; i n; i) { p (LinkList)malloc(sizeof(LNode)); p-next NULL; p-data.position i; printf(请输入%d 个人员姓名, i); scanf(%s, p-data.name); r-next p; // 挂到尾部 r p; // 尾指针后移 } r-next L-next; // 尾连头成环 free(L); // 释放头结点 L r-next; // L 指向第一个真实结点 }参数n是总人数循环里i从 1 到n正好对应编号。注意r-next L-next这一句必须在free(L)之前执行因为L-next存的是第一个真实结点的地址释放头结点后这个地址还在r-next里所以L r-next仍然有效。如果先free再取L-next就是访问已释放内存属于典型的 use-after-free调试时可能不报错但结果随机。2.3 删除第 i 个结点时头指针为什么要跟着动DeleteLinkList负责「数到第 PersonCount 个人就删掉」。它从当前头指针L出发走i-2步找到目标结点的前驱p然后q p-next是要删的结点保存数据到e再p-next q-next把 q 摘掉。关键在最后一句L p-next因为删除后下一轮报数要从被删结点的下一个开始所以头指针必须挪到q-next的位置否则下一轮会从旧位置重复数逻辑就乱了。void DeleteLinkList(LinkList L, int i, ElemType e) { LinkList p L, q; int j 1; while (j i - 1) { // 走到第 i-1 个结点 p p-next; j; } q p-next; // q 是第 i 个结点 e q-data; // 保存被删者信息 L q-next; // 下一轮从 q 的下一个开始 p-next q-next; // 摘链 free(q); // 释放 }这里有个隐含前提i 2。如果PersonCount输入 1while (j 0)一次都不执行p还停在头指针q p-next删的是第二个人逻辑就偏了。实际使用中报数上限至少是 2输入校验可以加一句if (i 2) return;兜底。另外这个函数没有处理「环里只剩一个结点」的情况删到最后一人时q-next指向自己L q-next和p-next q-next都指向自己虽然不会崩但后续遍历要小心死循环。2.4 主循环剩余人数控制淘汰节奏DieLinkList是调度中心先建表然后while (LeftCount LeftTotal)反复调用删除函数每删一个打印一行直到剩余人数达到安全线。LeftCount初始等于TotalCount每轮减一这个计数器就是循环的终止条件。void DieLinkList(LinkList L, int TotalCount, int PersonCount, int LeftTotal) { ElemType e; int LeftCount TotalCount; CreateLinkList(L, TotalCount); printf(跑到大海中人员名单\n编号\t姓名\n); while (LeftCount LeftTotal) { DeleteLinkList(L, PersonCount, e); LeftCount--; printf(%d\t%s\n, e.position, e.name); } }参数含义TotalCount总人数PersonCount报数到几淘汰LeftTotal需要保留的人数。注意函数名DieLinkList和正文里写的ThrowPerson不一致这是原始代码的命名改的时候统一一下就行不影响逻辑。DisplayLinkList负责打印幸存者从L开始打印然后while (p-next ! L)绕一圈回到起点停止这个遍历方式依赖环的完整性如果前面删除逻辑把头指针弄丢这里就会死循环或者打印错乱。3. 跑起来编译、输入与输出验证3.1 编译环境与引用参数的处理代码用了LinkList L这种 C 引用语法直接存成.c用 gcc 编译会报错。两种办法一是把文件后缀改成.cpp用g编译二是把引用改成二级指针函数内用*L访问。我一般选第一种改动最小。# 保存为 joseph.cpp g joseph.cpp -o joseph ./joseph如果坚持用纯 C把CreateLinkList(LinkList L, ...)改成CreateLinkList(LinkList *L, ...)函数体里所有L改成*L调用处传L。DeleteLinkList同理。这个改动涉及十几处改完记得每个L-next都检查一遍。3.2 一组可复现的输入输出用 5 个人、报数到 3、保留 2 人做验证输入姓名 A B C D E程序应该先淘汰编号 3 的 C然后从 D 开始数淘汰编号 1 的 A最后剩 B、D、E 中的两人。实际跑出来淘汰顺序是 3、1、5幸存 2、4。这个结果可以手算核对初始 1(A) 2(B) 3(C) 4(D) 5(E)从 1 数到 3 是 C删 C 后从 D 数D 是 1、E 是 2、A 是 3删 A再从 B 数B 是 1、D 是 2、E 是 3删 E剩 B 和 D。对上了说明删除和头指针重设的逻辑是自洽的。提示输入姓名时不要带空格scanf(%s)遇到空格就截断名字里有空格会读错位。3.3 边界输入会暴露哪些问题总人数输入 0 时CreateLinkList里r-next L-next等于NULLfree(L)后L r-next也是NULLDieLinkList的while条件0 LeftTotal如果LeftTotal是 0 就不进循环DisplayLinkList直接对NULL取data段错误。总人数 1、保留 1 人时建表后r-next指向自己L指向自己DisplayLinkList打印第一个人后p-next ! L为假正常退出这个边界反而是安全的。报数上限大于总人数时DeleteLinkList的while会绕环多走几圈因为环是闭合的p不会越界但j只增不减走够i-1步就停逻辑上等价于取模结果仍然正确只是多绕了几圈。这些边界情况建议在main里加输入校验比如TotalCount 1、PersonCount 2、LeftTotal TotalCount。4. 避坑与排查五个真实会踩的坑4.1 编译报错「expected ) before token」现象gcc 编译.c文件报引用语法错误。原因引用是 C 特性C 编译器不认。解决改后缀为.cpp用 g 编译或者把引用参数改成二级指针。我倾向改后缀因为二级指针要把函数里所有L-改成(*L)-容易漏改。4.2 运行后淘汰名单重复或人数不对现象淘汰列表里同一个人出现两次或者淘汰人数超过TotalCount - LeftTotal。原因DeleteLinkList里L p-next-next和p-next p-next-next的顺序如果写反或者L没有更新下一轮会从旧头开始数导致重复淘汰。解决严格按「先存q、再存e、再L q-next、再p-next q-next、最后free(q)」的顺序写L的更新必须在free之前因为q-next在free后就不可读了。4.3 幸存者打印死循环现象DisplayLinkList一直打印停不下来。原因删除过程中某次p-next q-next把环打断了p-next变成NULLwhile (p-next ! L)永远为真p p-next走到NULL后解引用崩溃或者环没断但L指向的结点被误删遍历永远回不到起点。解决在DeleteLinkList里加断言或打印确认每次删除后L非空且L-next能绕回L调试时可以先只删一个人手动检查环结构。4.4 姓名输入越界导致后续数据错乱现象输入较长姓名后淘汰名单里的编号或姓名变成乱码。原因char name[8]只能存 7 个字符scanf(%s)不限制长度超长输入覆盖了相邻内存。解决把name改大比如char name[32]同时scanf改成scanf(%31s, p-data.name)。这个坑在本地跑小数据时不明显一换真实姓名就翻车。4.5 总人数为 0 或保留人数等于总人数时段错误现象输入 0 人直接崩溃或者保留人数等于总人数时打印异常。原因空链表时L为NULLDisplayLinkList无条件访问p-data。解决main里加校验TotalCount 1直接提示重输LeftTotal TotalCount时跳过淘汰循环但DisplayLinkList仍要能处理「一个都没删」的情况此时L是完整环遍历正常所以真正要防的是TotalCount 0。5. 二次开发把固定报数改成可配置规则并验证这份代码最值得改的地方是淘汰规则太死——报数上限固定、每次只淘汰一人、淘汰后从下一个开始。实际业务里常见的变体是「报数上限逐轮递增」或者「淘汰后跳过 k 个人再开始数」。改法是在DieLinkList里维护一个step变量每轮传给DeleteLinkList之前调整它。void DieLinkList(LinkList L, int TotalCount, int PersonCount, int LeftTotal) { ElemType e; int LeftCount TotalCount; int step PersonCount; // 初始报数上限 CreateLinkList(L, TotalCount); printf(淘汰名单\n编号\t姓名\n); while (LeftCount LeftTotal) { DeleteLinkList(L, step, e); // 用动态 step 代替固定值 LeftCount--; printf(%d\t%s\n, e.position, e.name); step; // 每轮报数上限加一 if (step LeftCount) step 2; // 防止 step 超过剩余人数太多 } }改完之后验证方法很直接固定输入 6 人、初始报数 2、保留 1 人手算第一轮淘汰编号 2第二轮 step 变 3从 3 开始数 3 个淘汰 5第三轮 step 变 4从 6 开始数 4 个绕回淘汰 4依次推下去把程序输出和手算结果逐行比对。如果对不上优先检查step在DeleteLinkList里的取模行为——因为环是闭合的step大于剩余人数时会多绕圈结果等价于step % LeftCount但前提是DeleteLinkList的while (j i - 1)能正确走完不会因为i太大而提前撞上NULL。另一个改造点是给DeleteLinkList加返回值返回被删结点是否成功方便上层判断环是否已经退化到单结点。我自己的习惯是每次改完删除逻辑先用 3 人、报数 2、保留 1 人这种最小用例跑一遍确认淘汰顺序和幸存者都对再放大到 10 人以上。小用例能暴露头指针更新和环闭合的问题大用例才能看出计数器和终止条件有没有写错。从那以后我每次动循环链表的删除函数都强制先跑最小用例再跑随机用例省了不少回头查free之后野指针的时间。希望帮到你。本文还有配套的精品资源点击获取
