C中的单向链表

Question

我正在学习算法，我用C编写了单向链表实现，我需要对代码中可以改进的内容进行代码回顾，并且我希望确保没有可能的内存泄漏。

代码：

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

struct node {
    int data;
    struct node *next;
};

void push_back(struct node *node, int data) {
    while (node->next != NULL) {
        node = node->next;
    }
    node->next = malloc(sizeof(struct node));
    node->next->data = data;
}

int pop_back(struct node *node) {
    int data;
    if (node->next == NULL) {
        data = node->data;
        free(node);
        return data;
    }
    while (node->next->next != NULL) {
        node = node->next;
    }
    data = node->next->data;
    free(node->next);
    node->next = NULL;
    return data;
}

void push_front(struct node **node, int data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = *node;
    *node = new_node;
}

int pop_front(struct node **node) {
    struct node *tmp = (*(node))->next;
    int data = (*(node))->data;
    free(*node);
    *node = tmp;
    return data;
}

int contains(struct node *node, int data) {
    while (node->next != NULL) {
        if (node->data == data) {
            return 1;
        }
        node = node->next;
    }
    return 0;
}

int count(struct node *node, int data) {
    int count = 0;
    while (node->next != NULL) {
        if (node->data == data) {
            ++count;
        }
    }
    return count;
}

int get_elem(struct node *node, int offset) {
    int i = 0;
    while (node->next != NULL && i < offset) {
        node = node->next;
        ++i;
    }
    return node->data;
}

struct node *init_list(int data) {
    struct node *list = malloc(sizeof(struct node));
    list->data = data;
    list->next = NULL;
    return list;
}

void free_list(struct node *node) {
    while (node->next != NULL) {
        struct node *tmp = node;
        node = node->next;
        free(tmp);
    }
}

void print_list(struct node *node) {
    int i = 0;
    while (node != NULL) {
        printf("offset %d: %d\n", i, node->data);
        node = node->next;
        ++i;
    }
}

int main(int argc, char *argv[]) {
    struct node *node = init_list(10);
    push_back(node, 20);
    push_back(node, 30);
    push_back(node, 40);
    print_list(node);
    pop_back(node);
    print_list(node);
    // test other functions
    free_list(node);
    return 0;
}

Answer 1

Bug

测试代码更好。

int count(struct node *node, int data) {
    int count = 0;
    while (node->next != NULL) {
        if (node->data == data) {
            ++count;
        } 
        // !! Missing code to advance pointer!!
    }
    return count;
}

检测错误用法

有点问题，但在调试模式中很有用。

在释放之前，考虑破坏内存，以便更有可能在以后释放内存的使用中造成麻烦。

#ifndef NDEBUG
node->data = 42;
node->next = some_bad_pointer;  // e.g. (void*)0xDEADBEEF
#endif
free(node);

避免错误调整

大小

不要分配到类型的大小。分配到已记录数据的大小。更容易编写正确的代码，检查和维护。

// node->next = malloc(sizeof(struct node));
node->next = malloc(sizeof node->next[0]);

列表可能为空

int pop_front(struct node **node) (和其他人)假设*node不是NULL。避免那样做。

