Маркировка головы ссылкой на хвост связанного списка

Question

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

http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/

void recursiveReverse(struct node** head_ref) 
{ 
    struct node* first; 
    struct node* rest; 

    /* empty list */ 
    if (*head_ref == NULL) 
     return; 

    /* suppose first = {1, 2, 3}, rest = {2, 3} */ 
    first = *head_ref; 
    rest = first->next; 

    /* List has only one node */ 
    if (rest == NULL) 
     return; 

    /* reverse the rest list and put the first element at the end */ 
    recursiveReverse(&rest); 
    first->next->next = first; 

    /* tricky step -- see the diagram */ 
    first->next = NULL;   

    /* fix the head pointer */ 
    *head_ref = rest;    
} 

Мы первый переместить указатель на хвост связного списка. Во время размотки штабеля мы переставляем ссылки обратно. Но для всех вызовов разворачивания стека, * headref = rest. Так как первое изменение во время разворачивания стека к предыдущему значению стека, почему остальные не изменились. Я создал 4 узла и просмотрел значения через gdb. Остальные значения во время разматывания столов оставались постоянными, но первые значения менялись. Почему он не меняется.

Answer 1

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

С рекурсивной функцией более полезно предположить, что он корректно работает для ввода размера n, а затем проверяет его правильность для ввода размера n+1. Если «базовый регистр» (размер 0 или 1) покрыт, это доказывает, что он работает для всех входов

В вашем случае давайте предположим, что recursiveReverse работает нормально для списков длины 3, и давайте подпишем его список длины 4 a->b->c->d по вызова recursiveReverse(&p) где p=a

Оба first->next и rest будет b, следовательно, указывают на список b -> c -> d 3-элемента, так что (по нашему предположению) recursiveReverse(&rest) будет правильно обратить этот список. После вызова rest изменилось значение (от b до d) и теперь указывает на этот перевернутый список d->c->b

first->next все тот же указатель b, как перед вызовом, и, следовательно, теперь указывает на конце из список. Таким образом, first->next->next = first прикрепляет first до конца этого перевернутого списка, который затем становится d->c->b->a) Поскольку first сейчас является конечным в списке, нам нужно first->next = NULL. Последним шагом будет изменение *head_ref (от a до d), поэтому после возвращения от recursiveReverse(&p), p изменится с a на новый заголовок списка, d.

Это показывает, что всякий раз, когда функция работает правильно для списков n-element , она корректно работает для списков n + 1 элементов. Базовый чехол легко, , так что показали, что он работает для всех списков.

Теперь, почему вы не видите rest, изменяя значение в своем отладчике? Поскольку его значение изменяется только при вызове функции recursiveReverse(&rest).Прежде чем вы рекурсивно вызовете recursiveReverse, оно имеет одно значение, после того как вы вернетесь из него, оно имеет другое, вы не видите, что оно меняется при входе и выходе из каждого вызова функции. Задание, которое изменяет свое значение на самом деле самое последнее (*head_ref = rest) до возврата из функции, но правопреемник называется head_ref в этом фрейме стеки, не rest (как его называли в кадре стеки вызывающего абонента)

Этого это «те же названия, но разные значения», которые я упомянул выше.