约瑟夫环C语言环形链表实现与避坑

简介：面向C语言数据结构初学者与课程设计学习者的约瑟夫死亡游戏代码文档，围绕循环链表实现报数出列模拟，重点解决结构体定义、带头结点循环链表创建、按指定人数删除结点以及最后输出剩余人员等核心问题。文档结合设计思路与逻辑说明，给出ElemType、LNode、LinkList等类型组织方式，并覆盖初始化、插入、删除、释放结点和环形指针重置等关键环节，便于读者理解约瑟夫问题的链式存储解法，也可用于实验报告整理与课堂示例参考。压缩包内共1个docx文件，约18KB，篇幅精简但保留了较完整的算法说明与C语言实现片段。目前已有3145人学习下载，适合需要对照代码梳理循环链表操作、拆解删除逻辑和排错思路的读者使用。

1. 从一船 30 人说起：这段 C 代码怎么把约瑟夫环跑成可交互程序

轮船上有 30 个人，从第一个人开始报数，报到 9 的被扔进大海，下一个人重新从 1 报起，直到船上只剩 15 个人。这是约瑟夫死亡游戏最常被拿来讲的版本，也是数据结构课设里出现频率极高的一道题。这份 C 语言代码把它做成了一个能交互的小程序：你输入总人数、报数上限、要剩下的人数，它把被扔下海的人一条条打印出来，最后再打印幸存名单。核心结构就三个 typedef——元素类型、结点类型、链表类型，加四个函数——建环、删人、循环淘汰、打印剩余。

它适合两类人：一类是刚学完单链表、想找个完整例子把指针、malloc、引用传参一次性串起来的同学；另一类是要交课程设计，需要一个骨架再往里填功能的人。代码不长，但踩坑点密，尤其是那个LinkList &L的引用写法，纯 C 编译器直接报错。

2. 数据结构三连 typedef：ElemType、LNode、LinkList 的选型与环形链表搭建

2.1 为什么把数据域拆成 ElemType 而不是塞进 LNode

很多课设代码图省事，直接在人结点里写int id; char name[20]; struct Node *next;，能跑，但一旦要换存储结构（比如改成顺序表、改成数组模拟），所有函数签名都得跟着改。这份代码的处理方式是先定义元素类型，再定义结点类型，最后定义链表类型，三层分开：

typedef struct ElemType /* 元素类型：只关心"一个人"有什么字段 */ { int position; /* 上船时的编号，1 开始 */ char name[8]; /* 姓名，8 字节，后面会讲这是个隐患 */ } ElemType; typedef struct LNode /* 结点类型：数据域 + 指针域 */ { ElemType data; struct LNode *next; } LNode; typedef LNode * LinkList; /* 链表类型：本质就是指向结点的指针 */

这样拆的好处很直接：DeleteLinkList里那句e = p->next->data;一次就能把整条人员信息带回调用方，不用在函数里逐个字段赋值。LinkList这个 typedef 也不是装饰，它让函数签名从LNode **变成可读的LinkList &L，写起来像在操作一个"链表对象"。

参数上要注意name[8]：UTF-8 编码下一个汉字占 3 字节，8 字节只装得下两个汉字加一个结束符。名字三个字就会越界写坏相邻内存——这是后面避坑章节要专门讲的一条。

2.2 带头结点的循环链表：CreateLinkList 的尾插法与成环时机

建环这段是整个程序的地基，思路是"先造一个假头，尾插法挂人，最后把尾巴接回第一个真人，再把假头拆掉"：

void CreateLinkList(LinkList &L, int n) { LinkList r, p; /* r 永远指向尾结点，p 是新申请结点 */ int i; L = (LinkList)malloc(sizeof(LNode)); /* ① 先造头结点，数据域不用 */ L->next = NULL; /* 空表标志 */ r = L; /* 此刻头结点也是尾结点 */ for (i = 1; i <= n; i++) { p = (LinkList)malloc(sizeof(LNode)); p->next = NULL; p->data.position = i; /* ② 编号按上船次序写死 */ printf("请输入%d 个人员姓名：", i); scanf("%s", p->data.name); r->next = p; /* ③ 挂到当前尾巴后面 */ r = p; /* 尾指针后移一位 */ } r->next = L->next; /* ④ 尾结点回指第一个真人，成环 */ free(L); /* ⑤ 假头释放 */ L = r->next; /* ⑥ L 改指向环的入口 */ }