int pop_front(struct node **node) {
    if (*node == NULL) {
      ; // Handle error with TBD code
    } 
    ...

当列表没有更改时，请使用const

// int count(struct node *node, int data) {
int count(const struct node *node, int data) {

为什么是int长度？

关于列表长度，为什么int？int至少是合理的，但是unsigned，size_t值得考虑。

认为bool为真/假，如代码

bool比int更好地传达了功能的目标。

// int contains(struct node *node, int data) {
#include <stdbool.h>
bool contains(struct node *node, int data) {

散名空间

代码使用像node, contains, count这样的名称，这些名称肯定会与其他代码发生冲突。在名称空间中划出一个角落，也许用zp_node, zp_contains, zp_count, zp_...。

下一步

将代码分段为.c、.h和main.c文件。

举个例子。注意，struct ll_node_s的成员不是在这里编码的-只是在ll.c文件中。

#ifndef LL
#define LL 1

  typedef struct ll_node_s ll_node;
  int ll_pop_back(ll_node *node);
  void ll_push_back(ll_node *node, int data);
  ...

#endif

编辑：push_back()，pop_back()性能改进

这两个函数用O(n)时间遍历列表。然而，一个单链列表可以使用O(1)来处理其中的一个，而不会产生更多的存储。

示例:不是指向指向NULL的第一个节点和最后一个节点的链接列表，而是让链接列表指向最后一个节点，最后一个节点指向第一个节点。使用循环链表，通过与开始匹配来确定结束。

然后，push_back()类似于push_front()：O(1)。它们在更新链接列表指针方面存在差异.

这种方法的真正成本是要找到前端需要额外的->操作。

副作用：peek_back() (报告最终数据)的成本是O(1)而不是O(n)。peek_front()仍为O(1)。

Answer 2

想想那些失败的案例。例如：

struct节点*list = malloc(sizeof(struct节点))；list->data = data；list->next = NULL；返回列表；

如果malloc()失败，那么list将包含一个空指针，并且访问list->data和list->next是未定义的行为(这意味着我们不能就代码所做的事情做任何声明)。

我们在这里需要防御性，例如：

struct node *list = malloc(sizeof *list);
if (list) {
    list->data = data;
    list->next = NULL;
}
return list;

在调用函数时，我们还需要进行防御，因为它可以返回一个空指针：

int main(void)
{
    struct node *node = init_list(10);
    if (!node) {
        return EXIT_FAILURE;
    }
    push_back(node, 20);
    ⋮

Answer 3

您可能会考虑将struct node缩写为typedef名称：

typedef struct node {
    int data;
    struct node *next;
} *list;

以上这些将使list成为一个struct node *。虽然经常会看到typedef没有指针，并且等于struct名称。

malloc's的结果必须进行测试-如果内存不足，则为空.

除此之外，以下是完美的：

void push_front(struct node **node, int data) { ...

int pop_front(struct node **node) {
    struct node *tmp = (*node)->next;
    int data = (*node)->data;
    free(*node);
    *node = tmp;
    return data;
}

像push_back这样的其他函数不允许为空列表(一个空节点)调用。似乎您希望始终在列表中包含至少一个元素。不是个好主意。

void push_back(struct node **node, int data) {
    while (*node != NULL) {
        node = &(*node)->next;
    }
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = *node;
    *node = new_node;
}

在push_back中，变量node要么是传递的列表指针的别名，要么是next字段的别名。

int pop_back(struct node **node) {
    if (*node == NULL) {
        return 0; // Error
    }
    while ((*node)->next != NULL) {
        node = &(*node)->next;
    }
    int data = (*node)->data;
    free(*node);
    *node = NULL;
    return data;
}

同样，使用别名pop_back也很简单。

bool contains(struct node *node, int data) {
    while (node != NULL) {
        if (node->data == data) {
            return true;
        }
        node = node->next;
    }
    return false;
}

这是一个品味的问题，但是布尔人为代码添加了更多的语义信息，使用它。

int count(struct node *node, int data) {
    int count = 0;
    while (node != NULL) {
        if (node->data == data) {
            ++count;
        }
        node = node->next;
    }
    return count;
}

再一次统计一下，next太多了。get_elem也是如此。

int get_elem(struct node *node, int offset) {
    int i = 0;
    while (node != NULL && i < offset) {
        node = node->next;
        ++i;
    }
    if (node == NULL) {
        ...
    }
    return node->data;
}

struct node *init_list() {
    return null;
}

void free_list(struct node **node) {
    while (*node != NULL) {
        struct node *tmp = node;
        *node = &(*node)->next;
        free(tmp);
    }
}

free_list可以将其传递的变量设置为NULL，因此没有悬空指针。

void print_list(struct node *node) {
    puts("[");
    for (int i = 0; node != NULL; ++i) {
        if (i != 0) {
            puts(", ");
        }
        printf("%d: %d", i, node->data);
        node = node->next;
    }
    printf("]\n");
}

列表打印应该为空列表打印一些内容。我给它做了一个衬垫。