Помощь в понимании фрагмента кода, который переворачивает связанный список с помощью рекурсии - PullRequest
Новая
       38

Помощь в понимании фрагмента кода, который переворачивает связанный список с помощью рекурсии

2 голосов
/ 24 января 2011

Я готовлюсь к экзамену со связанными списками в C. Я нашел себя «рецензентом», у которого был этот фрагмент кода.Что касается жизни, я не могу понять, как все наоборот.Вот оно ... это из проблем со связанным списком мистера Ника Парланте (взято из библиотеки СНГ, Стэнфорд).Я добавлю комментарии г-на Ника.

Решение RecursiveReverse ()

Вероятно, самой сложной частью является принятие концепции, что RecursiveReverse (& rest) фактически полностью изменяет остальное.Затем есть хитрость, чтобы получить один передний узел до конца списка.Сделайте рисунок, чтобы увидеть, как работает трюк. 

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 elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer

}

Я сделал бесчисленные рисунки в попытках отследить, что происходит, и я просто не могу понять, как RecursiveRest (& rest) фактически полностью изменяет остальное.Пожалуйста помоги.Я очень разочарован.То, что я в конечном итоге получаю, это меньшие "остальные" ... и ничего не меняется.Заранее большое спасибо.

Ответы [ 2 ]

7 голосов
/ 24 января 2011

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

Обычно проще представить рекурсивную часть как уже законченную, и это единственная причина шага комбинирования (это наиболее полезно при разработке алгоритма).работает рекурсивный алгоритм, вы должны иметь в виду, что работают два процесса:

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

Это как улица с двусторонним движением.Сначала вы идете одним путем до конца дела, разбивая проблему.Затем вы решаете конец дела.После этого вы возвращаетесь в начале, комбинируя частичные результаты.

Для вашего случая это может пойти так.Обратите внимание, что [A-B] означает список. 

[A-B-C-D-E] // RecursiveReverse([A, B, C, D, E])
(A [B-C-D-E]) // this means we are calling RecursiveReverse([B, C, D, E])
(A (B [C-D-E])) // this means we are calling RecursiveReverse([C, D, E])
(A (B (C [D-E]))) // this means we are calling RecursiveReverse([D, E])
(A (B (C (D [E])))) // this means we are calling RecursiveReverse([E]) 
                    // hit the end case and solve it trivially
(A (B (C (D [E])))) // solved
(A (B (C [E-D]))) // and go back while applying the combination case
(A (B [E-D-C])) // combine
(A [E-D-C-B]) // combine
[E-D-C-B-A] // combine

Надеюсь, это поможет.

1 голос
/ 24 января 2011
  1. На каждом шаге код запоминает текущий и следующий узел (первый и отдых).
  2. Предположим, что RecursiveReverse (& rest) работает и переворачивает оставшийся список.
  3. Тогда остальной узел будет на последняя позиция, когда звонок возвращается. Так что вам просто нужно проверить последний три строки кода.
  4. Вы увидите, что отдых меняется на указать сначала (первый-> следующий-> следующий = первый), а первый указывает на NULL (first-> next = NULL), т. Е. Вы переходите сначала в конец списка.
...