约瑟夫环三种C语言实现：循环链表、数组与队列实战解析-北京尧图网络

约瑟夫环这题我在不少地方都见过它课程作业里有笔试面试题里有数据结构书的习题里也有。题目本身很短——n个人围成一圈从1号开始报数报到m的人出圈剩下的人继续从1报数直到最后只剩一个人。但就是这道看似简单的题能把C语言的指针、结构体、数组、队列、动态内存管理这些基本功全部串起来。这篇文章直接给出三种不同的实现方式循环链表、遍历数组、队列操作每段都有完整代码和我在实际敲码过程中踩过的坑。如果你正在学数据结构或者准备面试笔试又或者单纯想用一道题把C语言的基础模块复习一遍这篇都适合你。我不会只贴代码还会讲清楚每一步背后的道理因为约瑟夫环的真正价值不在于“做出来”而在于“为什么要用这种方式做”。1. 约瑟夫环问题到底在考什么三种思路的选型依据1.1 一个看似简单的报数游戏先用最直白的方式描述问题n个人编号从1到n围成一圈坐好。从第1个人开始从1报数凡是报到m的人就退出圈子退出后由下一个人重新从1报数这样一圈一圈循环直到圈子里只剩一个人。这里有几个容易忽略的细节报数是“循环”的最后一个人报完数下一个人是第一个人。被淘汰的人不再参与后续报数。报数值m可能比当前剩余人数大很多比如5个人报到9实际会绕好几圈。这种“不断循环、不断删人”的结构天然就和“环形”这个概念绑定在一起。而C语言里能表达环形的数据手段最典型的就是三种循环链表、数组下标取模、队列的队尾回插。三者在抽象层面对应的是同一个数学过程但落到代码上各自的思考方式和代码量完全不同。1.2 为什么是链表、数组、队列这三个方向先说链表。链表节点里有指针可以让最后一个节点指向第一个节点形成物理上的“环”。删除一个节点只需要改两个指针非常符合约瑟夫环“动态删人”的语义。再说数组。数组是连续内存本身没有环形结构但可以用(cur 1) % n这种取模操作让下标在0到n-1之间循环。配合一个状态数组标记谁还活着就能模拟整个报数过程。最后是队列。队列的特点是先进先出如果我从队头取一个人再把他放到队尾就相当于让他出队后又重新回到队伍末尾。这个过程刚好可以模拟“报数后没被淘汰的人继续排队”而报到m的人只出不进直接删除即可。这三个方向不是随便选的。它们分别代表了三种对“环形结构”的理解方式用指针串成环、用取模算成环、用队列操作转成环。把这三种都写一遍才算真正理解了约瑟夫环背后的数据结构思维。1.3 先看结论三套方法的成本对比在展开代码之前我先把结论放在前面方便你心里有个底。三种方法的时间复杂度其实都是O(n*m)数量级因为每淘汰一个人大致需要经过m次报数总共要淘汰n-1个人。真正的差异不在大O上而在代码的复杂程度、边界条件的处理难度和适用场景上。循环链表代码最贴近“环形删人”的直觉但指针操作最容易出错数组法代码最简单思路最直观适合快速实现队列法逻辑最巧妙写起来也短但需要额外实现一个队列结构。下面我分别展开每一份代码都会给出完整的可运行版本并标注关键细节。2. 循环链表实现处理环形结构和动态删除的完整过程2.1 节点定义与环形链表的构建循环链表法的第一步是把n个人串成一个环。每个节点保存一个人的编号和一个指向下一个节点的指针typedef struct Node { int data; struct Node *next; } Node;创建循环链表时有一个很重要的决定用不用头节点。我的选择是“无头节点、尾节点指向头节点”也就是最后一个节点的next指向第一个节点。这样形成的是一个纯粹的单向循环链表没有多余的哨兵节点删除操作更统一。Node* createCircle(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *p (Node*)malloc(sizeof(Node)); if (p NULL) { perror(malloc); exit(1); } p-data i; if (head NULL) { head tail p; p-next head; } else { tail-next p; p-next head; tail p; } } return head; }这里我用了尾插法每次把新节点挂在链表的末尾。如果你用头插法链表里的编号顺序会变成n到1和题目要求的编号顺序相反后面处理起来容易晕。所以构建环形链表顺序很重要。另一个容易被忽略的点是动态分配内存后系统不会自动清理。写练习代码还好但在真实项目里malloc后不检查返回值、用完不free都是事故来源。我习惯每一个malloc都判空而且会在函数结束时手动free每一个节点。2.2 报数与删除节点的核心循环循环链表实现的核心操作是“删除当前报数为m的节点”。单向链表删除节点时必须知道它的前驱节点因为要执行prev-next cur-next这行操作。所以我在循环里维护了两个指针cur指向当前报数者prev指向它的前驱。完整代码如下#include stdio.h #include stdlib.h 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)); if (p NULL) { perror(malloc); exit(1); } p-data i; if (head NULL) { head tail p; p-next head; } else { tail-next p; p-next head; tail p; } } return head; } Node* getTail(Node *head) { Node *p head; while (p-next ! head) { p p-next; } return p; } void josephusCircle(int n, int m) { if (n 0 || m 0) { return; } Node *cur createCircle(n); Node *prev getTail(cur); while (cur-next ! cur) { // 报数1到m-1的人不会被淘汰cur往前移动 for (int i 1; i m; i) { prev cur; cur cur-next; } // 此时cur指向报到m的人 Node *del cur; printf(%d , del-data); prev-next del-next; cur prev-next; free(del); } printf(\n最后幸存者%d\n, cur-data); free(cur); } int main(void) { int n, m; printf(请输入n和m); scanf(%d%d, n, m); josephusCircle(n, m); return 0; }逻辑并不复杂当链表不只一个节点时先让cur走m-1步走到第m个报数者跟前然后用prev把它摘下来输出编号后free掉最后让cur重新指向被删除节点的下一个节点作为下一轮报数起点。有一个细节值得讲为什么初始要让prev指向链表尾部因为当m1时第一个被淘汰的就是当前节点而当前节点可能就是头节点。如果没有prev的初始值第一步就会遇到空指针解引用。让prev先指向尾节点正好让头节点的前驱是尾节点删除逻辑就能统一处理。2.3 循环链表最容易翻车的三个细节第一个坑free之后一定要让指针接着往前走不要再用已经释放的指针。很多初写者习惯把被淘汰节点的data保存下来然后free掉del却忘了cur此时还指向del所指向的内存下一次循环就会访问悬空指针。我上面的代码里free(del)之前就已经把cur更新为prev-next这才是安全的。第二个坑单一节点怎么收尾。当循环链表只剩一个节点时cur-next cur成立。这时不能进入循环直接输出幸存者。上面的while条件cur-next ! cur就是干这个用的写代码时一定要记得判断这个终止条件否则会陷入无限循环。第三个坑内存泄漏。循环链表的每个节点都是malloc出来的如果中途异常退出或者最后忘了free内存就会一直挂着。尤其是OJ或者笔试环境内存泄漏不一定被检测出来但养成写free的习惯没有坏处。3. 数组标记法用下标滚动代替指针跳跃3.1 状态数组取模下标的思路如果你对指针还不太熟练或者想在最短时间内写出一版能跑的约瑟夫环数组法是最稳的选择。它不需要动态内存不需要结构体甚至不需要理解循环链表里复杂的指针移动一个数组加一个取模操作就够了。核心思想是用一个数组记录每个人还活着还是被淘汰了。1表示存活0表示已出圈。再用一个变量cur表示“当前正在报数的人”的下标每报一个人cur就通过(cur 1) % n移动到下一个人。因为下标是取模的所以数组虽然是线性的逻辑上却是一个环。这就是标题里说的“遍历数组”的实现方式。它和数组“物理上搬家”的做法不同——很多人一开始会想淘汰一个人就把后面的元素往前挪下次遍历长度减一这样做虽然可行但每次移动数组元素是O(n)的开销还会让下标管理变得混乱。用状态标记则干净得多。3.2 完整代码与逐段拆解下面这份代码是我在实际做题时比较常用的版本#include stdio.h #define MAXN 1000 int main(void) { int n, m; int alive[MAXN] {0}; printf(请输入n和m); scanf(%d%d, n, m); for (int i 0; i n; i) { alive[i] 1; } int remain n; int cur 0; // 下一个报数者下标0对应编号1 while (remain 1) { int count 0; while (count m) { if (alive[cur]) { count; if (count m) { alive[cur] 0; remain--; printf(%d , cur 1); break; } } cur (cur 1) % n; } cur (cur 1) % n; } for (int i 0; i n; i) { if (alive[i]) { printf(\n最后幸存者%d\n, i 1); break; } } return 0; }拆开看最关键的中间部分是内层循环。它的作用是数出第m个还活着的人。如果当前下标alive[cur]为0说明这个人已经被淘汰cur直接往后走count不增加如果alive[cur]为1说明这个人报了一个有效数count加一。当count数到m时把这个人标记为0输出编号然后break。这里有个容易写错的地方淘汰一个人之后cur不要立刻在break前手动加一。原因是break会直接跳出内层while这时cur还停留在被淘汰者的下标上。外层while结束后需要单独执行一次cur (cur 1) % n让下一轮从被淘汰者的下一个人开始报数。如果你在break前就加了就会漏掉一个人导致报数错位。最后扫描整个alive数组找到值为1的下标那个就是幸存者。因为数组法不像链表那样有尾指针所以最后一步必须线性扫描一次。3.3 数组法的隐藏成本和优化方向数组法代码虽然简单但有一个隐藏成本每当count数到第m个存活者之前内层循环有可能路过很多已经死掉的元素。比如n100m3如果当前只剩两个人而这两个人的位置刚好靠近数组末尾cur从末尾取模绕回开头中间要跳过98个alive为0的位置。所以数组法的时间复杂度虽然还是O(n*m)级别但常数会比循环链表大一些。如果要在数组法上做优化常见思路是“跳着走”——记录每个存活者的前驱后继形成一个静态链表。但这已经不是单纯的“数组法”了而是用数组模拟链表。本文不展开它因为标题要求的是遍历数组这种方法本身。另一个优化角度是如果只想知道最后幸存者的编号而不关心完整的出列顺序可以用约瑟夫环的递推公式时间复杂度降到O(n)。这个我在最后一节会简单提一下。4. 队列操作实现进出队模拟报数最直观也最容易忽略容量4.1 队列方法的核心逻辑把报数变成“队首搬到队尾”数组法和链表法都是从“数据结构形态”出发去模拟环形结构。队列法则有点不同它不刻意去构造环而是利用队列先进先出的性质把“报数过程”变成一个不断出队、入队的操作过程。想象一下一群人排成一队每次报数前队头的人先报。如果他报的数不是m他暂时不会出圈那就让他出队再站到队尾去如果他报的数正好是m那他直接出队不再回来。这个过程不断重复直到队列里只剩一个人。这其实就是把约瑟夫环的“围成一圈”翻译成了“排队转圈”队列的队头是当前报数的人队尾是新排到的人。报数就像是队头不断往队尾移动转了一圈又一圈。很多人在面试里拿到约瑟夫环会先想到链表和数组想到队列的人不多。但一旦说出“把前m-1个人从队头搬到队尾第m个人弹出”这个思路面试官通常会眼前一亮因为它展示的是抽象建模能力而不只是背熟了某一种解法。4.2 基于循环队列的完整实现C语言的标准库没有现成队列所以要么自己写一个数组队列要么自己写一个链表队列。这里我用循环队列实现因为代码最紧凑也更方便解释容量问题。#include stdio.h #define MAXQ 1000 int q[MAXQ]; int head 0; int tail 0; int cnt 0; void push(int x) { q[tail] x; tail (tail 1) % MAXQ; cnt; } int pop(void) { int x q[head]; head (head 1) % MAXQ; cnt--; return x; } int main(void) { int n, m; printf(请输入n和m); scanf(%d%d, n, m); for (int i 1; i n; i) { push(i); } while (cnt 1) { for (int i 1; i m; i) { push(pop()); // 不是第m个的人出队后重新入队 } printf(%d , pop()); // 第m个人淘汰 } printf(\n最后幸存者%d\n, pop()); return 0; }逻辑比我预想的还要短。初始化时把1到n全部入队然后只要队列人数大于1就循环执行前m-1个人依次先出队再入队第m个人只出队不入队并输出编号。循环结束后队列只剩一个人直接弹出就是幸存者。这段代码如果用普通数组队列而不是循环队列会有个潜在问题每次push都往tail递增方向写每次pop都从head递增方向读如果一直不取模tail会越来越大数组很快越界。所以循环队列几乎是必需的或者可以用动态数组和链表实现队列。这也是队列法里“最容易忽略的容量问题”所在。4.3 为什么队列容量只需要 n 而不是 n*m我第一次写队列版约瑟夫环时有个直觉每轮都要把m-1个人搬来搬去数组容量是不是要开很大后来仔细一想根本不用。因为队列里人数永远等于当前还活着的人数。push(pop())是先弹出一个人、再压入一个人一进一出队列总人数不变。第m个人被弹出后人数才减一。所以整个过程中队列里最多只有n个元素。队列容量开到n1就够用了我这里为了演示简单直接定义了MAXQ为1000实际使用时可以根据n动态调整。如果用的是“计数判空”的循环队列容量等于n其实也不会溢出因为初始入队n个元素后cntn再操作时总是先pop再pushcnt永远不会大于n。不过为了避免环形数组在“满”与“空”边界上的某些歧义我习惯把容量开到n1这是写循环队列时比较稳妥的习惯。队列法的另一个优势是代码很难出边界错。循环链表要调试指针数组法要处理下标偏移而队列法的核心逻辑就是两个函数push和pop。只要队列本身写对约瑟夫环主体部分几乎不会出问题。5. 三套代码的验证方法、横向对比与实用心得5.1 用手推结果验证n5m3的标准答案写完三种实现第一件事不是急着提交而是用手算来验证。以小规模数据n5、m3为例初始队列1 2 3 4 5从1开始报数。第1轮1报12报23报3所以3出列。此时剩1 2 4 5下一轮从4开始报1。第2轮4报15报21报3所以1出列。此时剩2 4 5下一轮从2开始报1。第3轮2报14报25报3所以5出列。此时剩2 4下一轮从2开始报1。第4轮2报14报22报3所以2出列。最后只剩4。所以标准答案是出列顺序为3 1 5 2最后幸存者是4。注意第4轮里只剩两个人2号报完1号后4号报2紧接着2号再次报3报数会绕圈。很多人手算时会在这个地方算错以为每个人只能报一次实际上报数没有“额度”绕回来继续算。你运行前面任意一份代码输入5和3应该得到完全相同的输出。如果结果不一致就可以拿着这个手算过程逐步对照代码的执行路径。5.2 三个实现横向对比表实现方式核心思想时间复杂度空间复杂度代码难度最适用的场景循环链表用指针构造物理环删除节点即淘汰O(n*m)O(n)偏高训练指针、链表操作和动态内存管理数组标记法状态数组下标取模遍历O(n*m)O(n)最低快速实现、入门教学、笔试手写代码队列操作队头出队再入队模拟报数轮转O(n*m)O(n)中等面试展示抽象建模能力锻炼队列基本功时间复杂度上三者都是O(nm)但常数略有差异。循环链表删除节点是O(1)每次找第m个节点需要走m步总共n轮所以是O(nm)。数组法每轮要找第m个存活者中间可能跳过大量已淘汰者常数略大。队列法每个非淘汰者每轮先出队再入队总计也是O(n*m)。空间上三者都需要O(n)的额外空间。链表法要动态分配n个节点数组法需要一个状态数组和一个循环数组队列法需要一个能容纳n个元素的循环队列。5.3 实战中我会怎么选面试、作业、竞赛的不同策略如果是做课程作业或者自己练习我建议三种都写一遍。写循环链表可以巩固指针和结构体写数组法可以训练下标思维写队列法则能加深对队列操作的理解。这份练习的收益不在于“会做约瑟夫环”而在于一次接触三种常见的数据结构用法。如果是笔试面试我一般会先写数组法。代码最短逻辑最清晰不容易出错。如果时间充裕再补充说明“还可以用循环链表和队列实现”并简述队列法的思路。面试官更看重的是你能否给出可运行的正确代码以及是否理解不同方法之间的区别而不是你背了多少种写法。如果是竞赛或需要处理大规模数据的场景比如n和m都到了10^5级别三种结构模拟法都会超时。这时候要换思路约瑟夫环有递推公式只求最后幸存者的话可以做到O(n)时间和O(1)空间。这里简单提一下递推公式从只剩1个人开始逆推f(0)0f(i)(f(i-1)m)%i最终结果是f(n)1。它和本文的三种结构方法不冲突但属于另一个层面的解法适合单独研究。最后分享一个我自己保持了很多年的小习惯写完约瑟夫环的任何一种实现第一件事不是急着提交而是先用n5、m3跑一遍对照出列顺序3 1 5 2和幸存者4。确认一致后再去测n1、m1、mn这些边界。这个小习惯帮我避开了不少自以为写对了的bug。如果你正准备面试或考试建议把这三份代码都亲手敲一遍敲完后再合上书本默写一次指针和队列的感觉会在第二次默写时突然就通了。

约瑟夫环三种C语言实现：循环链表、数组与队列实战解析

相关推荐

所谓一人公司，背后其实藏着真人助手+智能体+知识库的完整架构

乳酸化修饰在肿瘤免疫逃逸中的机制与应用

A股量化策略落地：特征工程与大模型决策的关键实践

更多资讯

从模糊标题到实时评估系统：Kafka Streams与Redis实战

litellm统一模型调用中间层：多模型接入与代理部署实战

2026正规的贵阳体育赛事救护保障车租赁:术后平稳转院全程陪护

四天工作制实验：技术团队效率提升21%的实践

Spring AI接入MCP协议：一行代码让Agent调用外部工具

小白程序员轻松入门大模型：AI赋能前端端到端交付实战指南

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？