简介基于循环链表的约瑟夫死亡游戏C语言实现方案面向正在学习数据结构、准备课程设计或竞赛训练的计算机专业学生。压缩包内为单份docx文档体积仅18KB内容集中呈现约瑟夫环问题的设计思路、核心逻辑与可运行代码。文档首先讲解ElemType结构体、LNode结点及LinkList链表类型的定义方式随后详细演示创建带头结点循环链表的过程包括尾指针r指向最后结点、逐个插入新结点并最终释放头结点连成闭环在删除环节通过临时指针p寻找第PersonCount-1个结点用q保存待淘汰结点并调整后继关系。函数DieLinkList按报数间隔反复调用删除操作直到剩余人数满足设定主函数支持输入总人数、报数间隔和安全剩余人数并可输出抛入大海人员名单与船上剩余人员名单。已有3143人学习下载对于希望掌握循环链表删除操作和指针指向变化或快速完成约瑟夫环课程设计的读者这份资源能提供从算法思路到代码实现的可读参考。1. 约瑟夫死亡游戏一个人扔一个为什么这份C语言代码值得跑一遍约瑟夫死亡游戏是数据结构课里少有的“代码不长、坑却不少”的综合练习。它要你用循环链表模拟一群人围成一圈数到第 PersonCount 个人就把他抛入大海一直数到船上只剩 LeftTotal 个人为止。这份资源把完整可编译的 C 语言代码、设计思路和循环链表算法一次给齐适合刚学完结构体和单链表、想练指针和动态内存的 C 语言学习者也适合期末冲刺时拿来对比自己写的版本。我第一次写这道题时自认为链表操作很熟结果栽在删除结点的指针重接上调试了一晚上才意识到问题出在“谁是指向被删者的前驱”。这份代码恰好把这些易错点都摊开在面前值得一行行走读一遍。2. 循环链表怎么搭ElemType、LNode 和 CreateLinkList 的建环细节2.1 为什么选循环链表而不是数组做约瑟夫环约瑟夫环最简单的实现其实是数组加取模下标用(i PersonCount - 1) % n算出下一个出列位置。但数组删除一个人需要把后面所有元素往前搬每次删除都是 O(n)总复杂度到了 O(n²)。更重要的是数组方案把“围成一圈”的逻辑藏在取模运算里初学者很难直观看到“报数”这件事发生在谁身上。循环链表的好处在于每个结点天然只知道自己后面的一个人末尾结点的 next 又指回首结点整个环长得就和“围成一圈的人”一模一样。删除一个人只需要让前驱结点的 next 跳过它时间复杂度 O(1)。代价是要小心处理指针而这道题的核心考点恰恰就是指针操作。用链表还有一个隐藏优势人一旦被扔下海就在物理上离开了那张环打印剩余名单时你看到的就是真实剩下的结点不需要额外维护一个 alive 数组。2.2 三层 typedef把数据、结点、链表分开声明的好处看代码开头这三段声明很多初学者会觉得啰嗦但它其实是这道题最容易照抄出错的地方。typedef struct ElemType { // 元素类型一个人有两个属性 int position; // 编号 char name[8]; // 姓名 } ElemType; typedef struct LNode { // 结点类型数据域 指针域 ElemType data; struct LNode *next; } LNode; typedef LNode *LinkList; // 链表类型本质上就是结点指针为什么要把 ElemType 单独拉出来因为后续算法只关心“删除第 i 个结点并取出它的数据”如果某天题目要求给每个人加年龄、性别你只需要改 ElemType 这个结构体删除和建环的代码一行都不用动。LNode 用struct LNode *next而不是LNode *next是因为在 C 语言里结构体内部引用自身时类型别名 LNode 还没定义完必须写全struct LNode。这是 C 语言初学阶段最容易踩的编译错误。LinkList 定义成指针类型之后函数参数就写成LinkList L修改 L 的值可以直接反映到调用方省去了二级指针的麻烦。2.3 CreateLinkList 的七个步骤带头结点、尾插、闭环、释放头结点建环是整份代码里最值得逐行读的函数因为它在“带头结点”和“不带头结点”两种写法之间做了一次漂亮的切换。void CreateLinkList(LinkList L, int n) { LinkList r, p; int i; L (LinkList)malloc(sizeof(LNode)); // 1. 先建一个头结点占位 L-next NULL; r L; // 2. r 始终指向当前最后一个结点 for (i 1; i n; i) { p (LinkList)malloc(sizeof(LNode)); // 3. 新建人员结点 p-next NULL; // 4. 新结点先断尾 p-data.position i; // 5. 写入编号 printf(请输入%d 个人员姓名, i); scanf(%s, p-data.name); // 6. 写入姓名 r-next p; // 7. 接在尾结点后面 r p; // 8. 新结点成为新的尾 } r-next L-next; // 9. 尾结点指向第一个人员结点闭合成环 free(L); // 10. 头结点用完释放 L r-next; // 11. L 直接指向第 1 号人员 }这里的核心步骤是最后三行。r-next 原本是 NULL在 for 循环结束后把它改成 L-next也就是第 1 号人员结点的地址环就闭合了。为什么建环时先用一个头结点因为 L 一开始是空链表没有头结点的话插入第一个结点时要单独判断“当前是不是第一次插入”代码分支会多一套。用头结点做占位所有插入都统一走“尾结点的 next 指向新结点”逻辑更简洁。闭合之后头结点就完成了使命把它 free 掉再让 L 指向第 1 号人员这样后面的删除逻辑里L 就始终是“当前报数起点”不需要每次穿过一个空头结点。参数说明n 是船上总人数也就是要创建多少个人员结点。这个函数执行完之后L 指向编号为 1 的结点整个链表呈环状。如果你把 free(L) 这行去掉后面所有遍历都会多一个头结点干扰打印会多出一行空数据删除报数也会错位一个位置。3. 删除与抛人入海DeleteLinkList 和 DieLinkList 的报数逻辑3.1 指针移动到第 PersonCount 个人删除函数的循环体删除函数是全代码最容易看晕的地方因为找到待删结点之前的那一步决定了整段指针操作是否正确。void DeleteLinkList(LinkList L, int i, ElemType e) { LinkList p; p L; int j 1; while (j i - 1) { // 从当前起点出发向后移动 i-2 次 p p-next; j; } e p-next-data; // 取被删者的数据 L p-next-next; // 下一轮报数起点被删者的下一个 p-next p-next-next; // 前驱跨过被删者 }这个函数做的事是从 L 指向的结点开始数到第 i 个人把他删掉。注意循环条件是j i - 1当 i2 时循环体一次都不执行p 还停在 L 上删除的是 p-next也就是从 L 往后数的第 2 个人。当 i3 时循环执行一次p 移到 L 的下一个人删除 p-next正好是第 3 个人。逻辑上是自洽的。真正关键的是L p-next-next这一行它把下一轮报数的起点设置成了被删者的下一个人这样 DieLinkList 的下一次调用不需要额外移动指针直接就能接着报数。这三行代码的顺序也不能换如果先改 p-next 再取 Lp-next-next 已经被改变L 指向的位置就错了。3.2 谁负责释放内存原版代码漏掉的 free原版删除函数里只看到指针重接没有看到 free。这在课堂演示里能跑出正确结果因为操作系统会在程序退出时回收所有分配的内存但这不是好习惯。被删结点已经从链表上摘下来它的内存却没有归还如果这段代码嵌进一个长时间运行的服务每次抛一个人入海就漏一小块内存跑几万次之后内存占用会明显上涨。正确写法是先用一个临时指针 q 保存待删结点的地址完成指针重接后再free(q)。void DeleteLinkList(LinkList L, int i, ElemType e) { LinkList p L, q; int j 1; while (j i - 1) { p p-next; j; } q p-next; // q 指向被删者 e q-data; // 先保存信息后面 q 就不能再用了 p-next q-next; // 跨过被删者 if (L q) // 如果删除的是当前起点 L q-next; // 下一轮起点变为被删者的下一个 free(q); // 归还内存 }我在自己写的时候习惯把e q-data放在指针重接之前因为 q-next 被改写成 p-next 之后q 本身的数据域还是完整的但更稳妥的做法是先把数据取出来再动指针避免以后改成别的数据结构时踩到悬垂指针。参数 i 表示报数间隔 PersonCounte 是输出参数用来把被删者的编号和姓名带回给调用方打印。3.3 主循环while(LeftCount LeftTotal) 而不是 for 循环抛人入海的主逻辑在 DieLinkList 函数里它负责建环、循环删除、打印被删名单。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); // 数到第 PersonCount 个人删除 LeftCount--; // 船上少一个人 printf(%d\t%s\n, e.position, e.name); } }这里为什么用 while 而不是 for因为删除次数不是提前固定好的它取决于 TotalCount 和 LeftTotal 的差值先把差值算成变量再用 for 当然也可以但 while 写出来更贴近题意“只要船上人还多就继续扔”。每次 DeleteLinkList 被调用时L 已经被上一次调用更新成新的报数起点所以看起来每次删除都只移动 PersonCount 次实际上去重了上一次的收尾工作。函数的三个输入参数中TotalCount 是总人数PersonCount 是报数到几就扔LeftTotal 是最后船上要剩多少人。3.4 复杂度能不能优化O(n×m) 的账要心里有数整个算法的时间复杂度是 O(TotalCount × PersonCount)因为每个被删的人从起点数到第 PersonCount 个平均要移动 PersonCount 个结点一共删除 TotalCount - LeftTotal 个人。这个复杂度在课程设计的数字范围里完全没有压力但如果你自己把总人数改成十万、报数间隔改成一万程序会肉眼可见地卡顿。到那时候要换思路后面第 6 章会聊数学解法和线段树方案。现阶段看懂链表版本的意义在于理解指针如何移动优化是在理解正确之后的事。4. 跑代码前的避坑几条来自真实编译和运行现场的踩坑记录4.1 编译期最容易翻车的输入与声明坑 1scanf(%s) 读取带空格的姓名导致编号和姓名错位现象输入“张三 李四”时程序只读到了“张三”李四被当成下一个人的姓名读走后面所有姓名都错位运气差一点的直接读进越界内存。原因scanf 用 %s 读字符串时遇到空格或换行就停止name[8] 只留了 8 个字节多读几个字就缓冲区溢出。中文在 UTF-8 编码下每个字占 3 字节8 字节连 3 个汉字都装不下。解决把姓名数组扩到char name[32]scanf 格式串加宽度限制scanf(%31s, p-data.name)或者干脆用scanf(%[^\n], p-data.name)读到换行才停。我一般用带宽度限制的 %s兼顾安全和简单。坑 2在 Visual Studio 里 scanf 直接报 C4996 错误在 Linux 下用 gcc 又提示符号比较告警现象同一份代码在 VS 里编译不过报“scanf 不安全建议使用 scanf_s”在 Linux 的 gcc 下编译通过但有 warning说while (j i - 1)里 int 和 unsigned int 比较。原因不同编译环境的运行时库策略不同VS 默认把 scanf 列为不安全函数gcc 的-Wall打开后会对有符号和无符号比较发出警告。解决课程作业可以按原代码提交自己复现时我建议统一用 gcc 的-Wall -Wextra编译把告警当错误对待。想在 VS 里省事可以在文件最前面加#define _CRT_SECURE_NO_WARNINGS但这不是改掉了问题只是绕过了检查。4.2 运行期那些让你怀疑人生的边界输入坑 3报数间隔为 1 时删除的人不对现象总人数 5、报数间隔 1、剩 0 人按规则应该按 1、2、3、4、5 的顺序把人全扔下去但程序先删 2 号再从 3 号开始数输出顺序变成 2、3、4、5……最后还剩一个 1 号删不掉。原因DeleteLinkList 的实现是“删除当前起点的下一个结点”这等价于数到第 PersonCount 个人前提是 PersonCount 大于等于 2。当 PersonCount 等于 1 时“数到的第 1 个人”就是当前起点自己应该删除 L而不是 L 的后继。解决在 DeleteLinkList 开头加一个if (i 1)分支单独处理“删除当前起点”的情况做法是先找到 L 的前驱再把前驱的 next 指向 L 的 next。这个分支不能省考试时改成 m1 是很常见的刁钻测例。坑 4LeftTotal 大于等于 TotalCount或者输入 0 和负数现象输入总人数 5、报数间隔 3、剩余 6程序一个都不删直接打印全部人员输入报数间隔 0删除函数进入奇怪的状态甚至死循环。原因while (LeftCount LeftTotal)从一开始就不成立循环体不执行报数间隔 0 时删除函数里j i - 1变成j -1永远不会进入循环删除的永远是 p-next逻辑完全错乱。解决在 main 函数里对三个输入做合法性检查约定PersonCount 1、LeftTotal TotalCount、LeftTotal 0。非法输入直接打印提示并重新读不要进算法。这个小习惯能帮你在课设演示时避免被老师输入刁钻数字当场难住。坑 5被删结点不 free运行久了内存泄漏printf 输出顺序时好时坏现象把代码嵌进循环跑十万次内存占用不断上涨在终端里运行输出正常重定向到文件后输出顺序变得奇怪甚至程序崩溃时最后几条名单没写进文件。原因原版 DeleteLinkList 没有释放被删结点游离结点只失去引用内存没归还。printf 到终端是行缓冲遇到换行就刷而重定向到文件变成全缓冲要等缓冲区满才写程序崩溃时缓冲区残留数据全部丢失。解决删除函数里补上 freemain 函数末尾加fflush(stdout)或直接return 0之前主动 flush。我自己的习惯是调试阶段加setbuf(stdout, NULL)关掉缓冲让每条输出立刻落盘排查输出顺序问题特别管用。5. 编译运行与验证用几组数字确认逻辑真的算对了5.1 在一台干净环境里把它编译跑起来把修正后的完整代码存成 josephus.c在终端里编译gcc -Wall -Wextra -g josephus.c -o josephus-Wall 和 -Wextra 打开所有常见告警-g 保留调试信息方便后面用 gdb。编译通过后运行./josephus程序会先让输入总人数再输入报数间隔最后输入需要剩余的人数。注意这是一个交互式程序输入三个数字时每个都要按回车不能在同一行用空格分开。如果你想一次把三个值都喂进去可以用下面这条命令echo 7 3 1 | ./josephusstdin 被重定向之后scanf 会依次从 echo 的输出里读走 7、3、1不需要人工干预。这个方法特别适合批量回归测试改一个数字跑一遍不用反复敲键盘。5.2 三组测试用例标准答案对上了才敢往下走我每次拿别人的约瑟夫代码第一件事就是用三组数字验正确性对不上直接放弃。下面这张表里的结果都是手推能算出来的总人数报数间隔剩余人数抛入大海顺序最后幸存者7314, 2, 7, 6, 3, 155212, 4, 1, 535101, 2, 3, 4, 5无第一组是约瑟夫环的经典场景 n7、m3幸存者编号为 5网上所有资料都能印证。第二组 n5、m2 的手推过程很短适合逐步对照你的指针移动。第三组就是上一章说的 m1 边界修正之前的原代码在这里直接翻车。这三组用例跑完删除顺序和幸存者都对程序基本就可以交差了。5.3 用 printf 观察指针移动别靠脑补链表题的调试黑匣子问题在于指针在环上绕圈打印结点值也不直观。我会在 DeleteLinkList 的 while 循环里临时加一行printf([debug] p moves to position %d, j%d\n, p-data.position, j);运行之后能看到 p 每一轮停在几号结点、j 走了多少次。对照着输入 “5 2 1” 的预期删除顺序你会发现第一轮 p 从 1 号出发没有移动直接删了 2 号第二轮 p 从 3 号出发不动删 4 号。每一轮的起点正好是上一轮被删者的下一个这个规律用眼睛看代码不好发现打印出来一眼就通。如果要用 gdb编译时带 -g然后gdb ./josephus break DeleteLinkList run程序会在每次删除进入函数时停下print *p看前驱结点数据print p-next-data看被删者数据print L-data看下一轮起点。观察两轮之后你对L p-next-next这行代码的理解就再也不会忘了。5.4 把手工测试脚本化一组命令回归所有边界把上面三组测试用例写成一个 shell 脚本以后每次改代码直接跑一遍for data in 7 3 1 5 2 1 5 1 0; do echo $data | ./josephus echo --- done输出里如果第二组的删除顺序不是 2, 4, 1, 5说明指针移动步数有误如果第三组不是 1, 2, 3, 4, 5说明 m1 的分支还没修对。脚本化的好处是做完一次改动几十秒内就能确认没有把原来好的功能改坏。我一般还会加一组 “1 3 1”总人数 1、报数间隔 3、剩余 1这时应该不删任何人直接打印 1 号。这个用例专门检查建环是否成功以及环闭合时 L 是否指向了正确的首结点。6. 三种进阶用法从课堂作业到拿得出手的代码6.1 改成不带头结点的版本原代码里建环时先建头结点、闭合后再释放很多教材讲循环链表时直接就是不带头结点。改法很简单CreateLinkList 里删掉L (LinkList)malloc(sizeof(LNode))这行把L NULL插入第一个人员结点时单独判断一次if (L NULL) { L p; } else { r-next p; }循环结束后同样让r-next L闭合。这样 L 从头到尾都指向 1 号结点删除函数的 m1 分支里找前驱的 while 循环条件pre-next ! L依然成立。不带头结点的写法人人都能看懂面试时聊这道题主动提这个改动会显得你是真的理解头结点的作用而不是背下来的模板。6.2 封装成函数返回完整出列顺序课堂版代码把输入输出全部写死在 main 里换个场景就没法复用。我一般会拆出一个JosephusSequence函数把删除顺序存进数组返回int* JosephusSequence(int n, int m, int* outLen) { // 建环循环删除并记录 e.position最后把顺序数组返回 // outLen 记录实际删除人数即 n - LeftTotal }这样命令行的交互版本只是一层壳核心算法可以被图形界面、Web 后端或其他模块调用也方便写单元测试。做课设答辩时老师看到你拆分了函数并留了接口观感会比一个几百行的 main 函数好不少。6.3 总人数很大时的替代方案链表方案的复杂度是 O(n×m)当 n 到了十万、m 到了几千跑一次要数几亿次明显吃力。如果只需要知道最后幸存者的编号用数学递推int survivor 0; for (int i 2; i n; i) survivor (survivor m) % i; // 幸存者编号 survivor 1这是约瑟夫环的标准 O(n) 解法代码一共三行跑一百万人的规模也毫秒级完成。但它只能算幸存者拿不到完整的删除顺序。如果需要完整的删除顺序又要 n 很大常见做法是把链表换成线段树或树状数组每次用二分找下一个出列位置复杂度降到 O(n log n)。这两种方案都是课程设计之后值得继续了解的方向但现阶段先把自己的链表演示代码走通更重要。从那以后我每次写完链表题都会强制自己先跑一遍空表、单结点、m1、m大于总人数、LeftTotal为0这五组用例再谈功能对不对。指针这种东西错一步后面全是玄学提前把边界堵住能省下大半夜。这份代码你照着跑通一遍再试着手改掉我提的这几个坑链表这块就真的吃透了希望帮到你。本文还有配套的精品资源点击获取