Sortieren mit verknüpften Liste

Question

Ich habe zwei Felder nämlich ID und Name. Nach dem Einfügen eines Knotens in eine verknüpfte Liste möchte ich ihn in absteigender Reihenfolge nach ID sortieren. Angenommen, es ist möglich, dass verschiedene Personen dieselbe ID haben können. Für das Beispiel

1001 CHARICE -> 1001 JUSTIN -> 1001 ANNA -> 1000 CHYNA -> 888 MIKEY -> NULL 

Die endgültige Liste soll wie folgt aussehen:

1001 ANNA -> 1001 CHARICE -> 1001 JUSTINE -> 1000 CHYNA -> 888 MIKEY -> NULL 

ich die Namen mit der gleichen ID in aufsteigender Reihenfolge sortieren, während die IDs in absteigender Reihenfolge sortiert werden. Hier ist mein Code:

NODE* insert_std(NODE *head, NODE* std){ 
    NODE *prev, *cur; 
    if(head==NULL) return std; 
    cur = head; 
    while (cur != NULL && std->ID < cur->ID){ 
     prev = cur; 
     cur = cur->next; 
    } 
    if(std->ID == cur->ID){ 
     while (cur != NULL && strcmp(std->name, cur->name)>=0){ 
      prev = cur; 
      cur = cur->next; 
     } 
    }  
    if (head==cur){ 
     if(std->ID >= head->ID) { 
     std->next = head; 
     head = std; 
     } 
    } else { 
     std->next = cur; 
     prev->next = std; 
    } 
    return head; 
} 

Aber ist nicht sortiert, wie ich es will. Was mache ich falsch?

Answer 1

Wenn Sie in Ihrer Einfügefunktion zwei Knoten vergleichen, vergleichen Sie zuerst die beiden IDs. Wenn einer kleiner als der andere ist, sagt dies Ihnen, welcher Knoten zuerst kommen soll. Wenn die IDs identisch sind, müssen Sie die Namen vergleichen, um zu entscheiden, welcher Knoten zuerst kommt.

Dies entspricht der Änderung std->ID <= cur->ID und std->ID > head->ID. Wenn ich Sie wäre, würde ich eine Hilfsfunktion schreiben, die zwei Zeiger auf NODE nehmen würde (nennen Sie sie A und B), vergleichen Sie sie in der oben beschriebenen Weise und geben Sie true zurück, wenn Knoten A vor Knoten B kommt. Integrieren Sie diese Funktion in Ihre insert_std ist dann trivial.

Answer 2

Ersetzen Sie einfach Ihre Vergleiche auf ID-Werte, und berücksichtigen Sie auch den Namen (zum Beispiel mit strcmp), wenn die ID-Werte identisch sind. Der einfachste Weg besteht darin, eine separate Funktion zum Vergleichen zweier Datensätze zu schreiben, die diesen Job ausführen.

Answer 3

&& std->ID == cur->ID auf der while-Schleife hinzufügen

while (cur != NULL && std->ID == cur->ID && strcmp(std->name, cur->name)>=0)