В первом заголовке функции *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