逐段说。① 处申请头结点是为了统一插入逻辑——没有头结点的话，插入第一个结点要单独判断"表是不是空的"，尾插法就得写两套分支。有了这个哨兵，循环里只需要无脑r->next = p; r = p;，代码短一半。

② 处position直接取循环变量i，意味着编号就是上船顺序，后面出列打印时靠它认人。姓名用scanf("%s")读，遇到空白就停，所以名字里不能有空格。

③ 是标准尾插，r始终是最后一个结点，插入是 O(1)，整个建表 O(n)。原代码里写的是p->next = r->next; r->next = p;，因为r->next在这一刻恒为 NULL，效果等价于p->next = NULL，写直白一点更好读。

④ 和 ⑤ 是这份代码最值得看的两行。成环必须放在循环外，不能边插边环——如果第一轮就把r->next指回去，后面的尾插会断链。free(L)之前必须先把r->next（也就是第一个真人的地址）留下来，否则释放完就找不到了，所以 ⑥ 紧跟着把L挪到环入口。这个"交接"顺序反了就是野指针，跑一次崩一次。

提示：调试建环是否成功，最省事的办法是在free(L)之前打印r->next->data.position，确认它等于 1；再打印L->next->data.position，确认不等于 NULL。

2.3 头结点的释放与新头指针的交接

接着上一段说，free(L); L = r->next;这两行的顺序是硬约束，但更值得琢磨的是"为什么非要把头结点拆掉"。

如果保留头结点，环的形状就变成"头 → 1 号 → 2 号 → … → n 号 → 头"，好处是插入删除不用特判空表；坏处是每次报数都得跳过它，DeleteLinkList里定位前驱的步数会多算一位，DisplayLinkList遍历时还得记住"从 L->next 开始打印"。教学代码选的是不留头结点，让L直接指向 1 号人员，报数起点天然就是 1，逻辑更贴近题面描述。

代价也有：一旦L指的就是真人，删除操作就必须处理"删的正好是 L 指向的结点"这种情况，否则L会悬空。这份代码用L = p->next->next;这一句把新头指针顺手交接了，具体推导放在 3.2 节。理解这个取舍，后面看删除函数才不会觉得莫名其妙。

另外补一句工程习惯：malloc之后应该判空，n <= 0时应该直接返回而不是建一个空环。教学代码省了这两处，自己改的时候补上，不然输入 0 会得到一个L == NULL的环，后面所有函数都对 NULL 解引用。

3. 出列链路拆解：DeleteLinkList 的步数计算与 DieLinkList 的循环收敛

3.1 定位前驱的步数推导：while (j < i - 1) 到底走几步

删除单链表结点必须拿到前驱，这是单链表绕不开的成本。环形链表没有 NULL 结尾，所以不用担心走飞，但也意味着步数算错不会崩，只会安静地删错人——比崩溃更难查。

void DeleteLinkList(LinkList &L, int i, ElemType &e) { LinkList p = L; /* p 从当前报数起点出发 */ int j = 1; while (j < i - 1) { /* 循环体执行 i-2 次 */ p = p->next; j++; } e = p->next->data; /* 前驱的后继就是第 i 个，先存下来 */ L = p->next->next; /* 下一轮从出列者的后继重新报 1 */ p->next = p->next->next; /* 摘链，前驱直接指向后继的后继 */ }

关键在步数。p初值指向第 1 个结点，j初值为 1，循环条件是j < i - 1，所以循环体执行i - 2次，p最终停在第1 + (i-2) = i - 1个结点上，正好是出列者的前驱。删掉的是p->next，也就是第i个。

拿i = 4走一遍：j=1进循环（1 < 3），p到第 2 个，j=2；再进（2 < 3），p到第 3 个，j=3；3 < 3不成立，退出。p停在第 3 个，删第 4 个。对上了。

参数含义再明确一遍：i就是主函数传进来的PersonCount，即"数到几出列"；e是输出参数，把被删结点的数据域整体拷回调用方，C 里没返回值就只能靠它带回两条信息（编号 + 姓名）；L是引用，函数内部会把它改成被删结点的后继，这样下一次调用就自动从下一个人开始数，不需要额外维护"当前指针"。

