Reverse-Traversierung einfach verknüpfte Liste in C++

Sind Sie vier mögliche Wege, dies zu erreichen, von denen jede Ihre eigenen Vorzüge.

Rekursion

void print_list(node* traverse)
{
    if (traverse == NULL) return;
    print_list(traverse->next);
    std::cout << traverse->data << std::endl;
}

Dies ist vielleicht die erste Antwort in den Sinn. Jedoch, der Prozess-stack-Größe ist begrenzt, so dass die Rekursion hat ein ziemlich niedriges limit. Eine große Liste provozieren einen stack-überlauf. Dies ist nicht ein sehr gutes design in C++.

Iteration

void print_list(node *n)
{
    using namespace std;
    deque<node*> res;
    for(;n != NULL; n = n->next) res.push_back(n);
    for_each(res.rbegin(), res.rend(), [](node* n){cout << n->data << endl;});
}

Natürlich, wenn Sie wollen, machen es die iterative Art und Weise, werden Sie brauchen, um Stapel der Knoten Zeiger selbst (auf der Prozess-heap) und nicht delegieren diese Aufgabe an die call-stack. Mit dieser Methode können Sie drucken viel größere Listen, und ist O(n) Berechnungen. Es ist jedoch O(n) Speicherverbrauch, aber Sie haben bereits eine Liste, die mit O(n) Speicher. Also das sollte kein Problem sein. Jedoch können Sie wirklich brauchen, um zu vermeiden, den Speicherverbrauch. Das bringt uns zur nächsten Idee.

Doppel-iteration

void print_list(node *head)
{
    node* last = NULL;
    while(last != head)
    {
        node* current = head;
        while(current->next != last)
            current = current->next;
        std::cout << current->data << std::endl;
        last = current;
    }
}

Dies mag eine dumme Lösung, da es O(n^2) Komplexität, aber das ist Rechen-Komplexität. Es hat O(1) Speicher-Komplexität und je nach dem aktuellen Kontext und dem genauen problem, kann es die Antwort sein, die Sie benötigen. Aber diese O(n^2) Komplexität ist viel zu bezahlen. Vor allem, wenn n so groß ist, dass Sie vermeiden wollte, ein weiteres O(n) - allocation. Das bringt uns zu der letzten Idee.

Hack der container

void print_list(node *head)
{
    node* last = NULL;
    for(node* next; head != NULL; head = next)
    {
        next = head->next;
        head->next = last;
        last = head;
    }
    for(node* next; last != NULL; last = next)
    {
        next = last->next;
        last->next = head;
        head = last;
        cout << last->data << endl;
    }
}

Du zuerst ändern Sie die container, dann die Iteration in Ihrer neuen Reihenfolge. Auf einer single-Link-Liste, können Sie einfach in umgekehrter Reihenfolge die links, dann rückwärts-Iteration, während die Umkehrung der links wieder. Das schöne daran ist, es bleibt O(n) in computing, und O(1) Speicher. Das problem ist, dass Sie ungültig wird der volle Behälter, während dies zu tun : Ihre bestens Betrieb nicht verlassen die Liste Konstante : dies ist nicht exception-sicher: wenn Sie Ihren Vorgang schlägt fehl, in der Mitte der iteration, die Liste ist nicht mehr gültig. Dies kann oder kann nicht ein Problem sein, je nach problem.

InformationsquelleAutor lip

Wenn Ihre Liste ist [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:

1) Sie möchten, um die Ausgabe der Liste Umgekehrt, Ihre ListBox sollte dann so Aussehen:

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

2) ist Es nicht wirklich möglich mit einer while-Schleife, es sei denn, Sie tun wirklich hässliche Dinge wie die Verkettung jedes Knotens Daten an den Anfang des Ergebnisses Zeichenfolge, die Sie drucken möchten.

3) Ihre wichtigsten scheint sehr seltsam zu mir. Ich verstehe nicht, warum Ihr 'Kopf' variable global ist, warum nicht in der main selbst?

Nicht zuletzt, warum nicht mit std::list?

InformationsquelleAutor roptch

1) Ändern

if (traverse->next == NULL)

zu

if (traverse == NULL)

2)

while(traverse != NULL) {
    //print sth
    traverse = traverse->next;
}

3) scheint ok zu mir. Warum erklären Sie den Kopf außerhalb der main?

InformationsquelleAutor hanslovsky