用C写的链表

Question

我一直在学习C中的数据结构和动态内存分配，作为一种学习经验，我编写了这个链接列表实现。我非常感谢我收到的关于我在这里发布的前一段代码的反馈，并希望听到你们对我可以对此做出的改进提出的任何建议。

我对设计进行了抽象，以实践“不透明指针”的使用，并对代码中的每个函数进行了详细的注释和描述。所有函数的测试都在main.c中进行。

下面是源文件和CMakeLists文件(其中包括启用了许多运行时Clang消毒液)。或者，可以使用以下方法轻松编译代码：cc *.c -o linkedlist && ./linkedlist

linkedlist.h

#ifndef DATASTRUCTURES_LINKEDLIST_H
#define DATASTRUCTURES_LINKEDLIST_H

// Incomplete type used for "opaque pointer"
struct Node;

/*
 * I typedef this struct for ease of use in the header file.
 * There are both benefits and harms from assigning a typedef
 * to a struct but in this scenario I see more benefits.
 */
typedef struct Node Node;

/**
 * Get node value (caller is responsible for ensuring node isn't NULL)
 * @param node
 * @return int value
 */
int get_node_val(const Node *node);

/**
 * Set node value (caller is responsible for ensuring node isn't NULL)
 * @param node
 * @param val - int value
 */
void set_node_val(Node *node, int val);

/***
 * Allocates memory for a node, and assigns data to the new node
 * @param data - integer to store in the new node
 * @return newly allocated node
 */
Node *create_node(int data);

/**
 * Appends a node to the end of the linked list
 * @param head - first node
 * @param to_add - node to add
 * @return head node
 */
Node *append_node(Node *head, Node *to_add);

/**
 * Prepends a node to the beginning of the linked list
 * @param head  - first node
 * @param to_add - node to add (becomes the new first node)
 * @return head node - should be reassigned to head
 */
Node *prepend_node(Node *head, Node *to_add);

/**
 * Searches for a value in the linked list
 * @param head - first node
 * @param search_val - value to search for
 * @return instance of node if it exists, or NULL if it doesn't exist
 */
Node *search_node(const Node *head, int search_val);

/**
 * Deletes the first occurence of "delete_val" from the linked list
 * @param head - first node
 * @param delete_val - value to delete from the linked list (may be head node)
 * @return head node - should be reassigned to head in case of first node being deleted
 */
Node *delete_node(Node *head, int delete_val);

/**
 * Prints each node in the linked list
 * @param head - first node to start traversing from
 */
void print_all(const Node *head);

/**
 * Frees all member of the linked list
 * @param head - first node to start traversing from
 */
void free_all(Node *head);

#endif //DATASTRUCTURES_LINKEDLIST_H

linkedlist.c

#include 
#include "linkedlist.h"
#include "utils.h"

struct Node {
    int value;
    struct Node *next;
};

int get_node_val(const Node *node) {
    return node->value;
}

void set_node_val(Node *node, int val) {
    node->value = val;
}

static size_t node_size(void) {
    return sizeof(struct Node);
}

static void *allocate_node(void) {
    return malloc(node_size());
}

Node *create_node(int data) {
    Node *new_node;
    if ((new_node = allocate_node()) == NULL) {
        gracefully_handle_failure();
    }
    new_node->value = data;
    new_node->next = NULL;
    return new_node;
}

Node *append_node(Node *head, Node *to_add) {
    if (head == NULL) {
        return NULL;
    }
    Node *current = head;
    while (current->next) {
        current = current->next;
    }
    // At the end, now let's add our new node
    current->next = to_add;
    to_add->next = NULL;
    return head;
}

Node *prepend_node(Node *head, Node *to_add) {
    to_add->next = head;
    head = to_add;
    return head;
}

Node *search_node(const Node *head, int search_val) {
    for (const Node *current = head; current != NULL; current = current->next) {
        if (current->value == search_val) {
            return (Node *) current;
        }
    }
    return NULL;
}

Node *delete_node(Node *head, int delete_val) {
    // Taken from "Linus Torvalds - The mind behind Linux" Ted Talk
    // https://youtu.be/qrYt4bbEUrU
    Node **indirect = &head;
    while ((*indirect)->value != delete_val)
        indirect = &(*indirect)->next;

    *indirect = (*indirect)->next;
    return head;
}