这里顺带说一个容易忽略的点：环形链表里p永远不会变成 NULL，所以这个 while 循环没有终止保护。如果i传进来是 0 或者负数，j < i - 1一开始就不成立，p停在原地，删掉的是第 2 个人——错得悄无声息。加一句if (i < 1) return;成本极低。

3.2 摘链与头指针交接：L = p->next->next 这一句在做什么

上一节留了个尾巴：为什么L要跟着改。

设想环上依次是 1、2、3、4、5，L指向 1，现在数到 2，要删 2 号。p停在 1 号（i=2时循环一次都不进），e拿到 2 号的数据，摘链后 1 号的next指向 3 号。如果L还指着 1 号，下一轮报数会从 1 号重新开始——1 号被数了两次，结果就全乱了。所以必须让L前移到 3 号，也就是p->next->next。

再看删的正好是L指向的结点的情况：环上只剩 3 和 5，L指向 3，数到 1 要删 3。此时p = L指向 3，p->next是 5，L = p->next->next就是 5 的next，也就是 3——L又指回了被删的结点，然后free掉就是野指针。这是i = 1时的典型翻车现场。由于DieLinkList的循环条件保证至少留LeftTotal个人，只要LeftTotal >= 1且PersonCount >= 2，日常输入不会触发；但只要你把PersonCount改成 1 试试，立刻就能看到后果。

还有一处：这份代码没有free被删结点。摘链只是把指针绕过去，那块sizeof(LNode)的内存还挂着，LeftCount上万时就是实打实的泄漏。正确写法是先存后删：

LinkList q = p->next; /* 先接住要出列的结点 */ e = q->data; /* 拷数据 */ L = q->next; /* 新起点 = 出列者的后继 */ p->next = q->next; /* 摘链 */ free(q); /* 再释放 */

顺序不能反：free之后q->next就是脏数据，L会指到一片已经还给堆管理器的内存上。这个坑我在早期的课设里踩过一次，现象是"名单偶尔多出几个乱码名字"，查了两天才定位到释放顺序。

3.3 循环终止条件：LeftCount 与 LeftTotal 的边界

淘汰循环本身只有五行，但终止条件写错就是全灭或者死循环：

void DieLinkList(LinkList &L, int TotalCount, int PersonCount, int LeftTotal) { ElemType e; int LeftCount = TotalCount; /* 剩余人数，初始等于总人数 */ CreateLinkList(L, TotalCount); /* 先把环建好 */ printf("跑到大海中人员名单\n 编号\t 姓名\n"); while (LeftCount > LeftTotal) { /* 剩到目标人数就停 */ DeleteLinkList(L, PersonCount, e); LeftCount--; /* 每删一个减一 */ printf("%d\t%s\n", e.position, e.name); } }

LeftCount是"当前还在船上的人数"，每轮删除后自减，等于LeftTotal时退出。因为是先删后减，所以循环体一共执行TotalCount - LeftTotal次，被扔下海的正好是这么多人。

三个边界要盯住。LeftTotal == 0时，最后一轮会去删环上唯一剩下的那个人，p->next指向自己，L也被设成自己，free之后L悬空，下一次打印必崩。LeftTotal >= TotalCount时循环一次都不进，直接打印全部人员，虽然不崩但语义是"一个都没扔"，得看题面允不允许。PersonCount == 1时如 3.2 所述，删的是下一个人而不是自己，逻辑整个偏移一位。

参数顺序也值得说一句：DieLinkList(L, TotalCount, PersonCount, LeftTotal)四个参数里，TotalCount其实只用来初始化LeftCount和传给建表函数，PersonCount转手给了DeleteLinkList，真正决定循环次数的是TotalCount - LeftTotal。改需求的时候，比如"扔到剩一半"，只要在调用处算好LeftTotal = TotalCount / 2传进去，函数体一行都不用动。

3.4 剩余人员遍历：DisplayLinkList 的环遍历写法

环形链表遍历的难点是"什么时候停"，因为没有 NULL 可以判：

