Понимание функции pu sh

Question

У меня проблемы с пониманием функции pu sh для связанного списка в C. Например, у меня есть следующая структура

typedef struct node {
    int val;
    struct node * next;
} node_t;

, и я создал связанный список как таковой

  // creating list
  node_t * head = NULL;
  head = (node_t *) malloc(sizeof(node_t));

  // checking if list is initialised sucessfully
  if (head == NULL) {
      return 1;
  }

  // 1st and 2nd element
  head = (node_t *) malloc(sizeof(node_t));
  head->val = 1;    
  head->next = (node_t *) malloc(sizeof(node_t));
  head->next->val = 2;
  head->next->next = NULL;

функция pu sh дана как таковая

void push(node_t ** head, int val) {
    node_t * new_node;
    new_node = (node_t *) malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}

---

Мой вопрос: почему new_node->next назначен разыменованному head? Я думал, что head должен быть указателем, что делает *head следующим node_t. new_node.next - это указатель, следовательно, вместо него должно быть new_node->next = head?

Во-вторых, последняя строка *head = new_node такая же, как head = &new_node? Более того, это так же, как **head = &new_node? Последнее было бы наиболее логичным для меня, поскольку мы передаем указатель указателя в качестве аргумента push.

Answer 1

Мой вопрос: почему new_node->next назначено разыменованной head?

Поскольку параметр head функции push является указателем на указатель головы. Вы должны разыменовать его один раз, чтобы получить (предполагаемый) указатель на головной узел вашего связанного списка. Это, конечно, должно совпадать на стороне вызывающей стороны - они должны передавать адрес указателя головы списка.

Я думал, что head должен быть указателем, что делает *head следующий node_t сам по себе.

Представленный код немного запутывает это, используя один и тот же идентификатор "head" в разных областях для представления разных уровней косвенности. В функции push параметр head равен node_t **. Да, это указатель, но не на головной узел. Вместо этого он указывает на другой указатель, который, в свою очередь, указывает на головной узел. *head есть node_t *, а не node_t.

Во-вторых, последняя строка *head = new_node совпадает с head = &new_node? Более того, это то же самое, что и **head = &new_node?

Нет, все они разные, что сразу следует из того факта, что head, *head и **head все обозначают разные предметы. В функции push(),

• head обозначает параметр функции, который имеет тип node_t ** и является локальным для функции . Назначение head = &new_node будет корректным по типу и в целом допустимым, установив head для указания на локальную переменную функции new_node, но это будет бесполезно, поскольку оно ничего не передает обратно вызывающей функции и служит в самой функции нет особой цели.

• *head, конечно, обозначает объект, на который указывает head, как выбрано вызывающим функцией. Он имеет тип node_t *. Этот объект указателя доступен вызывающей стороне и может, например, быть одной из локальных переменных вызывающей стороны. Присвоение *head = new_node изменяет этот объект, доступный для вызывающей стороны, и, следовательно, его эффект виден вызывающей стороне, для чего параметр является двойным указателем.

• **head обозначает объект, на который указывает *head, node_t. Этот объект также доступен вызывающей стороне, но его изменение не будет служить целям функции. В этом случае вызывающая сторона останется с тем же объектом node_t, но с другим содержимым. В любом случае выражение &new_node, a node_t **, не имеет правильного типа для присвоения **head. Если бы кто-то на самом деле хотел назначить ему, то вариант с корректным типом (но семантически неуместным) был бы **head = *new_node.

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

Причина передачи указателя на указатель заключается в том, что указатель на указатель может быть изменено функцией. В результате указатель вызывающей стороны указывает на узел, выделенный push, тогда как указатель next этого узла указывает на узел, на который изначально указывал указатель вызывающей стороны. Это именно то, что нужно для добавления узла в список. Вид вызывающего выглядит примерно так:

до пу sh ()

  X --next--> ... --next--> NULL
  |
  v
Value1        ...

после пу sh (значение2)

  Y --next--> X --next--> ... --next--> NULL
  |           |
  v           v
Value2      Value1        ...

Если вместо push вместо присвоено **head, то результатом будет

  X --next--> (depends)
  |
  v
Value2

Обратите внимание, что Value1 теперь нет, его заменили на Value2.

Answer 2

В функции push, head является указателем на указатель на головной узел . Для понимания кода может быть более полезным думать о head как о адресе ' указателя на головной узел '.

Код в функции push:

1. берет текущий указатель ' на головной узел ' (путем разыменования head) и присоединяет его к next член new_node и
2. , создающие new_node новый заголовок списка , взяв указатель на new_node и записав его обратно в указатель ' в головной узел 'путем разыменования head.

Answer 3

В дополнение к предыдущим ответам.

Будьте внимательны к тому, что вы делаете со своим «списком», когда он пуст с вашими операциями pop / pu sh. И подумайте, что вы собираетесь считать «пустотой» в своем внутреннем представлении. Будет ли голова, указывающая ни на что, или будет «фальшивый» узел?

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

PS. Небольшое замечание о стиле. Вы используете 'struct node => node_t'. Вы можете просто заменить 'node_t' на 'struct node' в вашем коде. Просто нет практической разницы. Но если вы выбрали указатель на структуру, код будет читаться намного лучше (в дальнейшем).