插入双向链表时C内存泄漏

Question

您好，我是 C 语言和指针的新手，在尝试实现以下双向链表结构时遇到了问题。我相信 listInsertEnd 发生内存泄漏？我很困惑为什么一个工作（至少输出中没有内存泄漏）而另一个不工作。我只粘贴了部分程序，非常感谢任何帮助或解释。

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

typedef struct node *Node;
struct node {
    int value;
    Node next;
    Node prev;
};

typedef struct list *List;
struct list {
    Node first;
    Node last;
    int count;
};

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) fprintf(stderr, "couldn't create new node\n");
    n->value = value;
    n->next = NULL;
    n->prev = NULL;
    return n;
}

void listInsertEnd(List newList, int value) {
    Node n = newNode(value);

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }
    nList->count++;
}

Answer 1

这个 typedef 声明

typedef struct node *Node;

令人困惑，风格不佳。例如考虑这个语句

Node n = malloc(sizeof(*n));

有人会认为这是一个错字，应该这样写

Node *n = malloc(sizeof(*n));

函数

void listInsertEnd(List newList, int value) {
    Node n = newNode(value);

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }
    nList->count++;
}

有未定义的行为。如果 newList 等于 NULL，那么您正在尝试使用空指针指向的内存。

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

并且最初数据成员newList->first和newList->last可以等于NULL。这也可能是未定义行为的原因，因为函数没有考虑到这一点。

在更改函数 listInsertEnd 之前，您应该按以下方式定义函数 newNode

Node newNode(int value) 
{
    Node n = malloc(sizeof(*n));

    if ( n != NULL )
    {
        n->value = value;
        n->next = NULL;
        n->prev = NULL;
    }

    return n;
}

该函数不应发出任何消息。如果需要，由函数的调用者决定是否发出消息。

在这种情况下函数listInsertEnd可以写成下面的方式

int listInsertEnd(List newList, int value) 
{
    Node n = newNode(value);
    int success = n != NULL;

    if ( success )
    {
        n->prev = newList->last;  

        if ( newList->first == NULL )
        {
            newList->first = newList->last = n;
        }
        else
        {
            newList->last = newList->last->next = n;
        }

        ++newList->count;
    }

    return success;
}

在 main 中，您应该按以下方式创建列表

int main( void )
{
    struct list list1 = { .first = NULL, .last = NULL, .count = 0 };
    // or
    // struct list list1 = { NULL, NULL, 0 };

并像

那样调用函数

listInsertEnd) &list1, some_integer_value );

Answer 2

首先说一下内存泄漏：你的代码中没有直接的内存泄漏。如果泄漏发生在某处，则它在这些功能之外。这很可能是因为您创建了一个或多个节点，然后忘记 free() 它们，但这与您显示的两个功能无关。

我看到您正在使用 typedef 来声明简单的指针类型，看看这个问题和答案以了解为什么这是不好的做法并且应该避免：Is it a good idea to typedef pointers?. Also, this particular piece 的 Linux 内核文档，其中更详细地解释了该问题。

其次，您显示的代码中的真正问题是您在测试它们无效后使用了指针 (NULL)。

这里：

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) fprintf(stderr, "couldn't create new node\n");
    n->value = value;
//  ^^^^^^^^ BAD!

还有这里：

if (newList== NULL) {
    newList->first = newList->last = n;
//  ^^^^^^^^^^^^^^ BAD!

如果某物是 NULL，则您不能取消引用它。将您的函数更改为在检测到无效指针后安全中止。

这可以通过多种方式完成。这是正确代码的示例：

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) {
        fprintf(stderr, "couldn't create new node\n");
        return NULL;
    }

    n->value = value;
    n->next = NULL;
    n->prev = NULL;
    return n;
}

void listInsertEnd(List newList, int value) {
    Node n;

    if (newList == NULL) {
        return;
        // You probably want to return some error value here.
        // In that case change the function signature accordingly.
    }

    n = newNode(value);

    if (newList->count == 0) {
        newList->first = newList->last = n;
    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }

    newList->count++;
}

注意：检查 newList->count == 0 假设您在 adding/removing 元素时正确 increment/decrement 计数。

插入双向链表时C内存泄漏

C memory leak when inserting into a doubly linked list

c

struct

linked-list

singly-linked-list