约瑟夫环C语言实现：循环链表核心算法与调试指南

约瑟夫环这道题写过的同学都知道说穿了就是循环链表加两个指针来回挪但当初我为了把它调通愣是在宿舍debug到凌晨。后来把“前驱指针”的思路理顺了再回头看其实这个题目考的就两件事把环形结构想清楚以及安全地删除一个链表节点。这篇文章我会用C语言完整拆解约瑟夫死亡游戏从数据结构选型、循环链表的构建、报数出列算法到数组模拟、数学递推公式最后附上我实际调试时踩过的一堆坑和测试建议。适合正在做课程设计、准备数据结构考试或者自学链表想找点实战项目的朋友。1. 约瑟夫问题到底在考什么循环链表的本质1.1 问题描述与建模思路约瑟夫问题最早来源于一个古老的传说故事一群人围成一圈按某种规则依次淘汰最后只剩下一个人。放到数据结构里标准描述是n个人编号为1到n围坐在一张圆桌周围从编号为1的人开始报数数到m的人出列然后从下一个人开始重新报数如此循环直到所有人都出列。题目通常要求输出出列顺序或者求出最后剩下的幸存者编号。我第一次拿到这个题目时第一反应就是这不就是一个循环遍历删除的过程吗确实如此。整个流程抽象出来包含三个核心动作沿着圈移动指定的步数、标记当前位置出列、从下一个位置继续。这三个动作不断重复直到圈内没有元素为止。这里有个容易忽略的地方题目里的“报数”是有方向性的始终沿着圆桌的同一方向前进并且报数起点是上一个出列者的下一位。这意味着数据集合必须支持“绕回头”的遍历方式。如果用数组写你需要在访问到末尾时手动把下标重置为0如果用链表写则天然支持从头绕回。所以这道题目的建模关键就是找出一种能自然表达“环形遍历”的数据结构。1.2 为什么循环链表是首选方案教科书和大多数习题把约瑟夫环放在“链表”章节不是没有原因的。它的核心操作是反复删除节点而单链表和循环链表删除节点只需要O(1)的指针修改操作不需要搬运数据。相比之下顺序表删除元素需要把后面的元素整体前移最坏情况是O(n)在n较大的时候开销很可观。另外一点很关键循环链表的next指针天然形成了“环形”的拓扑结构插入、删除、绕圈遍历都符合约瑟夫环的运行语义。你不用像数组那样在每次到达尾部时判断一下“该不该绕回0号下标”结构本身就帮你处理了边界。不过实话实说这不是唯一能做的方案。数组加状态标记也能模拟出列过程只是逻辑删除后仍需遍历剩余元素时间复杂度会高一些。我把数组模拟和数学递推放在第4章详细对比那种方案代码更短但可解释性和教学价值不如循环链表。如果目标是“理解数据结构如何解决实际问题”循环链表是最贴题的选型。1.3 复杂度分析与整体设计在链条很长的场景下每轮从报数开始到找到出列者需要移动m步每移动一步就是一次p p-next操作所以单轮复杂度是O(m)。总共n个人出列整体复杂度是O(n × m)。这个复杂度不算优秀但对于课程设计和入门学习完全够用因为重点是通过代码理解链表操作的本质。如果想优化可以使用数学递推公式把时间复杂度降到O(n)但那只适合求解最后一个幸存者的编号无法输出完整出列顺序。所以我的方案是主实现采用循环链表保留完整的出列过程额外提供一个数组模拟和一个数学公式实现用于对比和扩展。整体设计上我先实现一个环形链表的构建函数再做约瑟夫环出列函数最后在main函数中串起来。为了让代码可读性更高我还会加一个打印循环链表的辅助函数方便调试时确认链表结构是否正确。2. 从节点到循环链表核心数据结构一步步来2.1 节点结构体与基本约定链表的基本单位是节点。约瑟夫环里每个节点代表一个参与游戏的人节点里需要存储两样东西这个人的编号以及指向下一个人的指针。typedef struct Node { int data; struct Node *next; } Node;这里有个初学者容易纠结的问题data用什么类型。约瑟夫环的编号是正整数用int就够了。如果你以后想扩展成存储字符串姓名或者更复杂的信息可以把data替换成更复杂的结构体但这道题没必要。再来说说“头节点”的问题。我在教学代码中看到很多版本会创建一个不存数据的头节点再用它来管理循环链表。但约瑟夫问题描述的是一圈人没有“空节点”的概念所以代码里我不会引入单独的头节点而是直接让第一个实际节点充当“入口”。这样做有个好处打印链表时从任何一个节点出发绕一圈就能看到全部节点出列时所有节点都是实际参与者不存在跳过哨兵节点的判断。缺点是需要小心处理空链表不过输入n1时不会出现空链表。2.2 创建循环链表尾插法与成环构建一个包含n个节点的循环链表通常使用尾插法每次在链表尾部追加新节点最后把尾部节点的next指向头部节点。Node *createLoop(int n) { Node *head NULL; Node *tail NULL; for (int i 1; i n; i) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data 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; }第i个节点的data就是编号i这样编号天然有序。第一次插入时head和tail都指向同一个节点后续每次插入新节点挂在tail后面tail再往后移动。最关键的一行是tail-next head;。如果漏掉这一行链表就是一个普通的单链表约瑟夫环跑起来会直接越界到NULL程序大概率崩溃。我当年第一次写就栽在这后面第5章会专门讲这个坑。这里顺带说明一下为什么malloc之后要检查返回值在很多比赛和课程评测环境里内存分配失败会直接导致段错误提前检查并报错能让问题早点暴露。虽然是加分项但养成了好习惯。2.3 构建辅助函数打印循环链表调试链表题最朴素的方法就是把整个链表打印出来。循环链表不能像单链表那样用while (p ! NULL)判断结束因为环形结构里next永远不会是NULL。正确的打印方式是记录起始节点当遍历回到起始节点时停。void printLoop(Node *head) { if (head NULL) { printf(空链表\n); return; } Node *p head; do { printf(%d , p-data); p p-next; } while (p ! head); printf(\n); }为什么用do-while而不是while因为初始状态下p就是head如果用while判断p ! head第一次循环体根本不会执行打印结果就是空的。do-while保证至少执行一次正好符合“先打印再判断是否绕回起点”的逻辑。我在实际调试时发现这个打印函数的价值不仅在于验证链表创建是否正确还在于观察每轮出列后链表的状态。你可以在josephus函数里每删除一个节点就调用一次printLoop配合打印输出能非常直观地看到节点是怎么一步步减少的。3. 核心逻辑实现报数、出列与链表删除3.1 关键算法p始终指向前驱而不是待删节点这是整篇代码里最核心的思路也是我当初卡壳最久的地方。单链表删除一个节点必须知道它的前驱节点才能把前驱的next指向被删节点的下一个节点。约瑟夫环里的删除操作每轮都在做所以最稳妥的做法是维护一个指针p让它始终指向“当前报数为1的那个人”的前驱节点。这样做的好处是当需要删除某个节点时这个节点就是p-next我们只需要执行p-next p-next-next再free掉p-next不需要额外找前驱。为什么这么设计你可以想象成一个接力棒p本身永远不参与报数它只是站在报数起点前一个位置它的next指向报数起点。每报一个数p就顺着环走一步当报完m个数后p恰好停在待删除节点的前驱。删除完成后p-next自然指向下一轮的报数起点接力棒无缝交接。3.2 完整代码与运行效果#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createLoop(int n) { Node *head NULL; Node *tail NULL; for (int i 1; i n; i) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data 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; } void printLoop(Node *head) { if (head NULL) { printf(空链表\n); return; } Node *p head; do { printf(%d , p-data); p p-next; } while (p ! head); printf(\n); } void josephus(Node *head, int n, int m) { if (head NULL) { return; } Node *p head; // 让 p 指向尾节点也就是头节点的前驱 while (p-next ! head) { p p-next; } while (p-next ! p) { // p 始终指向报数起点位置的前驱 // 报到 m 的人出列所以 p 需要向后移动 m-1 次 for (int i 1; i m; i) { p p-next; } Node *del p-next; printf(%d , del-data); // 删除 del p-next del-next; free(del); } // 只剩最后一个节点 printf(%d\n, p-data); free(p); } int main() { int n, m; printf(请输入总人数 n 和报数间隔 m); scanf(%d %d, n, m); if (n 0 || m 0) { printf(输入不合法\n); return 1; } Node *head createLoop(n); printf(初始环形链表); printLoop(head); printf(出列顺序); josephus(head, n, m); return 0; }用n5、m3运行一下请输入总人数 n 和报数间隔 m5 3 初始环形链表1 2 3 4 5 出列顺序3 1 5 2 4对照手工推演1到31报1、2报2、3报33出列从4重新报15报21报31出列从2报14报25报35出列从2报12报24报34出列……不对这里要仔细核验一下。n5, m3的正确顺序是3 1 5 2 4吗出列顺序推演一下初始1 2 3 4 5从1报数。报1的是1报2的是2报3的是3所以3出列。剩下1 2 4 5从4重新报数。报1的是4报2的是5报3的是1所以1出列。剩下2 4 5从2重新报数。报1的是2报2的是4报3的是5所以5出列。剩下2 4从2重新报数。报1的是2报2的是4报3的是2所以2出列。最后剩下4。出列顺序3 1 5 2最后幸存者4。那我的代码运行出来显示的是3 1 5 2 4也就是把最后那个4也打印在出列顺序里了。从输出角度可以解释成“出列顺序包含最后一个人”或者如果想严格区分“出列的人”和“幸存者”可以在最后一行改成输出“幸存者4”。这个细节不影响算法正确性但如果你交作业注意题目要求是输出出列完整序列还是只输出幸存者。3.3 另一种写法对比维护prev指针的利与弊我也见过很多同学用另一种写法让p指向待删除节点本身再单独用一个prev指针保存它的前驱。逻辑上更直观但代码要多写几个分支。void josephus_prev(Node *head, int n, int m) { Node *p head; Node *prev NULL; // prev 指向头节点的前驱 while (p-next ! head) { p p-next; } prev p; p head; while (p-next ! p) { for (int i 1; i m; i) { prev p; p p-next; } printf(%d , p-data); // 删除 p prev-next p-next; Node *tmp p; p p-next; free(tmp); } printf(%d\n, p-data); free(p); }这个版本里p本身就是要出列的人理解起来更容易。但注意删除p之前你必须先保留prev-next p-next再free(p)然后把p移到被删节点的下一个节点。如果顺序写反比如先free(p)再用p-next就会出现悬空指针访问。相比之下前驱p版本减少了一个指针变量的维护循环内只需移动p删除操作固定是p-next p-next-next代码上更不容易写错。我最终推荐前驱版本因为它把“删除需要前驱”这个特性直接嵌入了循环不变式一劳永逸。4. 换条路走数组模拟与数学递推4.1 数组模拟逻辑删除的写法循环链表虽然最贴合题目语义但并不是唯一解法。如果你不想动指针用数组加状态标记一样可以模拟出列过程。数组下标从0到n-1代表编号1到n数组元素值为1表示还在圈内0表示已出列。用一个游标index在数组上不断前进碰到值为1的元素就报数报到m就标记为0。#include stdio.h #include stdlib.h void josephusArray(int n, int m) { int *people (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) { people[i] 1; } int remain n; int index 0; int count 0; while (remain 0) { if (people[index] 1) { count; if (count m) { printf(%d , index 1); people[index] 0; remain--; count 0; } } index (index 1) % n; } printf(\n); free(people); }这个写法很好理解永远用index (index 1) % n模拟环形回绕用people[index]判断当前位置的人是否还在圈内。逻辑删除比链表删除简单很多但代价是每轮报数计数时遇到已经出列的人还要继续往后走相当于在已删除元素上白白空转。整体时间复杂度是O(n × m)和链表版本相当但常数更大。数组模拟还有一个隐患如果m非常大count循环会转很多圈逻辑上没问题但运行时间会长一些。链表版本同样也会走很多步二者差不多。4.2 约瑟夫环的递推公式直接算出幸存者如果题目只要求输出最后幸存者编号有一个经典的数学递推解法时间复杂度O(n)代码只有几行。这个解法建立在编号0到n-1的约定上最后再把结果加1还原成题目要求的1到n。设f(n, m)表示n个人编号0到n-1每报到m出列的最终幸存者编号。显然f(1, m) 0。递推关系是f(n, m) (f(n-1, m) m) % n这个公式怎么理解第一轮删除的是编号(m-1) % n的人删除后圈内剩下n-1个人并且从编号m % n的人开始重新报数。如果我们把剩下的人按报数顺序重新编号为0到n-2那么新编号为i的人在原编号中是(i m) % n。所以n人规模问题的幸存者等于n-1人规模问题的幸存者“新编号”映射回原编号也就是f(n-1, m)加上偏移m并对n取模。写成循环int lastSurvivor(int n, int m) { int s 0; for (int i 2; i n; i) { s (s m) % i; } return s 1; }用n5、m3验证s从0开始i2时s(03)%21i3时s(13)%31i4时s(13)%40i5时s(03)%53最终s14。正确最后一个幸存者确实编号4。这个解法的局限是只能求幸存者编号不能输出完整出列顺序。所以如果你的作业要求打印出列过程数学递推只能用做答案校验不能替代链表主实现。4.3 三种实现方案横向对比实现方案能否输出完整出列顺序时间复杂度代码量学习价值循环链表能O(n×m)较多高重点考察指针与结构数组状态模拟能O(n×m)中等中逻辑清晰但实现简单数学递推不能O(n)极少低重在理解递推思想我在学习时习惯三种都写一遍然后分别跑同一组数据比对输出。这不仅是查漏补缺更能加深对“同一个问题可以有多种解法”的理解。数组适合快速签个到链表适合练基本功递推公式适合在比赛或面试中快速拿结果。5. 实战排查五个最容易踩的坑与测试建议5.1 坑1忘记成环这是我见过最高频的错误也是我第一次写这个题时的真实翻车现场。创建链表时如果最后一个节点的next仍然指向NULL约瑟夫函数里while循环一旦走到链表尾部就会对NULL解引用程序直接崩溃。排查方法很简单调用完createLoop之后先调用一次printLoop。如果打印出来的是1 2 3 4 5然后正常退出说明成环成功。如果打印出1 2 3 4 5后继续打印乱码或者直接段错误基本可以确定tail-next head这一行没写。另一个排查技巧是在printLoop末尾打印一下head的值和当前p的值如果两者相等说明环是闭合的。调试时可以加一行临时输出定位完再删掉。5.2 坑2删除节点时指针顺序错乱链表删除的经典误区是先free再改next。free之后那个节点所在的内存已经归还系统再去访问del-next就是悬空指针结果不可预知。正确的顺序永远是先把要删除节点的next保存到前驱的next字段中再执行free。对应到代码里就是先p-next del-next然后free(del)。我在实际调试中还遇到过另一种“看起来没错但很隐蔽”的错误删除时没有更新p导致下一次报数起点错位。因为前驱p在删除后要保持不动p-next已经自动指向下一轮报数起点如果你在删除后又执行了p p-next就会多跳一个节点。这一点我在3.2节代码中写得很清楚删除后p不动循环继续。5.3 坑3循环退出条件写错正确的是while (p-next ! p)意思是“当圈里剩下不止一个节点时继续删除”。退出循环后p指向唯一剩下的节点直接输出即可。但很多初学会写成while (p ! NULL)这在循环链表里永远为真程序陷入死循环。还有人写成while (p-next ! NULL)同样不成立因为环形链表里每个节点的next都不为NULL除非链表为空。这里有个辅助记忆单链表结束条件是p为NULL循环链表因为没有NULL终点结束条件只能是“发现回到了某个已访问的位置”。在约瑟夫环场景里最后剩下的节点它的next就是它自己所以p-next p就是终止信号。5.4 坑4内存泄漏与free时机课程设计一般不检查内存泄漏但如果你长期做C语言开发这是个绕不开的话题。约瑟夫环代码里有三种free时机很容易漏第一每轮删除节点时必须free(del)第二最后剩余的一个节点也要free(p)第三如果createLoop过程中malloc失败前面已分配的所有节点都要逐一释放。针对最后一点严格的写法是在malloc失败分支里遍历链表释放全部节点。实际教学作业可以简化但代码里至少要把前两种free写完整。否则程序跑完内存里还残留着一堆没释放的节点短时间看不出来多跑几组大数据就会有明显的内存占用增长。另外我在调试时习惯在free之后立刻把指针置为NULL比如free(del); del NULL;。虽然这个局部变量马上就废弃了但养成习惯后可以防止后面误用悬空指针。5.5 测试用例设计建议测试不能只跑一组数据。我自己的测试清单是这样的n1, m1边界情况链表只有一个节点应该直接输出1。n5, m1每轮都删当前报数起点出列顺序应该是1 2 3 4 5。n5, m2经典小规模用例出列顺序是2 4 1 5 3幸存者3。n5, m3出列顺序是3 1 5 2 4幸存者4。n10, m7中等规模用于验证循环绕圈的能力。n100, m999m大于n验证长步数下不出错。每组结果都可以用第4章的数学递推公式验算最后一个幸存者是否正确。我自己常用一个笨办法先手动推演n5和n6的小数据确认代码逻辑再放心跑大数据。数据结构题目最大的陷阱恰恰是“小数据看着对换组数据就崩”。6. 约瑟夫问题带来的工程启发与应用延伸6.1 现实生活中的约瑟夫环场景很多人觉得这类题目只是考试专用实际意义不大。其实约瑟夫环的抽象模型在真实场景里很常见。最简单的例子是多人轮流执行任务一个线程池里有n个可用的工作线程当一个任务完成就按顺序把下一个任务分配给下一个线程到达末尾后回到第一个这本质上就是一个约瑟夫环的轮转调度。再比如缓存淘汰策略中的“时钟算法”操作系统管理页面时会用一个环形缓冲区指针顺序扫描每个页面找到合适的页面进行替换。如果扫描过程中发现某些页面的访问位不符合要求就跳过继续找下一个。这和约瑟夫问题里“沿着环逐个人检查、决定是否移除”的思路如出一辙。还有一类游戏规则比如淘汰赛中的循环淘汰、抽奖活动中的固定间隔抽人只要符合“围成圈、按间隔淘汰”的规则都可以用约瑟夫模型描述。这也是为什么这道题在数据结构的作业里地位这么稳的原因它虽然简单但映射了一类真实的“环形淘汰”问题。6.2 约瑟夫环的常见变体掌握基础版本后可以试着想几个变体做完之后对链表和递归的理解会更深。变体一方向变化。报数方向从顺时针改成逆时针相当于每次改为沿着prev指针走。如果是双向链表只需要判断direction变量决定移动时用next还是prev。变体二动态步长。每轮淘汰一个人之后步长m发生变化比如m m 1。这类变体只要在每轮循环结束后更新m即可对链表结构本身没有额外要求。变体三每轮删除两个节点。比如报到m的人出列后再从他后面隔一个人也出列。这种题需要小心处理连续删除时的指针关系最容易出bug但也是练手的好题目。变体四只求幸存者但n巨大m也巨大。这时候循环链表O(n×m)会非常慢必须用数学递推优化。这个变体在面试题中反而更常见因为现场写递推公式通常比写百行链表代码更高效。6.3 从课程设计中学到的三点经验第一写链表代码前先在纸上画出节点之间的箭头指向尤其是删除操作前后的变化。画清楚了再动手代码基本不会错。我吃亏最多的环节就是脑子里的指针状态和实际的指针状态不一致。第二调试时用“打印大法”配合小数据。在关键位置加printf比如每轮循环开始前打印p-data删除后打印整个链表几轮下来就能定位问题。不要觉得打印log低级它比任何调试器都直观。第三至少实现一个“验证型”的替代方案。比如用数学递推公式算幸存者编号用数组模拟算出出列顺序然后交叉验证链表版本的结果。这一步能让你在交作业前心里有底而不是代码一跑没报错就以为万事大吉。最后再分享一个个人习惯我会把n和m的输入放在main函数里而不是写死在代码中。看似多两行scanf但调试时想换参数就不用重新编译改常量省很多事。如果条件允许还可以加上循环输入一次程序跑完多组测试数据测试效率翻倍。