数据结构复习笔记 - 约瑟夫问题

数据结构复习笔记 - 约瑟夫问题

简单介绍

约瑟夫问题（Josephus Problem）是经典的循环链表问题：n 个人围成一圈，从 1 开始报数，报到 m 的人出列，下一个人继续从 1 开始报数，直到只剩最后一人。

方法列表

函数	功能	参数
YSF(int m, int n)	求解约瑟夫问题	m: 总人数, n: 报数上限

重点注意

• 构建循环链表时，最后一个节点的 next 指向 head，形成环
• 每轮报数只需移动 n-1 次，因为当前节点本身就是报 1 的人
• 删除节点时必须先保存下一个节点，再修改指针，最后 delete
• 循环结束条件：curr->next == curr（只剩一个节点）

完整代码

#include <iostream>

/**
 * 链表节点结构体
 */
struct Node {
  int data;       // 编号（1 ~ m）
  Node *next;     // 指向下一人

  // 构造函数，统一初始化编号和指针
  Node(int d) : data(d), next(nullptr) {}
};

/**
 * 约瑟夫问题求解函数
 * 使用循环链表模拟报数过程
 *
 * @param m 总人数
 * @param n 报数上限（报到 n 的人出列）
 */
inline void YSF(int m, int n) {
  // 1. 创建循环链表
  Node *head = new Node(1);      // 头节点编号为 1

  Node *prev = head;             // prev 指向当前尾节点
  for (int i = 2; i <= m; ++i) { // 创建第 2 ~ m 号节点
    prev->next = new Node(i);
    prev = prev->next;
  }

  // 2. 成环：最后一个节点指向头节点
  prev->next = head;

  // 3. 开始报数出列
  Node *curr = head;             // curr 指向当前报数的人
  while (curr->next != curr) {   // 循环直到只剩一人
    // 报数：移动 n-1 次，因为当前节点本身就是报 1 的人
    for (int i = 1; i < n - 1; ++i) {
      curr = curr->next;
    }

    // 找到要出列的人（curr 的下一个节点）
    Node *tmp = curr->next;

    // 将出列节点从环中移除
    curr->next = tmp->next;

    // 释放出列节点内存
    delete tmp;

    // 下一轮从出列节点的下一个位置开始报数
    curr = curr->next;
  }

  // 4. 输出最后存活的人的编号
  std::cout << "The last one: " << curr->data << std::endl;

  // 5. 释放最后一个节点
  delete curr;
}