基本链表C的实现

Question

我已经写了一张单列的字符。这是我的第三个C程序，我想要一些反馈，我可以在任何方面改进。

如果你想直接看看回购，它就在这里：

https://github.com/JosephSBoyle/LinkedList

谢谢您的时间:D

linked_list.h

#include 

// define the node struct here so we can use it within it's own definition
typedef struct Node Node;

struct Node {
    /* A node in a linked list */
    char item;  // character at this node
    Node *next; // pointer to the next node
};

size_t NODE_SIZE = sizeof(Node);

/* Create a new list */
Node* list();

/* Destruct a list, freeing it's memory */
void free_list(Node* sentinel);

/* Add an element to the end of a list */
void add(Node* sentinel, char item);

/** Delete an element from a list.
 * @returns true if the operation succeeded, false if there is the list is shorter than
 * the supplied index argument.
 */
bool del(Node* sentinel, size_t idx);

/* Replace the value stored by the node at idx. */
bool replace(Node* sentinel, size_t idx, char item);

/* Get the length of a list */
size_t len(Node* sentinel);

/* Peak the idx'th node, or the last node if there are fewer than
   idx elements in the list. */
Node* peak(Node* sentinel, size_t idx);

/* Pretty-print a list */
void print(Node* sentinel);

/* Print a list as a contiguous string */
void pstring(Node* sentinel);

linked_list.c

#include 
#include 
#include 
#include "linked_list.h"
#include 

Node* list(){
    // create a 'sentinel node'.
    Node* sentinel = (Node*)malloc(NODE_SIZE);
    sentinel->next = NULL;
    sentinel->item = '\0';
    return sentinel;
}

Node* peak(Node* sentinel, size_t idx){
    Node* node = sentinel;

    // compare to idx + 1, since we want our peak to be zero-indexed
    // and we have a sentinel node
    for (size_t i=0; i != idx+1; i++){
        if (node->next == NULL){
            // return the sentinel node as there are fewer than idx elements in the list
            return sentinel;
        }
        node = node->next;
    }
    return node;
}

void free_list(Node* sentinel){
    // traverse each node in order and free it's memory.
    size_t i = 0;
    do {
        i++;
        free(sentinel);
        sentinel = sentinel->next;
    } while (sentinel->next != NULL);
}

void add(Node* sentinel, char item){
    // instantiate a new node
    Node* new_node = (Node*)malloc(NODE_SIZE);
    new_node->item = item;

    // traverse each node
    while (true){
        if(sentinel->next == NULL){
            // replace the last node with our new node.
            sentinel->next = new_node;
            break;
        } else {
            // point to the next node
            sentinel = sentinel->next;
        }
    }
}

bool del(Node* sentinel, size_t idx){
    // TODO find a way to leverage peak to simplify this
    for (size_t i=0; i != idx; i++){
        if (!sentinel){
            return false;
        }
        sentinel = sentinel->next;
    }
    if (sentinel->next){
        Node* index_node_ptr = sentinel->next;
        if (index_node_ptr->next){
            sentinel->next = index_node_ptr->next;
        } else {
            free(index_node_ptr);
            sentinel->next = NULL;
        }
        return true;
    }
}

bool replace(Node* sentinel, size_t idx, char item){
    Node* node = peak(sentinel, idx);
    // check if the sentinel and the peaked node are the same
    if (sentinel == node){
        return false;
    } else {
        node->item = item;
        return true;
    }

}
size_t len(Node* sentinel){
    Node* current_node = sentinel;
    size_t nodes = 0;
    while (true){
        // Check if we're at the final node.
        if(current_node->next == NULL){
            return nodes;
        }
        nodes++;
        current_node = current_node->next;
    }
}

void print(Node* sentinel){
    printf("[");
    while (sentinel->next != NULL){
        sentinel = sentinel->next;
        printf("'%c',", sentinel->item);
    }
    printf("]\n");
}

