c - 链接列表 Malloc() 插入？

Question

所以我一直在努力确保我完全理解链表。这是我目前所拥有的:

typedef struct node
{
    int num;
    struct node *next;

}node;

int main()
{
    node *HEAD = create(5);
    printf("Address:%p Value:%i\n", HEAD, HEAD->num);
    HEAD = insert(HEAD,3);
    printf("Address:%p Value:%i\n", HEAD, HEAD->num);
    HEAD = insert(HEAD,7);
    printf("Address:%p Value:%i\n", HEAD, HEAD->num); 
    return 0;
}

node* create(int value)
{
    node *HEAD = malloc(sizeof(node));
    if(HEAD == NULL)
    {
        printf("Space Unable to be allocated for HEAD\n");
    }
    HEAD->num = value;
    HEAD->next = NULL;
    return HEAD; 
}

node* insert(struct node *HEAD,int value)
{
    node *new_node = malloc(sizeof(node));
    new_node->num = value;
    new_node->next = HEAD;
    HEAD = new_node;
    return HEAD;
}

void print(struct node *HEAD)
{
    node *trav = HEAD;
    while(trav != NULL)
    {
        printf("Value in Linked List:%i\n",trav->num);
        trav = trav->next;
    }
}

这样就可以正常工作并打印出 5,3,7 了。但是，当在纸上绘制时，node *new_node = malloc(sizeof(node)); 让我有点困惑。因为在我看来，每次插入时我们都在创建一个名为“new_node”的新指针……这似乎有很多剩余指针只是悬而未决。更有意义的是 new_node 每次都更改为指向要插入的新节点的 malloc 空间。

所以我在这里做错了什么，或者当我 malloc 一些具有相同名称的东西时，旧的刚刚被重新分配(如果这有意义？)或者我应该在它被分配后释放()'ing new_node每次都插入？

谢谢

Answer 1

将链表想象成火车车厢，每次添加新车厢时，都需要将它连接到最后一节车厢，否则火车不会拉动新添加的节点。

所以伪代码应该是这样的:

main {
    // create the locomotive
    head = create_new_node(5);
    // link new car
    insert(head, 7);
    // link new car
    insert(head, 9);
    // hit the road jack
    dump(head);
}

创造一辆新车

create_new_node(value) {      
    // get the resources for a new car  
    node *p = (node*)malloc(sizeof(node));
    // load the car
    p->value = value;
    // attach the car connector
    p->next = null;
    // get the new car on field
    return *p;
}

插入到火车尾部

insert(head, val) {
    node *p = head;
    // go to the last train car
    while(p->next != null) p = p->next;
    // create new train car
    node *n = create_new_node(val);
    // link it to the last car
    p->next = n;
}

检查火车

dump(head) {
   // i don't want the 'head' to be changed, so I use a reference instead.
   node *p = head;
   // loop each car + the locomotive until end is reached
   while(*p != null)
   {
      // count the load
      write p->value;
      // inspect the next car
      p = p->next;
   }
}