用C语言链表代码实现约瑟夫环

### C语言链表实现约瑟夫环 以下是基于循环链表的C语言实现约瑟夫环问题的完整代码： #### 创建循环链表 `CreateCircle` 函数用于创建一个包含 `n` 个节点的循环链表，其中每个节点存储其对应的编号。 ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { int data; struct Node* next; } Node; // 创建循环链表 Node* CreateCircle(int n) { if (n <= 0) return NULL; // 如果人数小于等于0，则返回NULL Node *head = (Node*)malloc(sizeof(Node)); // 创建第一个节点 head->data = 1; head->next = head; // 自己指向自己形成循环 Node *tail = head; // 尾指针初始化为头节点 for (int i = 2; i <= n; ++i) { // 循环创建剩余节点 Node *new_node = (Node*)malloc(sizeof(Node)); new_node->data = i; new_node->next = head; // 新节点指向头节点 tail->next = new_node; // 当前尾部节点指向新节点 tail = new_node; // 更新尾部指针 } return head; // 返回头节点 } ``` #### 解决约瑟夫问题 `ysf` 函数实现了约瑟夫环的核心逻辑。它通过遍历和删除节点的方式模拟游戏过程，直到仅剩最后一个节点为止。 ```c void ysf(Node **head, int m) { if (*head == NULL || m <= 0) return; // 输入参数非法则退出 Node *current = *head; // 初始化当前节点为头节点 Node *prev = NULL; // 前驱节点初始为空 while (current->next != current) { // 只要链表不止一个节点 for (int count = 1; count < m; ++count) { // 移动到第m个位置 prev = current; current = current->next; } // 删除当前节点 printf("淘汰 %d\n", current->data); // 输出被淘汰的人 prev->next = current->next; // 跳过当前节点 free(current); // 释放内存 current = prev->next; // 更新当前节点 } // 打印最后剩下的那个人 printf("幸存者：%d\n", current->data); free(current); // 释放最后一个人的内存 *head = NULL; // 清空头指针 } int main() { int n = 7; // 总人数 int m = 3; // 报数间隔 Node *circle = CreateCircle(n); // 创建循环链表 ysf(&circle, m); // 模拟约瑟夫环 return 0; } ``` --- ### 关键点解析 1. **循环链表构建** 使用头插法或尾插法可以轻松构建循环链表。这里采用的是尾插法，在每次新增节点时将其连接到最后一个节点之后，并保持整个链表的闭环特性[^1]。 2. **约瑟夫环核心算法** - 初始状态设置两个指针：`current` 和 `prev`。 - 每次移动 `m-1` 步到达目标节点的位置。 - 删除目标节点并更新指针，继续下一轮操作直至只剩下一个节点[^2]。 3. **边界条件处理** 特殊情况如输入人数 `n=0` 或报数步长 `m<=0` 应当提前检测并终止程序运行[^3]。 4. **动态内存管理** 在每轮迭代中及时释放已删除节点所占用的空间，防止内存泄漏。 --- ###