c - 删除第一个节点后向后遍历 DLL

Question

我使用有效的插入方法设置了双向链表。 使用这个结构:

struct NODE
{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
 };
typedef struct NODE Node;

这个初始化:

void initializeList(Node *rt)
{
    rt->fwd = NULL;
    rt->bwd = NULL;
    rt->value = 0;
}

我的主要功能是:

main()
{
    Node root;
    int j;
    initializeList(&root);
    for (j = 0; j < 15; j++)
        insertFirst(&root, j);
    printf("The list traversed forward \n");
    traverseForward(root);
    printf("\n");
    printf("The list traversed backward \n");
    traverseBackward(root);
    printf("\n");
    printf("After first deletion traverse forward\n");
    deleteFirst(&root);
    traverseForward(root);
    printf("\n");
    printf("After first deletion traverse backwards\n");
    printf("\n");
    traverseBackward(root);
}

我的 deletefirst 函数是:

void deleteFirst(Node *rt)
{
    Node *newnode = rt;
    Node *tmp = NULL;
    if (newnode != NULL)
    {
        if (newnode->fwd != NULL)
        {
            newnode = newnode->fwd;
            tmp = newnode->bwd;
            *rt = *newnode;
        }
        else
            tmp = newnode;
    }
    free(tmp);
    }

插入函数:

int insertFirst(Node *rt, int val)
{
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) return 0;
    node->value = val;
    /* For a previously empty list */
    if (rt->fwd == NULL)
    {
        rt->fwd = node;
        rt->bwd = node;
        node->fwd = NULL;
        node->bwd = NULL;
    }
    /* For a list with at least one node */
    else
    {
        /* previous first node now new node's successor */
        rt->fwd->bwd = node;
        node->fwd = rt->fwd;
        /* no predecessor to the new first node */
        node->bwd = NULL;
        /* root points to this new first */
        rt->fwd = node;
    }
    return 1;
}

遍历函数:

void traverseForward(Node root)
{
    Node *q = root.fwd;
    while (q)
    {
        printf("%d ", q->value);
        q = q->fwd;
    }
}
void traverseBackward(Node root)
{
    Node *q = root.bwd;
    while (q)
    {
        printf("%d ", q->value);
        q = q->bwd;
    }
}

系统打印出向前遍历的列表

14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

系统打印出向后遍历的列表

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 

先删除正向遍历后

13 12 11 10 9 8 7 6 5 4 3 2 1 0

先删除后向遍历

(什么都不打印)

我不知道如何调整指针以使其正常工作。

Answer 1

我认为问题是因为您将指向列表开头和结尾的头指针和尾指针存储在根节点中，然后将其与列表的实际节点互换地混合在一起的方式很奇怪。如果您只有简单的 Node *head 和 Node *tail 指针，就可以消除这种混淆，但这只是一个建议。

在您的删除函数中，您将根节点有效地设置为 rt->fwd，这对于正向遍历来说很好，因为 rt->fwd->fwd 就是是需要的，但是您忘记考虑 rt->fwd->bwd 的值，它始终指向列表中第一项的 NULL(因为从技术上讲，该节点之前没有任何内容)，而不是列表的实际尾部，这是该逻辑所需的功能。

当您尝试使用它向后迭代时，这显然会导致问题，因为它认为列表是空的。您应该将删除代码更改为如下所示:

void deleteFirst(Node *rt)
{
  if (rt == NULL)
  {
    return; /* Return if an invalid root was passed in */
  }

  if (rt->fwd == NULL) {
    return; /* Return if the list is already empty */
  }

  Node *tmpfwd = rt->fwd; /* Store the current "head" */

  rt->fwd = rt->fwd->fwd; /* Set the root's head to the current head's next node */
  rt->fwd->bwd = NULL; /* Set the new head's previous node to NULL as it is the start of the list */

  free(tmpfwd); /* Delete the old "head" */
}

关于边缘情况和评论中提到的事情，这里还有很多其他问题(只是整体设计使这个问题非常严重)，但我认为这是您目前遇到的问题。