企业官网建设流程全解析

C语言学到链表和队列之后，约瑟夫环（Josephus Problem）几乎是绕不开的一道综合题。题面本身不难：n 个人围成一圈，从第 k 个人开始报数，报到 m 的人出列，然后下一个人重新从 1 报数，直到所有人出列。但它摆在 C 语言学习者面前时，往往让人卡住的不是逻辑，而是“圆环”这个概念到底该怎么用代码表示。本文不打算只给一个答案，而是把三种主流实现放在一起讲透：循环链表、遍历数组、队列操作。三套代码都能直接编译运行，内部细节和边界条件也会逐一拆解，适合正在复习链表、准备校招笔试，或者想把线性表知识串起来的同学。

1. 约瑟夫环在问什么?三种解法的统一视角

1.1 从报数规则到抽象模型

先明确输入。通常题目会给定三个参数：

• n：总人数
• k：从编号为 k 的人开始报数
• m：报数到 m 的人出列

比如 n=5、k=3、m=2，用手工推一遍：

初始编号：1 2 3 4 5 从3号开始报数： 报1落在3号，报2落在4号 → 4号出列； 从5号开始重新报数： 报1落在5号，报2落在1号 → 1号出列； 从2号开始： 报1落在2号，报2落在3号 → 3号出列； 从5号开始： 报1落在5号，报2落在2号 → 2号出列； 最后剩下5号，直接出列。

所以这个输入对应的出列顺序是：

4 1 3 2 5

不管用哪种数据结构实现，本质都是在做同一件事：维护一个“环形序列”，每次从当前起点前进 m 个位置，把这个位置上的元素移除，再把新起点定位到被移除元素的下一个位置，重复直到序列为空。

所谓三种解法，其实是三种“环形序列”的落地方式：循环链表用节点和指针构造圆环；数组用下标取模来模拟绕圈；队列则靠出队/入队操作把圆环拍平成线性循环。理解了这个统一视角，后面看代码就不会觉得三个算法是三个独立的东西，它们只是同一套逻辑的三种表达。

1.2 三种数据结构的分工

在动手写代码前，先把思维对照表放在这里：

这个表格看起来简单，却决定了三份代码的难易点完全不同。链表难在指针操作和内存释放，数组难在状态判断和死循环预防，队列难在理解“出队再入队”为什么就等价于“按圆圈顺序扫描”。

1.3 输入参数的统一处理

三个程序都必须处理一个细节：输入的 k 可能大于 n，也可能等于边界值。如果 k 表示“从编号 k 开始”，那最稳妥的归一化写法是：

k = (k - 1) % n + 1;

这样不管 k 给 1 还是 100，都能落到区间 [1, n] 内。另一个要处理的是 m。实际报数场景里 m 通常是正整数，但考试或面试题里偶尔会给 m=1，这时不能报错退出，必须正确处理。后面三份代码都会考虑这种情况。

2. 循环链表解法：把圆环交给指针，报数和删除都是指针动作

2.1 环的构建：节点定义与尾插法

链表解法的第一步是构建一个循环链表。每个节点保存编号 data，next 指向下一个节点，最后一个节点的 next 指回头部，形成一个闭合环。

节点定义很常规：

typedef struct Node { int data; struct Node *next; } Node;

创建环形链表时我习惯用尾插法：先建立一个 data 为 1 的自环节点作为头，然后从 2 到 n 逐个插入。每插入一个新节点，都让新节点的 next 指向 head，同时把原尾节点的 next 接到新节点上，更新尾节点。这样不需要额外维护尾指针，创建完成后直接返回 head 即可。

这里有个初学者容易踩的细节：每次插入都必须让新节点指向 head，而不是指向自己或上一个节点。写成node->next = head; tail->next = node; tail = node;就对了。如果写成了node->next = node;，整个环就断了。

2.2 淘汰过程：报数、找前驱、断链、释放

