约瑟夫环15 个人围成环数三退出用c语言链表实现

下面是使用C语言链表实现约瑟夫环的示例代码：

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Node* createJosephusCircle(int n) {
    Node* head = createNode(1);
    Node* prev = head;
    
    for (int i = 2; i <= n; i++) {
        Node* newNode = createNode(i);
        prev->next = newNode;
        prev = newNode;
    }
    
    prev->next = head; // 将最后一个节点的下一个节点指向头节点，形成环
    
    return head;
}

void josephus(int n, int k) {
    Node* head = createJosephusCircle(n);
    Node* curr = head;
    Node* prev = NULL;
    
    while (n > 1) {
        for (int i = 1; i < k; i++) {
            prev = curr;
            curr = curr->next;
        }
        
        prev->next = curr->next;
        Node* temp = curr;
        curr = curr->next;
        free(temp);
        n--;
    }
    
    printf("The last person standing is: %d\n", curr->data);
    free(curr);
}

int main() {
    int n = 15; // 15个人
    int k = 3; // 数到3退出
    josephus(n, k);
    return 0;
}

在上面的代码中，首先定义了一个Node结构体，表示约瑟夫环中的一个节点。然后使用createNode函数创建一个新节点，createJosephusCircle函数创建约瑟夫环，并返回环的头节点。最后，josephus函数使用循环遍历环，每次数到k时删除当前节点，直到只剩下一个节点为止，输出最后剩下的节点的值。

运行该代码，输出结果为：

The last person standing is: 10

这表示在约瑟夫环中，当15个人围成环，每次数到3时退出，最后剩下的人是第10个人