有n个人围成一圈,按顺序从1到n编号。从第一个人开始报数,报到3的人退出圈子,下一个人从1开始报数,报到3的人退出圈子。如此下去,直到留下最后一个人。请按退出顺序输出退出圈子的人的编号。。用c语言代码编写

以下是使用循环链表的C语言代码实现：

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

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

Node *createCircle(int n) {
    Node *head, *prev, *curr;
    head = prev = (Node*) malloc(sizeof(Node));
    head->num = 1;
    for (int i = 2; i <= n; i++) {
        curr = (Node*) malloc(sizeof(Node));
        curr->num = i;
        prev->next = curr;
        prev = curr;
    }
    prev->next = head;  // 链接成环
    return head;
}

void josephus(int m, Node *head) {
    Node *p = head, *q;
    int count = 1;
    while (p->next != p) {
        if (count == m-1) {  // 找到数到m-1的人
            q = p->next;
            p->next = q->next;
            printf("%d ", q->num);  // 输出退出的人的编号
            free(q);  // 释放退出的节点的内存
            count = 0;
        }
        p = p->next;
        count++;
    }
    printf("%d\n", p->num);  // 最后剩下的人的编号
    free(p);
}

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

解释一下代码：

- `Node` 结构体表示链表节点，包含一个编号 `num` 和一个指向下一个节点的指针 `next`。
- `createCircle` 函数用于创建长度为 `n` 的循环链表，返回头节点的指针。
- `josephus` 函数用于实现约瑟夫问题的求解，`m` 表示每次数到第几个人退出。使用 `count` 记录当前报数的人是第几个，当 `count` 等于 `m-1` 时，删除下一个节点，并输出该节点的编号。最后剩下的节点即为胜者。
- `main` 函数读入总人数 `n` 和报数 `m`，调用 `createCircle` 创建循环链表，再调用 `josephus` 求解问题。