如果你正在啃何钦铭、颜晖的《C语言程序设计第四版》刷到第八章指针的练习题时多半会被一道“报数”题卡上那么一会儿。题面看着特别像一个小学奥数游戏一群人围成一圈挨个报数报到某一个数的人出列然后下一个人重新从1开始继续循环直到剩下最后一个人。可等你真正动手写代码会发现这门“报数”其实就是数据结构里赫赫有名的约瑟夫环问题。而教材把它放在指针这一章意图很明确——考的不是你会不会算而是你能不能熟练使用指针去遍历、删除、回绕。这篇文章就把这道题彻底拆开先讲清楚为什么它放在指针章再给两套能直接跑通的实现——指针数组模拟法和循环链表法然后把我自己当年踩过的指针坑、边界条件和调试方法全部交代一遍最后聊聊当n和m变大之后这道题还能怎么玩。不管你是正在赶作业的学生还是想复习C指针的初学者照着我给的思路走写完这题你对指针的理解会上一个台阶。1. 报数问题到底在考什么从一个数学游戏到指针训练场1.1 你拿到的原始题面一般是这个样子的教材里的原题大致是这样的有n个人围成一圈按顺序编号1到n。从第1个人开始报数报到m的人退出圈子然后下一个人重新从1开始报数如此循环直到所有人都退出圈子。题目有时候让你输出每个人的出列顺序有时候只问最后剩下的是几号。这个游戏有两处关键的动作一是“在环里不停往前走”二是“把某人从环里摘掉”。把这两件事放到C语言里前一个动作天然对应指针的移动——让指针沿着数组或者链表节点往前走后一个动作对应两种处理思路——数组里的元素前移覆盖或者链表里的指针重连。所以这道题表面上是数学游戏实际上是考察“指针作为游标”的核心用法。1.2 为什么这道题偏偏放在指针这一章我见过不少人用纯数组下标硬写这道题也能写出来。但教材把它放进指针章不是为了让你们用下标硬扛而是希望你体会一件事当你需要把一个“当前位置”不停移动、并且还要修改这个位置上的数据时指针变量比固定下标灵活得多。你可以把指针理解成一个“会走路的索引”。数组下标是死的你要移动位置就得改变下标变量的值而指针本身就装着地址你直接对指针做加减运算、赋值、比较它就能在数组的各个元素之间游走。报数问题的核心逻辑是“当前位置不停前进前进到末尾还要回到开头”这恰好就是指针游走的经典场景。等你用指针写完这题再看第八章后面那些交换变量、字符串处理、函数指针的题目会发现很多操作的底层逻辑都是一样的操作地址而不是操作值。1.3 解题前必须先想清楚的三件事动手写代码之前有三件事我建议你先在纸上理清楚否则写出来的代码大概率改半天。第一“报数1”的位置在哪里。题目说从第几个人开始报数这个人的报数值是1不是m。我见过有人把起始位置直接当成报m的人结果全错。第二报到m的人出列之后下一轮从谁开始报1。注意是出列者的下一个人接着报1不是出列者自己。这意味着你处理完删除动作以后游标必须停在正确的下一个起点上。第三环怎么处理。数组是有边界的走到最后一个元素之后必须回到第一个链表如果建成循环链表天然没有边界但你要保证最后一个节点的next指针确实指回了头节点。这三件事对应到代码里就是指针的初始化位置、删除后的游标修正、以及边界回绕逻辑。每一件都值得单独说下面我分别用两种解法把它们落到实处。2. 先别急着上链表指针数组加下标回绕的直白解法很多人的第一反应是用链表因为“删除人”这个操作在链表里很自然。但我想先说数组版本原因有两个一是数组版代码量小逻辑直白适合先建立对报数流程的直觉二是它能帮你理解指针和数组之间的等价关系——数组名就是首元素地址指针加减就是移动下标这两件事其实是同一件事的两副面孔。2.1 用指针指向数组元素模拟报数思路是这样的开一个长度为n的数组第i个元素存编号i1。再定义一个指向int的指针cur让它指向“当前报数1的人”所在的位置。每次数到m就是让cur连续向后移动m-1次每移动一次对应报数值加1。数组走到末尾之后要用取模回绕的办法让它回到头部。这里有个实现上的细节因为数组是连续存储的指针每次加1就能移动到下一个元素但当cur已经到达当前有效数组的最后一个元素时cur1就出界了。所以每移动一次都要检查“cur是否越过了当前有效区的末尾”如果越过了就让它重新指向数组首元素。2.2 出列后的“人”怎么处理前移法数组不像链表可以随便摘节点数组里删除一个元素最直接的做法就是把后面的所有元素依次向前挪一位然后让剩余人数减1。这个过程也叫“覆盖删除”。它有一个副作用删除之后有效区的最后一个位置会残留一个旧值但你不用管它因为剩余人数已经减1后面的逻辑都只会在有效区内操作。举个例子数组是1、2、3、4、5m3第一轮cur停在3的位置输出3之后把4移到3的位置再把5移到4的位置剩余人数变成4有效数据变成1、2、4、5。这时cur还停留在原3的位置也就是新4的位置下一轮正好从这里开始报1逻辑完美衔接。唯一要小心的是如果删除的是当前有效区的最后一个元素比如上例里如果出列的是5那么前移循环不用执行剩余人数减1之后cur就站在了有效区末尾的下一个位置这一轮结束后必须让cur回绕到数组首元素。2.3 这段代码里的指针边界要这样守完整代码我贴在下面你直接抄就能跑#include stdio.h #include stdlib.h int main(void) { int n, s, m; printf(请输入总人数n、起始位置s、报数上限m); scanf(%d%d%d, n, s, m); if (n 0 || s 1 || s n || m 1) { printf(输入不合法\n); free(NULL); /* 占位实际不需要 */ return 1; } int *persons (int *)malloc(n * sizeof(int)); if (persons NULL) { printf(内存分配失败\n); return 1; } for (int i 0; i n; i) { persons[i] i 1; } int *base persons; // 数组首地址用来做回绕比较 int *cur persons s - 1; // 第s个人报数1 int remain n; // 当前有效人数 printf(出列顺序); while (remain 0) { int count 1; while (count m) { cur; if (cur - base remain) { cur base; } count; } printf(%d , *cur); // 前移覆盖删除cur指向的元素 for (int *p cur; p base remain - 1; p) { *p *(p 1); } remain--; // 如果cur超出了有效区末尾回绕到首元素 if (remain 0 cur base remain) { cur base; } } printf(\n); free(persons); return 0; }这段代码里最值得讲的是第30行cur - base remain。这里用的是指针减法两个同数组内的指针相减得到的是它们之间的元素个数比如cur指向persons[3]base指向persons[0]那么cur-base的值就是3。这个值一旦大于等于剩余人数remain就说明cur已经站在有效区之外了必须回绕。注意我每次只让cur走一步所以最多越界一个位置直接回绕到base是安全的。用n5、m3、s1验证一下输出应该是3 1 5 2 4和手推的约瑟夫环结果一致。这说明前移法和真实出列过程是等价的。3. 循环链表方案指针真正的用武之地数组解法能跑通但它有个天生的短板每次删除都要把后面的一堆元素往前挪最坏情况下时间复杂度是O(n)。如果n是10个人当然无所谓可如果n是10万数组解法就会明显慢下来。这时候就需要循环链表上场了。链表删除一个节点只需要改两条指针完全不涉及数据移动这才是指针最擅长的事。3.1 节点结构设计与环形链表的构建先定义一个最简单的单向链表节点typedef struct Node { int data; struct Node *next; } Node;每个节点存一个人的编号next指向下一个人。要建成“围成一圈”的效果只需要在创建完所有节点之后把最后一个节点的next指回头节点这就形成了一条循环链表。创建循环链表的代码我这里写成一个函数方便后面复用Node *create_circle(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *tmp (Node *)malloc(sizeof(Node)); if (tmp NULL) { printf(内存分配失败\n); exit(1); } tmp-data i; tmp-next NULL; if (head NULL) { head tail tmp; } else { tail-next tmp; tail tmp; } } tail-next head; // 首尾相连形成环 return head; }这里有个新手容易忽略的细节创建过程里我同时维护了head和tailhead一直指向第一个节点tail随着循环不断更新。最后一行tail-next head是整段代码的灵魂少了它这只是一条普通单链表报数走到末尾就不知道怎么回去了。3.2 前驱指针pre的核心作用删除节点必须先找到它链表的删除操作有个老生常谈的规则要删除节点cur必须找到它的前驱节点pre然后执行pre-next cur-next。单链表只能从前往后走所以你没法在“到达cur的同时”拿到它的前驱。报数问题的难点就在这里你不仅要知道“谁报到了m”还得知道“谁站在他的前面”。我见过很多同学的写法是先用一个指针cur数到报m的人然后再用一个循环从头找他的前驱。这样也能做但每删除一个人就要从头遍历一次不优雅。更好的做法是同时维护两个指针pre始终是cur的前驱cur和pre一起移动。初始化时先让pre指向链表的最后一个节点也就是头节点的前驱cur指向头节点。这样cur就是报数1的人pre站在cur身后。之后每报一个数pre和cur同时向后走一步。走到m次之后cur就是要出列的人pre正好是他的前驱直接删除。3.3 完整可运行代码与出列顺序验证完整代码如下#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *create_circle(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *tmp (Node *)malloc(sizeof(Node)); if (tmp NULL) { printf(内存分配失败\n); exit(1); } tmp-data i; tmp-next NULL; if (head NULL) { head tail tmp; } else { tail-next tmp; tail tmp; } } tail-next head; return head; } int main(void) { int n, s, m; printf(请输入总人数n、起始位置s、报数上限m); scanf(%d%d%d, n, s, m); if (n 0 || s 1 || s n || m 1) { printf(输入不合法\n); return 1; } Node *head create_circle(n); // 先让pre指向最后一个节点即head的前驱 Node *pre head; while (pre-next ! head) { pre pre-next; } // 让pre从头节点开始走s-1步使pre-next成为第s个人 for (int i 1; i s; i) { pre pre-next; } Node *cur pre-next; // 第s个人报数1 int remain n; printf(出列顺序); while (remain 0) { // cur从报数1走到报数m一共走m-1步 for (int i 1; i m; i) { pre pre-next; cur cur-next; } printf(%d , cur-data); pre-next cur-next; // 摘除cur free(cur); remain--; if (remain 0) { cur pre-next; // 下一轮从出列者的下一位开始报1 } } printf(\n); // 理论上这里应该释放剩余节点程序结束前交给操作系统即可 return 0; }这个版本里m1的情况也能正确处理。因为m1时内层循环一次都不执行cur就是当前报数1的人直接出列然后cur移动到pre-next也就是原来的下一个人。这就是前驱指针方案相比某些特判写法的优势不用为m1开小灶。我用n5、s1、m3验证过输出同样是3 1 5 2 4。你可以把这个结果和数组版输出对比两种解法结论完全一致说明核心逻辑没有偏差。4. 指针陷阱自查清单这些坑我当年每个都踩过报数题写起来不难错起来也是千奇百怪。我把自己和周围人在这道题上踩过的坑归拢成一份自查清单你写完代码对着过一遍能省下不少调试时间。4.1 指针自增越界与“回绕”的时机数组版里最容易翻车的就是cur之后忘了检查是否越界。有人把回绕写成if (cur base n) cur base;用初始总人数n做判断。这在删除还没有发生时是对的可一旦有人出列、有效区缩短n就不再是“当前有效人数”。正确的判断要用remain也就是当前剩余人数。还有一个隐蔽问题回绕判断的时机。我推荐“每走一步就检查一次”而不是“走完m-1步再统一检查”。因为如果中途越界下一步cur会在错误的位置上继续走整个游标就乱了。每步检查虽然代码看起来啰嗦但逻辑最稳。4.2 链表删除中的断链与野指针链表版最常见的翻车现场是找到报m的节点后直接free(cur)忘了改它前驱的next。这样做的后果是链表里留下了一个悬空的地址下次遍历走到这里就会访问非法内存程序大概率直接崩溃。正确顺序永远是先pre-next cur-next把环接上再free(cur)。顺序反了的话cur-next虽然还存着下一个节点的地址但pre的指向已经没法改了。这个顺序问题我在初学阶段至少犯过三次每次都是调了半天才发现是free写早了。另外提醒一句链表删到只剩最后一个节点时cur-next就是它自己pre-next cur-next会让pre的next指向cur自己其实是指向已被释放的地址但这时的环已经没用了程序马上退出所以不会出问题。如果你打算把链表保留下来继续用就需要在释放前用临时变量保存头节点地址最后再统一释放或者干脆用双向链表。4.3 free的位置内存泄漏与重复释放内存泄漏在这道题里不太容易被发现因为程序跑完就结束了操作系统会把进程的内存回收。但如果你是在一个长时间运行的模块里调用这段逻辑每次都malloc却不free内存会缓慢增长这就是泄漏。链表版里每次删除都用free释放了出列节点这部分是对的。容易漏的是头节点本身循环结束后链表已经为空逻辑上没问题。但如果你在循环外又写了一句free(head)此时head已经是悬垂指针再次free就是重复释放行为未定义可能直接报错。我的建议是考试和作业场景下循环删除时每个节点都free程序结束前不必额外释放交给操作系统兜底就行。4.4 数组指针与指针数组别搞混这道题写久了很容易顺手写错一个声明int *persons[...]。这是指针数组它的每个元素都是一个指针而我们要的是int *persons它才是指向数组首元素的指针。两者只差一个括号或者声明的写法含义天差地别。再对照着复习一下第八章里容易混的一对int (*p)[n]是数组指针指向一个长度为n的int数组int *p[n]是指针数组包含n个int指针。写报数题时如果用数组指针去遍历单个元素会发现在p1之后跳过了整整n个int整个游标逻辑全错。这个坑不是报数题专属但报数题由于要频繁移动指针特别容易触发。5. 边界条件与调试手段报数题挂在哪儿一道题能不能拿满分很多时候不是看主流程写得对不对而是看边界条件处理得稳不稳。报数题最常挂的输入组合我列在下面。5.1 三个最容易翻车的输入组合第一个是m1。这时候每轮报数1的人直接出列出列顺序就是起始位置开始的自然顺序s, s1, ..., n, 1, 2, ..., s-1。数组版和链表版按照我上面的写法都能正确处理但如果你用的是“先走m-1步再删除”的写法m1时走0步相当于删除当前节点逻辑本身没问题怕的是有人特判写成了“m1时单独处理”一旦特判写错整个程序就崩。能不用特判就别用特判。第二个是s不等于1。很多人写完代码只测s1代码跑通了就交。可起始位置一变游标的初始化就容易出错。链表版里我先把pre定位到最后一个节点再从头走s-1步让pre-next成为第s个人这个步骤每一轮都要保证pre是cur的前驱。你测试时至少把s换成3、n换成6跑一次。第三个是n1。只有一个玩家时无论m是多少唯一的人直接出列。数组版中baseremain-1和base相等前移循环不会执行链表版中cur-next就是cur自己pre和cur都指向同一个节点。这个输入一旦没想清楚很容易在删除环节写出访问空指针的代码。我把这几个边界整理成一张表方便你自测输入期望行为易错点n1, m任意输出1删除唯一节点时不要访问空指针m1按起始位置顺序出列不要误写特判导致死循环s1从第s个人开始报1游标初始化偏移容易算错mn指针或游标需要绕圈多轮回绕判断要用remain而非n所有人出列后链表为空程序正常结束不要重复free头节点5.2 用printf插桩观察指针走过的路调试指针问题我强烈建议在关键位置加printf把指针当前指向的元素和指针值打出来。比如数组版里在cur之后打印一行printf(当前cur指向第%d个位置值为%dremain%d\n, (int)(cur - base), *cur, remain);链表版里可以在内层循环结束、删除之前打印printf(即将出列%d前驱pre-data%d\n, cur-data, pre-data);这样你就能直观看到cur是不是按预期移动、pre和cur是否始终保持前后关系。报数题最常见的死循环原因往往是删除之后cur没有正确更新导致下一轮又回到了已删除的位置。插桩之后这类问题一眼就能定位。调试完记得把printf删掉或者用注释包起来。我见过有人交作业时把调试输出留在答题区被扣了格式分很亏。5.3 与教材答案不同的变体怎么应对教材后面的习题里报数题有时会改几个条件最常见的变体有三种一是“报到m的人出列后从出列者自己重新开始报1”这相比我们上面的规则差了一个人的偏移你只需要把出列后的cur从pre-next改成pre-next-next二是“最后一个人和出列顺序同时输出”多数题目只要求最后一个幸存者你可以用数学递推直接算下一节我会讲三是“报数方向每轮反向”这种用单向链表做会很痛苦建议改用双向循环链表删除和反向移动都方便。我的建议是做题前先大声把题面读一遍尤其注意“从谁开始报1”和“出列后从哪里继续报”这两个关键动作。它们差之毫厘结果谬以千里。6. 升级思考当n和m变得很大时如果你只想通过这道习题前面两套代码已经够用了。但如果你愿意多想一层报数问题的本质是什么当n和m变大之后这两套解法还扛得住吗6.1 两种解法的复杂度对比数组版的删除需要前移每次删除最坏情况移动O(n)个元素总复杂度O(n^2)在n等于十万的量级下会明显变慢。链表版的删除只需要改指针每次删除O(1)但找一个报m的人需要走m步总复杂度O(n·m)。所以如果m很小链表版很快如果m很大链表版会在环上绕很多圈子。解法每次找人的代价每次删除的代价总复杂度数组前移O(m)O(n)O(n·m n^2)循环链表O(m)O(1)O(n·m)数组标记O(m·已出列数)O(1)O(n·m)第三种“数组标记”是我没细讲的方案开一个bool数组记录每人是否出列报数时跳过已出列的人。它在“找下一个人”时要多走很多步但删除本身不用移动数据适合写起来图省事、n又不大的场景。三种方案没有绝对优劣关键看题目给的数据范围。6.2 约瑟夫环的递推公式与“只要最后一人”的场景如果题目只问“最后剩下的是谁”不要求输出出列顺序那就有一个经典数学结论可以秒杀模拟。从0开始编号令J(k)表示k个人的环最后幸存者的编号则递推式为J(1) 0J(k) (J(k-1) m) % k算出J(n)后加1就得到1到n编号下的幸存者编号。这个公式的核心逻辑是每淘汰一个人环的规模从k变成k-1并且下一轮的起点整体后移了m位反向推算时只要把k-1规模下的幸存者位置向后平移m再对k取模就能还原出它在k规模环里的位置。对应代码只有几行int survivor(int n, int m) { int j 0; // 只有1个人时的幸存者编号0开头 for (int k 2; k n; k) { j (j m) % k; } return j 1; // 转回1开头编号 }这其实就是典型的“递推代替模拟”O(n)就能出结果。如果起始位置不是第1个人而是第s个人可以先按s1算出结果再做一个编号旋转假设1到n的普通人编号是1~n从s开始报1等价于把数组左旋s-1位幸存者编号也就跟着平移最后换算回去即可。6.3 从这道题延伸出去环形缓冲、游戏匹配等真实应用报数问题不只是习题。环形链表本身就是一个很有用的数据结构操作系统里的环形缓冲区、游戏中的回合制匹配、消息队列的循环消费底层都是“走到末尾回到开头”的游标思想。你在这道题里练熟的指针回绕、前驱指针维护、删除节点后重置游标将来写更复杂的C程序时都会反复用到。特别是“维护一个正在动态变化的环”这个场景比如在线游戏的房间循环踢人、任务队列的轮询调度报数题里的循环链表方案几乎可以原封不动地迁移过去。所以别只把它当成一道为了交差的作业多花半小时把两套解法吃透第八章的其他指针题你会突然觉得顺畅很多。我个人在实际操作中的体会是这道题最好的学习方法不是盯着答案看而是把数组版和链表版各写一遍然后故意把m1、sn、n1这些边界输入一个一个喂进去观察程序是在哪一步崩掉的。崩一次你对指针的理解就深一层。等你哪天能不看代码直接在白纸上画出指针每一步指向哪个节点这题才算真正过关。