C语言循环链表实现约瑟夫死亡游戏：建环、淘汰与剩余名单

简介：这份面向C语言数据结构学习者的约瑟夫生死游戏代码文档，围绕循环链表解决经典约瑟夫环问题展开，适合课程实验、课程设计或算法入门阶段对照研读。压缩包内共1个docx文件，约18KB，集中收录完整C语言代码与设计思路说明，涵盖元素类型与链表结点结构定义、带头结点循环链表的创建、按指定人数删除结点、释放空间以及输出剩余人员名单等核心环节。文档结合代码讲解尾指针维护、环形连接、删除后头指针重置等实现细节，并给出主函数调用流程，便于读者理解指针操作、边界条件处理和模块划分方式。已有3145人学习，可作为课程作业参考或算法复习材料，帮助读者从结构体设计走到完整程序实现，理清循环链表在约瑟夫问题中的算法逻辑。

1. 从“数到就出局”到可交付代码：约瑟夫死亡游戏的需求边界与适用人群

约瑟夫死亡游戏这道 C 语言代码题，真正落到课程设计里，考的不是背一个递推公式，而是把“位置+姓名”装进循环链表，按步长淘汰并输出剩余名单。很多人第一反应是数组模拟，人数一多、删除点一散，下标维护就开始玄学。这套方案要解决的是：给定总人数、每次数到几、最终留几人，程序能完整走完建环、淘汰、打印剩余名单这条链路；适合正在做 C 语言课设、数据结构毕设，或需要一份能讲清循环链表完整链路的参考实现的人。

它不适合只想背结论的人。因为验收时老师通常会让你改步长、改剩余人数，甚至把总人数设成 1，看你的L指针怎么更新、空链表怎么处理。把这些边界提前想清楚，比代码写得多漂亮更重要。

2. 数据模型与总体设计：位置姓名结构体、循环链表和淘汰流程怎么划分

先把需求定死，再谈代码。约瑟夫死亡游戏的业务规则可以拆成三个输入和两个输出：输入总人数TotalCount、每次数到的人数PersonCount、轮船安全需要剩余的人数LeftTotal；输出被抛入大海的人员顺序，以及最后轮船上剩余的人员名单。计数从当前起点开始数 1，数到PersonCount的人出局，出局者的下一个人成为下一次计数的起点，重复到剩余LeftTotal人为止。编号是人员最初的站位，不随链表头移动而改变；姓名在建表时一次性录入，删除时随结点一起带出。

这个场景下，循环链表比数组更贴合规则。数组删除元素要搬移后续元素，或者用标记位跳过已删除位置，步长一大就要反复取模；循环链表删除一个结点只改两个指针，出局后直接把L移到下一个结点，计数起点自然衔接。代价是指针操作多，成环、断链、释放顺序都容易翻车，所以总体设计要把“建表”和“淘汰”分开，别把输入、删除、打印全塞进一个函数里。

2.1 三个输入与两个输出先定死

总人数必须是正整数，步长至少为 1，剩余人数不能小于 0，也不能大于总人数。剩余人数等于总人数时，程序不删除任何人，直接打印全部名单；剩余人数为 0 时，最后链表会被删空，显示函数必须能处理L == NULL。这些边界不写进设计，代码跑通常规用例也会在答辩现场被问住。

输出格式通常固定为两列：编号和姓名。淘汰名单按实际出局顺序打印，剩余名单按当前环的顺序打印。这里有一个容易被忽略的点：删除后L指向被删结点的下一个，所以剩余名单从L开始遍历，未必按原始编号升序。如果验收明确要求按编号升序，通常的做法是先把剩余结点收集到数组，再按position排序输出；如果没要求，保留环顺序更省一次遍历，答辩时说明“剩余名单按环顺序展示”即可。

2.2 ElemType、LNode、LinkList 的类型分层

元素类型和结点类型要分开。ElemType只关心业务数据，包含位置和姓名；LNode关心链表结构，包含数据域和指针域；LinkList是指向结点的指针类型，用来表示链表头。这样删除时可以用一个ElemType变量把被删人的信息带出来，结点释放后仍然能打印姓名和编号。

#include <stdio.h> #include <stdlib.h> /* 业务元素：编号 + 姓名 */ typedef struct ElemType { int position; char name[8]; } ElemType; /* 链表结点：数据域 + 指针域 */ typedef struct LNode { ElemType data; struct LNode *next; } LNode; /* 链表类型：指向结点的指针 */ typedef LNode *LinkList;

