Ошибка путаницы в C

Question

Я читаю очень популярный документ Стэнфорда * о связанных списках в C. В нем есть простая функция, которая строит простой LL с тремя членами. Единственное, чего я не получаю, и я смущен, заключается в том, что он говорит, что он хранит указатель head в «локальной переменной стека». Но что head указатель выделяется в кучу! Пожалуйста, взгляните на код и помогите мне понять, почему это локальная переменная стека?

/* 
Build the list {1, 2, 3} in the heap and store 
its head pointer in a local stack variable. 
Returns the head pointer to the caller. 
*/ 
struct node* BuildOneTwoThree() { 

struct node* head = NULL; 
struct node* second = NULL; 
struct node* third = NULL; 

head = malloc(sizeof(struct node)); // allocate 3 nodes in the heap 
second = malloc(sizeof(struct node)); 
third = malloc(sizeof(struct node)); 

head->data = 1; // setup first node 
head->next = second; // note: pointer assignment rule 
second->data = 2; // setup second node 
second->next = third; 
third->data = 3; // setup third link 
third->next = NULL; 

// At this point, the linked list referenced by "head" 
// matches the list in the drawing. 
return head; 
} 

В документе приведен нижеследующий чертеж для того, как будет выглядеть связанный список в памяти. Я не понимаю, почему указатель head рисуется в области Stack!

*: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf, страницы 5 и 6

Answer 1

Но что головной указатель выделяется в куче!

Не совсем, часть памяти, на которую указывает указатель, находится в куче. Сам указатель хранится в вашем стеке функций.

На чертеже в стеке отображается только head, но указатели second и third также находятся в стеке. Указатели здесь ссылаются на переменную, содержащую адрес. Адрес, указанный этими переменными, - это то, что находится в куче.

С head->next принадлежит second, у вас есть два указателя на одно и то же. И так далее с third. Обратите внимание: head->next является указателем, хранящимся в куче, и указывает на другой адрес памяти кучи. Это то же самое, что и second, который является указателем, хранящимся в стеке, с адресом, указывающим на ячейку памяти кучи (опять же, как и head->next). Таким образом, другой способ сделать список состоит в том, чтобы выделить только первый (head) и использовать его указатель next, чтобы выделить следующий элемент, хранящий адрес там напрямую. Недостаток по сравнению с используемым (с прямым указателем на второй и третий элементы) заключается в том, что вы теряете этот прямой адрес. Вам нужно будет посетить первый и второй, чтобы найти адрес третьего.

Answer 2

он хранит указатель на голову в «локальной переменной стека». Но то, что указатель главнокомандующего выделяется в куче!

Каждый узел содержит как часть данных, так и часть указателя. Выше сказано, что указательная часть головы указывает на первый узел, который равен 1 (находится в куче). Однако сама переменная указателя головы находится в стеке.

Цель указателя головы - просто отслеживать первый узел и также может использоваться для доступа к нему через его адрес, который он удерживает.