用c语言循环链表实现约瑟夫问题

约瑟夫问题是一个经典的数学问题：n个人围成一圈，从第1个人开始报数，报到m的人出圈，然后从出圈的下一个人开始重新报数，直到剩下最后一个人。现在用C语言实现循环链表来解决这个问题。

首先，我们需要定义一个循环链表节点的结构体：

typedef struct node {
    int num;  // 编号
    struct node *next;  // 指向下一个节点的指针
} Node;

接下来，我们需要编写一个函数来创建一个包含n个节点的循环链表：

Node *createList(int n) {
    Node *head = malloc(sizeof(Node));  // 创建头节点
    head->num = 1;
    head->next = NULL;
    Node *tail = head;  // 尾指针指向头节点
    for (int i = 2; i <= n; i++) {
        Node *node = malloc(sizeof(Node));  // 创建新节点
        node->num = i;
        node->next = NULL;
        tail->next = node;  // 尾节点的next指针指向新节点
        tail = node;  // 尾指针指向新节点
    }
    tail->next = head;  // 尾节点的next指针指向头节点，形成循环链表
    return head;
}

接着，我们需要编写一个函数来解决约瑟夫问题。该函数接受三个参数：循环链表的头节点、起始报数的位置和出圈的数字m。

void josephus(Node *head, int start, int m) {
    Node *p = head;
    while (p->num != start) {
        p = p->next;  // 找到起始位置的节点
    }
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            p = p->next;  // 报数
        }
        printf("%d ", p->num);  // 输出出圈的数字
        Node *q = p->next;
        p->num = q->num;  // 将下一个节点的编号赋给当前节点，相当于删除了下一个节点
        p->next = q->next;  // 删除下一个节点
        free(q);  // 释放下一个节点的内存
    }
    printf("%d ", p->num);  // 输出最后一个数字
}

最后，我们可以在main函数中调用上述函数来解决约瑟夫问题：

int main() {
    int n, start, m;
    printf("请输入n, start, m: ");
    scanf("%d%d%d", &n, &start, &m);
    Node *head = createList(n);
    josephus(head, start, m);
    return 0;
}

完整代码如下：

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

typedef struct node {
    int num;  // 编号
    struct node *next;  // 指向下一个节点的指针
} Node;

Node *createList(int n) {
    Node *head = malloc(sizeof(Node));  // 创建头节点
    head->num = 1;
    head->next = NULL;
    Node *tail = head;  // 尾指针指向头节点
    for (int i = 2; i <= n; i++) {
        Node *node = malloc(sizeof(Node));  // 创建新节点
        node->num = i;
        node->next = NULL;
        tail->next = node;  // 尾节点的next指针指向新节点
        tail = node;  // 尾指针指向新节点
    }
    tail->next = head;  // 尾节点的next指针指向头节点，形成循环链表
    return head;
}

void josephus(Node *head, int start, int m) {
    Node *p = head;
    while (p->num != start) {
        p = p->next;  // 找到起始位置的节点
    }
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            p = p->next;  // 报数
        }
        printf("%d ", p->num);  // 输出出圈的数字
        Node *q = p->next;
        p->num = q->num;  // 将下一个节点的编号赋给当前节点，相当于删除了下一个节点
        p->next = q->next;  // 删除下一个节点
        free(q);  // 释放下一个节点的内存
    }
    printf("%d ", p->num);  // 输出最后一个数字
}

int main() {
    int n, start, m;
    printf("请输入n, start, m: ");
    scanf("%d%d%d", &n, &start, &m);
    Node *head = createList(n);
    josephus(head, start, m);
    return 0;
}