循环链表插入两个后只有一个元素

Question

我正在尝试实现一个循环链表，但它没有像我预期的那样工作。即使我使用 insertAfter 插入两个元素，printList 也只打印一个节点。这是一个最小的例子:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct dnode_elm {
    int item;
    struct dnode_elm *next, *prev;
};

struct dnode_elm *
insertAfter(struct dnode_elm *a, int value) {
    struct dnode_elm *v= malloc(sizeof(struct dnode_elm));
    v->item=value;
    a->next=v;
    v->prev=a;
    v->next=a->next;
    a->next->prev=v;
    return v;
}

void
printList(struct dnode_elm *h) {
    while (h != h->next) {
        h = h->next;
        printf("%d --> ",h->item);
    }
}

int
main(void) {
    struct dnode_elm h = { INT_MAX, &h, &h };
    insertAfter(&h, 1);
    insertAfter(&h, 2);
    printList(&h);
}

Answer 1

你的插入逻辑是错误的。

a->next=v;
v->prev=a;
v->next=a->next;
a->next->prev=v;

在这一系列代码之后，v->next 等于v，这可能不是您想要的。

一个可能的解决方法是先分配v 的指针，然后再修复v 周围的节点。

v->prev = a;
v->next = a->next;
v->next->prev = v;
v->prev->next = v;

举例说明:

---

在 a 之后插入 v。

---

设置v->next和v->prev。

---

设置v->next->prev和v->prev->next。

---

但是，您也可以通过将第一个分配移到最后一个来重新安排代码中的分配。

v->prev=a;
v->next=a->next;
a->next->prev=v;
a->next=v;

这允许对 a->next->prev 的分配按您预期的方式工作。

---

此外，您的打印逻辑存在缺陷。您需要记住初始列表指针是什么，以便您可以正确检测到何时到达末尾。

void *start = h;
while (start != h->next) {
    h = h->next;
    printf("%d --> ",h->item);
}