Aide pour comprendre l'extrait de code qui inverse la liste liée en utilisant la récursivité

Question

Je suis étudiant pour un examen avec Listes Liées en C. Je me suis trouvé un "critique" il avait cet extrait de code. Pour la vie de moi, je ne peux pas comprendre comment le reste est inversé. Ici c'est ... il est de Linked List Problems par Mr.Nick Parlante (pris CIS Library, Stanford). Je vais mettre dans les commentaires de M. Nick.

RecursiveReverse() Solution

Probablement le plus dur est d'accepter le concept selon lequel la RecursiveReverse (& repos) fait en fait inverser le reste. Ensuite, il y a une astuce pour obtenir le nœud frontal jusqu'à la fin de la liste. Faire un dessin pour voir comment fonctionne le tour.

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 

}

Je l'ai fait d'innombrables dessins pour tenter de retracer ce qui se passe, et je ne peux pas comprendre comment RecursiveRest (& repos) inverse fait le reste. S'il vous plaît aider. Je suis très frustré. Ce que je finis par obtenir est plus petit "repos" et rien n'est inversé. Merci beaucoup d'avance.

Answer 1

La récursion est généralement difficile à comprendre car il est difficile de voir comment elle se décompose en étapes de base.

Il est généralement plus facile de penser que la partie récursive est déjà terminée et seulement la raison de l'étape de combinaison (ceci est très utile lors de la conception de l'algorithme).

Lorsque vous essayez de visualiser comment fonctionne vous avez un algorithme récursif pour garder à l'esprit qu'il ya deux processus au travail:

• la décomposition du problème d'origine dans les petits problèmes jusqu'à ce que vous trouver le cas de la résiliation
• la résolution du cas de terminaison
• la combinaison des résultats.

C'est comme une rue à double sens. D'abord vous allez dans un sens jusqu'à la fin du cas tout en brisant le problème. Vous résolvez ensuite le cas final. Après cela, vous revenez au début tout en combinant les résultats partiels.

Pour votre cas, cela pourrait aller comme ceci. Notez que [A-B] signifie une liste.

[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 

Espérons que cela aide.

Answer 2

1. À chaque étape, le code se souvient du courant et le noeud suivant (premier et repos).
2. Supposons que RecursiveReverse (& reste) fonctionne et inverse la liste restante.
3. Ensuite, le nœud de repos sera à la dernière position lorsque l'appel reviendra. Donc, il vous suffit de vérifier les dernières trois lignes de code.
4. Vous verrez que le repos est changé en point premier (de première> Continuer-> next = premier), et le premier point à NULL (de première> next = NULL), soit vous déplacez d'abord à la fin de la liste.