Einfügung sortierte verkettete Liste C++

Question

Ich versuche, einen Code zu schreiben, um eine verkettete Liste zu sortieren, die ganze Zahlen enthält, aber es funktioniert nicht, wie ich dachte, dass es basierend auf meiner Argumentation ich dafür mit Bleistift und Papier arbeitete. Anstatt die Liste zu durchlaufen, vergleicht sie das erste Wertepaar, löscht den zweiten Wert in der Liste und gibt den Rest der Liste zurück. Meine Methode Code ist:

//typedef Node * ListType; 

void insertionSort(ListType &list) { 
    ListType p = list; 
    Node * curr; 
    if(p == NULL || p->next == NULL){ 
     return; 
    } 
    while(p != NULL){ 
     curr = p->next; 
     if(curr == NULL){ 
      break; 
     } 
     if(p->data > curr->data){ 
      p->next = curr->next; 
      curr->next = p; 
     } 
     p = p->next; 
    } 
} 

Nehmen wir zum Beispiel ich mit einer Liste beginnen: 5 2 3 4 Der Ausgang I in dieser Liste nach dem Aufruf dieser Methode erhalten ist: 5 3 4

I‘ m nicht mit Zeigern. Jede Hilfe wird geschätzt!

Answer 1

Diese Art von Aufgabe funktioniert viel besser, wenn Sie anstelle eines Zeigers einen Zeiger auf einen Zeiger verwenden. Es funktioniert auch besser, wenn das neue Element separat übergeben wird und nicht am Anfang der Liste "eingefügt" wird.

Aber gehen wir mit dem, was Sie haben, und der neue Knoten ist am Anfang der Liste eingefügt, und Sie möchten es an die richtige Position verschieben.

Dann, es wird so etwas sein:

#include <iostream> 

class Node { 

public: 

    Node *next; 

    int data; 
}; 

typedef Node * ListType; 

void insertionSort(ListType &list) { 
    ListType *p = &list; 

    while ((*p)->next && (*p)->next->data < (*p)->data) 
    { 
     ListType node= *p; 

     *p=node->next; 

     node->next=node->next->next; 

     (*p)->next=node; 

     p= &(*p)->next; 
    } 
} 

int main() 
{ 
    Node *head=0; 

    int n; 

    while (std::cout << ">>> ", std::cin >> n) 
    { 
     Node *p=new Node; 

     p->data=n; 

     p->next=head; 
     head=p; 

     insertionSort(head); 

     for (p=head; p; p=p->next) 
      std::cout << p->data << " "; 
     std::cout << std::endl; 
    } 
} 

Beispielergebnisse:

$ ./t 
>>> 5 
5 
>>> 7 
5 7 
>>> 1 
1 5 7 
>>> 3 
1 3 5 7 
>>> 9 
1 3 5 7 9 
>>> 6 
1 3 5 6 7 9 
>>> 0 
0 1 3 5 6 7 9 

Der Trick hier, dass anstelle von p einen Zeiger auf den Knoten sind Sie Einfügen, p ist der Zeiger auf den Zeiger auf den Knoten, der eingefügt wird. Wenn Sie also den neuen Knoten weiter unten in der Liste "drücken" müssen, ist der "vorherige" Zeiger *p, den Sie jetzt leicht aktualisieren können.

Obwohl dies auf den ersten Blick verwirrend erscheint, ist dies viel weniger unordentlich, dass Sie den "vorherigen" Knoten verfolgen, dessen nächsten Zeiger Sie aktualisieren müssen. Alle if Statement Haarbälle gehen komplett weg. Da kommt die ganze Verwirrung her.

Auch, wenn, wie ich eingangs erwähnt, der neue Knoten ist nicht am Anfang der Liste eingefügt, und wird als separater Zeiger übergeben, dann wird dies viel einfacher zu verstehen. Aber das war dein Ausgangspunkt, also ...