c - 双向链表没有正确创建

Question

我试图在 C 中创建一个双向链表，但它不起作用，我也不知道为什么。它只打印我介绍的最后一个元素。我在创建列表的代码部分没有看到任何问题。也许你能看到它？

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

typedef struct node
{
    int data;
    struct node *next;
    struct node *prev;
}NodeT;

struct d_linked_list
{
   NodeT *first;
   NodeT *last;
};

int main()
{
    int d;
    struct d_linked_list *l;
    NodeT *p,*q;
    p=(NodeT*)malloc(sizeof(NodeT));
    q=(NodeT*)malloc(sizeof(NodeT));
    l->first=NULL;
    l->last=NULL;
    while (fscanf(stdin,"%d",&d)!=EOF)
    {
        p->data=d;
        if (l->first==NULL)
        {
            l->first=p;
            l->last=p;
            p->next=NULL;
            p->prev=NULL;
        }
        else
        {
            l->last->next=p;
            p->prev=l->last;
            l->last=p;
        }
    }
    l->last->next=NULL;
    for (q=l->first;q!=NULL;q=q->next)
        printf("%d ",q->data);
    return 0;
}

Answer 1

像往常一样，有很多问题，其中一些已经在其他答案或评论中发现，还有一些(我认为)以前没有发现:

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

typedef struct node
{
    int data;
    struct node *next;
    struct node *prev;
}NodeT;

struct d_linked_list
{
   NodeT *first;
   NodeT *last;
};

到目前为止，还不错。

int main()
{
    int d;
    struct d_linked_list *l;

您没有为l 分配空间。使用起来可能更简单(因此可能更好):

struct d_linked_list head;  // Or maybe list instead of head

然后在你的代码中引用head而不是l；您也可以使用 l = &head; 而无需进一步更改。

    NodeT *p,*q;
    p=(NodeT*)malloc(sizeof(NodeT));
    q=(NodeT*)malloc(sizeof(NodeT));

您永远不会使用分配给 q 的空间，您最终会覆盖它，从而导致泄漏。您应该检查 malloc() 是否工作，如果失败则做一些适当的事情(停止并显示错误消息？)。

    l->first=NULL;
    l->last=NULL;
    while (fscanf(stdin,"%d",&d)!=EOF)

您应该使用 while (fscanf(stdin, "%d", &d) == 1) 检查您是否得到一个整数；循环在 EOF 或转换失败时中断。

    {
        p->data=d;

您在循环之前分配了 p，但每个后续条目都覆盖了相同的空间。您需要为读取的每个值分配一个新节点。 (这之前并未被确定为问题——尽管我在输入我的代码时看到 Filipe Gonçalves 将其添加到他的 answer 中。)

        if (l->first==NULL)
        {
            l->first=p;
            l->last=p;
            p->next=NULL;
            p->prev=NULL;
        }
        else
        {
            l->last->next=p;
            p->prev=l->last;
            l->last=p;
        }
    }

从表面上看，上面的代码看起来还不错；我没有运行它，所以可能存在我没有发现的问题。

正如 Filipe 指出的那样，我注意到“未彻底检查”并且确实存在问题。 if 子句是可以的，我认为，但是else 子句需要设置p->next = NULL;。一般来说，完全创建节点是个好主意:p->data = d; p->下一个=空； p->prev = NULL: 然后将节点hook到链表中。

    l->last->next=NULL;

这一行应该是不必要的。在循环的每个循环结束时，列表应该正确形成。测试这一点的一种方法是在每个循环中打印出列表的内容(使用函数)。您还可以使用该函数代替后面的循环。我经常使用的一个界面设计是:

void dump_list(FILE *fp, char const *tag, struct d_linked_list const *list)

在给定的文件流上打印识别标签和列表的内容。我为每个重要的数据结构保留了这样的函数，以便以后更容易调试。

    for (q=l->first;q!=NULL;q=q->next)

这个循环丢失了分配给 q 的空间。

        printf("%d ",q->data);

你应该在某个时候输出一个换行符。

您还应该完成释放所有分配空间的 Action ，只是为了确保您知道如何做到这一点。当你要退出一个程序时，这并不重要，但如果你在一个长时间运行的程序中使用该列表，该程序每分钟需要一个列表，然后关闭并执行不相关的操作，那么你会泄漏所有内存，您的长时间运行的程序将在一段时间后停止运行，因为它缺少必要的内存(因为它泄漏了——浪费了——列表中的内存)。

    return 0;
}