Рекурсивно обратный связанный список - PullRequest
Новая
       14

Рекурсивно обратный связанный список

3 голосов
/ 01 июня 2019

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

void RecursiveReverse(struct node** headRef) 
{
  struct node* first;
  struct node* rest;

  if (*headRef == NULL) return; // empty list base case

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

  if (rest == NULL) return; // empty rest base case

  RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                           // after: rest = {3, 2}

  first->next->next = first; // put the first element on the end of the list
  first->next = NULL;

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

Я понимаю, что при создании стека рекурсивных вызовов и после того, как список содержит только {3}, пустой базовый регистр остатка if (rest == NULL) в первый раз равен true.

После этого стек рекурсивных вызовов начинает разрываться и впервые набирает first->next->next = first;, {2, 3},

Перед выполнением этой строки выведите в gdb: 

(gdb)p *first
{data = 2, next = 0x1003001f0}

(gdb) p *rest
{data = 3, next = 0x0}

После выполнения этой строки, 

(gdb) p *rest
{data = 3, next = 0x1003000a0}

Продолжаем выполнение кода, нажимая first->next->next = first;, во второй раз: 

(gdb) p **head_ref
{data = 1, next = 0x1003000a0}

(gdb) p *rest
{data = 3, next = 0x1003000a0} // expected p *rest to be 2

Здесь я ожидал, что локальный указатель rest должен указывать на узел 2, поскольку при построении стека рекурсивных вызовов **headRef указывает на узел 1, а после строки rest = first->next; выполняется rest указывает на узел 2 .

После выполнения *headRef = rest; разве headRef не должно указывать на узел 2?

Почему локальное состояние потеряно, а остальное указывает на узел 3?

Ответы [ 2 ]

2 голосов
/ 01 июня 2019

Предположим, что у вас есть список, а его остальная часть уже перевернута.

Перед изменением остальной части список имел такую ​​структуру 

first -> first_of_rest -> second_of_rest->...->nth_of_rest->nullptr

Перевернув оставшуюся часть, вы получите 

first -> nullptr <- first_of_rest <- second_of_rest <-...<-nth_of_rest
         |                                                      |
         ________________________________________________________
                            the rest part of the list

Таким образом, элемент данных, следующий за узлом first, указывает на first_of_rest, а элемент данных, следующий за узлом first_of_rest, "указывает" на nullptr.

Итак, в данный момент нам нужно установить элемент данных узла first_of_rest так, чтобы он указывал на узел first 

first->next->next = first;

abd установить элемент данных рядом с узлом first, чтобы "указать" на nullptr. 

first->next = NULL;

Таким образом, мы имеем 

nullptr <-first <- first_of_rest <- second_of_rest <-...<-nth_of_rest
0 голосов
/ 01 июня 2019

Вот упрощенный псевдокод. Это в основном работает так: 

RecursiveReverse(head):
    if head is empty:
        return
    RecursiveReverse(head->next)

    // When we come here, the whole list except the first
    // element has been reversed. So all that's left to do
    // is to reverse the final step

    head->next->next = head
    head->next = NULL

Самая важная вещь, которую нужно осознать, это то, что ПОСЛЕ рекурсивного вызова весь список, КРОМЕ первого элемента, был перевернут.

...