C语言用链表+malloc实现约瑟夫环(Josephus problem)代码报错求助

问题定位 #

你的代码核心错误集中在链表遍历、节点删除两个核心逻辑，具体错误如下：

• 步长遍历逻辑错误：原代码中for (i = 1; i <= m; i++) p = q->Next; 每次仅将p赋值为q的下一个节点，没有更新指针位置向前移动，m次循环后p永远指向同一个节点，完全没有实现数m个节点的效果
• 节点删除逻辑错误：删除节点时没有将前驱节点的Next指针指向待删节点的后继，直接将p->Next设为NULL后释放节点，直接打断了循环链表的结构，后续遍历必然崩溃
• 初始指针位置错误：循环链表构造完成后没有对齐遍历起始位置，第一次计数的起始节点不符合约瑟夫环的规则

修正后可运行代码 #

#include "stdlib.h"
#include "stdio.h"

struct Node {
    int num;
    struct Node *Next;
};

typedef struct Node *PtrToNode;

int main() {
    int n, m, i;
    PtrToNode p, prev;

    printf("Please input n, m\n");
    scanf("%d %d", &n, &m);

    // 构造循环链表
    p = (PtrToNode)malloc(sizeof(struct Node));
    p->num = 1;
    p->Next = p;
    prev = p;

    for (i = 2; i <= n; i++) {
        PtrToNode new_node = (PtrToNode)malloc(sizeof(struct Node));
        new_node->num = i;
        new_node->Next = p;
        prev->Next = new_node;
        prev = new_node;
    }
    // 此时prev指向最后一个节点，p指向第一个节点，作为遍历起始位置

    while (prev != p) { // 只剩一个节点时前驱等于自身，循环终止
        // 向后数m-1步，p即为待删除节点
        for (i = 1; i < m; i++) {
            prev = p;
            p = p->Next;
        }
        printf("%d, ", p->num);
        prev->Next = p->Next; // 拼接链表跳过待删节点
        free(p);
        p = prev->Next; // 下一轮计数从待删节点的下一个开始
    }
    // 输出最后剩下的节点
    printf("%d\n", p->num);
    free(p);
    return 0;
}

核心修改说明 #

• 新增prev指针专门保存当前节点的前驱，删除节点时直接修改前驱的Next指针即可维持链表结构
• 遍历步长调整为m-1步，符合约瑟夫环“从当前节点数1，数到m出局”的规则
• 循环终止条件调整为prev != p，仅剩一个节点时自动退出循环

内容的提问来源于stack exchange，提问作者jonathan kevin