简介这份资源围绕经典的约瑟夫死亡游戏展开面向正在学习C语言数据结构与算法的初学者及课程设计者帮助理解循环链表在实际问题中的建模与求解过程。压缩包内仅含1个docx文档约18KB以文字形式完整呈现设计思路、算法逻辑与代码实现便于边读边对照练习。内容从元素类型与结点类型的定义入手逐步讲解带头结点循环链表的创建、按指定间隔删除结点、重新设置头指针以及循环淘汰直至剩余指定人数的完整流程并给出CreateLinkList、DeleteLinkList、DieLinkList、DisplayLinkList等函数的实现细节与主函数调用示例。读者可借此掌握循环链表的指针操作、边界处理与内存释放方法理解约瑟夫问题的递推与模拟思路并在此基础上自行扩展姓名存储、剩余人数输出等功能。目前已有3143人学习适合作为数据结构实验、课程设计或算法入门的参考材料。1. 约瑟夫死亡游戏为什么一个报数删人的循环链表能让人卡三天约瑟夫死亡游戏这个名字听起来像恐怖片本质却是一道被无数教材讲烂、又被无数人写翻车的经典数据结构题n 个人围成一圈从某处开始报数每报到第 m 个人就把他扔进大海然后从下一个人重新报数直到剩下 k 个人为止。很多人第一次写脑子里想的是数组模拟一下不就行了结果一上手就发现——删掉一个人之后下标怎么接、从谁开始数、什么时候停全是坑。真正让这道题值得深挖的地方不是约瑟夫这三个字而是它逼着你把循环链表这个结构从知道变成会用头结点怎么处理、尾指针怎么维护、删除后头指针指向谁每一步都在考验你对指针关系的理解。搞懂它等于把链表的增删查改一次性打通后面再遇到任何环形结构、轮询调度、令牌环之类的场景你脑子里会自动浮现出这套指针操作。这也是为什么它常年霸占 C 语言课程设计榜单——不是因为它难而是因为它把指针 结构体 动态内存三件事拧在了一起任何一个环节松了程序就崩给你看。2. 循环链表为什么头结点是临时工尾指针才是真主角2.1 从带头结点到无头结点的转身约瑟夫问题的核心数据结构是单向循环链表。普通单链表有个头结点它的 next 指向第一个真实元素好处是插入删除时不用特判空表和首元素两种情况。但约瑟夫游戏有个特殊需求报数是环形的数到末尾要自动回到开头。如果保留头结点那么回到开头就会撞上这个不存数据的空结点逻辑上要多绕一圈容易出错。所以这份代码走了一条更干净的路先带头结点建表建完立刻把头结点释放掉。看这段创建逻辑void CreateLinkList(LinkList L, int n) { LinkList r, p; int i; L (LinkList)malloc(sizeof(LNode)); // 先造一个头结点 L-next NULL; r L; // r 是尾指针初始指向头结点 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); p-next r-next; // 新结点 next 先接上 r 原来的后继 r-next p; // 尾结点指向新结点 r p; // r 后移永远指向最后一个 } r-next L-next; // 关键一步尾结点指回第一个真实结点成环 free(L); // 头结点是临时工用完就释放 L r-next; // L 重新指向第一个真实结点 }这里有个容易被忽略的细节p-next r-next;这一句在循环里其实是多余的因为每次r-next都是 NULL尾结点后面还没接东西但保留它体现了一种防御性写法——万一以后改成头插法或者中间插入这行代码就能保证新结点不会丢掉后面的链。真正决定成败的是最后三行r-next L-next让尾结点指回头部free(L)释放临时头结点L r-next把链表入口重新定位到第一个真实结点。顺序不能反如果先free(L)再取L-next就是访问已释放内存典型的 use-after-free程序可能当场崩也可能看起来正常但埋下隐患。2.2 尾指针 r 为什么必须一直跟着走很多人写链表喜欢只维护一个头指针插入时从头遍历到尾时间复杂度 O(n)。这份代码用了一个r尾指针每次插入都是 O(1)整体建表从 O(n²) 降到 O(n)。对于约瑟夫这种人数可能上百的场景这个优化不是炫技是实打实的效率差别。更重要的是r在成环那一步扮演了不可替代的角色。因为只有r知道最后一个结点是谁才能让它的 next 指回第一个结点。如果没有r你就得再遍历一遍找到尾结点代码多一层循环出错概率也翻倍。我一般会这么理解头指针负责从哪进尾指针负责从哪绕回来循环链表里两者缺一不可。2.3 结构体嵌套ElemType 和 LNode 为什么要分开代码里定义了两个结构体typedef struct ElemType { int position; // 位置编号 char name[8]; // 姓名最多 7 个字符 \0 } ElemType; typedef struct LNode { ElemType data; // 数据域类型是 ElemType struct LNode *next; // 指针域指向同类型结点 } LNode; typedef LNode * LinkList; // 链表类型就是结点指针把ElemType和LNode拆开是数据结构设计里很经典的一招数据归数据结构归结构。ElemType只关心存什么LNode只关心怎么串起来。好处是如果以后要把姓名换成学号、把 position 换成身份证号只需要改ElemType链表操作函数一行都不用动。这就是抽象的力量——虽然课程设计里看起来有点过度设计但养成这个习惯写大项目时能省下大量重构时间。char name[8]这个长度也值得说一句它意味着姓名最多 7 个汉字或 7 个英文字符中文 UTF-8 下每个字 3 字节实际能存 2 个汉字。如果输入超长scanf(%s)不会检查边界直接缓冲区溢出。这是这份代码的一个真实短板后面避坑章节会专门讲。3. 删除第 m 个结点指针重接的后悔药为什么必须提前吃3.1 删除逻辑拆解找前驱、存数据、重接、释放约瑟夫游戏每轮要做的事本质就是删除链表中第 PersonCount 个结点。看DeleteLinkList的实现void DeleteLinkList(LinkList L, int i, ElemType e) { LinkList p; p L; int j 1; while (j i - 1) { // 走到第 i-1 个结点要删结点的前驱 p p-next; j; } e p-next-data; // 先把要删的数据存下来 L p-next-next; // 头指针指向被删结点的后继 p-next p-next-next; // 前驱跳过被删结点 }这段代码只有 8 行但每一行都有讲究。while (j i - 1)让p停在被删结点的前驱上因为单链表删除必须知道前驱——你没法从当前结点往回走。e p-next-data是后悔药先把数据保存到引用参数e里后面free掉结点后数据还能用来打印谁被扔下海了。如果先free再取数据就是访问已释放内存输出可能是乱码也可能直接段错误。L p-next-next这一句是约瑟夫游戏特有的因为报数是环形的删完一个人后下一轮要从被删者的下一个人开始数所以头指针L必须跟着移动。普通链表删除不需要动头指针这里必须动否则下一轮会从错误的位置开始。3.2 为什么没有 free(q)一个隐藏的内存泄漏注意看代码里没有free被删结点。原文设计思路里写了定义临时指针 q存储要扔入大海人的地址 q p-next……free(q)但实际给出的代码里q和free(q)都不见了。这是一个真实存在的内存泄漏每删一个人那个结点的内存就永远收不回来。对于课程设计这种跑一次就退出的程序泄漏几十个结点无所谓操作系统会在进程结束时统一回收。但如果把这个逻辑放进长期运行的服务里比如一个轮询调度器跑几天内存就爆了。正确的写法应该是LinkList q p-next; // 先记住要删的结点 e q-data; // 存数据 L q-next; // 头指针后移 p-next q-next; // 前驱跳过 free(q); // 释放内存 q NULL; // 防止野指针多出来的q NULL是防御性编程习惯free之后指针还指向那块已释放的内存如果不置空后面误用就是 use-after-free。虽然这里q是局部变量函数返回就销毁了但养成这个习惯没坏处。3.3 报数循环LeftCount 和 LeftPerson 的命名陷阱主循环在DieLinkList里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); } }原文设计思路里写的是设置变量剩余人数 LeftPerson初始化 LeftPerson PersonCount但代码里实际用的是LeftCount TotalCount。原文这里写错了——剩余人数当然应该初始化为总人数初始化成报数阈值PersonCount逻辑上说不通。这种设计文档和代码不一致的情况在实际项目里很常见读代码时要以代码为准同时心里要清楚哪个是对的。循环条件是LeftCount LeftTotal每删一个人LeftCount--直到剩余人数等于安全人数LeftTotal就停。这个逻辑没问题但有个边界情况没处理如果LeftTotal TotalCount循环一次都不进直接输出全部人员这算合理如果LeftTotal 0就会无限删下去直到链表空掉然后崩溃。健壮的代码应该在入口处校验参数。4. 输出剩余人员循环链表的遍历为什么不能用 while(p ! NULL)4.1 环形遍历的终止条件删除结束后要把剩下的人打印出来。看DisplayLinkListvoid DisplayLinkList(LinkList L) { LinkList p; 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); } }普通单链表遍历用while (p ! NULL)因为尾结点的 next 是 NULL。但循环链表没有 NULL 结尾尾结点的 next 指回第一个结点所以终止条件必须改成p-next ! L——绕回起点就说明走完一圈了。这里有个细节第一个结点在循环外单独打印循环从第二个开始。为什么因为如果循环条件写成while (p ! L)然后先p p-next再打印逻辑也能对但代码会绕一点。当前写法更直观先处理起点再往后走直到回到起点。两种写法都对但当前这种更容易读懂。4.2 只剩一个人时的特殊情况如果LeftTotal 1链表里只剩一个结点此时这个结点的next指向它自己因为成环时尾结点指回头部只剩一个时头尾重合。DisplayLinkList先打印这个结点然后判断p-next ! L——此时p-next就是L自己条件为假循环不进入正好打印一个人。逻辑自洽。但如果LeftTotal 0所有人都被删光L会变成什么看DeleteLinkList最后一步L p-next-next当链表只剩一个结点时p-next是那个结点p-next-next是它自己自环所以L还指向那个结点但下一轮删除会出问题。实际上LeftTotal 0时循环会在删完最后一个人后停止但L指向的是一个已经被逻辑删除的结点DisplayLinkList会打印出一个不该存在的人。这是边界处理的漏洞实际使用中应该禁止LeftTotal 0或者在删除逻辑里加空表判断。4.3 内存释放程序退出前该不该手动 free整份代码从头到尾没有释放链表。程序结束时操作系统会回收所有内存所以课程设计里不 free 也能跑。但严格来说main返回前应该遍历链表把每个结点 free 掉。这不是洁癖而是习惯写任何 malloc 都要想好在哪里 free。如果这份代码被改造成一个函数库被别的程序反复调用不 free 就是实打实的内存泄漏。我一般会这么理解课程设计可以偷懒但脑子里要清楚哪里偷了懒、为什么可以偷、什么情况下不能偷。这个判断力比写不写 free本身更重要。5. 避坑与排查这份代码跑起来会遇到的 5 个真实问题5.1 输入姓名超过 7 个字符导致程序崩溃或输出乱码现象输入一个 10 个字符的姓名程序可能正常跑完但打印出来的姓名是乱码或者直接段错误。原因char name[8]只留了 8 字节scanf(%s, p-data.name)不检查长度超长输入会覆盖相邻内存。ElemType里position是 int4 字节name是 8 字节总共 12 字节但编译器可能做内存对齐。超长写入会踩到next指针把链表结构破坏掉。解决把name改大比如char name[32]或者用scanf(%7s, p-data.name)限制读入长度7 是数组长度减 1留给\0。更稳妥的是用fgets读整行再手动去掉换行符。5.2 PersonCount 输入 1 时删除逻辑走偏现象报数阈值输入 1期望每轮删当前第一个人但实际删除的位置不对或者程序卡死。原因DeleteLinkList里while (j i - 1)当i 1时条件是j 0初始j 1循环一次都不进p停在L上。然后e p-next-data取的是第二个人的数据L p-next-next跳过了第二个人——删错了对象。正确逻辑应该是删第一个人即L自己。解决PersonCount 1是合法输入虽然游戏里少见需要在DeleteLinkList开头特判如果i 1直接删L指向的结点更新L L-next再调整前驱指针。或者干脆在main里限制PersonCount 2。5.3 LeftTotal 大于等于 TotalCount 时输出异常现象安全人数设成比总人数还大程序不删人直接输出但输出格式或内容不对。原因while (LeftCount LeftTotal)条件为假循环不执行L还是完整的循环链表DisplayLinkList能正常打印所有人。这本身不算 bug但用户可能期望输入非法的提示。解决在main里加校验LeftTotal必须在[1, TotalCount]范围内否则提示重新输入。这是用户体验问题不是逻辑错误但好的程序应该处理。5.4 删除后头指针 L 更新错误导致死循环现象程序删了几个人之后卡住不动CPU 占用飙升。原因L p-next-next这一句如果p-next是 NULL链表断裂就会解引用空指针崩溃如果链表成环但L更新到了错误位置下一轮DeleteLinkList可能永远走不到i-1while循环无限转。解决在DeleteLinkList里加断言或检查确保p-next不为 NULL删除后打印当前L的 position 用于调试确认头指针指向正确。更根本的是理解删除后 L 必须指向被删者的下一个这是约瑟夫游戏的核心不变式。5.5 编译时报 LinkList L 语法错误现象用某些编译器尤其是纯 C 编译器如 gcc 默认模式编译报expected ;, , or ) before token。原因LinkList L是 C 的引用语法标准 C 不支持。这份代码虽然看起来像 C用了printf、malloc但引用参数是 C 特性。用.c后缀编译会失败。解决把文件后缀改成.cpp用 C 编译器编译或者把引用改成指针的指针LinkList *L函数内用*L访问调用时传L。两种方式都能跑但改指针方式改动量大建议直接当 C 编译。6. 从能跑到写对约瑟夫问题真正教给你的设计取舍写完这份代码回头看约瑟夫死亡游戏真正有价值的地方不是报数删人这个游戏规则而是它逼你在几个关键节点做取舍而这些取舍在真实工程里天天遇到。第一个取舍头结点要不要留。留着头结点插入删除逻辑统一但环形遍历时要多绕一层不留头结点遍历干净但建表时要多一步释放头结点 重定位 L。这份代码选了后者代价是free(L); L r-next;这两行必须写对顺序写反就是 use-after-free。真实项目里也一样抽象层能简化上层逻辑但抽象本身的维护成本要算清楚。我见过太多项目为了统一接口加了一层又一层包装最后调试时根本不知道数据在哪一层被改了。第二个取舍尾指针要不要维护。维护r让插入变 O(1)但每次插入后都要记得r p漏一次就断链。不维护r每次从头遍历代码简单但慢。这份代码选了维护因为约瑟夫问题里建表是高频操作。这对应到工程里就是缓存 vs 实时计算的经典权衡缓存快但有一致性风险实时算慢但不会错。选哪个取决于你的读写比例和容错要求。第三个取舍删除时要不要 free。课程设计里不 free 也能跑因为进程退出会回收。但这份代码的设计思路里明明写了free(q)实际代码却漏了——这种文档和实现不一致在真实项目里是 bug 的重灾区。我的血泪经验是任何 malloc 都要在同一个函数或同一个模块里有对应的 free哪怕暂时用不上也要写个注释说明为什么先不释放。否则三个月后接手的人可能是你自己根本不知道这是故意泄漏还是忘了写。第四个取舍边界条件怎么处理。PersonCount 1、LeftTotal 0、LeftTotal TotalCount、姓名超长——这些边界这份代码基本都没处理。课程设计里老师可能只测正常输入但真实系统里用户什么都敢输。我一般会这么理解核心逻辑写对只是及格边界处理才是区分能跑和可靠的分水岭。写完主流程后强制自己列一张边界表每个参数取最小值、最大值、非法值各跑一遍这个习惯能挡掉 80% 的线上事故。如果要验证自己真的懂了我建议做三件事第一把DeleteLinkList改成带free的版本用 valgrind 跑一遍确认无泄漏第二把PersonCount 1的 bug 修掉加测试用例覆盖第三把链表改成数组模拟对比两种实现的时间复杂度和代码复杂度亲手感受一下数据结构选择如何影响代码形态。做完这三步约瑟夫问题就不再是一道题而变成你脑子里一个可复用的环形删除模式。从那以后我每次写链表相关的代码都会先在纸上画三个结点、标好指针、模拟一遍删除和插入确认指针重接顺序无误再动手敲键盘。这个习惯帮我省下了无数个调试到凌晨的夜晚。希望帮到你。本文还有配套的精品资源点击获取