链表的淘汰逻辑核心是：让 cur 指向“当前报数起点”，然后让 cur 走 m-1 步，走到应出列的节点上。因为删除单链表节点需要找到它的前驱节点，否则断链后无法接上，所以维护一个 pre 指针，始终跟在 cur 后面一步。

每次淘汰的步骤是：

1. pre 和 cur 同步移动 m-1 步，pre 成为 cur 的前驱；
2. 输出 cur->data；
3. 用pre->next = cur->next把 cur 从环中摘除；
4. 保留 cur 的临时指针，让 cur 指向下一个节点，再 free 掉旧节点。

这里最妙的点是：因为链表本身就是环，pre 和 cur 同步走 m-1 步之后，不会越界，不需要取模，也不会出现“走到空节点”的问题。这就是循环链表作为约瑟夫环数据结构最直观的原因。

2.3 完整可运行的链表版代码

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* createCircle(int n) { Node *head = (Node*)malloc(sizeof(Node)); head->data = 1; head->next = head; Node *tail = head; for (int i = 2; i <= n; i++) { Node *node = (Node*)malloc(sizeof(Node)); node->data = i; node->next = head; tail->next = node; tail = node; } return head; } void josephusCircle(Node *head, int k, int m) { Node *pre = NULL; Node *cur = head; // 先把 cur 移动到编号 k 的节点 for (int i = 1; i < k; i++) { pre = cur; cur = cur->next; } while (cur != cur->next) { // 报数 m 次，cur 移动 m-1 步 for (int i = 1; i < m; i++) { pre = cur; cur = cur->next; } // 处理 k==1 且 m==1 的极端情况：此时 pre 还没有就位 if (pre == NULL) { for (pre = cur; pre->next != cur; pre = pre->next) ; } printf("%d ", cur->data); pre->next = cur->next; Node *tmp = cur; cur = cur->next; free(tmp); } printf("%d\n", cur->data); free(cur); } int main() { int n, k, m; printf("输入 n k m（空格分隔）: "); if (scanf("%d %d %d", &n, &k, &m) != 3 || n <= 0 || m <= 0) { printf("参数不合法\n"); return 1; } k = (k - 1) % n + 1; Node *head = createCircle(n); josephusCircle(head, k, m); return 0; }

这份代码里有一个很多人第一版都会漏掉的保护：如果 k=1 而且 m=1，第一次进入 while 时 for 循环一次都不执行，pre 还是 NULL，直接解引用 pre 会崩溃。我的处理是临时绕一圈找到 cur 的前驱。这个分支虽然不常触发，但面试里一旦问“m=1 时怎么办”，能答上来就会加分。

2.4 边界条件与常见错误

链表版最容易出的问题有三个。

第一个是 free 顺序问题。删除节点时必须先记录临时指针，再移动 cur，最后才 free(tmp)。如果先 free 再改 next，就是典型的悬空指针。第二个是单节点环。当 n=1 时，createCircle 创建一个自环节点，while 条件cur != cur->next不成立，直接输出最后一个节点并释放，这正好覆盖了“最终只剩一人”的终止条件。第三个是 m 特别大的场景。因为链表是环，cur 可以一直沿着 next 走，m 再大也只是走很多圈，不会越界。

另外建议用 Valgrind 或 AddressSanitizer 跑一遍链表版，重点检查每个节点的内存是否都释放了。链表解法不做内存回收，运行一万次就泄露一万次节点空间，这在课程设计和面试手写代码时都是硬伤。

3. 数组解法：存活标记 + 下标取模，抛弃物理删除

3.1 为什么数组也能模拟圆环

数组本身是线性结构，要变成“圆环”只需要在访问尾部时取模回到头部。用index = (index + 1) % n就能让下标从 n-1 自然跳回 0。这个取模技巧是数组方案的核心。

但还有一个问题需要解决：链表节点删掉后就没了，数组的“删掉”却无法物理消失。常见做法是用一个状态数组 alive[]，值为 1 表示还在场上，值为 0 表示已经出列。每次从 index 往下走时，只对 alive[index] == 1 的位置计数。这样一来，数组容量始终不变，但“有效人数”通过状态位计算。

3.2 核心逻辑：报数计数、状态翻转、起点推进

数组版的外层循环是while (remaining > 0)，remaining 记录场上剩余人数。每一轮内部的步骤是：

1. 用 cnt 记录报数，从当前 index 出发；
2. 每遇到一个 alive 为 1 的下标，cnt 加一；
3. cnt 达到 m 时停下，说明该下标就是要出列的人；
4. 输出index + 1作为编号，把 alive[index] 置 0，remaining 减一；
5. 让 index 继续向后移动，找到下一个 alive 为 1 的下标，作为下一轮报数起点。

这里最需要注意的是第 5 步。删除当前节点后，不能简单index++就完事。假如 index 的下一个位置早就出列了，那就必须继续跳，直到找到活着的节点。我一开写就漏过这个判断，结果程序跑了一段时间后会把已经出列的人再输出一遍。

3.3 完整可运行的数组版代码

#include <stdio.h> #include <stdlib.h> void josephusArray(int n, int k, int m) { int *alive = (int*)malloc(n * sizeof(int)); if (!alive) return; for (int i = 0; i < n; i++) { alive[i] = 1; } int remaining = n; int index = (k - 1) % n; while (remaining > 0) { int cnt = 0; // 报数，只对仍然存活的人计数 while (cnt < m) { if (alive[index]) { cnt++; if (cnt == m) break; } index = (index + 1) % n; } printf("%d ", index + 1); alive[index] = 0; remaining--; // 把 index 移动到下一个存活者，作为下一轮起点 if (remaining > 0) { index = (index + 1) % n; while (!alive[index]) { index = (index + 1) % n; } } } printf("\n"); free(alive); } int main() { int n, k, m; printf("输入 n k m（空格分隔）: "); if (scanf("%d %d %d", &n, &k, &m) != 3 || n <= 0 || m <= 0) { printf("参数不合法\n"); return 1; } josephusArray(n, k, m); return 0; }

这份代码在示意图上比链表简单，但有一个隐藏的复杂度问题：当场上只剩最后一个人时，报数过程可能在数组中绕很多圈。特别是 m 很大时，单轮耗时可能接近整个数组长度。好在单个人最多出列一次，整体最坏复杂度仍可以视为 O(n×m)。

3.4 数组解法的调试与复杂度把控

数组版最常见的 bug 是死循环。典型场景是：把 alive 中所有元素都置了 0，但仍然在while (!alive[index])里移动 index，导致永远找不到活人。我自己的规避方法是让 while 前置判断remaining > 0，因为只要 remaining 大于零，数组里就一定存在某个 alive 为 1 的位置，这个跳转循环必然终止。

另一个建议是，调试时打印每一步的 alive 数组状态。比如一行输出：

index = 2, alive = [1 1 1 1 1] index = 4, alive = [1 1 1 0 1]

这样能快速看出“该出列的人”是否选对。我第一次用手工模拟 n=5、k=3、m=2 时，就是因为没打印状态，误以为 3 号先出列，后来才发现自己把报数起点理解错了。

如果觉得状态数组本身浪费了 n 个字节，还可以把 alive 换成字节类型。但说实话，这种优化对一个数组题没什么意义，清晰度比省那几个字节重要。

4. 队列解法：出队、判断、再入队，环形移动一目了然

4.1 把圆环“拍扁”成队列

队列解法乍一听很反直觉，因为队列是先进先出的线性结构，怎么能表示圆环？但实际上，它表达环形的方式非常巧妙：让队伍从头到尾把“人”走一遍，每次从队头取出一个人，如果这个人报数没到 m，就把它重新放到队尾；如果报到了 m，就只出队、不再入队。这样一来，队列里的顺序始终是整个圆环的顺序，所有活着的成员会不断从队头跑到队尾，形成自然的循环轮转。

这种思路的好处是：不需要下标取模，不需要状态数组，删除的人只需要“不回去”。你只需要维护队列本身，就能把圆环移动完整表达出来。

4.2 循环队列的封装与约瑟夫驱动

队列版我先写一个循环顺序队列，用数组存储元素，front 指向队头下标，rear 指向队尾下标，size 记录元素个数。入队时rear = (rear + 1) % capacity，出队时front = (front + 1) % capacity，容量初始设为 n。

约瑟夫驱动逻辑如下：

1. 把 1 到 n 全部入队；
2. 把前 k-1 个人出队再入队，让第 k 个人到达队头；
3. 进入循环：每次把前 m-1 个人出队再入队，第 m 个人出队且不再入队；
4. 队列只剩 1 个人时，直接输出并结束。

为什么是 m-1 而不是 m?因为队头就是当前报数起点，它报的是 1。要找到报数为 m 的人，只需要让前 m-1 个人“走个过场”回到队尾，第 m 个人自然出现在队头。比如 n=5、k=3、m=2，队头先是 3，报 1 后 3 出队入队，队头变成 4，报 2 的数，4 出列。这个逻辑不会错。

4.3 完整可运行的队列版代码

#include <stdio.h> #include <stdlib.h> typedef struct Queue { int *data; int front; int rear; int capacity; int size; } Queue; Queue* createQueue(int capacity) { Queue *q = (Queue*)malloc(sizeof(Queue)); if (!q) return NULL; q->data = (int*)malloc(capacity * sizeof(int)); if (!q->data) { free(q); return NULL; } q->front = 0; q->rear = -1; q->capacity = capacity; q->size = 0; return q; } int queueEmpty(Queue *q) { return q->size == 0; } void enqueue(Queue *q, int value) { // 本场景保证每次入队前都有出队，size 不会超过 capacity q->rear = (q->rear + 1) % q->capacity; q->data[q->rear] = value; q->size++; } int dequeue(Queue *q) { int value = q->data[q->front]; q->front = (q->front + 1) % q->capacity; q->size--; return value; } void josephusQueue(int n, int k, int m) { Queue *q = createQueue(n); if (!q) return; for (int i = 1; i <= n; i++) { enqueue(q, i); } // 把第 k 个人调整到队头 for (int i = 1; i < k; i++) { int value = dequeue(q); enqueue(q, value); } while (q->size > 1) { // 前 m-1 个人报数未中，出队后回到队尾 for (int i = 1; i < m; i++) { int value = dequeue(q); enqueue(q, value); } // 第 m 个人出列且不再入队 int out = dequeue(q); printf("%d ", out); } printf("%d\n", dequeue(q)); free(q->data); free(q); } int main() { int n, k, m; printf("输入 n k m（空格分隔）: "); if (scanf("%d %d %d", &n, &k, &m) != 3 || n <= 0 || m <= 0) { printf("参数不合法\n"); return 1; } // 起始位置归一化 k = (k - 1) % n + 1; josephusQueue(n, k, m); return 0; }

这份代码有一个值得注意的细节：循环队列容量设为 n，但我并不会真正把队列塞满。因为每一次入队之前，必然有一次出队发生，队列的 size 始终不会超过 n，所以 enqueue 里没有写满队列判断也不会出错。当然，如果要把这段代码改成通用队列组件，就必须补上if (q->size == q->capacity)的判满逻辑。

4.4 队列方案的局限与选型

队列解法的代码量和链表差不多，但逻辑上更适合口头解释：只要一句话——“报数没中的人绕到队尾继续排，报数中的人直接离队”，面试官立刻就能理解。它也比数组方案省掉了下标管理和状态判断，不容易出现“死循环跳过头”的低级错误。

限制在于，它本质还是一个 O(n×m) 的模拟，队列的出入队操作本身有常数级开销。当 m 非常大时，每次都要把大量元素转一遍，性能并不理想。所以队列版本更适合作为“教学演示”和“思路表达”，而不是大规模数据下的最优解。

如果用 C++，队列版可以直接拿 std::queue 简化，代码能缩短三分之一。但本文专注 C 语言，所以保留手写队列的完整实现，顺便复习循环顺序队列的入队出队操作，也算一题两用。

5. 三种方法横向对比与实战取舍

5.1 复杂度、代码量、内存开销对照表

为了直观对比，我把三份实现放在同一张表里：

从时间上看，三种方案在最坏情况下的量级是一样的，差异主要在代码实现难度、内存管理复杂度、以及表达圆环的方式上。

5.2 不同场景下的选型建议

如果你是在准备笔试手写算法，数组版最稳妥。它不依赖复杂的指针操作，也不会在判题环境里因为内存泄露扣分。如果是在课程设计或者数据结构大作业里，链表版更值得做，因为它能体现你对指针、结构体、动态内存管理的掌握程度。如果是面试中连说带写，队列版是最容易讲顺口的方案，第一步讲“出队再入队”，第二步讲“第 m 个人只出不进”，面试官基本不会再追问细节。

从练习角度，我更建议三份都实现一遍。写完数组版，再写链表版，你会真正理解“逻辑删除”和“物理删除”的差别；写完链表版，再写队列版，你会意识到同一个问题可以被不同的数据结构以完全不同的方式表达。这才是约瑟夫环在 C 语言学习里的最大价值：它不是一道套模板的题，而是检验你是否真正理解数据结构的试金石。

5.3 从模拟到数学推导：当 n 到十万时怎么办

如果数据规模变大，比如 n=10万、m=10万，三份代码都会因为 O(n×m) 的复杂度跑不动。这时候需要转到数学解法。

约瑟夫问题有一个著名的递推公式：

f(1) = 0 f(i) = (f(i - 1) + m) % i

其中 f(i) 表示 i 个人从 0 号开始报数，最终幸存者的下标。循环一遍，时间复杂度只有 O(n)。如果题目要求算出最后一个人的编号，而中间过程的出列顺序不重要，直接上这个公式即可。

这个递推不是本文主角，但建议在学完三种模拟实现后自己推导一遍。你会发现，所有模拟方案都告诉你“谁走了”，而数学方案直接告诉你“谁留下”，两者的思考维度完全不同。

5.4 我的验证习惯：对拍测试与内存排查

最后分享一个我自己的编码习惯。写这类多解法模拟题时，我会先写数组版作为“标准答案”，因为数组版最容易读、最不容易错，然后用链表版和队列版的输出结果跟数组版对比。手动对比太慢，可以直接写一个简单的对拍循环，随机生成 n、k、m，同时调用三种函数，比较三份输出序列。

比如 n=5、k=3、m=2 时，三份代码都输出：

4 1 3 2 5

n=1、k=1、m=7 时，都输出 1。m=1、n=6、k=4 时，输出应该是 4 5 6 1 2 3。这几组测试样例能覆盖大部分边界，值得先跑一遍。

链表版的额外检查是内存。我一般用 AddressSanitizer 编译，或者用 Valgrind 跑一遍，确认没有内存泄漏和非法访问。C 语言面试手写代码时，考官往往不会只盯着功能正确，内存释放和边界保护这些细节才是拉开差距的地方。

约瑟夫环做到这里，我个人最大的体会是：数据结构不是背出来的，而是“选出来的”。同样一个圆环，链表用指针闭合，数组用下标取模，队列用出入队轮转，没有绝对的好坏，只看你手上的工具和场景。把这三份代码吃透，下一次遇到环形队列、循环缓冲区、轮询调度相关的问题，你会发现自己比想象中淡定得多。