运用c语言的循环链表完成约瑟夫环问题
时间: 2023-05-13 16:06:28 浏览: 118
可以的,以下是一个使用C语言循环链表解决约瑟夫环问题的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node *createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = i;
newNode->next = NULL;
if (head == NULL) {
head = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
tail->next = head; // 将尾节点指向头节点,形成循环链表
return head;
}
void josephus(int n, int m) {
Node *head = createList(n);
Node *p = head, *prev = NULL;
while (p->next != p) {
for (int i = 1; i < m; i++) {
prev = p;
p = p->next;
}
prev->next = p->next;
printf("%d ", p->data);
free(p);
p = prev->next;
}
printf("%d\n", p->data);
free(p);
}
int main() {
int n, m;
printf("请输入总人数n和报数m:");
scanf("%d%d", &n, &m);
josephus(n, m);
return 0;
}
```
该程序首先创建一个包含n个节点的循环链表,然后按照报数m的规则依次删除节点,直到只剩下一个节点为止。最后输出剩下的节点的编号,即为约瑟夫环问题的解。