请用c语言实现约瑟夫环代码
时间: 2024-03-06 15:46:40 浏览: 121
好的,以下是一个C语言实现约瑟夫环问题的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义结构体表示链表节点
struct Node {
int data; // 节点数据
struct Node* next; // 指向下一个节点的指针
};
// 创建并初始化链表
struct Node* initList(int n) {
struct Node* head = (struct Node*)malloc(sizeof(struct Node)); // 创建头节点
head->data = 1; // 头节点数据为1
head->next = NULL;
struct Node* tail = head;
int i;
for (i = 2; i <= n; i++) { // 创建n个节点并插入链表尾部
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = i;
node->next = NULL;
tail->next = node;
tail = node;
}
tail->next = head; // 将链表首尾相连,形成环
return head;
}
// 删除节点并返回下一个节点指针
struct Node* removeNode(struct Node* node) {
struct Node* next = node->next; // 保存下一个节点指针
node->next = next->next; // 删除当前节点
free(next);
return node->next; // 返回下一个节点指针
}
// 解决约瑟夫环问题
void josephProblem(int n, int m) {
struct Node* head = initList(n); // 创建并初始化链表
struct Node* tail = head;
int i;
for (i = 0; i < n; i++) { // 移动尾指针到最后一个节点
tail = tail->next;
}
struct Node* node = head;
while (n > 0) { // 循环删除节点,直到链表为空
int count = m % n; // 计算需要报数的次数
if (count == 0) count = n; // 特殊处理count为0的情况
for (i = 1; i < count; i++) { // 移动节点指针到要删除的节点的前一个节点
node = node->next;
}
printf("%d ", node->data); // 输出要删除的节点的数据
node = removeNode(node); // 删除节点并获取下一个节点指针
n--;
}
printf("\n");
free(tail); // 释放头节点
}
int main() {
int n = 10; // 总人数
int m = 3; // 报数上限
josephProblem(n, m); // 解决约瑟夫环问题
return 0;
}
```
该代码中,`initList`函数用于创建并初始化链表,`removeNode`函数用于删除节点并返回下一个节点指针,`josephProblem`函数用于解决约瑟夫环问题。在`main`函数中,设置了总人数为10,报数上限为3,然后调用`josephProblem`函数来解决约瑟夫环问题,并输出结果。
阅读全文