（C语言）猴子选大王链式结构

好的，下面给出 C 语言的链式结构代码实现：

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

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

/**
 * 创建一个长度为n的循环链表
 */
Node* createCircularLinkedList(int n) {
    Node* head = (Node*)malloc(sizeof(Node));  // 创建第一个节点
    head->value = 1;
    head->next = NULL;
    Node* p = head;
    for (int i = 2; i <= n; i++) {  // 创建其他n-1个节点并链接到链表中
        Node* node = (Node*)malloc(sizeof(Node));
        node->value = i;
        node->next = NULL;
        p->next = node;
        p = node;
    }
    p->next = head;  // 将最后一个节点的next指向头节点，形成循环链表
    return head;
}

/**
 * 猴子选大王
 */
int josephus(int n, int m, int k) {
    Node* head = createCircularLinkedList(n);
    Node* p = head;  // 指针指向第一个猴子
    int count = 0;  // 计数器，记录已经出列的猴子数量
    while (count < n - 1) {  // 只有最后一个猴子没有出列，循环继续
        for (int i = 0; i < k - 1; i++) {
            p = p->next;  // 报数，一直报到第k个猴子
        }
        Node* q = p->next;  // q指向要删除的节点
        p->next = q->next;  // 将q从链表中删除
        free(q);  // 释放q节点的内存空间
        count++;  // 出列的猴子数量加1
        p = p->next;  // 将指针指向下一个猴子
    }
    int king = p->value;  // 最后一个未出列的猴子即为猴王
    free(p);  // 释放最后一个猴子的内存空间
    return king;
}

int main() {
    int n = 10, m = 3, k = 4;
    int king = josephus(n, m, k);
    printf("The monkey king is %d\n", king);
    return 0;
}

这段代码中使用了动态内存分配，需要注意在程序结束时释放节点的内存空间。在实际应用中，如果 n 的值比较大，可能会导致节点的数量过多，从而占用大量的内存空间。此时可以考虑使用顺序结构来实现，避免内存空间的浪费。