Node * head与Node ** head有什么区别？

Question

我正在编写一个C代码来查找链表的中间部分。我理解逻辑，但无法弄清楚如何使用指针。 Node *head和Node** head_ref的工作方式有何不同？

void middle(struct Node *head) ;

void push(struct Node** head_ref, int new_data) ; 

Answer 1

在第一个函数头中，*head是指向在内存中某处分配的节点对象的指针：

void middle(struct Node *head);
              _____________________
             |                     |
   *head --> |     Node object     |
             | [val=1][*next=NULL] |
             |_____________________|

而在第二个函数头中，**head_ref是指向内存中某个节点对象的指针：

void push(struct Node** head_ref, int new_data); 
              _____________________
             |                     |
   *head --> |     Node object     |
     ^       | [val=1][*next=NULL] |
     |       |_____________________|
     |    
 **head_ref

这是另一层间接。为什么第二个结构是必要的？好吧，如果我想修改在我的函数范围之外分配的东西，我需要一个指向其内存位置的指针。在第一个例子中，我可以取消引用*head指针（使用head->）来访问内存中的底层Node对象并对其进行修改或访问其属性。

将这个逻辑带到下一个间接层，如果我想将一个新的Node对象推到列表的前面以使其成为新头，我需要修改head指针本身。正如我想用指针操纵Node对象一样，现在我需要一个指向*head（它恰好是指针而不是Node对象）的指针才能修改它。

这是push的内容和一个前/后函数调用：

void push(struct Node** head_ref, int new_data) {
    Node *new_head = malloc(sizeof(Node)); // allocate memory for the new head node
    new_head->data = new_data;             // set its value

    new_head->next = *head_ref;            // make it point to the 
                                           // old head pointer

    *head_ref = new_head;                  // make it the new head by modifying
                                           // the old head pointer directly
}

/* Before push */
              _____________________
             |                     |
   *head --> |     Node object     |
     ^       | [val=1][*next=NULL] |
     |       |_____________________|
     |    
 **head_ref

/* After calling push(&head, 2);
 *                    ^
 *                   `&` operator gets the memory address of `head`, 
 *                       which is a pointer.
 */

              _________________      _____________________
             |                 |    |                     |
   *head --> |   Node object   |    |      Node object    |
     ^       | [val=2] [*next]----->| [val=1][*next=NULL] |
     |       |_________________|    |_____________________|
     |    
 **head_ref

这是一个完整的例子：

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void push(Node** head_ref, int new_data) {
    Node *new_head = malloc(sizeof(Node));
    new_head->data = new_data;
    new_head->next = *head_ref;
    *head_ref = new_head; 
}

void print(Node *head) {
    while (head) {
        printf("%d->", head->data);
        head = head->next;
    }

    puts("NULL");
}

void free_list(Node *head) {
    while (head) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main() {
    Node *head = malloc(sizeof(Node));
    head->next = NULL;
    head->data = 1;
    printf("Before push:\n");
    print(head);
    push(&head, 2);
    printf("\nAfter push:\n");
    print(head);
    free_list(head);
    return 0;
}

输出：

Before push:
1->NULL

After push:
2->1->NULL

Answer 2

struct Node * head - >这里指针头是指向链接列表头部的指针。 Head是一个指向节点结构的指针。

例如。

如果您有这样的链接列表： - ____ ____ _____ | _1__ | ---> | _2__ | ---> | _3__ | ---> .......地址 - 1000 1004 1008

您的Node * head将是一个指针变量，其中包含值为1的节点地址（头节点的地址，即存储值为1的节点）。头部内容= 1000

struct Node ** head_ref - >这里head_ref是指向链表开头指针的指针。

例如。

如果您有这样的链接列表： - ____ ____ _____ | _1__ | ---> | _2__ | ---> | _3__ | ---> .......地址 - 1000 1004 1008 | *头部地址 - 5050 | **头

您的Node * head将是一个指针变量，其中包含值为1的节点地址（头节点的地址，即存储值为1的节点）。 head的内容= 1000 ** head_ref的内容将是头指针的地址，即5050。

** head_ref用于间接引用。