1. 题目拆解三个变体到底在考什么约瑟夫问题Josephus Problem算是数据结构课程设计里的常青树了几乎每年都会出现在各个学校的练习列表里。它本质上描述的是一个淘汰游戏n个人围成一圈按顺序编号从某个人开始报数报到m的人出列然后从下一个人开始重新报数直到剩下最后一个人。我记得2021年这套题目里问题C、D、E把约瑟夫问题拆成了三个递进的级别每一题都在考察不同的知识点从最基础的循环链表操作到带数据域的动态链表设计再到对复杂度和边界条件的把控层层加码。对于正在做课设的同学来说这套题的价值不只是“会写代码让程序跑通”更重要的是把链表这个最基本的线性结构的增删改查真正练扎实。许多同学学链表时只会单向遍历碰到约瑟夫问题这种“边遍历边删除”的场景就开始手忙脚乱。而这套题的三段式设计恰好把各种可能的考点都覆盖到了第一个变体要求按固定步长模拟出列第二个变体引入了动态的“密码”每一步的报数上限都在变化第三个变体进一步升级单纯靠暴力模拟很容易在大数据量下超时必须结合数学推导来优化。抛开具体题目代号我会把这三种变体分别理解成“基础模拟版”“动态参数版”和“性能优化版”。无论题目给你的描述长什么样子核心考察点都不会偏离这三条线。基础模拟版n个人编号1到n从编号1开始报数报到M的人出列输出完整的出列顺序。这是最原始的约瑟夫环。动态参数版每个人身上带一个密码假设初始报数上限为M当前出列的人身上的密码值会作为下一轮报数的上限。这种设计让节点必须携带额外信息链表节点不再只是“数据指针”。性能优化版通常要求计算最后一个剩下的编号或者要求能够处理大规模输入在时间上有明确的限制。这种版本考察的是能否跳出“模拟出列”的惯性思维用数学递推直接算出结果。能把这三种变体一次性做完大部分学校的数据结构课程设计要求也就基本达标了。下面我从头到尾把每道题的思路、代码和坑位都梳理一遍提供你可以直接照着写的方案。2. 数据结构选型为什么首选循环链表很多人在做约瑟夫问题时第一个念头是用数组把编号存下来然后用一个下标游标模拟报数。这确实能跑但一旦题目改成“动态密码版”数组方案的代码就会迅速变得纠缠不清而且每次删除都要移动大量元素时间复杂度明显偏高。用链表来做删除节点只需要改两个指针天然契合这个场景。不过用链表不代表随便用一个单向链表就行。约瑟夫问题的核心特点是“围成一圈”每个节点在逻辑上都是环形的最后一个人的后继要指向第一个人。如果你用带头的单向链表遍历到底部还得手动把头指针接回来很容易漏掉边界判断。最自然的数据结构是“不带头节点的循环单链表”首节点就是当前报到的那个人尾节点的next指针直接指向首节点。我自己在一开始选择数据结构时犹豫过一下要不要用双向链表后来想想约瑟夫问题的删除操作只需要知道当前节点和它的前驱就可以了单向循环链表完全够用。双向链表多了prev指针反而让初始化和删除逻辑变得冗余。记住一个原则数据结构永远是为操作服务的别为了炫技引入不必要的复杂度。2.1 不带头节点的循环链表怎么搭初始化一个n节点的循环链表逻辑其实不复杂但很多同学的代码会在这里出问题。核心在于创建第一个节点时它的next先指向自己然后再依次往尾部插入节点保证最后一个节点的next指回头节点。typedef struct Node { int data; struct Node *next; } Node; Node* createCircle(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-data i; if (head NULL) { head p; p-next head; tail head; } else { p-next head; tail-next p; tail p; } } return head; }这里有一个关键细节创建第二个节点时它的next要指向head同时前一个节点即第一个节点的next也要改成新节点。如果顺序写反链表就会断掉。你可以自己在纸上画一下两个节点的链表是如何指向的画完就能理解为什么必须先“p-next head”再“tail-next p”。2.2 什么时候数组反而是更好的选择链表是这题的经典解法但并非所有情况下都用链表。假如题目只要求输出最后一个幸存者的编号而且n能达到百万级别此时用循环链表纯模拟会产生大量的malloc和free操作时间开销非常夸张。如果你想追求极致性能可以考虑直接用数学递推公式算最后一个幸存者连链表都不用建。这个思路我在第三个变体会详细展开。还有一种情况也可以用数组当题目明确说n很小比如小于1000并且你只需要输出出列序列。此时用“标记法”也就是用一个int数组值为1代表还在圈内值为0代表已出列遍历时跳过0。代码量小不容易产生指针问题。缺点是每次删除一个节点要完整扫描一遍数组去找下一个还在圈内的人总复杂度偏高n一大就容易超时。就这么说吧如果你有充足的时间把链表方案练熟是最稳的它最能体现课程设计的核心知识点如果只是求最后一个幸存者且数据规模极大数学方案才是正确的追求方向。3. 核心实现三段代码的逐行拆解下面我会把三个变体分别用代码实现并详细解释每一段关键逻辑。这里的代码以C语言为准这是数据结构课程设计的主流语言。如果你用的是C思路完全一样只需要把malloc/free换成new/delete即可。3.1 变体Ⅰ基础模拟版的核心代码基础版的规则是n个人编号1到n从编号1开始数数到M的人出列然后从下一个开始重新数。这里最容易被搞混的是“数到M的人”到底需要遍历几步。如果当前指针指向1号M3那么报数过程是1号报1、2号报2、3号报3所以3号出列。也就是说从当前指针出发只需要移动M-1步就能到达要删除的节点。Node* josephusBasic(Node *head, int M) { if (head NULL) return NULL; Node *cur head; Node *prev NULL; while (cur-next ! cur) { // 找到要出列的节点prev: 报数之前的前驱 // 走 M-1 步cur 到出列节点 for (int i 1; i M; i) { prev cur; cur cur-next; } printf(%d , cur-data); // 删除 cur 节点 prev-next cur-next; Node *tmp cur; cur cur-next; free(tmp); // 注意此时 cur 已经是下一个人的位置 } printf(%d\n, cur-data); free(cur); return NULL; }这段代码有一个初学者很容易踩的坑当链表只有一个节点时while的条件是cur-next ! cur此时循环不会进入会直接走最后一行打印和释放。这是正确的但前提是你在外面调用时要记得如果链表一开始只有一个人这个函数也能正常工作。还有一点在删除节点前必须记录前驱节点prev。删除一个节点本质上要靠前驱的next来跨过它如果循环链表只有当前节点没有prev这个节点就删不干净。我建议你在阅读这段代码时自己跟着画一个3个节点的例子把cur和prev的变化写下来。这一步做完后面所有变体你都能轻松掌握。3.2 变体Ⅱ动态密码版的关键设计动态密码版的规则是初始给一个报数上限M每个人有一个密码pw正整数。从1号开始报数报到当前M的人出列出列后把该出列者的密码作为新的M然后从他下一个人开始重新从1报数。这样一来Node结构体里就不能只有一个data还得有一个password字段。typedef struct Node { int data; // 编号 int password; // 每个人的密码 struct Node *next; } Node;动态密码版的删除流程大体和基础版一致唯一的区别是每次删除前步长M是变化的而且它可能很大。很多人的第一反应是如果M1000000难道真的要循环一百万次吗当然不能这样。我们需要一些技巧来缩短报数过程。这里要介绍一个非常重要的优化操作取模。假设当前圈中还剩cnt个节点报数上限是M。实际上从当前指针开始完整地绕圈整圈再回到起点没有任何变化所以要走的步数可以化简为M对cnt取模后的余数。但是要特别小心如果M % cnt 0说明正好要报数到当前节点的前一个节点也就是走cnt步会回到自己走了0步又不对因为“报数到M的人”是前驱节点。处理方式是把步数修正为(M - 1) % cnt。让我再详细一点解释这个坑。假设当前有5个人cur指向编号1的人M5。报数过程为1报12报23报34报45报5所以出列的是5号也就是cur往前数4步到达的节点。如果用M%cnt0去算你得到0步删除的就是cur自己这显然是错的。正确公式是走(M-1)%cnt步。因为每次报数当前指向的人报的数是1而不是0。统一写法int cnt n; while (cnt 1) { int step (M - 1) % cnt; for (int i 0; i step; i) { prev cur; cur cur-next; } M cur-password; printf(%d , cur-data); prev-next cur-next; Node *tmp cur; cur cur-next; free(tmp); cnt--; }动态密码版的代码和基础版相比只多了三样东西一个password字段、M根据cur-password更新的语句、以及用于取模的cnt计数器。但就这三样东西就使得程序的行为从“机械报数”变成了“动态联动”。这种从“静态结构”到“动态结构”的转变正是这题考察的核心思维能力。3.3 变体Ⅲ性能优化与数学递推第三个变体通常要求更高的性能比如n能到几十万甚至上百万此时用链表模拟很不划算。测试数据一旦做到20万个人每轮报数都要经历上百次指针跳转总操作量会达到上亿次即使能跑完也非常勉强时间一长容易被卡。这里就需要引入约瑟夫问题的数学解法用递推公式求最后一个幸存者的编号。公式非常简单f[1] 0 f[i] (f[i-1] M) % i其中f[i]表示i个人围成一圈时最后一个幸存者在这一轮里的下标从0开始。最后答案是f[n] 1因为编号从1开始。为什么这个递推成立我用自己的话解释一下假设第一个人出列后剩下n-1个人。如果用一个新编号方案从出列者的下一个人开始编号为0、1、2……那么这n-1个人的幸存者编号就是规模为n-1的约瑟夫问题的解f[n-1]。要把这个解映射回原来的编号需要加上M并且对n取模。因为出列的人后面第一个人原本的编号是(M) % n从0开始新编号0对应旧编号M%n新编号k对应的旧编号就是(M k) % n。所以f[n] (f[n-1] M) % n。用代码实现只需要一个循环int josephusMath(int n, int M) { int pos 0; for (int i 2; i n; i) { pos (pos M) % i; } return pos 1; }注意这求的是“最后一个幸存者”不是完整的出列序列。如果第三变体要求输出全部出列顺序那数学递推就没法直接用了因为你必须真实模拟每一次删除。但实际课程设计里第三变体往往会把问题转向“求最后留下的人”或“数据规模极大”此时数学方案就是正解。一个常见的问题是如果M很大pos M会不会溢出在C语言里int的取值范围大约是21亿M如果超过这个范围就要改用long long。虽然实际课程设计中一般不会出这么大的数据但在考试或比赛中这是必须考虑的边界。写代码时养成用long long的习惯能省掉很多麻烦。3.4 代码级细节报数边界、首节点删除、循环终止代码写完之后真正影响程序正确性的往往是一些细节判断。第一首节点删除的处理。看一个最简单的场景n3M1。每次删除的都是当前指针指向的节点也就是第一次删除1号然后cur指向2号删除2号最后剩3号。上面的代码能正确处理是因为每次走步数是(M-1)%cnt0也就是不移动直接删除cur。此时prev需要怎么处理注意在第一次删除时prev是NULL因为找不到前驱节点。这会导致代码直接崩溃。正确的做法是在初始化链表时额外维护一个tail指针它可以作为首节点的前驱这样删除任意节点时都有prev可用。上面的示例代码里初始化返回了一个head头指针但如果你要从任意位置删除节点我建议保留tail指针并让prev从tail开始走。更好的方式是把循环链表同时持有head和tail删除时如果cur是head要同步更新head。我实现时常常直接让prev从tail开始cur从head开始每次移动step步这样prev一定会指向cur的前驱。Node *prev tail; Node *cur head; for (int i 0; i step; i) { prev cur; cur cur-next; }这个写法有一个好处step0时curheadprevtail天然就是正确的“前驱为最后一人”状态没有空指针风险。第二循环终止条件的判断。链表模拟的终止条件是只剩一个节点也就是cur-next cur。但是当每次删除后cur会成为下一个人的位置prev是出列节点的前驱。此时依然满足“尾巴节点永远连接着头部”的不变量。这个不变量一旦被破坏程序大概率会死循环或者打印出乱序数据。第三无论是哪种变体记得释放内存。链表模拟的程序经常因为malloc了节点但没有逐一free导致内存泄漏。虽然课程设计的评测系统一般不会严格查内存泄漏但这是写C程序的基本素养。好习惯是每次删除后用free释放节点最后剩下一个节点时也要释放。4. 调试实录我踩过的坑和排查思路这部分是整篇文章的灵魂了。代码写得再漂亮不知道坑在哪运行起来照样可能崩。下面我把自己做这道题时真实踩过的几个坑和排查思路完整记录下来希望你能绕开。4.1 第一个坑死循环出不去的根因我第一次写完基础版时试了n5、M3程序一开始能正常输出3、1、5、2到最后却卡住了控制台一直停着不出结果。排查了很久发现在删除节点后我没有正确更新tail指针导致链表的环被打破了一处。循环链表最怕的就是环被破坏一旦某个节点的next指向了NULLwhile(cur-next ! cur)就永远判断不成立也不会进入循环但遍历时又会访问NULL指针行为极其混乱。解决的办法很直接每次打印节点时手动检查它和前后节点的关系。我加了几行临时printf输出前后节点的编号立刻看出在第二次删除后某个节点的next指向了已释放的地址。这里也引出一个重要的调试技巧凡是涉及指针的程序输出指针指向的地址和它next指向的地址往往比看纯数据更快定位问题。4.2 第二个坑取模优化导致少删人使用取模优化后我调试n5、M3时发现输出完全正确但把数据换成n7、M10输出序列和标准答案对不上。经过一番验证才发现我在取模时没有处理“余数为0”的特殊情况。我之前写的是step M % cnt然后走step步结果当M正好是cnt的整数倍时step0于是删除了当前指向的人而正确答案其实应该删除当前人的前一个。这就是逻辑上的“差一步”。修正成step (M - 1) % cnt后所有测试数据瞬间全部通过。这也再次提醒我任何优化都必须基于最原始的“一步步报数”逻辑去验证不要想当然。注意取模优化“只跳步、不乱序”依赖一个前提当前节点报的数是1。如果你在另一个版本里让当前节点从0开始报数那公式又会不一样。写代码前先在注释里写清楚报数的起点这是避免混乱最有效的方法。4.3 第三个坑输入数据用EOF还是固定格式课程设计的评测系统通常会有多组测试数据你要么用while(scanf(...) ! EOF)循环读要么按题目要求固定读一组。我一开始没注意题目中关于输入行数的描述写了固定读取结果评测时数据被截断后面几组测试直接不输出。正确的做法是仔细检查题目说明如果题目没有明说只有一组输入那基本默认就是EOF处理while (scanf(%d %d, n, M) 2) { // 处理每一组数据 }另外注意读空格和换行的问题不要用getchar处理数字后的空字符直接用scanf %d就能跳过空白字符。4.4 测试用例设计手工展开最靠谱在提交评测前我用一组手工展开的测试用例来验证程序。这个方法我强烈推荐给大家。选一组小数据比如n8M4自己在纸上模拟一遍出列顺序。然后跑程序对比。我第一次手工展开时发现自己模拟的是“出列后从下一个开始从0报数”但程序逻辑是“从下一个开始从1报数”完全是两个不同的规则难怪输出不一致。从这以后我每次写约瑟夫问题前都会先明确“下一轮报数从几开始”这个基本约定。再附上一组可以直接测试的经典数据n5M3出列顺序应为3、1、5、2、4从1号开始报数报数从1开始n6M2出列顺序应为2、4、6、3、1、5n7M1出列顺序就是1、2、3、4、5、6、7这些数据都是基础版的基准测试。验证完基础版再验证动态密码版假设n4M3密码序列是3、1、2、4。手工列出3号数到3出列密码为2下一轮从4号开始数到2出列密码4下一轮1号数到4出列密码3最后2号出列。输出顺序应该是3、4、1、2。4.5 常见问题速查表现象可能原因处理方法输出第一个元素就错报数起点理解错误或cur初始指向不对确认当前节点是否报1确认head是否指向1号输出到中途死循环删除节点后环被破坏tail未更新检查删除逻辑确保tail-next始终是head每次输出顺序但最后剩的不是预期编号循环终止条件错误删除了最后一个节点检查while条件是cur-next ! cur而不是cur ! NULL大数据超时暴力模拟未做取模优化或数据结构选择不当对M%cnt做跳步优化或改用数学递推动态密码版密码没更新出列节点的数据被提前free在free之前先取出password值多组输入只跑出一组未用EOF循环读取改为while(scanf(...) x)循环这张表是我做完三道变体后总结出来的。你会发现大部分问题都指向同一个根源没有透彻理解节点的前驱和后续关系。只要画图搞清楚指针指向这题就成功了大半。5. 复杂度分析与边界条件优化有人说约瑟夫问题算法简单不就是模拟嘛。这话对了一半。如果只是应付基础版的课设模拟确实够了但要想拿高分就必须把复杂度的账算清楚这是很多同学容易忽略的部分。5.1 三种方案的复杂度对比暴力链表模拟删除n个节点每次都从当前位置往后走M步所以整体复杂度是O(n*M)。如果M很大这就是个灾难。取模优化后的链表模拟因为我们用M % cnt缩短跳步总操作次数近似为O(n^2)级别的指针移动。虽然不理想但n在几千以内可以轻松跑完。数学递推从头到尾就是一个for循环复杂度O(n)没有任何指针操作空间复杂度O(1)。这是求最后一个幸存者的最优方案。我把对比列在这里方案时间复杂度空间复杂度适用场景数组标记法O(n*M) 或 O(n^2)O(n)n很小代码简单循环链表模拟O(n*M)O(n)需输出完整序列n不大取模优化链表O(n^2) 实际移动量O(n)输出序列且M较大数学递推O(n)O(1)只求最后一个幸存者从这张表可以看出没有哪个方案是绝对最好的关键看你要什么输出和数据规模。课程设计不像比赛不必一味追求高性能但应有的优化意识还是得体现出来。5.2 动态密码版为什么不好用数学递推动态密码版就要多说一句了。因为每一轮步长M都依赖于上一轮出列者携带的密码密码的分布取决于整个删除过程理论上不存在一个简单递推公式可以跳过中间步骤直接算出幸存者。所以动态密码版只能采取模拟手段这一点不用怀疑。既然算法上没得选优化点就只能放在细节跳步时用(M-1)%cnt取模同时在节点定义里用int保存密码不要每次访问都做malloc。如果你用C还可以用list容器代替手写链表处理起来更省心。但课程设计一般要求手写链表这部分能力也正是需要练的。5.3 边界条件全面核查不管哪个版本有几个边界条件建议在写代码前就准备好第一n1。此时链表只有一个节点cur-next就是自己。基础版会直接打印该节点动态密码版也会直接退出数学递推则返回pos11。第二M1。这就相当于每次删除当前节点。链表版本需要保证删除第一个节点后cur指向下一个节点并且新的环依然完整。第三密码为1的动态密码版。每次删除当前节点同时新的M也变成1过程单调清晰这是测试动态更新逻辑是否正常的好数据。第四n和M都很大比如n200000M1000000007。链表模拟必然超时数学递推则瞬间出结果。如果你在课程设计里被要求处理这种数据直接优先用递推求幸存者。我自己的习惯是写一道题时先列出所有能想到的边界条件再动手编码。这不只是为了应付评测更是高效排查Bug的手段。你调一次Bug花的时间往往比想边界条件多得多。6. 一点个人经验总结这套题做完以后我最深的感受是数据结构题目千万不能眼高手低。约瑟夫问题看起来只有几十行代码但真正能从逻辑到指针、从API到内存管理全做对并不容易。如果你只是把网上代码抄一遍、跑通就交差收获会非常有限。我建议每个变体都自己从零推演一遍把链表从创建到释放的每一步都搞清楚。作为课程设计汇报展示时老师大概率会问你“为什么选循环链表”“数组行不行”“复杂度怎么算”。所以即使最终评测过了也要能口头讲清楚里面的取舍。这不仅关系到分数更是为你以后写更复杂的数据结构打基础。最后分享一个我后来一直在用的小技巧用VS或任意IDE调试时为链表写一个打印函数可以在每一步删除后输出当前环的所有节点帮助自己直观理解指针变动。打印时不需要太花哨节点编号next指向的编号就够了。这种临时的调试代码看起来不够优雅但在调试自己写的指针程序时非常高效。约瑟夫问题在课程设计里可能只是一个起点但它背后涉及的循环链表、指针操作、取模优化、数学递推、边界测试每一个点都足够单独展开成一道题。认真做完这套题你掌握的其实就是数据结构课程最核心的几项基本功。剩下的时间推荐换着不同的数据规模反复跑一跑这几种实现你会对链表和复杂度有更直观的感受。
