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

在C语言中，我们可以使用循环链表（Circular Doubly Linked List，简称CDLL）来实现约瑟夫环（Josephus Problem）。这个经典问题描述的是：一群人按照顺序报数，从某个人开始，每隔k人处留下一个人，直到剩下最后一个人为止。

以下是实现步骤：

1. 首先，我们需要定义一个结构体表示节点，包含指向前一个节点、下一个节点以及当前数值的数据成员：

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

2. 创建一个函数来初始化循环链表，并计算起始位置（因为是约瑟夫环，所以我们需要知道从哪一个人开始报数）：

Node* createJospehRing(int n, int k, int start) {
    // 初始化链表头部和尾部
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    head->next = head;
    head->prev = head;

    for (int i = 1; i < n; ++i) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = start + i * k;
        newNode->prev = tail;
        newNode->next = head;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

3. 定义一个删除节点并返回下一个存活者（即报完数的人）的函数：

Node* josephusStep(Node* current) {
    Node* next = current->next;
    if (next == current) {  // 如果到达链表尾部，重新指向头
        current = head;
    } else {
        // 删除当前节点
        free(current);
    }
    return next;
}

4. 主循环：不断调用`josephusStep`直到只剩下一个节点：

void josephusGame(Node* head, int k) {
    while (head->next != head) {
        head = josephusStep(head);
    }
    printf("剩下的最后一个节点数据: %d\n", head->data);
}