void DisplayLinkList(LinkList L) { LinkList p = L; printf("轮船上剩余人员名单：\n 编号\t 姓名\n"); printf("%d\t%s\n", p->data.position, p->data.name); /* 先打印起点 */ while (p->next != L) { /* 转一圈回到起点就停 */ p = p->next; printf("%d\t%s\n", p->data.position, p->data.name); } }

先打印L再进循环，是因为循环条件判的是p->next != L，如果写成普通的while (p != NULL)会无限转圈。这种"先输出首结点、再判后继是否回到首结点"的写法是环遍历的标准套路，换成do { ... } while (p != L);更紧凑，效果一样。

它也能容忍只剩一个人的情况：p->next指向自己，等于L，循环直接不进，只打印一次。但如果L是 NULL（比如LeftTotal = 0导致最后一个人被删光），这里就是空指针解引用，所以 3.3 节说的边界保护不是可选项。

到这一步，四个函数串起来的完整链路就清楚了：CreateLinkList建环 →DieLinkList反复调DeleteLinkList淘汰 →DisplayLinkList收尾打印。数据流只有一个L，全程靠引用在函数间传递，没有全局变量，这一点比很多课设代码干净。

4. 把它跑起来：编译命令、三组输入样例和一次手工推演

4.1 编译命令与文件组织

这份代码是单文件，不需要 Makefile，但有一件事必须先说清楚：LinkList &L是 C++ 的引用语法，用gcc编译会直接报expected ')' before '&' token。两条路，任选一条：

# 路线一：用 g++ 编译，代码一行不改 g++ -Wall -Wextra -g -o joseph joseph.cpp # 路线二：坚持纯 C，就得把引用改成二级指针（第 6 章给改法） gcc -std=c99 -Wall -Wextra -g -o joseph joseph.c

-Wall -Wextra建议一直带着，它会提示void main()不符合标准、scanf返回值未使用、name[8]可能的截断等问题，等于免费帮你做一轮静态检查。-g是为了后面用 gdb 单步看指针。

文件就一个joseph.cpp（或者你改名成.c走路线二），目录里放一个README记输入格式就够了。运行：

./joseph

程序会依次问三件事：总人数、报数上限、要剩下的人数，然后要求逐个输入姓名。

4.2 三组输入样例与预期输出

第一组，最经典的 5 人报 2 剩 2：

请输入总人数：5 请输入抛入大海时要数到的人数：2 请输入轮船安全需要剩余的人数：2 请输入1 个人员姓名：A ...（依次输入 B C D E）

预期扔下海的是2 B、4 D、1 A，剩余3 C、5 E。这组数据小，适合手工核对。

第二组，PersonCount = 4，用来验证 3.1 节的步数推导真的走了多步：

总人数 5，报数 4，剩余 2，姓名 A B C D E

预期扔下海4 D、3 C、5 E，剩1 A、2 B。

第三组，边界验证，总人数 1，报数 2，剩余 1：建环后只有一个人，LeftCount(1) > LeftTotal(1)不成立，循环一次不进，直接打印幸存名单，输出一个人。这组能跑通说明你的空环、单结点分支没写错。

反向用例也得有：总人数 5，报数 1，剩余 1。按正常语义应该每次删掉报数者自己，但这份代码会删掉下一个，输出会和手算对不上——这正是 3.2 节说的偏移问题，拿它当"已知缺陷测试用例"。

4.3 手工推演 n=5, m=4, left=2 的完整链路

光看输出对不上号，还是得手推一遍。环上依次 1(A) → 2(B) → 3(C) → 4(D) → 5(E) → 回到 1，L指向 1。

第一轮，i = 4。p = L指 1，j = 1，1 < 3成立走一步到 2，j = 2；2 < 3成立再走一步到 3，j = 3；退出。p停 3，e取p->next->data得 4(D)，L = 4 的后继 = 5，3->next = 5。环变成 1 → 2 → 3 → 5 → 1，剩 4 人，L指 5。

第二轮，p = 5。走两步：到 1（j=2）、到 2（j=3）。p停 2，e得 3(C)，L = 3 的后继 = 5，2->next = 5。环变成 1 → 2 → 5 → 1，剩 3 人，L指 5。

