链表实现约瑟夫环c语言
时间: 2024-02-02 16:04:56 浏览: 77
以下是使用循环链表实现约瑟夫环的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义循环链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建循环链表
Node* createCircularLinkedList(int n) {
Node* head = NULL;
Node* prev = NULL;
for (int i = 1; i <= n; i++) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = i;
if (head == NULL) {
head = newNode;
} else {
prev->next = newNode;
}
newNode->next = head;
prev = newNode;
}
return head;
}
// 删除指定位置的节点
Node* deleteNode(Node* head, int position) {
if (head == NULL) {
return NULL;
}
Node* current = head;
Node* prev = NULL;
// 找到要删除的节点
for (int i = 1; i < position; i++) {
prev = current;
current = current->next;
}
// 删除节点
if (prev == NULL) {
prev = current;
while (prev->next != head) {
prev = prev->next;
}
prev->next = current->next;
head = current->next;
} else {
prev->next = current->next;
}
free(current);
return head;
}
// 约瑟夫环算法
void josephusCircle(int n, int m) {
Node* head = createCircularLinkedList(n);
Node* current = head;
printf("假设第一次从编号为1的人开始数,数到%d的那个人出环\n", m);
for (int i = 1; i <= n; i++) {
// 找到要出环的节点
for (int j = 1; j < m; j++) {
current = current->next;
}
// 输出出环的节点
printf("第%d次出环的元素是%d\n", i, current->data);
// 删除出环的节点
head = deleteNode(head, current->data);
current = current->next;
}
}
int main() {
int n = 5; // 假设5个人围坐一圈
int m = 2; // 数到2的那个人出环
josephusCircle(n, m);
return 0;
}
```