C 训练营教程

主题

Lesson 33: 循环链表与约瑟夫问题 ​

练习任务 ​

难度：中-难

实现循环链表的核心操作，并用它求解经典的约瑟夫环问题：

  1. clist_insert(cur, val) — 在 cur 节点之后插入新节点 val。如果是第一个节点（cur == NULL），新节点形成自环（item->next = item），返回新节点作为 cursor。
  2. clist_delete(item) — 删除 item 节点，返回其后继节点。如果是唯一节点（item->next == item），释放后返回 NULL。

N 个人围成一圈，从 1 开始报数，每报到 K 的人出列，输出淘汰顺序。make_node 函数已提供。

本课共有 2 组测试用例：

输入 "10 3"  → 输出 "3 6 9 2 7 1 8 5 10 4"
输入 "5 2"   → 输出 "2 4 1 5 3"

提示：循环链表与单链表的唯一区别是——尾节点的 next 指向头节点而非 NULL。这一差别引发了四个关键变化：自环初始化、do-while 遍历、prev->next != item 查找前驱、唯一节点特判。理解这些变化的根因，你就掌握了循环链表的全部。

核心知识点 ​

  • 循环链表与单链表的本质区别 — 尾节点 next 指向头节点，形成闭环，没有 NULL 终点
  • 自环初始化 — item->next = item 是循环链表的最小有效状态，绝不能用 NULL
  • do-while 遍历 — 循环链表必须用 do { ... } while (p != cur) 而非 while，否则起点被跳过
  • 前驱查找 — 使用 prev->next != item 而非 prev != item，因为循环链表没有 NULL 终点
  • 唯一节点特判 — item->next == item 时直接 free 返回 NULL，否则找前驱时死循环
  • cursor 游标模式 — 维护"当前位置"指针，每次操作后更新，方便下一次操作
  • 数据结构选型 — 数组标记、数组移位、循环链表三种方案在删除复杂度、空间、建模直观性上的差异
  • 约瑟夫环递推公式 — f(N) = (f(N-1) + K) % N，O(N) 时间 O(1) 空间求幸存者
  • K 取模优化 — 每轮 K %= 剩余人数减少无效绕圈

代码框架 ​

33_circular_josephus.c
c
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

/* 创建值为 val 的新节点（已实现） */
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val;
    p->next = NULL;
    return p;
}

/* 循环链表插入：首节点自环，后续节点插在 cur 之后，返回新节点（作为新 cursor） */
struct node *clist_insert(struct node *cur, int val)
{
    // 创建新节点 p = make_node(val)

    // 如果是第一个节点（cur == NULL）：p->next = p（自环）

    // 否则：插在 cur 之后
    //   p->next = cur->next;
    //   cur->next = p;

    // 返回 p（新节点成为新的 cursor）
    // 在这里实现 clist_insert
}

/* 循环链表删除：删除 item，返回后继节点（淘汰后下一轮从这里开始） */
struct node *clist_delete(struct node *item)
{
    // 如果 item 为 NULL，返回 NULL

    // 如果是唯一节点（item->next == item）
    //   free(item); return NULL;

    // 找到 item 的前驱节点
    //   struct node *prev = item;
    //   while (prev->next != item)  ← 注意条件！不是 prev != item
    //       prev = prev->next;

    // 跳过 item: prev->next = item->next;
    // 保存后继: struct node *next = item->next;
    // 释放: free(item);
    // 返回后继
    // 在这里实现 clist_delete
}

int main(void)
{
    int N, K;
    char line[64];
    fgets(line, sizeof(line), stdin);
    sscanf(line, "%d %d", &N, &K);

    // 构建循环链表 1 → 2 → ... → N → 回到 1
    struct node *cursor = NULL;
    for (int i = 1; i <= N; i++)
        cursor = clist_insert(cursor, i);
    // 移到第一个节点作为起点
    cursor = cursor->next;

    // 约瑟夫环淘汰过程：
    // while (cursor != NULL) {
    //     走 K-1 步（当前站的人已经算 1）
    //     打印被淘汰者的 data
    //     删除节点，cursor 指向后继
    // }
    // 在这里完成 main 函数

    printf("\n");
    return 0;
}

阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：第一个节点如何形成自环？如何正确找到被删节点的前驱？while 遍历和 do-while 遍历的区别是什么？

TIP

先不要往下翻看参考解答。尝试理解循环链表的三个关键操作——自环初始化、前驱查找、唯一节点删除。如果卡住了，回头想想循环链表"没有 NULL"这个根本性质对代码的每个判断条件产生了什么影响。

深度讲解 ​

1. 循环链表 vs 单链表——唯一的区别，深远的影响 ​

1.1 一条语句的差异，整个使用范式的改变 ​

循环链表与单链表在结构定义上完全相同（都是 data + next 指针），区别只在于最后一个节点的 next 指向哪里：

单链表:    [1] → [2] → [3] → NULL    (有终点，next==NULL 标志结束)
循环链表:  [1] → [2] → [3]            (闭合环，无 NULL)
            ↑              ↓
            └──────────────┘

这一条语句的差异——尾节点 next 从 NULL 改为指向头节点——引发了四个关键行为变化：

方面单链表循环链表
终止条件p == NULLp == cur（回到起点）
遍历方式while (p)必须 do { ... } while (p != cur)
空链表head == NULLcursor == NULL
首节点初始化head 直接指向自环 item->next = item
查找前驱while (p->next != target)（遇到 NULL 停止）while (prev->next != item)（无 NULL！）

理解这四条变化，就理解了循环链表的全部。下面逐一深入分析。

1.2 自环——循环链表的最小有效状态 ​

当插入第一个节点时，它既没有前驱也没有后继——唯一的合法做法是让它指向自己：

self_loop.c
c
// 第一个节点（cur == NULL）
struct node *p = make_node(val);
p->next = p;        // 关键！指向自己，形成"自环"
return p;
自环在内存中的样子:

        ┌─────────────┐
        │ struct node  │
        │  data = 1    │
        │  next ───────┼───┐
        └─────────────┘   │
              ↑           │
              └───────────┘
         (next 指向自己)

为什么不能用 p->next = NULL？

如果第一个节点的 next 设为 NULL，循环链表就不再"循环"了：

  • 遍历时 do { p = p->next; } while (p != cur) 会因遇到 NULL 而段错误
  • 删除操作找前驱时，prev->next != item 会因 prev 走到 NULL 而崩溃
  • 自环是循环链表的最小有效状态——任何循环链表都必须从自环开始构建

IMPORTANT

自环 item->next = item 不是"特殊情况"，它是循环链表的基础状态。就像一个空集是集合论的起点一样，自环是所有循环链表操作的前提。如果这里写错，后续一切都会崩溃。

1.3 遍历必用 do-while——while 为何漏掉起点 ​

在非空循环链表中，任何节点开始遍历，起点和比较目标相同:

do_while_vs_while.c
c
struct node *p = cursor;

// ❌ 错误：while 先判断再执行
while (p != cursor) {       // 首次判断 p == cursor 为假 → 循环体从不执行！
    process(p);
    p = p->next;
}
// 后果：cursor 指向的节点（起点）被跳过

// ✅ 正确：do-while 先执行再判断
do {
    process(p);             // 先处理 cursor 点 ✓
    p = p->next;
} while (p != cursor);      // 然后判断是否回到起点
do-while 的执行时序:

  时刻 1: process(p)          ← 起点首次被处理 ✓
  时刻 2: p = p->next          ← 移到下一个节点
  时刻 3: p != cursor ?        ← 判断是否绕完一圈

while 的执行时序:

  时刻 1: p != cursor ?        ← 起点时 p==cursor → false! 循环终止 ✗
          起点从未被处理！

根因：循环链表节点的终止条件 p == cur 在起点处就为真，while 先判后执行意味着循环体零次执行；do-while 先执行后判意味着至少执行一次。这不是经验法则，是逻辑必然。

1.4 前驱查找——为什么是 prev->next != item？ ​

在单链表中，查找前驱通常写为：

c
struct node *prev = head;
while (prev != NULL && prev->next != target)
    prev = prev->next;

注意这里用了 prev != NULL 作为安全网——当 target 不在链表中时，prev 最终走到 NULL 停止。

但在循环链表中有 NULL**：

