Изменение указателя головы в связанном списке

Question

У меня проблемы с пониманием этого кода.Все, что мне действительно нужно, это изменить указатель головы, чтобы он указывал на первый элемент.Так почему бы * не работать головой?Изменение значения * head меняет то, куда указывает этот указатель, и это должно работать, верно?Я прочитал проход по ссылке / передать по значению, но мне трудно это понять.Может кто-нибудь помочь прояснить это?Ценю твою помощь.Спасибо.

В C / C ++ проще ошибаться при неправильном использовании указателя.Рассмотрим код C / C ++ для вставки элемента в начало списка:

bool insertInFront( IntElement *head, int data ){
  IntElement *newElem = new IntElement;
  if( !newElem ) return false;

  newElem->data = data;
  head = newElem; // Incorrect!
  return true;
}

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

bool insertInFront( IntElement **head, int data ){
  IntElement *newElem = new IntElement;
  if( !newElem ) return false;

  newElen->data = data;
  *head = newElem; // Correctly updates head
  return true;
}

Answer 1

Вам нужна помощь, чтобы понять разницу, верно?

Представьте вызывающую функцию в первом случае:

IntElement *head;
int data;
...
insertInFront (head, data);

Теперь в этом случае адрес, на который указывает head, помещается в стек и передается в качестве аргумента для insertInFront. Когда insertInFront делает head = newElement; изменен только аргумент (в стеке).

Во втором случае вызывающей стороной будет:

IntElement *head;
int data;
...
insertInFront (&head, data);

В этом случае адрес head помещается в стек и передается в качестве аргумента для insertInFront. Когда вы делаете * head = newElement, этот переданный адрес отменяется, чтобы получить адрес исходного заголовка списка, и он изменяется.

Answer 2

Это довольно просто, когда вы понимаете, что такое указатель. В первом коде IntElement *head заголовок является указателем на существующий заголовок связанного списка. Таким образом, вызывающая сторона передает в адрес заголовка элемент списка. Изменение значения head в функции вставки впереди не меняет НИЧЕГО назад у вызывающей стороны. Значение этого адреса было передано вашей функции, а не тому, что удерживало этот адрес у вызывающей стороны.

Вам необходимо передать свою функцию «адрес адреса руководителя» - или IntElement **head. Это позволит этой функции изменить адрес, сохраняемый вызывающим абонентом, то есть обновить связанный список, чтобы он указывал на новый заголовок.

Answer 3

Вы не хотите изменять значение, на которое указывает заголовок, вы хотите изменить указатель, который хранится в самой голове, поэтому не используйте * заголовок, используйте указатель для заголовка. Головка имеет тип IntElement *, поэтому параметр должен указывать на такой тип: IntElement **

Answer 4

Всякий раз, когда у вас есть значение T x где-то, и вы хотите, чтобы какая-то другая функция изменила его, вы передаете указатель на x:

T x;             // set to some value

modify_me(&x);   // will change x

/* ... */

void modify_me(T * x)
{
  *x = new_value;
}

Теперь просто примените эту механику к T = IntElement*.Значения, которые вы хотите изменить, сами по себе являются указателями!

(Возможно, использование typedef сделает вещи менее запутанными: typedef IntElement * NodePtr;.)

Также обратите внимание, что ваш связанный список поврежден, потому что выникогда не устанавливайте указатель «следующий» для нового элемента так, чтобы он указывал на старую голову, и аналогично указателю «предыдущий», если список имеет двойную связь.