用链表实现猴子选王（C++）

在编程领域，猴子选王问题是一个有趣的算法问题，它通常被用来考察开发者对数据结构，尤其是链表的掌握程度。本问题的C++实现利用了链表的基本操作，包括链表的创建、插入、遍历以及删除节点。下面我们将详细讨论这个算法的实现及其涉及到的链表知识。 链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在猴子选王问题中，链表的每个节点代表一只猴子，通过特定的规则淘汰猴子，直到只剩下一个为王。 我们需要定义一个链表节点结构体，它包含两个部分：一个存储猴子编号的数据字段和一个指向下一个节点的指针。例如： ```cpp struct ListNode { int val; // 猴子编号 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数 }; ``` 接下来，我们需要创建一个链表，表示所有参与选举的猴子。这可以通过循环插入节点到链表头部完成： ```cpp ListNode* createList(int n) { ListNode* head = new ListNode(1); // 创建首节点 ListNode* current = head; for (int i = 2; i <= n; i++) { ListNode* newNode = new ListNode(i); current->next = newNode; current = current->next; } return head; } ``` 猴子选王的问题规则是：每次从1到当前剩余猴子数的随机数中选择一只猴子淘汰，直到只剩一只猴子为止。在链表中，我们可以通过迭代或递归的方式来实现这一过程。这里我们以迭代为例： ```cpp ListNode* monkeyKing(ListNode* head, int n) { while (n > 1) { int randomIndex = rand() % n; // 生成随机淘汰位置 ListNode* current = head; for (int i = 0; i < randomIndex - 1 && current != NULL; i++) { current = current->next; } if (current != NULL) { // 如果随机位置有效，删除该节点 ListNode* temp = current->next; current->next = temp->next; delete temp; } n--; } return head; // 返回最后剩下的猴子（链表的头节点） } ``` 为了测试和展示这个算法，我们可以编写一个主函数，生成一定数量的猴子并调用上述函数，然后输出结果： ```cpp int main() { int numMonkeys = 10; // 假设我们有10只猴子 ListNode* monkeyList = createList(numMonkeys); ListNode* king = monkeyKing(monkeyList, numMonkeys); cout << "The Monkey King is numbered: " << king->val << endl; return 0; } ``` 在这个实现中，我们主要运用了链表的创建、插入、遍历和删除操作。链表作为一种灵活的数据结构，能够有效地处理动态变化的数据集合，因此在解决各种算法问题时都有其独特的应用。在猴子选王问题中，链表不仅简化了数据的管理，也使得淘汰过程变得更加直观。理解和熟练掌握链表的使用，对于提升编程能力至关重要。