参数说明：position存初始编号，name[8]表示姓名最多 7 个字符加结束符；data是值拷贝，删除结点前把q->data赋给e，释放q后仍能输出被删人的信息。这里有一个 C 语言作业里常见的坑：原始写法void CreateLinkList(LinkList &L, int n)用了 C++ 的引用语法，用 C 编译器会直接报错。交 C 语言版本时通常改成LinkList *L，调用时传&L；或者让函数返回新的头指针。下面统一用二级指针，语义仍然是“在函数内修改链表头”。

2.3 带头结点创建再释放头结点的设计取舍

创建循环链表时，先建一个头结点，可以让尾插法少写很多特判。L指向头结点，尾指针r一开始也指向头结点；每读入一个人，就申请新结点p，把编号和姓名写进去，执行r->next = p、r = p。第一个结点插入时不需要判断“链表是否为空”，因为头结点已经在了。所有结点插完后，执行r->next = L->next，让尾结点指回第一个有效结点；再free(L)释放头结点，最后L = r->next，让链表头直接指向第一个有效结点。

这个取舍的好处是建表逻辑顺，坏处是收尾必须记得释放头结点并回正指针。忘了free，链表里会多一个没赋姓名的头结点，打印时出现编号 0 或乱码；忘了L = r->next，L还指着已经释放的头结点，下一次访问就是野指针。课堂代码选择释放头结点，是为了让后续删除时L直接表示当前计数起点；如果保留头结点，删除和打印都要从L->next开始，虽然也能做，但初学阶段更容易绕。

2.4 淘汰流程的状态机与复杂度预估

淘汰过程可以看成一个简单状态机：当前链表头L是计数起点，当前剩余人数left从TotalCount开始；每一轮删除第PersonCount个结点，left减 1，打印被删者；当left == LeftTotal时停止。删除函数会把L更新为被删结点的下一个结点，所以下一轮不用额外移动起点。

复杂度上，建表是 O(n)，每轮删除要沿环走PersonCount - 1步找前驱，总共删除n - k人，时间大致是 O((n-k)×m)。如果步长可能大于当前剩余人数，直接走会绕圈，通常的做法是每轮先算actualStep = (PersonCount - 1) % left + 1，把步长折算到当前环长内，再调用删除。空间复杂度是 O(n)，每个人员一个结点。把这一点讲清楚，答辩时老师问“步长比人数大怎么办”，你就有话可说。

3. 核心操作落地：创建、删除第 i 人与按步长淘汰的完整代码链路

这一章把三个核心函数串起来：CreateLinkList负责建环，DeleteLinkList负责删除第 i 个结点并带回被删者信息，ThrowPerson负责按步长循环淘汰，DisplayLinkList负责打印剩余名单。代码用 C 兼容的二级指针写法，编译时直接用 C 编译器即可。输入姓名用%7s限宽，避免name[8]越界；删除函数对i == 1单独处理，因为循环链表没有头结点后，删除第一个结点要先找到尾结点。

3.1 CreateLinkList：尾插法、成环和头指针回正

建表的关键顺序是：申请头结点、尾指针指向头结点、循环尾插、尾结点指回第一个有效结点、释放头结点、L回正。p->next = NULL只是临时置空，最后统一成环；r永远指向最后一个结点，所以新结点直接接在r后面。n == 1时，r->next = L->next会让唯一结点指向自己，形成自环，这也是后面删除唯一结点时必须判断q->next == q的原因。

void CreateLinkList(LinkList *L, int n) { LinkList head, r, p; int i; head = (LinkList)malloc(sizeof(LNode)); if (head == NULL) { printf("内存分配失败\n"); exit(1); } head->next = NULL; r = head; for (i = 1; i <= n; i++) { p = (LinkList)malloc(sizeof(LNode)); if (p == NULL) { printf("内存分配失败\n"); exit(1); } p->data.position = i; printf("请输入第%d个人员姓名：", i); scanf("%7s", p->data.name); /* 限宽，防止姓名越界 */ p->next = NULL; r->next = p; /* 新结点接在尾结点后面 */ r = p; /* 尾指针后移 */ } r->next = head->next; /* 尾结点指回第一个有效结点，成环 */ free(head); /* 释放临时头结点 */ *L = r->next; /* L 指向第一个有效结点 */ }

参数说明：L是二级指针，函数内通过*L修改调用方的链表头；n是总人数，必须大于 0。head只是临时头结点，不存业务数据；r是尾指针；p是每次新申请的结点。成环后r->next就是第一个有效结点，所以free(head)之后用*L = r->next回正。注意free(head)后不能再访问head->next，顺序不能反。

