圆形链表在插入两个后只有一个元素

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;

为了显示:

插入v后a.

设置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);
}