(C语言)猴子选大王链式结构
时间: 2023-06-22 19:41:28 浏览: 39
好的,下面给出 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 的值比较大,可能会导致节点的数量过多,从而占用大量的内存空间。此时可以考虑使用顺序结构来实现,避免内存空间的浪费。