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

Question

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

Что меня беспокоит, так это какНапример, ссылка на узел изменяет исходное значение списка, но не сам список.

Я объясню лучше:

void insertNode(struct node** head, int value) {

    struct node* new = malloc(sizeof(struct node*));
    struct node* ref = (*head); //this is a reference. -> same address.

    //base case 
    if((*head) == NULL) {
        //do things
    } else { // not null
        while(ref->next != null) {
            ref = ref->next; //THIS: how can this not modify the head itself?
        }

        //null spot found, set up node
        new->value = 10; //some int here
        new->next = NULL;

        ref->next = new; //Instead, how can this modify the head? and why?
    }
}

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

ref = ref->next;

изменяет только сам реф, а

ref->next = new

модифицирует и голову?

через GDB Я увидел, что оба вначале совместно используют одну и ту же адресную память, но ref только изменяет список ссылок на новую вставку.

Может кто-нибудь объяснить это?

Answer 1

Возможно, некоторые изображения помогут.

Перед вызовом insertNode у вас есть последовательность узлов, связанных так:

+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

У вас есть указатель (назовите его h), который указывает на первый элемент списка:

+---+
| h |
+---+
  |
  V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

Когда вы вызываете insertNode, вы передаете указатель на h в качестве параметра, который мы называем head:

+------+
| head |
+------+
  |
  V
+---+
| h |
+---+
  |
  V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

Вы создаете переменную-указатель с именем ref, которая принимает значение *head (h);IOW, ref указывает на первый элемент списка:

+------+ +-----+
| head | | ref |
+------+ +-----+
  |        |       
  V        |
+---+      |
| h |      |
+---+      |
  |   +----+
  V   V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

Затем вы создаете другой узел в куче и присваиваете этот указатель локальной переменной с именем new:

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next |
+------+ +-----+ +-----+      +-------+------+
  |        |       
  V        |       
+---+      |       
| h |      |    
+---+      |     
  |   +----+     
  V   V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

Итак, следует отметить, что хотя ref и *head (h) имеют одинаковое значение (адрес первого узла в списке), ониэто разные объекты.Таким образом, все, что изменяет значение ref, не влияет ни на head, ни на h.

Итак, если мы выполним этот цикл

while(ref->next != null) {
    ref = ref->next; 

, результат первой итерации будет

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next |
+------+ +-----+ +-----+      +-------+------+
  |        |       
  V        |       
+---+      |       
| h |      |    
+---+      |     
  |        +------------+     
  V                     V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

После другой итерации мы получим

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next |
+------+ +-----+ +-----+      +-------+------+
  |        |       
  V        |       
+---+      |       
| h |      |    
+---+      |     
  |        +----------------------------------+     
  V                                           V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

В этот момент ref->next равно NULL, поэтому цикл завершается.

Затем мы присваиваем значения new->value и new->next, так что new->next равно NULL:

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next | ---|||
+------+ +-----+ +-----+      +-------+------+
  |        |       
  V        |       
+---+      |       
| h |      |    
+---+      |     
  |        +----------------------------------+     
  V                                           V
+-------+------+      +-------+------+      +-------+------+      
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+      

Наконец, мы устанавливаем ref->next на значение new, добавив, таким образом, узел new, указывающий на конец списка:

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next | ---|||
+------+ +-----+ +-----+      +-------+------+               
  |        |                    ^                                
  V        |                    |                               
+---+      |                    +-------------------------------+
| h |      |                                                    |
+---+      |                                                    |
  |        +----------------------------------+                 |
  V                                           V                 |
+-------+------+      +-------+------+      +-------+------+    |  
| value | next | ---> | value | next | ---> | value | next | ---+
+-------+------+      +-------+------+      +-------+------+      

Обратите внимание, что ref->next не указывает на переменную new,это указывает на то, на что указывает new.

Поэтому обновление ref не влияет на head (или *head (h)).В базовом случае, когда список пуст, будет в итоге записывать в *head (h), устанавливая его так, чтобы он указывал на новый узел, выделенный из кучи.

Answer 2

ref - просто указатель;изменение ref не изменит то, что указано на ref.

Цикл while на самом деле просто ищет последний элемент списка.После цикла while, ref будет просто указывать на последний элемент списка.

Первая «загадочная» строка:

ref = ref->next; //THIS: how can this not modify the head itself?

Здесь мыпросто прочитайте ref->next, чтобы голова не могла быть изменена.

Вторая «загадочная» строка:

ref->next = new; //Instead, how can this modify the head? and why?

Здесь мы изменяем то, на что указывает ref,В этой строке ref указывает либо на последний элемент списка, либо указывает на заголовок (который также является последним элементом списка, если в списке только один элемент, или который является вновь созданным заголовком)сделать в //do things), если список пуст.