find_prev.c
c
// ❌ 错误：prev != item 在循环链表中是恒真的！
struct node *prev = item;
while (prev != item) {          // prev 从 item 出发，prev!=item 为假
    prev = prev->next;          // 循环体从不会执行！
}
// 更糟：如果 prev 并非 item 自身开始，prev 会绕圈直到回到 item，死循环

// ✅ 正确：检查 next 指针是否指向 item
struct node *prev = item;
while (prev->next != item) {    // 找「next 指向 item」的那个节点
    prev = prev->next;
}
查找 item=[3] 的前驱:

  [1] → [2] → [3] → [4] → [5] → [1] → ...
          ↑
         prev 从这里出发：

  step 1: prev->next = [3] → prev->next == item? [3] == [3] ✓ 找到！
           prev([2]) 就是 item([3]) 的前驱

原理：在循环链表中，「前驱」就是「唯一一个 next 指向 item 的节点」
     prev->next == item 等价于「prev 后面是 item」

为什么 prev != item 不行？ 在循环链表中，prev 从 item 出发时，prev != item始就是假，循环体零次执行。即使从其他位置出发，绕完一圈回到 item后条件才变假——但此时prev又回到了item`，不是前驱。

1.5 唯一节点——必须特判的边界 ​

singleton_delete.c
c
// 唯一节点：item->next == item
if (item->next == item) {
    free(item);
    return NULL;
}

为什么必须特判？ 如果直接走通用删除流程——找前驱 while (prev->next != item)一节点上，prev->next 永远等于 item（因为唯一的节点指向自己），条件永远为假，循环永远不停止。

唯一节点的自环:
        ┌──────┐
        │ [1]  │──┐
        └──────┘  │
           ↑      │
           └──────┘
  
  prev = [1], prev->next = [1] → prev->next == item(=[1])? → true！
  条件为真，循环永不进入 → 无法找到前驱 → 死锁

因此唯一节点必须首先判、单独处理——这是循环链表删除中"最少代码但最容易忘记"的一条。

2. 构建过程完整跟踪 ​

从空链表开始，逐步构建 1→2→3→4→5 的循环链表：

构建过程（每次 clist_insert 返回新节点作为 cursor）：

step 1: cursor = clist_insert(NULL, 1)
  首个节点, 自环: [1]↺, cursor → [1]

step 2: cursor = clist_insert(cursor, 2)
  在 [1] 后插入 2: [1] → [2] → [1] → ..., cursor → [2]

step 3: cursor = clist_insert(cursor, 3)
  在 [2] 后插入 3: [1] → [2] → [3] → [1] → ..., cursor → [3]

step 4: cursor = clist_insert(cursor, 4)
  在 [3] 后插入 4: [1] → [2] → [3] → [4] → [1] → ..., cursor → [4]

step 5: cursor = clist_insert(cursor, 5)
  在 [4] 后插入 5: [1] → [2] → [3] → [4] → [5] → [1] → ..., cursor → [5]

curso後后插入的 [5]。
要访问第一个节点: cursor = cursor->next → 指向 [1] ✓

为什么构建完要 cursor = cursor->next？ 因为 cursor 始终指向最后插入的节点（即 clist_insert 的返回值），而约瑟夫环要求从 1 开始报数。cursor->next 恰好指向链表中最早插入的节点（1）。

3. 约瑟夫环完整逐轮跟踪：N=5, K=2 ​

构建完: cursor → [5], cursor = cursor->next → [1] (移到起点)

════════════════════════════════════════════════════════════
轮 1:
════════════════════════════════════════════════════════════
从 [1] 走 K-1 = 1 步: cursor = cursor->next → [2]
淘汰 [2]！输出 "2 "
删除 cursor(=[2]): 前驱 [1], [1]->next = [3], free([2])
cursor = [3]  (被删节点的后继)
链表: [1] → [3] → [4] → [5] → [1] → ...

════════════════════════════════════════════════════════════
轮 2:
════════════════════════════════════════════════════════════
从 [3] 走 1 步: cursor → [4]
淘汰 [4]！输出 "4 "
删除 [4]: 前驱 [3], [3]->next = [5], free([4])
cursor = [5]
链表: [1] → [3] → [5] → [1] → ...

════════════════════════════════════════════════════════════
轮 3:
════════════════════════════════════════════════════════════
从 [5] 走 1 步: cursor → [1]
淘汰 [1]！输出 "1 "
删除 [1]: 前驱 [5], [5]->next = [3], free([1])
cursor = [3]
链表: [3] → [5] → [3] → ...

════════════════════════════════════════════════════════════
轮 4:
════════════════════════════════════════════════════════════
从 [3] 走 1 步: cursor → [5]
淘汰 [5]！输出 "5 "
删除 [5]: 前驱 [3], [3]->next = [3] (自环!), free([5])
cursor = [3]
链表: [3]↺ (唯一节点!)

════════════════════════════════════════════════════════════
轮 5:
════════════════════════════════════════════════════════════
从 [3] 走 1 步: cursor → [3] (自环上走一圈回到自己)
淘汰 [3]！输出 "3"
删除 [3]: item->next == item（唯一节点）→ free([3]), return NULL
cursor = NULL
链表: 空

最终输出: 2 4 1 5 3 ✓

4. 约瑟夫环的行走步数——为什么是 K-1 步？ ​

起点算第 1 个数:

  假设 K=3, 从 [1] 开始:
  
  "1!" [1]  - 第1声, 站着
  "2!" [2]  - 第2声, 站着
  "3!" [3]  - 第3声 → 淘汰! ← 走了 2 步 (K-1=2)

  所以代码中: for (int i = 1; i < K; i++) cursor = cursor->next;
  等价于:     走 K-1 步

直觉在某个节点上，这个位置已经算"第 1 声"了。要到达第 K 声的位置，只需要再走 K-1 步。

5. 选型——为什么用循环链表？ ​

约瑟夫环问题有三类常见解法：

维度数组（标记删除）数组（元素前移）循环链表
删除复杂度O(1) 标记，后续扫描需跳过O(n) 所有后续元素前移O(1) 修改指针
遍历 K 步O(K) 逐元素检查存活状态O(K) 直接索引O(K) 跟随 next 指针
单轮总开销O(n) 需扫描已被删元素O(n) 数组移位O(K) 随
空间O(N)O(N)O(N) + 指针字段开销
性需额外 visited[] 标记数组索引取模绕弯天然映射"围成一圈"
三种方案的代码脉络:

数组标记法:
  int alive[N];  // 为标记付出 O(N) 额外空间
  while (remaining) {
      step = K % remaining;
      while (step) {
          cur = (cur + 1) % N;
          if (alive[cur]) step--;   ← 跳过已淘汰的位置
      }
  }

数组移位法:
  每次淘汰后，将后续所有元素向前移一位:
  for (j = cur; j < remaining-1; j++)
      arr[j] = arr[j+1];           ← O(n) 每轮移位

循环链表法:
  cursor = cursor->next;           ← 纯指针跟随，无浪费
  free(clist_delete(cursor));      ← O(1) 删除

结论：循环链表是约瑟夫环的"自然"数据结构——"围成一圈"的物理模型就是循环链表。数组方案在 N 大时因扫描已淘汰元素而退化为 O(n²)，循环链表每轮只需 O(K) 时间。额外指针开销在现代机器上可忽略。

NOTE

如果只需要求最终幸存者（不需要淘汰过程），有更高效的数学解法。如果 K 极大（如 K=10^9），无论哪种数据结构都需 K %= remaining 优化。下一节讲这个。

6. 数学解法：约瑟夫环的递推公式 ​

6.1 递推公式及其推导直觉 ​

约瑟夫环有一个 O(N) 时间、O(1) 空间的递推公式解：

f(1, K) = 0                        (基础状态：1个人，幸存者是索引0)
f(N, K) = (f(N-1, K) + K) % N     (递推：先淘汰1人，剩下的问题规模减1)

f(N, K) 返回幸存者的 0-based 索引**（即第几个人幸存，从 0 开始计数）。

推导直觉:

N 个人从 0 开始报数到 K，淘汰 (K-1) % N 号。

淘汰之后，从 K%N 号重新开始报数。如果把这个新起点"平移"成从 0 开始，
相当于把每个人编号重新映射: 
  旧编号 → 新编号:  (旧编号 - K) % N
  新编号 → 旧编号:  (新编号 + K) % N

所以: f(N, K) = (f(N-1, K) + K) % N

6.2 手动推算：N=5, K=2 ​

f(1, 2) = 0                                          ← 1人，幸存者索引0

f(2, 2) = (f(1, 2) + 2) % 2 = (0 + 2) % 2 = 0       ← 2人，幸存者索引0

f(3, 2) = (f(2, 2) + 2) % 3 = (0 + 2) % 3 = 2       ← 3人，幸存者索引2

f(4, 2) = (f(3, 2) + 2) % 4 = (2 + 2) % 4 = 0       ← 4人，幸存者索引0

f(5, 2) = (f(4, 2) + 2) % 5 = (0 + 2) % 5 = 2       ← 5人，幸存者索引2

幸存者索引 = 2 → 编号 3（1-based 则是第 3 个人，值 = 3）
与链表模拟结果对比: 淘汰顺序 2 4 1 5 3 → 最后剩下 3 ✓

两种方法的定位：链表法展示淘汰的过程（可视化、教学友好），公式法给出最终的结果（高效、竞赛友好）。两者可以交叉验证。

6.3 K 取模优化 ​

modulo_optimization.c
c
// 每轮行走前，对 K 取模减少无效绕圈
int remaining = N;
while (remaining > 0) {
    int step = (K - 1) % remaining;  // K%remaining 步等价于 K 步的淘汰位置
    for (int i = 0; i < step; i++)
        cursor = cursor->next;
    // ... 淘汰 cursor ...
    remaining--;
}
为什么 K %= remaining 是等价的？

  N=5, K=7 的情况:
  7 声 = 绕 1 整圈(5) + 2 声 = 淘汰"第 7 声"对应的位置 = 淘汰"第 2 声"对应的位置
  所以: step = (K-1) % remaining = 6 % 5 = 1，只需走 1 步（K-1=6步 被化简为 1步）

当 K 远大于 remaining 时（如 K=10000），这个优化的效果立竿见影。

7. 双向循环链表——O(1) 删除的扩展 ​

7.1 双向循环链表的结构 ​

doubly_circular.c
c
struct dnode {
    int data;
    struct dnode *prev;    // 指向前一个节点
    struct dnode *next;    // 指向后一个节点
};
双向循环链表结构:

        ┌─────┐  ┌─────┐  ┌─────┐
        │  1  │  │  2  │  │  3  │
   ┌── ┤prev │  │prev │  │prev │──┐
   │    │next ├─→│next ├─→│next │  │
   │    └─────┘  └─────┘  └─────┘  │
   └───────────────────────────────┘
         (prev 指针反向串联成环)

7.2 O(1) 删除的秘密 ​

在单向循环链表中，删除一个节点需要 O(n) 找前驱。双向循环链表中，前驱直接通过 prev 指针访问：

doubly_delete.c
c
// 单向循环链表删除: O(n) 找前驱
struct node *prev = item;
while (prev->next != item)    // ← 最多绕一整圈
    prev = prev->next;
prev->next = item->next;

// 双向循环链表删除: O(1) 无需遍历
item->prev->next = item->next;  // 前驱的下一个 = 被删节点的下一个
item->next->prev = item->prev;  // 后继的前一个 = 被删节点的前一个
free(item);

// 甚至不需要特判唯一节点——唯一节点的 prev==next==self，
// item->prev->next = item->next → self->next = self ✓
// item->next->prev = item->prev → self->prev = self ✓

代价：每个节点多 8 字节（64 位系统）存储 prev 指针。N=100 万时，额外开销 8MB——在现代硬件上通常可以接受。

8. 常见错误与正确做法 ​

错误后果正确做法
首个节点 next = NULL后续遍历段错误自环：item->next = item
遍历用 while 而非 do-while起点被跳过do {...} while (p != cur)
删唯一节点不判 item->next == item找前驱死循环先判 item->next == item
前驱查找用 prev != item（而非 prev->next）永远找不到前驱/死循环while (prev->next != item)
构建完忘记 cursor = cursor->next从最后插入点开始报数移到第一个节点再开始
报数走 K 步（应是 K-1 步）多淘汰一个人走 K-1 步

参考解答 ​

练习: clist_insert 和 clist_delete 完整实现
solution_33_circular_josephus.c
c
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val;
    p->next = NULL;
    return p;
}

struct node *clist_insert(struct node *cur, int val)
{
    struct node *p = make_node(val);

    if (cur == NULL) {
        /* 第一个节点：自环——循环链表的最小有效状态 */
        p->next = p;
        return p;
    }

    /* 插在 cur 之后 */
    p->next = cur->next;
    cur->next = p;
    return p;   /* 新节点成为新的 cursor */
}

struct node *clist_delete(struct node *item)
{
    if (item == NULL)
        return NULL;

    /* 没有必须特判，否则找前驱时死循环 */
    if (item->next == item) {
        free(item);
        return NULL;
    }

    /* 找前驱：prev->next == item，而不是 prev == item */
    struct node *prev = item;
    while (prev->next != item)
        prev = prev->next;

    /* 跳过 item，保存后继 */
    prev->next = item->next;
    struct node *next = item->next;
    free(item);
    return next;    /* 继，作为下一轮的起点 */
}

int main(void)
{
    int N, K;
    char line[64];
    fgets(line, sizeof(line), stdin);
    sscanf(line, "%d %d", &N, &K);

    /* 构建循环链表 1 → 2 → ... → N → 回到 1 */
    struct node *cursor = NULL;
    for (int i = 1; i <= N; i++)
        cursor = clist_insert(cursor, i);
    /* 移到第一个节点作为起点 */
    cursor = cursor->next;

    /* 约瑟夫环淘汰过程 */
    int first = 1;
    while (cursor != NULL) {
        /* 走 K-1 步（当前站的人已经算 1） */
        for (int i = 1; i < K; i++)
            cursor = cursor->next;

        /* 打印被淘汰者 */
        if (!first) printf(" ");
        printf("%d", cursor->data);
        first = 0;

        /* 点，cursor 指向后继 */
        cursor = clist_delete(cursor);
    }
    printf("\n");

    return 0;
}

核心逻辑解析：

  1. 自环初始化：cur == NULL 时 p->next = p，确保循环链表从最小有效状态起步。
  2. 前驱查找：while (prev->next != item) 而非 prev != item——循环链表没有 NULL 终点，prev != item 在起点就是假的。
  3. 唯一节点：item->next == item 时直接 free 返回 NULL，避免找前驱死循环。
  4. 行走 K-1 步：起点算第 1 个，只需再走 K-1 步到达第 K 个。
  5. 删除返回后继：clist_delete 返回被删节点的 next，刚好作为下一轮的起点。

对照检查：插入首节点做了自环吗？clist_delete 中判了 item->next == item 吗？main 中 cursor = cursor->next 移到起点了吗？报数走了 K-1 步吗？

课堂讨论 ​

  1. 循环链表插入第一个节点时，为什么必须 item->next = item（自环）？如果写成 item->next = NULL 会发生什么？
  2. 为什么循环链表的遍历必须用 do-while 而不能用 while？给出一个具体的循环链表节点布局来说明起点是如何被 while 跳过的。
  3. clist_delete 中找前驱时，为什么用 prev->next != item 而不是 prev != item？这两个条件在循环链表中的行为有什么不同？
  4. 约瑟夫环的数学递推公式 f(N) = (f(N-1) + K) % N 的物理含义是什么？用 N=5, K=3 手动推一遍验证结果。
  5. 如果改用双向循环链表，clist_delete 可以怎么简化？为什么不需要特判唯一节点了？

讨论答案 ​

Q1: 为什么必须自环，不能 next=NULL？

绝对不能 next = NULL，因为循环链表的前提就是"没有 NULL"的闭环。

如果第一个节点 next = NULL：

  • 遍历时 do { p = p->next; } while (p != cur) 走到 NULL 时解引用 → 段错误
  • 删除操作 while (prev->next != item) 中 prev->next = NULL → prev = prev->next 解引用 NULL → 段错误

自环 item->next = item 是循环链表小有效状态它满足"每个节点的 next 都指向一个有效节点"的循环链表不变量（invariant）。这个不变量在所有操作后必须保持，是循环链表设计的第一准则。

Q2: 为什么遍历必须 do-while？

while 在起点处判断 p != cur 为假，循环体零次执行，起点被跳过。

具体例子：链表 [1] → [2] → [3] → [1] → ...，从 [1] 开始遍历。

c
struct node *p = cur;   // p = [1]

// while 版本
while (p != cur) {      // [1] != [1]? → false → 循环不执行！
    process(p);         // ← 永远不会走到这里
    p = p->next;
}
// [1] 从未被处理 ✗

// do-while 版本
do {
    process(p);         // 处理 [1] ✓
    p = p->next;        // p = [2]
} while (p != cur);     // [2] != [1]? → true → 继续
// 继续处理 [2], [3]，直到 p 回到 [1] 为止 ✓

根本原因：在循环链表中，起点的 p 和终止条件的目标 cur 是同一个节点。while 先判后执行意味着首次判断就为假；do-while 先执行后判保证起点至少被处理一次。

Q3: 为什么是 prev->next != item 而不是 prev != item？

在循环链表中没有 NULL 终点，prev != item 永远无法安全终止。

具体情况：

  • prev != item：prev 从 item 出发，一开始就 prev == item，循环零次执行。如果从其他地方出发，绕完一整圈回到 item 时才变假——但那时 prev 又等于 item 自身，不是前驱。
  • prev->next != item：找的是"next 指向 item 的节点"——这个节点有且只有一个，就是 item 的前驱。绕圈过程中一旦找到就停止，逻辑明确。
c
// 以链表 [1]→[2]→[3]→[1]→... 为例，删除 [3]
// 方法 prev != item:
struct node *prev = [3];
while (prev != [3])    // [3] != [3]? → false → 循环不执行
    prev = prev->next;
// prev 仍为 [3] → 无法删 ✗

// 方法 prev->next != item:
struct node *prev = [3];
while (prev->next != [3])  // [3]->next=[1] != [3]? → true
    prev = prev->next;     // prev=[1]
// [1]->next=[2] != [3]? → true → prev=[2]
// [2]->next=[3] == [3]? → false → 停止
// prev=[2] 就是 [3] 的前驱 ✓
Q4: 递推公式的物理含义

f(N, K) 是 N 人从 0 开始报数到 K 淘汰，幸存者的 0-based 索引。

公式 f(N) = (f(N-1) + K) % N 的含义：N 人情况下，先淘汰第 (K-1)%N 号，剩下的 N-1 人从 K%N 重新开始。把新队伍"平移"到从 0 开始编号——旧编号 j 在新队伍中变成 (j - K) % N，反过来新队伍中的索引 x 对应旧编号 (x + K) % N。

手动推算 N=5, K=3：

f(1, 3) = 0

f(2, 3) = (0 + 3) % 2 = 1     ← 2人中幸存者索引1（第2个人）

f(3, 3) = (1 + 3) % 3 = 1     ← 3人中幸存者索引1（第2个人）

f(4, 3) = (1 + 3) % 4 = 0     ← 4人中幸存者索引0（第1个人）

f(5, 3) = (0 + 3) % 5 = 3     ← 5人中幸存者索引3（第4个人）

验证（链表模拟 N=5, K=3 的淘汰顺序）：
报数: 1 2 3 → 3淘汰
报数: 4 5 1 → 1淘汰
报数: 2 4 5 → 5淘汰
报数: 2 4 2 → 2淘汰
剩下: 4 → 编号4，索引3 ✓
Q5: 双向循环链表如何简化删除

删除从 O(n) 降为 O(1)，且不再需要特判唯一节点。

c
struct dnode *dclist_delete(struct dnode *item)
{
    if (item == NULL)
        return NULL;

    // 即使只有一个节点，item->prev == item->next == item 也成立
    item->prev->next = item->next;   // 前驱跳过 item
    item->next->prev = item->prev;   // 后继反向连接前驱

    struct dnode *next = item->next;
    // 如果删完只剩自己（唯一节点），next 就是 item，说明全删了
    if (next == item)
        next = NULL;

    free(item);
    return next;
}

为什么不需要特判唯一节点？即使 item 是唯一的节点，item->prev 和 item->next 都指向自己：

  • item->prev->next = item->next → item->next = item->next → 恒等，不变
  • 同样 item->next->prev = item->prev 是 恒等

结构仍然是合法的双向循环链表（尽管只有一个节点，释放后就没了）。代价是每个节点多一个指针——经典的"空间权衡。

课后练习 ​

  1. 反向构建：修改 clist_insert 的实现，使插入方式从"插在 cursor 为"插在 curs后"。用修改后的插入构建 1→2→3 的循环链表，验证节点顺序是否正确。

    知识点提示：插在之前需要先找到 cursor 点（单向循环链表中需要遍历一圈），然后插入在前驱之后。这比插在之后多了一步 O(n) 的前驱查找。

    参考解答
    clist_insert_before.c
    c
    struct node *clist_insert_before(struct node *cur, int val)
{
    struct node *p = make_node(val);

    if (cur == NULL) {
        p->next = p;
        return p;
    }

    /* 找到 c前驱 */
    struct node *prev = cur;
    while (prev->next != cur)
        prev = prev->next;

    /* 在前驱之后插入（即在 cur 之前） */
    p->next = prev->next;   /* p->next = cur */
    prev->next = p;
    return p;   /* 返回新节点作为新 cursor */
}

  2. 实现 clist_print(cursor) 打印循环链表：从 cursor 出发，打印一圈所有节点的 data，元素间空格分隔。当 cursor == NULL 时打印空行。验证打印结果是否与预期相符。

    知识点提示：使用 do-while 遍历，首次打印前不输出空格，后续打印前加空格。cursor == NULL 时直接返回。

    参考解答
    clist_print.c
    c
    void clist_print(struct node *cursor)
{
    if (cursor == NULL) {
        printf("\n");
        return;
    }

    struct node *p = cursor;
    do {
        printf("%d", p->data);
        p = p->next;
        if (p != cursor)
            printf(" ");
    } while (p != cursor);
    printf("\n");
}

  3. K 很大的优化：修改约瑟夫环的 main，在每轮行走前加入 K %= remaining（其中 remaining 是当前剩余人数）。测试 N=5, K=1000 的输出是否与数学公式结果一致。

    知识点提示：int step = (K - 1) % remaining。K 取余 remaining 等价于只保留"不满一圈"的部分，因为每绕一整圈的位置是等价的。

    参考解答
    josephus_optimized.c
    c
    int remaining = N;
while (cursor != NULL) {
    int step = (K - 1) % remaining;
    for (int i = 0; i < step; i++)
        cursor = cursor->next;

    if (remaining < N) printf(" ");
    printf("%d", cursor->data);

    cursor = clist_delete(cursor);
    remaining--;
}

  4. 公式法求幸存者：实现 int josephus_index(int N, int K)，用递推公式 f(1)=0; f(i)=(f(i-1)+K)%i 计算幸存者的 0-based 索引。列出 N=10, K=3 和 N=41, K=3 的结果，与链表模拟交叉验证。

    知识点提示：for (int i = 2; i <= N; i++) f = (f + K) % i;。返回索引（0-bas打印时需要 +1 转为 1-based 编号。

    参考解答
    josephus_formula.c
    c
    int josephus_index(int N, int K)
{
    int f = 0;  /* f(1, K) = 0 */
    for (int i = 2; i <= N; i++)
        f = (f + K) % i;
    return f;
}

int main(void)
{
    printf("N=10, K=3: survivor index = %d (person %d)\n",
           josephus_index(10, 3), josephus_index(10, 3) + 1);
    // 输出: N=10, K=3: survivor index = 3 (person 4)
    // 汰顺序: 3 6 9 2 7 1 8 5 10 4 → 幸存者是 4 ✓

    printf("N=41, K=3: survivor index = %d (person %d)\n",
           josephus_index(41, 3), josephus_index(41, 3) + 1);
    // 输出: N=41, K=3: survivor index = 30 (person 31)

    return 0;
}

参考资料 ​

  • Josephus Problem — Wikipedia，包含历史背景、数学递推和多种变体
  • 《具体数学》(Concrete Mathematics) §1.3 — Knuth 等著的数学经典，约瑟夫问题的完整数学分析
  • 《数据结构与算法分析 — C 语言描述》§3.2 — 循环链表的 ADT 现
  • Linux 内核链表 list.h — 工业级双向循环链表实现，list_for_each_entry 宏的设计哲学
  • K&R《C 语言》§6.5 — 自引用结构与链表的基础，包含 alloc 和 free 的链表用法

"The purpose of computing is insight, not numbers." — Richard Hamming

Released under the MIT License.

Copyright © 2026-present OpenCamp C Team