void pstring(Node* sentinel){
    while (sentinel->next != NULL){
        sentinel = sentinel->next;
        printf("%c", sentinel->item);
    }
    printf("\n");
}

/* Tests */
void main(){
    Node* sentinel = list();

    add(sentinel, 'h');
    add(sentinel, 'e');
    add(sentinel, 'l');
    add(sentinel, 'l');
    add(sentinel, 'o');
    print(sentinel);

    replace(sentinel, 4, '0');
    pstring(sentinel);

    // check that deleting works for a valid index
    assert(del(sentinel, 4));
    // and fails when that index becomes invalid.
    assert(!del(sentinel, 4));

    // check peaking an invalid index returns the sentinel node
    assert(sentinel == peak(sentinel, 4));

    pstring(sentinel);
    free_list(sentinel);
}

运行代码(在ubuntu上测试)：

$ gcc -o run linked_list.c
$ ./run

Answer 1

总体上:一个“我的第三个C程序”的好代码。

良好的格式

良好的.h文件文档。(可能会更详细地描述预期案例。)

No需要对象 NODE_SIZE

只需使用#define NODE_SIZE sizeof(Node)。

实际上，每个包含.c的linked_list.h文件都会生成一个对象NODE_SIZE，最终导致多个定义。.h文件不应定义任何对象。

Information隐藏

struct Node的定义属于.c文件。这些函数的用户从来不需要查看内部信息。将struct Node { ...};移动到.c文件。

Name空间

代码使用像Node, list, add, del, peak, print, ...这样的通用名称，这些名称很可能与其他代码发生冲突。考虑一个常见的前缀。linked_list_add, linked_list_del, linked_list_peek, ...。

声明中的Empty参数

声明中没有任何参数与任何参数集匹配。使用void。

// Node* list();
Node* list(void);

这与函数定义不同。在下一个C版本中，这一区别可能会改变。

<#>add() may失败

由于add()调用了malloc()，该分配可能会失败。考虑在这里返回一个错误标志。

// void add(Node* sentinel, char item);
bool add(Node* sentinel, char item);

What如果为空列表？

在这种情况下，peak()不描述返回值。

练习 *.h include独立性

在linked_list.c中，首先包含它的配套.h文件，以帮助验证不需要文件。

// #include 
// #include 
// #include 
// #include "linked_list.h"
// #include 

#include "linked_list.h"
#include 
#include 
#include 
#include 

使用 const

对于不更改*sentinel的函数，请使用const。这增加了函数的适用性，更好地传达了代码的意图，并允许一些较小编译器看不到的优化。

// Node* peak(Node* sentinel, size_t idx)
Node* peak(const Node* sentinel, size_t idx)

NULL <>参数

list()可能无法分配，在这种情况下应该重写以返回NULL。

free_list(Node* sentinel)应该检查sentianl == NULL是否什么都不做--就像free(NULL)一样。这简化了调用代码的错误处理。

Cast不需要

在C中，不需要强制转换来将void *转换为object *。此外，我建议将大小调整为引用对象，而不是类型。更容易编写正确的代码，检查和维护。

检查分配是否成功。

// Node* sentinel = (Node*)malloc(NODE_SIZE);
Node* sentinel = malloc(sizeof sentinel[0]);
if (sentinel == NULL) {
  return NULL;
}

Test代码

考虑将main()测试代码移动到第三个文件，而不是linked_list.c，以允许其他应用程序使用/链接linked_list.c，而不是与main()发生冲突。

peek() 返回

我希望peak()返回item而不是struct Node。或者，要提供错误返回，可以考虑返回指向错误项和NULL的指针(例如，空列表)或其他接口--任何不要求用户查看Node内部信息的指针。

Code警卫

linked_list.h应该得到代码保护。

Answer 2

在free_list中有一种免费的使用。

所有函数都不检查sentinel参数是否为空。

add不确保新节点的next为空。

我认为如果你给del最后一项的索引，它就失败了。在这个路径中，它绝对没有return调用。