3.2 DeleteLinkList：定位前驱、摘链、释放和 L 更新

删除第i个结点分两种情况。i > 1时，从L出发走i - 2步找到前驱p，被删结点是q = p->next；保存q->data到e，执行p->next = q->next把q摘出环，再让*L = q->next，表示下一轮从被删者的下一个人开始数，最后free(q)。i == 1时没有前驱，要先沿环找到尾结点，让尾结点指向q->next，再更新*L。如果环里只剩一个结点，q->next == q，删除后直接把*L置空。

void DeleteLinkList(LinkList *L, int i, ElemType *e) { LinkList p, q; int j; if (*L == NULL || i < 1) { return; } p = *L; if (i == 1) { /* 删除第一个结点：先找尾结点 */ while (p->next != *L) { p = p->next; } q = *L; *e = q->data; if (q->next == q) { *L = NULL; /* 只剩一个结点，删空 */ } else { p->next = q->next; /* 尾结点跳过 q */ *L = q->next; /* 新头指向被删者的下一个 */ } free(q); return; } j = 1; while (j < i - 1) { p = p->next; j++; } q = p->next; /* q 是要删除的结点 */ *e = q->data; /* 先保存数据，再释放 */ p->next = q->next; /* 前驱跳过 q */ *L = q->next; /* 下一轮从 q 的下一个开始数 */ free(q); }

参数说明：i是 1-based 的第几个结点，调用方要保证i不超过当前环长；e用来带回被删者的编号和姓名。q = p->next后先赋值*e = q->data，再改指针、再free(q)，顺序反了就会读到已释放内存。删除后*L指向q->next，这是淘汰循环能连续跑下去的关键。

3.3 ThrowPerson 与 DisplayLinkList：淘汰循环和剩余名单

ThrowPerson先建表，再循环删除。每一轮根据当前剩余人数left计算实际步长：actualStep = (PersonCount - 1) % left + 1。这样即使PersonCount大于left，也能折算到环内，不会在删除函数里绕圈绕出问题。循环条件是left > LeftTotal && *L != NULL，删到剩余人数达标或者链表为空就停。DisplayLinkList先判断L是否为空，非空时用do-while至少打印一次，然后沿环走回L停止。

void ThrowPerson(LinkList *L, int TotalCount, int PersonCount, int LeftTotal) { ElemType e; int left, actualStep; CreateLinkList(L, TotalCount); left = TotalCount; printf("抛入大海人员名单\n编号\t姓名\n"); while (left > LeftTotal && *L != NULL) { actualStep = (PersonCount - 1) % left + 1; DeleteLinkList(L, actualStep, &e); left--; printf("%d\t%s\n", e.position, e.name); } } void DisplayLinkList(LinkList L) { LinkList p; if (L == NULL) { printf("轮船上无剩余人员\n"); return; } printf("轮船上剩余人员名单：\n编号\t姓名\n"); p = L; do { printf("%d\t%s\n", p->data.position, p->data.name); p = p->next; } while (p != L); }

参数说明：TotalCount是总人数，PersonCount是步长，LeftTotal是最终剩余人数；left是当前剩余人数，每删一个减 1；actualStep是折算后的步长，保证 1 到left之间。DisplayLinkList的参数是LinkList而不是二级指针，因为只读不修改头指针。剩余名单按当前环顺序输出，如果剩余人数为 0，直接打印“轮船上无剩余人员”，不会访问空指针。

3.4 完整可运行版本与参数说明

把上面的函数按顺序拼起来，再加一个带输入校验的main，就是完整可运行版本。main里检查总人数、步长和剩余人数的范围，不合法直接返回；合法时调用ThrowPerson，再调用DisplayLinkList。编译命令可以用gcc joseph.c -o joseph，运行后按提示输入三组数字和每个人姓名。

int main(void) { int TotalCount, PersonCount, LeftTotal; LinkList L = NULL; printf("请输入总人数："); scanf("%d", &TotalCount); printf("请输入抛入大海时要数到的人数："); scanf("%d", &PersonCount); printf("请输入轮船安全需要剩余的人数："); scanf("%d", &LeftTotal); if (TotalCount <= 0 || PersonCount < 1 || LeftTotal < 0 || LeftTotal > TotalCount) { printf("输入不合法\n"); return 1; } ThrowPerson(&L, TotalCount, PersonCount, LeftTotal); DisplayLinkList(L); return 0; }

这段main的关键是输入校验和LinkList L = NULL初始化。LeftTotal == TotalCount时允许运行，循环不删除任何人，直接显示全部名单；LeftTotal == 0时会把链表删

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