猴子选大王：循环链表实现

"猴子选大王" 是一个经典的算法问题，通常用来演示链表操作。这个源码使用了循环链表实现，而不是数组。程序首先创建一个循环链表表示猴子，然后按照特定规则（通常是丢弃每轮的最后一个猴子）进行淘汰，直到选出最后的大王。 以下是详细的解释： 在C++编程语言中，我们首先定义了一个结构体`node`来表示链表中的节点，它有两个成员：一个整型变量`number`存储猴子的编号，以及一个指向下一个节点的指针`next`。 ```cpp struct node { int number; struct node* next; }; ``` `main`函数是程序的入口。在这里，用户通过输入`p`和`m`来指定猴子的数量和进行游戏的轮数。`atoi`函数用于将输入的字符串转换为整数。 ```cpp int N = atoi(m); // 轮数 int monkeyNum = atoi(p); // 猴子数量 ``` 接着，我们创建并初始化一个头节点`head`，然后通过循环构造一个循环链表，每个节点代表一只猴子。链表的构建是通过动态内存分配完成的，`malloc`函数用于分配新的节点，并将它们连接起来。 ```cpp struct node* p1; struct node* p2; struct node* head = (struct node*)malloc(sizeof(structnode)); head->number = 1; head->next = 0; p1 = p2 = head; for (int i = 2; i <= monkeyNum; i++) { p2 = (struct node*)malloc(sizeof(structnode)); p2->number = i; p1->next = p2; p1 = p2; } p2->next = head; // 创建循环链表 p1 = head; ``` 在链表构建完成后，我们开始执行“猴子选大王”的逻辑。首先，设置一个指针`p1`指向当前的猴子，另一个指针`q`用于记录要删除的猴子。`while`循环会在`monkeyNum`不等于1时持续执行，表示游戏未结束。 ```cpp struct node* q; while (monkeyNum != 1) { for (int i = 1; i <= N - 2; i++) { // 模拟每一轮的过程，跳过N-2只猴子 p1 = p1->next; } p2 = p1->next->next; // 记录下一个要被删除的猴子 q = p1->next; // 保存要删除的节点 p1->next = p1->next->next; // 删除该猴子，更新链表 free(q); // 释放被删除节点的内存 p1 = p2; // 移动指针到下一个存活的猴子 monkeyNum--; // 剩余猴子减一 } ``` 当游戏结束时，`p2`指向的就是最后剩下的大王，输出它的编号。 ```cpp cout << p2->number << endl; ``` 这段代码的核心在于链表操作，包括创建、遍历、删除节点等。它展示了如何在实际问题中运用链表数据结构，以及如何根据问题规则调整链表结构。在实际编程中，理解和掌握链表操作是相当重要的，因为链表在处理动态数据、存储复杂关系等方面有其独特优势。