void print_all(const Node *head) {
    for (const Node *current = head; current != NULL; current = current->next) {
        printf("%d -> ", current->value);
    }
    puts("NULL");
}

void free_all(Node *head) {
    for (Node *current = head; current != NULL; current = current->next) {
        free(head);
    }
}

main.c

#include 
#include 
#include "linkedlist.h"

int main() {
    // These are simply tests for the Linked List
    Node *head = create_node(12);
    // Add 20 after head node (12)
    append_node(head, create_node(20));
    // 12 -> 20 -> NULL
    // Prepend 30 before head node (12)
    head = prepend_node(head, create_node(30));
    printf("Head is %d\n", get_node_val(head));
    set_node_val(head, 32);
    // 32 -> 12 -> 20 -> NULL
    print_all(head);
    head = delete_node(head, 32);
    // 12 -> 20 -> NULL
    if (search_node(head, 20)) {
        printf("%d found\n", 20);
    }
    print_all(head);
    free_all(head);
    return EXIT_SUCCESS;
}

CMakeLists.txt

# Improved version adapted from https://codereview.stackexchange.com/a/210770/78786
cmake_minimum_required(VERSION 3.13)
project(DataStructures C)

add_executable(${CMAKE_PROJECT_NAME} main.c linkedlist.c linkedlist.h utils.c utils.h)

set(CMAKE_C_COMPILER clang)
target_compile_features(${CMAKE_PROJECT_NAME} PRIVATE c_std_99)
target_compile_options(${CMAKE_PROJECT_NAME} PRIVATE
        $<$:
        -Weverything
        -fsanitize=undefined,integer,implicit-conversion,nullability,address,leak,cfi
        -flto
        -fvisibility=default>)
target_link_options(${CMAKE_PROJECT_NAME} PRIVATE
        $<$:
        -fsanitize=undefined,integer,implicit-conversion,nullability,address,leak,cfi
        -flto>)

Answer 1

我的评论集中在linkedlist.c上：

• 有些函数不检查空指针(get_node_val、set_node_val)。在文档中，其他函数也会检查空指针。
• 要追加和预置节点的函数要求调用方调用该函数来创建节点。在函数中创建节点并返回新创建的节点可能是一个更好的主意。
• 函数append不返回新节点，而函数prepend返回。
• 数据只能是一个整数；在列出的数据上有一个空指针允许有任何类型的数据。但是，此更改将使您的搜索功能不可用。
• 打印数据是处理数据的一种方法。这似乎是打电话者的角色。
• 您可能需要考虑使用一个函数来返回列表的长度。

Answer 2

数据只能是一个整数；在列出的数据上有一个空指针允许有任何类型的数据。..。

我认为搬到void*是一个很好的建议。如果你想继续做你的代码库的话，这是一个很好的下一步。

..。但是，此更改将使您的搜索功能不可用。

要使搜索函数在void*中可用，最有意义的是将比较功能卸载到消费者提供的函数中。这就是posix氏bsearch功能的工作方式：

int (*compar)(const void *, const void *)

手册页解释说

compar例程应该有两个参数，它们按照这个顺序指向键对象和数组成员，如果发现键对象小于、匹配或大于数组成员，则应该返回小于、等于或大于零的整数。

这种做法是有道理的。如果您不知道列表中对象的类型，就无法比较它们，这是消费者必须为您做的事情。传递函数指针是一种非常标准的方法；Q排序的工作方式也是一样的。

Answer 3

与使用void*或函数指针不同，我认为标记的联合也将提供一种安全的方式来允许更灵活的节点数据。

使用标记的联合将确保只分配最大元素的大小，再加上任何需要的填充，以将长度提高到对齐边界(参考手册，第5版，Sec )。5.7.2，第162页。使用相应的枚举，在遍历链接列表时可以访问适当的数据。可以为每种受支持的类型使用不同的函数来实现搜索。

下面是一个简单的示例，可以用3种类型来说明：

enum Tag {
    INT_TYPE, FLOAT_TYPE, STRING_TYPE
};

struct Node {
    enum Tag tag;
    union {
        int int_val;
        float float_val;
        char* string_val;
    };
    struct Node *next;
};

/* Searching methods which would take an argument and traverse the list,
accessing data based on the type specified in the enum */