第三轮，p = 5。走两步到 1、到 2。e得 5(E)，L = 5 的后继 = 1，2->next = 1。环变成 1 → 2 → 1，剩 2 人，L指 1。LeftCount从 3 减到 2，等于LeftTotal，退出。

打印剩余：1(A)、2(B)。和 4.2 的预期一致。

这个推演里有个细节值得盯：每轮结束L都指向"下一个开始报 1 的人"，而不是被删结点的位置。第二轮结束L指 5，第三轮从 5 开始数，5 是报 1，1 是报 2，2 是报 3，5 是报 4——等等，这里要小心：p停在 2，说明 2 是报 3 的人，p->next是 5，5 报的是 4。对上了。

4.4 输出对不上时先看哪里

调试这类链表题，最有效的三个观察点，按顺序看：

第一，建环后立刻打印L->data.position和环上结点个数（转一圈计数）。如果不是 1 和n，问题在CreateLinkList，别往下查。

第二，每轮删除前后各打印一次L->data.position。按 4.3 的推演，这个值应该依次是 5、5、1。对不上说明步数或头指针交接错了。

第三，如果名单人数对但名字错位，八成是name[8]越界踩了相邻字段。现象是编号正常、姓名变成半截乱码，或者后面某个人的姓名莫名其妙变了。

用 gdb 的话，在DeleteLinkList的while前后各下一个断点，p joseph看p、p->next、L三个值，一轮一轮对，比在脑子里转圈靠谱得多。

5. 踩坑排查：这份教学代码里五处会让你卡住的细节

5.1 现象：gcc 编译报expected ')' before '&' token

原因：函数签名写的是void CreateLinkList(LinkList &L, int n)，&L是 C++ 的引用参数，C 语言没有这个语法。教学环境里很多老师用 C++ 编译器跑 C 代码，学生拿回去用 gcc 就炸。

解决：短期换g++编译，g++ -o joseph joseph.cpp即可，代码一个字不用动。长期还是改成纯 C 的二级指针，函数内用(*L)访问，调用处传&L。第 6 章给了完整改法。别用"把.c后缀改成.cpp就完事"糊弄自己，后面接进纯 C 工程照样得返工。

5.2 现象：输入三个字的名字后，后面几个人的姓名变成乱码

原因：char name[8]装不下。UTF-8 下一个汉字 3 字节，两个汉字已经 6 字节，加结束符 7 字节，第三个汉字直接写到position字段或者结构体尾部之外。scanf("%s")又不检查长度，来者不拒。

解决：数组开到 32 字节起步，scanf加宽度限制scanf("%31s", p->data.name)。要支持带空格的名字就换fgets(p->data.name, sizeof(p->data.name), stdin)，注意它会把换行符读进去，需要手动裁掉尾部\n。改完记得重新跑一遍 4.2 的样例，确认打印没串行。

5.3 现象：报数设成 1 时，被扔下海的不是报数者本人

原因：DeleteLinkList的语义是"删第i个"，而p从L出发走i - 2步停在前驱。i = 1时循环一次不进，p就是L，p->next是第 2 个，于是删了下一个。环形链表没有 NULL，这个错误不会崩，只会安静地算错。

解决：在函数开头特判i == 1，此时前驱是环上最后一个结点，需要先绕一圈找到它：LinkList q = L; while (q->next != L) q = q->next;，然后按常规摘链。或者干脆在main里拦住PersonCount < 2的输入，告诉用户报数至少从 2 开始。前者通用，后者省事，看你要不要留这个功能。

5.4 现象：人数上千时程序越跑越慢，任务管理器里内存一直涨

原因：DeleteLinkList摘链后没free被删结点。每轮泄漏一个sizeof(LNode)，几十个人看不出来，几万轮就是实打实的浪费。更隐蔽的是野指针风险：如果先free再取q->next，L会指向已释放内存，表现是"偶尔打印出几个不认识的名字"。

解决：按 3.2 节的顺序来——先q = p->next接住，e = q->data拷数据，L = q->next和p->next = q->next交接指针，最后才free(q)。这个顺序我建议当成肌肉记忆，凡是"摘链 + 释放"都按这个模板写。

5.5 现象：编译一堆 warning，程序能跑但结果偶尔诡异

