用c语言链表方式写约瑟夫环

用C语言实现约瑟夫环（Josephus Problem）通常涉及创建一个双向链表，并按照特定步长跳过节点。以下是简单的步骤：

首先，我们需要定义链表结构体和一些辅助函数：

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 添加节点到链表
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        newNode->prev = *head;
        (*head)->next = newNode;
        *head = newNode;
    }
}

接下来，我们编写约瑟夫环的主函数，这里以每k步前进为例：

void josephusRing(Node* head, int k) {
    int count = 0; // 计数器
    Node* current = head;

    while (current != NULL) {
        count++;
        current = current->next;

        if (count % k == 0) { // 如果是k的倍数，则删除当前节点
            if (current == head) {
                head = head->next;
                if (head != NULL) {
                    head->prev = NULL;
                }
            } else {
                current->prev->next = current->next;
                if (current->next != NULL) {
                    current->next->prev = current->prev;
                }
            }
            free(current); // 释放内存
        }
    }
}

最后，你可以这样使用它：

int main() {
    Node* head = NULL;
    // 初始化链表...
    // ...插入节点...

    int k = 3; // 约瑟夫环步长
    josephusRing(head, k);

    // 打印剩余节点
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }

    return 0;
}