约瑟夫环问题 C 语言实现 - 代码详解 - 常规

"创建一个JosephusCircle，返回一个指向头节点的指针。首先创建头节点，然后用prev指针记录当前节点的前一个节点，循环创建n-1个节点，并将前一个节点的next指针指向当前节点。最后将最后一个节点的next指针指向头节点，形成一个环。"\n\nc\nNode* createJosephusCircle(int n) {\n Node* head = createNode(1);\n Node* prev = head;\n \n for (int i = 2; i <= n; i++) {\n Node* newNode = createNode(i);\n prev->next = newNode;\n prev = newNode;\n }\n \n prev->next = head; // 将最后一个节点的下一个节点指向头节点，形成环\n \n return head;\n}\n\n\n2. "josephus函数接受两个参数n和k，分别表示参与游戏的人数和每次数到的数字。首先调用createJosephusCircle函数创建一个环形链表。然后用curr指针指向头节点，prev指针初始化为NULL。"\n\nc\nvoid josephus(int n, int k) {\n Node* head = createJosephusCircle(n);\n Node* curr = head;\n Node* prev = NULL;\n \n while (n > 1) {\n for (int i = 1; i < k; i++) {\n prev = curr;\n curr = curr->next;\n }\n \n prev->next = curr->next;\n Node* temp = curr;\n curr = curr->next;\n free(temp);\n n--;\n }\n \n printf("The last person standing is: %d\n", curr->data);\n free(curr);\n}\n\n\n3. "使用while循环，当还剩下一个节点时结束循环。在循环中，首先使用for循环将curr指针移动到第k个节点的位置，并用prev指针记录curr指针的前一个节点。"\n\nc\nwhile (n > 1) {\n for (int i = 1; i < k; i++) {\n prev = curr;\n curr = curr->next;\n }\n\n prev->next = curr->next;\n Node* temp = curr;\n curr = curr->next;\n free(temp);\n n--;\n}\n\n\n4. "将prev节点的next指针指向curr节点的下一个节点，即跳过curr节点。"\n\nc\nprev->next = curr->next;\n\n\n5. "创建一个temp指针指向curr节点，然后将curr指针移动到下一个节点。"\n\nc\nNode* temp = curr;\ncurr = curr->next;\n\n\n6. "释放temp指针指向的节点，并将n减1。"\n\nc\nfree(temp);\n n--;\n\n\n7. "循环结束后，打印剩下的最后一个节点的data值，即为最后留下的人。"\n\nc\nprintf("The last person standing is: %d\n", curr->data);\n\n\n8. "释放最后剩下的节点。"\n\nc\nfree(curr);\n