原因：void main()不是标准写法，GCC 会给警告；scanf的返回值没检查，输入字母而不是数字时，变量保持未初始化值，TotalCount可能是任意垃圾数，后面malloc直接吃光内存；malloc返回值也没判空。

解决：签名改成int main(void)，末尾return 0;。scanf改造成if (scanf("%d", &TotalCount) != 1) { printf("输入无效\n"); return 1; }，三处输入都这么处理。malloc之后加if (L == NULL) return;。这几行加上去，程序从"能跑"变成"输入错了会告诉你错在哪"。

6. 二次开发：从 C++ 引用改成纯 C 指针，再抽出可测试的出列核心

先说改法。引用换二级指针，核心是把函数里所有L改成(*L)：

/* 纯 C 版：删第 m 个，L 是二级指针，顺带补上 free 和 m==1 的分支 */ void delete_node(LinkList *L, int m, ElemType *e) { LinkList p = *L, q; int j = 1; if (m == 1) { /* 特判：数到 1 就是自己出列 */ q = *L; while (p->next != q) p = p->next; /* 绕一圈找前驱 */ } else { while (j < m - 1) { p = p->next; j++; } q = p->next; } *e = q->data; /* 先拷数据 */ *L = q->next; /* 起点后移 */ p->next = q->next; /* 摘链 */ free(q); /* 最后释放 */ }

调用处从DeleteLinkList(L, PersonCount, e)变成delete_node(&L, PersonCount, &e)。参数含义不变：L是链表指针的地址，函数内部通过它改调用方的L变量；m是报数上限；e是输出参数。m == 1的分支多绕一圈找前驱，是因为此时p初值就是q，得先走到环尾才能摘。

第二件事，把"算"和"打印"拆开。教学代码把printf埋在执行逻辑里，想批量跑一百组参数做验证就只能靠重定向，很不方便。抽一个纯函数出来，返回出列顺序数组：

/* 数组模拟环，只算出列顺序，不打印、不 malloc 结点，方便写测试 */ int joseph_order(int n, int m, int *out) { int *next = (int *)malloc(sizeof(int) * (n + 1)); int i, cnt = 0, prev, cur; for (i = 1; i <= n; i++) next[i] = (i == n) ? 1 : i + 1; /* 建环 */ prev = n; cur = 1; while (cnt < n) { for (i = 1; i < m; i++) { prev = cur; cur = next[cur]; } /* 报数 */ out[cnt++] = cur; /* 记录出列者编号 */ next[prev] = next[cur]; /* 摘链 */ cur = next[cur]; /* 从下一个人重新报 1 */ } free(next); return cnt; /* 返回出列总人数，恒等于 n */ }

参数：n总人数，m报数上限，out由调用方提供、长度至少n的数组，函数把出列顺序写进去，返回值是实际写入的个数。next[i]存的是"编号 i 的下一个人"，下标从 1 开始所以数组开n + 1。这版没有链表指针，全部是下标运算，用assert对着 4.3 的手推结果一条条比，跑一遍就知道逻辑对不对。

改完之后建议按下面这张表验一遍，每行都是一次可复现的检查：

valgrind --leak-check=full ./joseph这一条特别值得跑，它会把"没释放的结点数""非法读写"直接列出来，比盯着代码猜快得多。

再往前走一步，就是把输入输出也换掉：从文件读名单（一行一个名字，避免scanf的空白截断），出列结果写成 CSV，这样同一份代码可以批量跑参数组合，用脚本算出"哪个 m 能让指定的人活下来"。约瑟夫环本身有 O(n) 的数学解法，不需要模拟，但拿它做对照测试正好——模拟结果和公式结果一致，说明你的链表实现是对的。

最后说个我自己的教训。早些年带人做这类课设，我总默认"能跑就行"，直到有次帮人看一个跑了一晚上没出结果的程序，才发现是PersonCount = 1时环退化成了自环，while (LeftCount > LeftTotal)永远为真，LeftCount一直减到负数还在转。从那以后，我每写完一个环形链表的函数，都强制先把n = 1、m = 1、LeftTotal = 0这三种输入各跑一遍，再跑正常用例。这几个边界值花不了两分钟，能省掉大半夜的排查。希望帮到你。

本文还有配套的精品资源，点击获取