Как работает разыменование указателя?

Question

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

Этот код отсюда, выбранный ответ на этот вопрос .

Я не могу понять 3 строки здесь:

*pnext = list1;
pnext = &list1->next;
list1 = *pnext;

Может ли кто-нибудь помочь мне? Объясни мне это?

Отредактировано: Могу ли я изменить эти 2 строки:

pnext = &list1->next;
list1 = *pnext;

до

 list = list-> next; 

Answer 1

С самого начала: у вас есть два списка и новый заголовок списка, который вы будете возвращать.Изначально pnext указывает на это.

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

list1          pnext->list->Null
|
V
o->o->o...

list2
|
V
o->o->o...

Swapчтобы гарантировать, что меньший элемент является первым из списка1.Эти строки делают:

Шаг за шагом:

*pnext = list1;

Получает * pnext (список перед первой итерацией), указывающий на узел, содержащий наименьший элемент:

list1
|
V
o->o->o...
^
|
list<-pnext

list2
|
V
o->o->o...

.

pnext = &list1->next;

Хитрая часть, как отмечалось ранее, & оператор имеет низкий приоритет.Также трудно отобразить графически, потому что это фактически смотрит на часть конструкции Node.Примерно так:

list1
|
V
o---->o->o...
^     ^
|     |
list  x<-pnext

list2
|
V
o->o->o...

, где x - следующий указатель на o, на который указывает list1.

list1 = *pnext;

Продвигает заголовок list1 по мере обработки его первого элемента.

   list1<-pnext
   |
   V
o->o->o->...
^
|
list

list2
|
V
o->o->o->...

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

Инвариант, в котором есть пустые точки, указывает на точку, где последний обработанныйследующий элемент указывает на то, куда должен идти самый маленький элемент из list1-2.Интересные вещи случаются со свопами, попробуйте сами отработать точную процедуру (трудно рисовать, как это, и хорошее упражнение, чтобы понять, что ** делает).Я мог бы добавить его, если найду хороший способ нарисовать его.

Вы не можете использовать list = list-> next;, потому что он будет делать что-то вроде этого:

   list1
   |
   V
o->o->o->...
   ^
   |
   list

list2
|
V
o->o->o->...

Что означает, что вы потеряете этот одинокий o(и все остальное, в конце концов, по мере выполнения цикла).

edit: *pnext = list2; в конце делает это:

Завершение цикла (состояние перед указанным оператором):

         list1<-pnext
         |
         V
o->o->o->null
^
|
list

      o->o->o->...
      ^
      |
      list2

После оператора:

         list1
         |
         V              
o->o->o  Null
^     |
|     |
list  |
      V
      o->o->o->...
      ^
      |
      list2<-pnext

Этот оператор добавляет оставшийся список в конец списка.Затем возвращается список узлов Node *, указывающий на начало объединенного списка.

edit2:

И все же, pnext будет лучше представлен следующим образом:

         list1
         |
         V              
o->o->o  Null
^     |
|     |<-pnext
list  |
      V
      o->o->o->...
      ^
      |
      list2

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

Answer 2

pnext - это указатель на указатель на Node.

"*pnext" означает, что вы работаете со значением, на которое указывает pnext.Таким образом:

*pnext = list1;

означает, что любой указатель, на который указывал pnext, теперь указывает на то же самое, что и list1.

---

Следующая строка должна быть заключена в скобки для ясностина это:

pnext = &(list1->next);

list1->next означает, что вы получаете доступ к атрибуту next того, на что указывает list1, а & означает получение адреса этого элемента.По сути, вы указываете pnext указатель на следующий элемент.

---

Последняя строка:

list1 = *pnext;

означает, что вы беретезначение, указанное в pnext и присвоение ему list1.

Answer 3

list1 имеет тип Node*, а pnext имеет тип Node**, что означает, что он должен содержать адрес переменной, тип которой Node*.

*pnext = list1;

При разыменованииpnext, вы получите Node*.Таким образом, это назначение является правильным.

pnext = &list1->next;

Здесь -> имеет более высокий приоритет над &.Таким образом, он возвращает адрес указателя (т. Е. Адрес типа Node *)

list1 = *pnext;

Это просто противоположность первой инструкции.Разыменование pnext дает Node*, которое можно присвоить list1.

---

Да, вы можете изменить это (т. Е. Логически они делают то же самое) -

pnext = &list1->next;
list1 = *pnext;

на

list1 = list1->next ;

Но у вас естьоператор -

 *pnext = list2;

Если pnext не инициализирован, как в двухэтапной последовательности, разыменование неинициализированного указателя (т. е. *pnext) приведет к ошибке сегментации.Вот причина.

Answer 4

Попробуйте установить Visual Studio Express Edition. После того, как вы отладите программу в VS-2012, вы можете просто навести курсор мыши на указатель, и он покажет вам содержимое, разыменовав адрес.