C 中的链表操作阅读证明

Question

我正在尝试写出所有链表的基本操作（push、pop、add_at_end、pop_from_end、add_at_index、pop_from_index）。这不是学校作业，尽管它看起来像一个。我已经写了代码。尽管我不是 C 大师，但我自己已经对其进行了很多测试。如果您能告诉我您是否对代码在效率、内存处理、可读性、清晰度等方面有任何建议/更正，我会很高兴。

生成的代码已添加到此处：http://vladotrocol.ro/wiki/linked-lists

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

//Node structure
typedef struct node {
    int data;
    struct node * next;
} node_t;

void print_list(node_t *head); //print the list data iteratively
int push(node_t **head, int data); //add a node at the head of the list
int pop(node_t **head); //remove the node from the head of the list
int add_at_end(node_t **head, int data); //add a node at the end of the list
int remove_last(node_t **head); //remove the node from the end of the list
int add_at_index(node_t **head, int n, int data); //add a node at the nth position
int remove_by_index(node_t **head, int n); //remove the node at the nth position

int main()
{
    node_t *head = NULL; //create a new list

    //initialise the list with one element
    head = malloc(sizeof(node_t));
    //check if memory allocation was possible
    if (head == NULL) { 
      return -1;
    }
    head->data = 1;
    head->next = NULL;

    //print the list
    print_list(head);
    return 0;
}
//print the list data iteratively
void print_list(node_t *head) {
    node_t *current = head;
    while (current != NULL) {
        printf("%d\n", current->data);
        current = current->next;
    }
}
//add a node at the head of the list
int push(node_t **head, int data) {
    //create a new node with the diven data
    node_t *new_node = NULL;
    new_node = malloc(sizeof(node_t));
    //check if memory allocation was possible
    if (new_node == NULL) { 
      return -1;
    }
    new_node->data = data;
    new_node->next = *head; //the new node link points to the old head of list
    *head = new_node; //the new node becomes the new head of list
    return 1;
}
//remove the node from the head of the list
int pop(node_t **head) {
    int retval = -1;
    //if the list is empty do nothing
    if (*head == NULL) {
        return -1;
    }
    //if there is only one node in the list make the list empty
    if ((*head)->next == NULL) {
        printf("here");
        retval = (*head)->data;
        free(*head);
        *head = NULL;
        return retval;
    }
    //if the list has multiple nodes
    node_t *next_node = NULL;
    next_node = (*head)->next; //get the second node
    retval = (*head)->data;
    free(*head);
    *head = next_node; //the second node becomes the head of the list
    return retval;
}
//add a node at the end of the list
int add_at_end(node_t ** head, int data) {
    node_t *new_node = NULL;
    new_node = malloc(sizeof(node_t));
    //check if memory allocation was possible
    if (new_node == NULL) { 
      return -1;
    }
    //create the new node
    new_node->data = data;
    new_node->next=NULL;
    //if the list is empty the new node becomes the head of the list
    if(*head==NULL){
        *head = new_node;
        return 1;
    }
    //otherwise iterate to the end of the list
    node_t *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    //the last node instead of pointing to NULL points to the new node
    current->next = new_node;
    return 1;
}
//remove the node from the end of the list
int remove_last(node_t **head) {
    int retval = -1;
    //if the list is empty do nothing
    if (*head == NULL) { 
      return -1;
    }
    //if the list has one node only list beomes empty
    if ((*head)->next == NULL) {
        (*head)->data;
        free(*head);
        *head = NULL;
        return retval;
    }
    //if the list has multiple nodes go to second last one
    node_t *current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    retval = current->next->data;
    //remove the last node
    free(current->next);
    current->next = NULL;
    return retval;
}
//add a node at the nth position
int add_at_index(node_t **head, int n, int data) {
    /*if the list is empty or the position to be inserted at 
    is the first one add the new node at the head of the list*/ 
    if(n == 0 || *head==NULL){
        push(head, data);
        return 1;
    }
    //if the list is not empty we iterate n-2 times to reach the (n-1)th node
    node_t *current = *head;
    while(n>1 && current->next!=NULL){
        current = current->next;
        n--;
    }
    /*if we didn't perform all iterations it means the required 
    position is bigger than the length of the list*/
    if(n>1){
        return -1;
    }
    //if we reached the desired node we create a new one
    node_t *new_node = NULL;
    new_node = malloc(sizeof(node_t));
    //check if memory allocation was possible
    if (new_node == NULL) { 
      return -1;
    }
    new_node->data = data;
    //the new node points to the node the current node was previously pointing to
    new_node->next = current->next;
    //the current node now points to our newly create node
    current->next = new_node; 
    return 1;
}
//remove the node at the nth position
int remove_by_index(node_t **head, int n) {
    /*if the list is empty or the required position is the first one use the pop
     function which removes the head node or does nothing if the list is emty*/
    if(n == 0||*head==NULL){
        pop(head);
        return 1;
    }

    //if the list has multiple elements got to the nth node
    node_t *current = *head;
    node_t *curr_head = NULL;
    while(n>0 && current->next!=NULL){
        curr_head = current; //this time we need to remember the previous node
        current = current->next;
        n--;
    }
    /*if the iterations have not completed it means 
    the list is emty and there is nothing to do*/
    if(n>0){
        return -1;
    }
    /*instead of pointing to the current node, 
    the previous node is now pointing to the next node*/
    curr_head->next = current->next;
    free(current); //delete the current node
    return 1;
}

Answer 1

我没有彻底审查所有代码，但我粗略地看了一眼，我认为有几点值得一提。请注意，这有时可能是主观的，并不是每个人都同意使用相同的约定。但这里有一小部分我认为可以改进的地方：

1.

在指针声明中，您似乎遵循在星号和标识符之间放置 space 的约定。我不推荐这个。为什么？因为指针声明符不是基本类型的一部分（它是一个声明符）。如果你在星号和标识符之间放一个 space，你 有一天会 写出这样的代码：

int * x, y;

并误认为x和y是指向int的指针，而实际情况是x是指针，而y是一个 int。帮自己一个忙，改为这样写：

int *x, y;

（不管怎样，这还不如写int* x,y的人那么糟糕——那真是自找麻烦）。

2.

在确定要分配的内存量时，不要对类型名称进行硬编码。而不是这个：

head = malloc(sizeof(node_t));

使用更灵活的形式：

head = malloc(sizeof(*head));

sizeof 不计算它的操作数，所以这样做总是安全的。如果您总是这样做，那么您就是安全的，因为您总是分配正确数量的内存。此外，它使代码更易于维护，因为如果 head 的类型发生变化，代码仍然可以工作并且仍会分配正确的内存量。

3.

add_at_end() 和其他分配内存的函数不检查 malloc() 是否成功。

C 中的链表操作阅读证明

Linked List Operations in C Read Proof

c

linked-list

data-structures