Durchqueren Sie eine einfach verkettete Liste in der Reihenfolge

Ich habe versucht zu denken, eine Weise zu durchqueren, eine einfach verkettete Liste.

Dies so weit ist, was ich getan habe:

#include <iostream>

typedef struct node {                                                               
      int data;               //will store information
      node *next;             //the reference to the next node
};  


int printList(node *traverse) {
    if (traverse->next == NULL) {
        return -1;
    }
    traverse=traverse->next;
    printList(traverse);
    cout << traverse->data << endl;
    return 0;
}

int main() {
    node *head = NULL;      
    for (int i = 0; i < 10; i++) {
        node *newEntry = new node;
        newEntry->data = i;
        newEntry->next = head;
        head = newEntry;
    }
    printList(head);
    return 0;
}

Kann ich nicht denken, eine Möglichkeit zum drucken der letzten Stelle(9) in printList() Funktion. Wie würde ich in der Lage sein, dies zu erreichen?
Meine zweite Frage ist, wie kann ich die traverse gleiche in einer while-Schleife statt einer rekursiven Funktion.

Wie einige von Ihnen versucht zu beantworten, bevor, ich bin nicht auf der Suche nach Durchlaufen dieser von 9 auf 0, Das sollte traverse von 0 bis 9, Sie können finden Sie in der Ausgabe von http://codepad.org/ynEdGc9S

  • Wenn dies Produktions-code dann benutzen Sie std::list. Wenn nicht, dann genießen.
  • Mehr wie std::forward_list.
  • SB Touche
InformationsquelleAutor Sarp Kaya | 2013-07-03
  1. 3

    Gibt es hier ein paar Dinge:

    In main() die Weise, die Sie die Liste erstellen ist falsch. Zeichnen Sie, was Sie tun, werden Sie feststellen, dass Ihre head ist das Letzte Element in der Liste, D. H., es wird wahrscheinlich einen Wert von 9. (Drucken-Kopf-Wert nur vor dem Aufruf von printList um dies zu überprüfen).

    Lassen Sie mich erklären (Folgen Sie entlang in Ihrem code) mit der iteration i = 1:

    Aktueller Stand: head=[0]

    1. Eine neue temporäre Knoten zugeordnet ist [ ]
    2. Dann ordnen Sie die Daten, um es [1]
    3. Dann setzen Sie mit dieser temporären Knoten ist neben Ihrem Kopf [1]-->[0] ; head=[0]
    4. Dann setzen Sie mit Kopf, um diese temporären Knoten [1]-->[0] ; head = [1]

    So können Sie sehen, was hier passiert. Der Kopf sollte noch [0] und seine nächsten sein sollten [1] nicht die andere Weise herum.

    Können Sie erkunden und überlegen Sie sich die richtige Art, dies zu tun.

    ListBox, diese ist Ausdruck der rekursiven stack und nicht der Traversierung. Traversal würde in umgekehrter Reihenfolge drucken, weil Ihre Liste ist in umgekehrter Reihenfolge (überprüfen Sie den vorhergehenden Abschnitt ^ warum).

    Dies ist die richtige Art und Weise zu drucken, den link in einem traversal. Dies wird drucken Sie die Elemente der Liste in der Art, wie Sie sind.
    , Wenn Sie überprüft, für die traverse->next==NULL, traverse gehalten, das Letzte element ist. Da Sie nur beendet die Rekursion durch zurückgegeben -1, das Letzte element wurde nie gedruckt.

    int printList(node *traverse) {
   if (traverse == NULL) {  
       return -1;
    }
    cout << traverse->data << endl;
    printList(traverse->next);
    return 0;
}

    Iterative

    int printList(node *traverse) {
   while(traverse != NULL) {  
    cout << traverse->data << endl;
    traverse = traverse->next;
   }
}

    Fühlen Sie sich frei, Fragen zu stellen, etc.

    InformationsquelleAutor
  2. 1

    Statt if (traverse->next == NULL) versuchen if (traverse == NULL)

    Diese Weise das drucken des aktuellen Knotens, wenn es eine tatsächliche Knoten mit Daten. Sie dann recurse. Schließlich, am Ende werden Sie recurse in eine NULL Zeiger, die Sie können leicht entweichen.

    • Segmentierung Fehler
    InformationsquelleAutor Chris
  3. 0

    Als Antwort auf den zweiten Teil, könnte der code wie folgt Aussehen:

    void printList_iter(node* node)
{
    while (node)
    {
        cout << node->data << endl;
        node = node->next;
    }
}

    Diese wird in einer Schleife durch die Liste, drucken jedes element, bis es zu einem NULL-Knoten, was bedeutet, dass das Ende der Liste. Es ist ein ziemlich standard-iteration-Algorithmus.

    • Dies gilt nicht drucken, was ich will, Mir Abzüge von 0 bis 8, in der Erwägung, dass diese Drucke von 9 auf 0
    • oh, sorry, ich wusste nicht, waren die Werte in umgekehrter Reihenfolge. Ich Mach meinen code.
    • eigentlich drucken die Liste in umgekehrter sehr viel einfacher Rekursion als iteration mit. Warum brauchen Sie diesen Algorithmus werden iterativ?
    • Vor kurzem habe ich in einem interview gefragt. So Frage ich mich die Antwort.
    • Dieses ist, weil Ihre version druckt die Liste in umgekehrter, diese Drucke es in der Reihenfolge wie du gefragt. Der Kopf ist in der Regel als den Beginn der verketteten Liste. Wenn Sie dies ändern, dann seien Sie nicht überrascht, um Antworten zu erhalten wie diese.
    • OK, ich werde es zu beheben Dank.
    • wenn Sie wollen, es zu tun iterativ (in umgekehrter Reihenfolge), werden Sie brauchen, um eine stack-Datenstruktur (zu verdinglichen der implizite Aufruf-stack an, der erzeugt werden würde, wenn der Algorithmus wurden rekursiv). Willst du mir gehören?

    InformationsquelleAutor feralin
  4. 0

    Warum nicht Sie interchange diesen Aussagen?

    traverse=traverse->next;
printList(traverse);
cout << traverse->data << endl;

    Dies sollte geändert werden zu:

    cout << traverse->data << endl;
traverse=traverse->next;
printList(traverse);

    Sollte diese Arbeit. Und ändern Sie dann

    if(traverse->next==NULL)

    zu

    if(traverse==NULL)
    • Ich sehe nicht den Unterschied zwischen den ersten beiden code-snippets.
    • sorry. bearbeitet
    InformationsquelleAutor Aswin Murugesh
Schreibe einen Kommentar