数据结构约瑟夫环用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函数中，我们使用了两个循环来找到起始报数位置和出圈节点，然后将出圈节点从链表中删除并释放空间，最后输出出圈节点数据。当链表中只剩一个节点时，循环结束，输出最后剩下的节点数据并释放空间。