约瑟夫环问题 C语言链表实现 - 15个人数三退出

使用链表可以很方便地解决约瑟夫环问题。下面是一个用C语言实现的例子：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n// 定义链表节点结构体\ntypedef struct Node {\n int data;\n struct Node* next;\n} Node;\n\n// 创建一个新的节点\nNode* createNode(int data) {\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->data = data;\n newNode->next = NULL;\n return newNode;\n}\n\n// 构建约瑟夫环链表\nNode* buildJosephusCircle(int n) {\n Node* head = createNode(1);\n Node* curr = head;\n\n for (int i = 2; i <= n; i++) {\n curr->next = createNode(i);\n curr = curr->next;\n }\n\n curr->next = head; // 将最后一个节点指向头节点，形成环\n\n return head;\n}\n\n// 在约瑟夫环链表中删除第 m 个节点\nvoid deleteNode(Node** head, int m) {\n Node* curr = *head;\n Node* prev = NULL;\n\n // 找到要删除的节点\n while (curr->next != *head) {\n m--;\n prev = curr;\n curr = curr->next;\n\n if (m == 0) {\n break;\n }\n }\n\n // 如果删除的是头节点\n if (prev == NULL) {\n prev = *head;\n while (prev->next != *head) {\n prev = prev->next;\n }\n *head = curr->next;\n prev->next = *head;\n } else {\n prev->next = curr->next;\n }\n\n free(curr);\n}\n\n// 打印约瑟夫环链表\nvoid printJosephusCircle(Node* head) {\n Node* curr = head;\n\n printf("Josephus Circle: ");\n\n do {\n printf("%d ", curr->data);\n curr = curr->next;\n } while (curr != head);\n\n printf("\n");\n}\n\nint main() {\n int n = 15;\n int m = 3;\n\n Node* head = buildJosephusCircle(n);\n\n for (int i = 0; i < n - 1; i++) {\n deleteNode(&head, m);\n }\n\n printJosephusCircle(head);\n\n free(head);\n\n return 0;\n}\n\n\n这个程序首先使用 buildJosephusCircle 函数构建了一个包含 n 个节点的约瑟夫环链表。然后使用 deleteNode 函数在约瑟夫环链表中删除第 m 个节点，直到只剩下一个节点为止。最后使用 printJosephusCircle 函数打印出最后剩下的节点。\n\n运行上述代码，输出结果为：\n\n\nJosephus Circle: 9\n\n\n这表明在15个人围成环的约瑟夫环问题中，最后剩下的人的编号为9。