Visuelle Erklärung Leitung notwendig, für die Umkehrung der Verlinkten Liste datastructure-code?

Habe ich folgende Stück Programmcode für die Umkehrung der verlinkten Liste. Ich bin immer verwirrt in der while-Schleife, und so würde es sicherlich zu schätzen wissen, wenn jemand kann geben Sie eine visuelle Erklärung, wie es eigentlich funktioniert.

 static void Reverse (struct node** headRef)
{
     struct node* result = NULL;
     struct node* current = *headref;
     struct node* next;

     while(current != NULL)
     {
        next = current->next;
        current->next = result;
        result = current;

        current = next;
     }     
     *headRef = result;

}

InformationsquelleAutor Rachel | 2009-09-26

11

OK, hier ist mein Versuch zu machen, Walja die Antwort noch klarer (obwohl ich dachte, es war ziemlich gut schon):

Sagen, wir haben diese Liste:
```
//a->b->c->d->e->NULL
```
Wir starten mit dem ersten Knoten a enthält einen Zeiger (next) zu b:
```
//a->b ...
```
Die Linie next = current->next; setzt next zu b (einfach genug). Die nächste Zeile current->next = result; tut:
```
//NULL<-a  b ... (notice there is no longer a pointer from a to b)
```
Dann haben wir result = current; setzt result zu a (wieder, einfach genug). Und schließlich haben wir die alle wichtigen current = next;, die current zu b.

So auf der nächsten iteration der while-Schleife, mit next eingestellt b, result eingestellt a, und current eingestellt b starten wir über:
```
next = current->next;

//NULL<-a<-b  c ...
current->next = result;

result = current;
```
Dann tun wir es wieder:
```
next = current->next;

//NULL<-a<-b<-c  d ...
current->next = result;

result = current;
```
Haben wir einmal bekommen, um das Letzte Element in der verknüpften Liste (e in diesem Beispiel), geschieht dies:
```
next = current->next; //next becomes NULL

//NULL<-a<-b<-c<-d<-e
current->next = result;

result = current; //result is now e

current = next; //current is now NULL
```
Jetzt, da current NULL ist, wird die while-Schleife beendet, und wir bleiben mit:
```
*headRef = result;
```
die, wie Sie sehen können, jetzt macht headRef Punkt zu e, Behandlung von e als die neue erste Element in unserer Link-Liste, mit e->next Hinweis auf d, d->next Hinweis auf c usw.

InformationsquelleAutor Dan Tao

Machte ich ein Diagramm im Punkt, dass ich denke, wird grafisch erklären, was Los ist:

Visuelle Erklärung Leitung notwendig, für die Umkehrung der Verlinkten Liste datastructure-code?

Link zum full-size image

Und hier ist der (schlampig) dot-Quelle, falls jemand interessiert:

digraph g {
    label = "Start"
    subgraph cluster_1
    {
        a1 -> b1 -> c1;
        current1 -> a1;
        result1
        a1 [label="a"]
        b1 [label="b"]
        c1 [label="c"]
        current1 [label="current"]
        result1 [label="result"]
    }
    label = "Once through loop"
    subgraph cluster_2
    {
        current2 -> b2;
        result2 -> a2;
        b2 -> c2;
        a2 [label="a"]
        b2 [label="b"]
        c2 [label="c"]
        current2 [label="current"]
        result2 [label="result"]
    }
    label = "Twice through loop"
    subgraph cluster_3
    {
        current3 -> c3;
        result3 -> b3;
        b3 -> a3;
        a3 [label="a"]
        b3 [label="b"]
        c3 [label="c"]
        current3 [label="current"]
        result3 [label="result"]
    }
    label = "Final"
    subgraph cluster_4
    {
        result4 -> c4 -> b4 -> a4;
        a4 [label="a"]
        b4 [label="b"]
        c4 [label="c"]
        current4 [label="current"]
        result4 [label="result"]
    }
    label = ""

}

Dies ist viel hilfreicher. Kein Wunder, dass Sie sagen, ein Bild sagt mehr als tausend Worte

InformationsquelleAutor Mark Rushakoff

2

Check-out diese Seite für eine visuelle Darstellung.

Es sieht aus wie eine gute codeproject Erklärung hier zu (Siehe Schritt 3).

InformationsquelleAutor SwDevMan81
1

Liste sah aus wie:
```
=>(1) => => => => => => => => =>(10)
```
wir Umgekehrt jedes Stück von der Liste
```
<=(1) => => => => => => => => =>(10)
<=(1) <= => => => => => => => =>(10)
<=(1) <= <= => => => => => => =>(10)
...
<=(1) <= <= <= <= <= <= <= <= <=(10)
```
so, jetzt starte ist am Ende, und wir schauen uns die Liste aus dem anderen Blickwinkel und sehen:
```
=>(10) => => => => => => => => =>(1)
```
- Bieten Sie schematische Erklärung, wie eigentlich die Dinge sind passiert in jedem Schritt ?
- überprüfen Sie den link in dem anderen Kommentar: openasthra.com/c-tidbits/reverse-linked-list-using-3-ptrs
- Ja, meine Antwort gibt eine visuelle Darstellung
InformationsquelleAutor Valentin Golev

-2

Sehen hier für eine gute Erklärung. Hier der Auszug:

public class List {
    private class Node {
        int data;
        Node next;
    }
   private Node head;

   public void reverse() {
      if (head == null) return;
      Node prev = null,curr = head,next = null;
      while (curr != null) {
         next = curr.next;
         curr.next = prev;
         prev = curr;
         curr = next;
      }
      head = prev;
   }
}

The list:
==========
1->2->3->4->5
------------------------------------------------------------------
Running of the code:
============================
At start:
**********
head = 1;
prev = null,curr = 1, next = null
1st iteration of while loop:
******************************
next = 2;
2->3->4->5
curr.next = null;
1->null
prev = 1;
1->null
curr = 2;
2->3->4->5
2nd iteration of while loop:
******************************
next = 3
3->4->5
curr.next = 1
2->1->null
prev = 2
2->1->null
curr = 3
3->4->5
3rd iteration of while loop:
******************************
next = 4
4->5
curr.next = 2
3->2->1->null
prev = 3
3->2->1->null
curr = 4
4->5
4th iteration of while loop:
******************************
next = 5
5->null
curr.next = 3
4->3->2->1->null
prev = 4
4->3->2->1->null
curr = 5
5->null
5th iteration of while loop:
******************************
next = null
null
curr.next = 4
5->4->3->2->1->null
prev = 5
5->4->3->2->1->null
curr = null
There is no 6th iteration and the while loop terminates since 
curr is null and the check is for curr != null.
last statement: 
==================
head = prev
This statement leaves the list reversed with referencing head with the reversed node prev 
to become the new head node.

InformationsquelleAutor

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.