数据结构约瑟夫环用c++实现
时间: 2023-05-30 09:02:23 浏览: 117
用c++实现约瑟夫环
以下是使用C语言实现约瑟夫环的代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node, *LinkList;
LinkList initList(int n); // 初始化链表
void showList(LinkList head); // 打印链表
void josephus(LinkList head, int k, int m); // 约瑟夫环算法
int main() {
int n, k, m;
printf("请输入总人数n:");
scanf("%d", &n);
printf("请输入起始报数位置k:");
scanf("%d", &k);
printf("请输入出圈间隔m:");
scanf("%d", &m);
LinkList head = initList(n); // 初始化链表
printf("初始链表为:\n");
showList(head); // 打印链表
printf("约瑟夫环出圈序列为:\n");
josephus(head, k, m); // 约瑟夫环算法
return 0;
}
LinkList initList(int n) {
LinkList head = (LinkList)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
LinkList tail = head;
for (int i = 2; i <= n; i++) {
LinkList p = (LinkList)malloc(sizeof(Node));
p->data = i;
p->next = NULL;
tail->next = p;
tail = p;
}
tail->next = head; // 将链表首尾相连,形成环
return head;
}
void showList(LinkList head) {
LinkList p = head;
do {
printf("%d ", p->data);
p = p->next;
} while (p != head);
printf("\n");
}
void josephus(LinkList head, int k, int m) {
LinkList p = head;
while (p->next != p) { // 只剩一个节点时结束循环
for (int i = 1; i < k; i++) {
p = p->next; // 找到起始报数位置
}
for (int i = 1; i < m; i++) {
p = p->next; // 找到出圈节点
}
LinkList q = p->next; // q为出圈节点
p->next = q->next; // 将出圈节点从链表中删除
printf("%d ", q->data); // 输出出圈节点数据
free(q); // 释放出圈节点空间
}
printf("%d\n", p->data); // 输出最后剩下的节点数据
free(p); // 释放最后剩下的节点空间
}
```
在上面的代码中,我们使用了循环链表来实现约瑟夫环。initList函数用于初始化链表,showList函数用于打印链表,josephus函数实现了约瑟夫环算法。在josephus函数中,我们使用了两个循环来找到起始报数位置和出圈节点,然后将出圈节点从链表中删除并释放空间,最后输出出圈节点数据。当链表中只剩一个节点时,循环结束,输出最后剩下的节点数据并释放空间。
阅读全文