2021年数据结构课程设计题目列表里写着“问题 C-E: Josephus问题(Ⅰ)(Ⅱ)(Ⅲ)”的时候我就预感这次不是一道普通上机题——同一个问题拆成三个阶段摆明了是让我们从基础模拟一路做到进阶优化。等我把三个题全部做下来回头发现这确实是一个把线性表、循环链表、递推数学、复杂度分析和报告撰写全部串起来的“组合拳”。这篇文章就按我当时完整走下来的顺序把题目怎么拆、链表怎么建、报数怎么走、递推怎么推、测试怎么设计、答辩怎么准备通通整理一遍给正在被这个经典问题折磨的同学当一份完整的实操参考。先说明一下这种ⅠⅡⅢ的题目结构在不同学校的版本里细节可能略有差异但主线基本一致第一阶段是基础模拟第二阶段会让你动手实现特定的数据结构通常是循环链表并处理输入输出第三阶段则会要求优化算法或者扩展应用比如递推公式、双向链表、报数方向变化等等。核心思路完全可以平移细节跟着你的题面走就行。1. 题目拆解三个子题到底在考什么1.1 从故事到抽象Josephus问题的数学模型Josephus问题最经典的描述是这样的N个人围成一圈从第S个人开始报数报到M的人出列然后从下一个人重新开始报数仍然报到M出列循环直到最后只剩下一个人目标是输出出列顺序或最后幸存者。这个故事翻译成数据结构语言其实是一个围成一圈的线性表操作过程N个元素构成一个循环结构每个元素有唯一的编号每一步从当前起点开始按固定步长M数到目标元素目标元素从结构中删除下一次从被删除元素的下一个元素重新开始。这套描述里最核心的两个字是循环。因为每次删除完下一个报数起点就是删除位置的下一个结点这个到达尾部再回到头部的行为恰好和循环链表指针的走向完全一致。这也是为什么绝大多数课程设计都会把Josephus问题和循环链表绑在一起的原因。1.2 三个阶段的递进逻辑我做这套题时对ⅠⅡⅢ的理解是这样的问题Ⅰ通常要求先把流程跑通给定N、S、M能够正确输出出列序列。这一阶段不限制实现方式数组、链表、甚至手动模拟都行核心是让你理解报数—删除—从下一个重新开始这个过程问题Ⅱ一般会强行要求用链表来实现并且要求处理各种输入边界比如M大于N、S大于N、N等于1这些特殊情况。这一阶段考察的是链式存储的操作能力和代码健壮性问题Ⅲ则是进阶变体常见的做法是要求用数学递推把时间复杂度从O(NM)降到O(N)或者要求用双向循环链表处理报数方向切换、双向交替删除等扩展规则。我当时给这道题定的目标是链表版必须写得能跑通、可解释递推版必须能推导、能证明。这样无论第三题具体要求的是什么我都能接得住。2. 建模与选型为什么第一反应是循环链表2.1 数组模拟的痛点和链表建模的直觉第一次看到这个题很多人第一个想法是用数组存编号搞个当前下标步长取模不就行了。确实能跑但数组有一个隐藏代价删除一个元素之后后面的所有元素都要往前移动这一步是O(N)的。如果用户输入N是几百、几千问题不大但N一上万、M一上万数组模拟的速度就会肉眼可见地变慢。更重要的是从建模角度来说数组并不天然表达围成一圈这个关系。你需要在取模运算里小心翼翼处理下标回绕稍不留神就出现越过末尾多跳一个或者删除之后位置对不上的bug。而循环链表结点的next指针天然就指向下一个结点最后一个结点的next指向头结点整个圈就长在数据结构里了不需要额外做任何下标运算。除此之外循环链表删除一个结点的代价是O(1)只需要改指针不需要搬动任何数据。这正好对应题目中频繁删除固定位置元素的核心操作。我最后选的是带头结点的循环链表因为头结点的存在可以统一处理删掉的是链表第一个元素这种尴尬情况代码逻辑会更简洁。提示链表在时间复杂度上不一定优于数组模拟整体模拟都是O(NM)它的优势是结构表达清晰、删除操作天然直接。真正的性能突破来自第三阶段的递推公式这一点在写报告时要分开讲清楚不能混为一谈。2.2 循环链表的最小实现骨架这里给出一份基于C语言的循环链表核心定义和创建函数作为整个实现的地基#include stdio.h #include stdlib.h typedef struct Node { int id; // 结点编号按题意通常从1开始 struct Node *next; } Node; // 创建一个包含 n 个结点的单向循环链表编号 1..n Node* createCircle(int n) { Node *head (Node*)malloc(sizeof(Node)); Node *tail head; head-id 0; // 头结点不参与编号只作为辅助起点 for (int i 1; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; tail-next p; tail p; } tail-next head; // 尾结点指向头结点形成环 return head; }这里有一个很关键的细节我用了一个不参与业务编号的头结点。很多初学者喜欢直接让1号结点作为头结点但在删除环节会出现如果要删除的是头结点怎么处理头指针的麻烦。带头结点之后头指针本身固定不变每次遍历从头结点的next开始删除结点时只需要改前驱结点的next代码统一很多。3. Ⅰ、Ⅱ阶段实现要点报数循环与出列处理的边界3.1 报数指针怎么走走M步还是M-1步必须想清楚这是整个链表模拟里面最容易出错的点。假设cur已经指向当前要报数的人那么报到M的人出列这个动作cur应该前进多少步答案是从cur开始报1cur-next报2依次类推报到M的人应该是cur走M-1步之后指向的结点。如果写成了走M步就会把下一个人删掉。但这里还有一个更隐蔽的细节如果是单向循环链表我们是没有办法直接删除当前结点的因为要删除当前结点必须让它的前驱的next指向它的后继而单向链表里找不到前驱。所以更常规的做法是让cur停留在待删除结点的前驱上然后通过cur-next cur-next-next完成删除。这样指针到底要停在哪个位置假设我们让cur一开始就指向待删除结点的前驱那么报数报M下的过程中cur应该移动M次才能让cur-next正好是待删除结点。我用一个带头结点的循环链表初始时cur指向头结点让头结点视为S号结点的前驱位置整个逻辑会非常顺void josephusByLinkedList(int n, int s, int m) { Node *head createCircle(n); Node *cur head; // 让 cur 移动到 S 号结点的前驱 for (int i 1; i s; i) { cur cur-next; } while (cur-next ! cur) { // cur 每次走 m 步让 cur-next 指向待删除结点 for (int step 1; step m; step) { cur cur-next; } Node *del cur-next; printf(%d , del-id); cur-next del-next; free(del); } printf(%d\n, cur-id); // 最后一个幸存者 free(cur); }注意看这个写法我在报数循环里用的是step m让cur走M-1步于是cur还是指向待删除结点的前驱待删除结点是cur-next。这个设计把报数位置和删除位置很好地统一在了一组指针关系里避免每次删除完还要反复寻找前驱。3.2 删除结点的三处细节删除操作看起来简单实际有三个细节决定代码是否稳第一确认链表不为空。判断条件cur-next ! cur表示当前循环链表里只剩下一个结点此时不能再删除应该直接输出它作为最后幸存者。第二释放内存的顺序。必须先保存待删除结点的指针上面代码里的del修改前驱结点的next再free。如果先free再改指针相当于访问了已释放的内存属于悬空指针轻则崩溃重则数据错乱。第三删除之后cur应该指向哪里。按照题目规则删掉M号结点后M1号从1开始报数而在我们的指针布局里M1号恰好是del-next也就是修改后cur-next的值。所以删除后不用额外移动cur直接进入下一轮报数循环就行。如果删除后手动让cur cur-next再走M-1步就会凭空多跳一个人。3.3 输入输出格式的一点点讲究课程设计的上机评测通常对输入输出有严格要求不是功能对了就行。我当时吃过一次亏用了scanf(%d,%d,%d)但题目输入是空格分隔结果样例第一个就过不去。我的建议是输入格式提前看三遍明确分隔符是空格、逗号还是换行输出出列序列时通常要求相邻编号之间用空格分隔最后一个编号后换行不要多输出多余内容写代码前先设计一个题目要求的输入输出样例用纸笔手动算出期望结果再写程序这样可以避免以为写对了其实理解错题意。还有一个容易被忽略的输入陷阱S和M都可能大于N。S大于N时可以S (S - 1) % N 1标准化M大于N时不能简单对N取模就完事因为报数时跳过一圈和取模后直接删除在链表模拟里结果本质相同但一定要保证循环本身能正确处理大数比如循环步进可以用step m直接跑不需要取模。还有一种更稳妥的写法是m m % n但如果m % n 0要特别处理成n否则步数归零会死循环。我个人更推荐保持原始M直接让循环走完简单不容易出错。4. Ⅲ阶段的关键升级递推公式与双向循环链表4.1 O(N)递推N很大、M很大时怎么玩链表模拟虽然直观但复杂度是O(NM)。如果N是10万、M是1万这个循环要跑十亿次量级课程设计里如果是超大测试点一定会超时。这时候就需要用递推公式把整个问题化成O(N)。先约定一种0基编号假设N个人编号为0到N-1从0号开始报数报1、2、……、MM号出列。定义f(N, M)表示在这种0基编号下N个人最终幸存者的编号也是0基。当只有1个人时显然有f(1, M) 0当有N个人时第一轮报数后出列的人是(M - 1) % N号。删除这个人后剩下的N-1个人从M % N号开始重新编号原编号M % N变成新编号0原编号M % N 1变成新编号1依此类推。假设这N-1个人构成的子问题里幸存者在新编号体系下的位置是f(N-1, M)那么它映射回N个人原始编号时就是f(N, M) (f(N-1, M) M) % N这个递推的边界和转移都非常干净。写成代码甚至只需要几行// 返回N个人从0号开始报数的幸存者编号0基 int survivorZeroBase(int n, int m) { int pos 0; for (int i 2; i n; i) { pos (pos m) % i; } return pos; } // 处理从第 s 个人开始报数编号 1..n int finalSurvivor(int n, int s, int m) { int pos survivorZeroBase(n, m); return (pos s - 1) % n 1; }我当时在报告里专门画了一个映射表来说明这个递推印象很深整个过程就是从1个人的结果一直往上回推每轮只做一次加法一次取模完全不依赖删除操作。写完这个公式后N就算是一千万也只需要循环一千万次几乎瞬间出结果。提示递推公式版本和链表版本经常在最终结果上差1或者编号偏移因为一个用0基、一个用1基。我自己的保险做法是在代码注释开头明确写下编号约定所有函数的命名都带上ZeroBase或直接写清返回值是实际编号然后做一组小规模测试对拍。4.2 双向循环链表当方向反转成为规则的一部分问题Ⅲ还有一种很常见的扩展方向报数方向每轮或每隔若干轮反转一次或者删除方向与报数方向相反。这种时候单向链表就比较难受因为反向走要求每个结点都能找到前驱于是自然引出双向循环链表。双向循环链表的结构定义如下typedef struct DNode { int id; struct DNode *prev; struct DNode *next; } DNode;创建时和单向类似但要同时维护两个方向的指针首尾相接时也要双向接上。核心的删除逻辑是del-prev-next del-next; del-next-prev del-prev; free(del);这段代码把查找前驱这个操作变成了O(1)删除一个结点只需要改两条指针。如果报数方向需要反转可以维护一个方向标志int dirdir1表示正向用nextdir-1表示反向用prev报数时根据dir选择移动方向即可。下面给出一个简化版的方向切换框架void josephusWithDirection(int n, int s, int m, int dir) { DNode *head createCircleDouble(n); DNode *cur head; // 初始还是借助头结点定位 // 移动方向由 dir 决定 // dir1 走 nextdir-1 走 prev while (cur-next ! cur) { cur dir 1 ? cur-next : cur-prev; // 按方向报数 M-1 次 // 删除当前结点 DNode *del cur; cur-prev-next cur-next; cur-next-prev cur-prev; cur dir 1 ? cur-next : cur-prev; // 从删除结点的下一个/上一个重新开始 free(del); } }这里要注意的是从删除结点的下一个重新开始报数这句话在双向链表里变成了下一个还是上一个取决于方向规则。如果题目要求报数顺时针、删除逆时针那逻辑又要单独写成两条路径不能简单只用一个dir。我在实现时把报数移动和删除后迁移位置分开做成了两个函数这样不管规则怎么组合都只是调用顺序的变化。5. 测试用例设计与边界验证5.1 常规用例标准序列核对我测试的第一组永远是教材里的经典输入N7S1M3。手动推一遍输出序列是3号报数到3出列剩余1、2、4、5、6、7从4开始继续删6、2、7、5、1最后剩下4。所以期望输出是3 6 2 7 5 1 4最终幸存者4。链表版本和递推版本都用这组数据对拍。另一个非常自然的用例是M1。此时每个人报数就是自己出列顺序应该和编号顺序完全一致N5的期望输出就是1 2 3 4 5最后剩5。这个用例专门用来检查报数步长是否多走一格。我还准备了一组带起点偏移的用例N6S2M4。手动模拟一轮后得到出列顺序5 3 2 4 1最终幸存者6。这组数据可以直接验证S参数是否生效、递推公式的编号偏移是否正确。场景输入期望输出最终幸存者经典用例N7, S1, M33 6 2 7 5 1 44M1边界N5, S1, M11 2 3 4 55起点偏移N6, S2, M45 3 2 4 16单节点N1, S1, M811M大于NN5, S1, M7445.2 边界用例N1、M1、S大于N、M大于N边界测试是课程设计拿分的关键。我当时给自己列了一份边界清单N1时无论S、M是什么输出都应该只有1号本身程序不能崩S大于N时比如N5、S8等价于从3号开始程序不能越界访问M1时出列顺序就是自然顺序M远大于N时比如N5、M7递推版结果应该等于N5、M2的结果因为7 % 5 2但链表版要确保循环能在删到只剩一个人之前完成不要因为M太大导致死循环N很大时比如N100000、M99991链表模拟会明显变慢递推版要保证毫秒级出结果。每次改完代码我都是把这五组测试全部跑一遍再和手动推导的结果人工核对确认通过了才会提交。很多同学只测了第一组经典用例就交结果M1或者N1的测试点直接翻车很亏。6. 报告撰写与答辩追问把代码变成分数6.1 复杂度分析要真实课程设计报告里复杂度分析是老师必看的内容这里最容易出现两个极端要么什么都不写要么写错。链表模拟版本的正确分析是创建链表需要O(N)每次删除需要报数M次共删除N-1个结点因此模拟部分为O(NM)整体算法时间复杂度为O(NM)空间复杂度为O(N)。递推版本的时间复杂度是O(N)空间复杂度是O(1)。这里有一个值得强调的点递推版本通过数学重编号绕开了删除这个物理操作本质上是用高中数学里的映射思想做了一次问题归约。报告里如果能把这一步推导写清楚分数通常不会低。6.2 老师常问的几个追问根据我做课程设计答辩的经验老师特别喜欢围绕为什么和边界情况提问。我提前准备了以下几个问题的应答思路为什么用循环链表而不用数组答数组删除要移位循环链表删除O(1)并且循环结构天然匹配围成一圈的语义代码可读性更高。递推公式是怎么推出来的答从剩余N-1个人的新编号体系出发建立原编号到新编号的映射关系从而把问题的规模递归压缩。M大于N时怎么处理答链表版本不需要特殊处理按原值报数即可递推版本取模等价但要留意取模后为0的情况。单向链表无法直接删除当前结点你是怎么绕过的答让指针停在待删除结点的前驱利用cur-next定位删除目标。如果每轮M的值都在变化递推公式还能用吗答不能直接用因为每轮删除后子问题的编号映射不再一致此时只能回到链表模拟但可以把每轮的M作为参数传进循环。6.3 报告结构建议我把报告分成了五个部分题目分析与需求理解、数据结构设计、核心算法实现、测试结果、总结与心得。其中数据结构设计部分画的是链表结点示意和指针变化过程核心算法实现部分只贴了关键代码而不是全部源码测试结果部分贴了运行截图和上表里那几组测试用例。经验是报告宁可图多文字少也不要整页整页的源码。老师真正想看的是你对结构的理解和对复杂度的分析而不是代码复制粘贴。另外在总结与心得里我没有写套话而是实打实地写了递推公式解决编号偏置时花了半小时这种具体问题反而让报告显得更真实。7. 我踩过的坑和最后的建议7.1 三个最容易翻车的细节第一个坑是编号基准混乱。链表我习惯用1到N递推公式是0基最后输出时忘了把pos 1导致N7、M3的最终幸存者从4变成了3整个表现都偏了一位。后来我把输出前转换的代码单独成行并加了注释才彻底解决。第二个坑是报数步长边界。M1时如果报数循环写成step m就会多走一步把原本第一个报数的人的下一个人删掉。后来我定了死规矩想删除cur-next就写step m想删除cur指向的结点就写step m - 1。每条代码对应哪种语义先看清楚再动手。第三个坑是循环链表创建时的尾指针回指。第一次写创建函数最后忘了把tail-next指向head结果遍历链表直接跑飞程序卡死。解决后我还养成了一个习惯每次创建完链表先写一个简单的遍历函数输出一圈确认环已经闭合再继续实现后续逻辑。7.2 给后来者的小建议如果时间来得及我强烈建议把递推版本也写出来哪怕课程设计只要求链表。因为面试里问约瑟夫环最优解时递推公式几乎是标准答案你现在把它推明白以后都是加分项。实际开发中如果遇到类似按规则循环淘汰一组对象的场景先想想能不能用数学规律缩短模拟过程而不是上来就写链表。数据量小的时候链表可读性好数据量一大递推或者更高级的抽象往往才是出路。我自己做完这三道题最大的感受是经典题之所以经典不是因为它刁钻而是因为一个个知识点的边界就藏在那些看似不起眼的细节里——前驱、步长、编号起点、方向转换。每踩过一个坑对数据的理解就深一层。按照上面这套流程走下来链表版能稳定通过测试递推版能讲清楚推导报告和答辩也有充足素材可写这门课程设计基本就拿稳了。