1

我打算使用链表解决 C 中的约瑟夫斯问题，但它不起作用。我已经尝试了多种方法来做到这一点，所以我很困惑。

#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, q;

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

    p = (PtrToNode)malloc(sizeof(struct Node));
    p->num = 1;
    p->Next = p;

    for (i = 2; i <= n; i++) {
        q = (PtrToNode)malloc(sizeof(struct Node));
        q->num = i;
        q->Next = p;
        p->Next = q;
        p = q;
    }

    while (q->Next != q) {
        for (i = 1; i <= m; i++)
            p = q->Next;
        q = p;
        printf("%d, ", q->num);
        p->Next = NULL;
        free(q);
    }
    printf("%d\n", p->num);
    free(p);
    //system("pause");
    return 0;
}

我有点理解 struct 函数和 typedef，所以我想我在那里没有任何问题（？）。我猜我在主函数中犯了一个错误。

4

1 回答 1

0

一些问题：

  • 第一个循环中的以下分配创建了一个长度始终为 2 的循环：

    q->Next = p;
p->Next = q;

    目的是链接回第一个节点，但您不再引用第一个节点，只有前一个 ( p)。所以引入另一个不会移动的变量：head，然后用q->next=head. 实际上，您可以在循环之后执行此操作，仅针对添加的最后一个节点。

  • 在下一个循环中，在for循环内部，以下内容将在每次迭代中执行相同的操作：

    p = q->Next;

    由于q没有移动，这只会导致在p每次迭代中分配相同的值。这样做会更有意义q = q->Next

  • 您的代码没有正确分离要删除的节点。它只是在那里结束列表：

    p->Next = NULL;

    这没有考虑到前面还有一个节点p仍在引用p. 实际上，需要重新布线的是前面的节点。因此，您实际上希望前面的循环提前一步停止，因此您可以引用前面的 node q，然后执行以下操作：

    p = q->Next; // p will be deleted
q->Next = p->Next; // Rewiring around p

这是更正后的main：

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

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

    head = (PtrToNode)malloc(sizeof(struct Node));
    head->num = 1;

    p = head;
    for (i = 2; i <= n; i++) {
        q = (PtrToNode)malloc(sizeof(struct Node));
        q->num = i;
        p->Next = q;
        p = q;
    }
    p->Next = head;

    while (q->Next != q) {
        for (i = 1; i < m; i++)
            q = q->Next;
        p = q->Next;
        printf("%d, ", p->num);
        q->Next = p->Next;
        free(p);
    }
    printf("%d\n", q->num);
    free(q);
    return 0;
}
于 2021-10-13T17:22:45.267 回答