c语言使用循环链表解决约瑟夫环问题

约瑟夫环问题是一个经典的数学问题，具体描述如下：有n个人（编号为1~n），围成一个圆圈，从第一个人开始报数，报到m的人出圈，然后从他的下一个人开始重新报数，重复这个过程，直到剩下最后一个人。

下面是使用循环链表解决约瑟夫环问题的C语言实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int num;
    struct node *next;
} Node;

void create_circle(Node **head, int n) {
    Node *tail = NULL, *p = NULL;
    for (int i = 1; i <= n; i++) {
        p = (Node *)malloc(sizeof(Node));
        p->num = i;
        if (*head == NULL) {
            *head = p;
            tail = p;
        } else {
            tail->next = p;
            tail = p;
        }
    }
    tail->next = *head; // 将尾节点指向头节点，形成循环链表
}

void josephus_circle(Node **head, int m) {
    Node *p = *head, *q = NULL;
    int count = 0;
    while (p->next != p) {
        count++;
        if (count == m) {
            q->next = p->next;
            printf("%d出圈\n", p->num);
            free(p);
            p = q->next;
            count = 0;
        } else {
            q = p;
            p = p->next;
        }
    }
    printf("剩下%d号\n", p->num);
    *head = p;
}

int main() {
    int n, m;
    Node *head = NULL;
    printf("请输入总人数n和报数m：");
    scanf("%d%d", &n, &m);
    create_circle(&head, n);
    josephus_circle(&head, m);
    return 0;
}

首先，使用 `create_circle` 函数创建一个有 n 个节点的循环链表，其中头节点指针保存在 `head` 变量中。

然后，使用 `josephus_circle` 函数来模拟约瑟夫环问题。使用两个指针 `p` 和 `q` 遍历循环链表， `count` 记录报数的次数。当 `count` 等于 `m` 时，删除节点 `p`，并输出其编号。否则，指针 `p` 和 `q` 向后移动。当循环链表中只剩下一个节点时，输出其编号并退出循环。

最后，将头节点指针 `head` 指向最后剩下的节点，返回其编号。