C++: Hinzufügen von Knoten zu doppelt verknüpften Liste in alphabetischer Reihenfolge

Question

Ich versuche, Knoten zu einer doppelt verknüpften Liste in alphabetischer Reihenfolge in Bezug auf das Titelelement des Knotens hinzuzufügen. Bisher habe ich versucht, die Liste zu durchlaufen und nach dem Fall (strcmp(title, currTitle) > 0) zu suchen. Die Iteration funktioniert jedoch nicht (aus Gründen, die ich nicht sicher bin), da der unten aufgeführte Versuch der verknüpften Liste keine Elemente hinzufügt.

Der Satz von vier Bedingungen für den if - else-Block fügt Elemente erfolgreich zur Liste hinzu, wenn sie nicht mit dem Sortierversuch implementiert wird.

void SongList::addSongSorted(const Song &aSong) 
{ 
    //sort inputs to the list by alphabetical order of the entire title 
    char title[MAX_CHAR]; 
    char currTitle[MAX_CHAR]; 
    aSong.getTitle(title); 

    Node * newNode = new Node(aSong); 

    Node * curr = head; 
    //Increment through list as added...this does not work 
    for(curr = head; curr; curr = curr->next) 
    { 

     if(strcmp(title, currTitle) > 0) 
     { 

      if(!head) 
      { 
       head = newNode; 
       tail = newNode; 
       head->next = NULL; 
       head->prev = NULL; 
      } 
      else if(head->prev == NULL) 
      { 
       newNode->next = head; 
       head = newNode; 
       newNode->prev = NULL; 
      } 

      else if(head->next == NULL) 
      { 
       curr->next = newNode; 
       newNode->prev = curr; 
       newNode->next = NULL; 
       tail = newNode; 
      } 

      else 
      { 
       newNode->next = curr->next; 
       newNode->prev = curr; 
      } 
     } 
    } 
} 

Wie ist es, dass Inkrementieren durch die Liste und Hinzufügen an einem Knoten basierend auf dem Vergleich von Elementen nicht funktioniert? Was ist eine Lösung?

Answer 1

Wie @verbose sagt, weisen Sie currTitle niemals einen Wert zu, versuchen Sie am Anfang der Schleife curr.getTitle(currTitle) oder verwenden Sie statt dessen curr->title.

In Bezug auf das Einfügen in Reihenfolge müssen Sie sich nicht um head vorherigen Wert kümmern, nur wenn der Kopf selbst Null ist, oder der Titel kommt vor dem Kopf. Sie sollten die Liste durchlaufen, wenn der Titel nach dem aktuellen Knoten kommt und der nächste Knoten null ist, setzen Sie curr auf das nächste Element (erledigt in der for-Schleife) und überprüfen Sie erneut. Wenn das nächste Element NULL ist und der Titel nach dem aktuellen steht, haben Sie das Ende der Liste erreicht, können das Lied einfügen und brechen. Wenn der Song-Titel vor dem aktuellen steht oder gleich ist, fügen Sie den neuen Song vor dem aktuellen Song ein und kehren zurück. Beispielcode unten:

if(!head) 
{ 
    // set head to currnode, as you have 
    head = newNode; 
    tail = head; 
    next = NULL; 
    prev = NULL; 
    return; // no need to iterate through the list 
} 
bool inserted = false; 
while (!inserted) 
{ 
    curr->song.getTitle(currTitle); 
    if(strcmp(title, currTitle) > 0) 
    { 
     // If the title goes after the current title 
     if(curr->next == NULL) 
     { 
      // End of the list, insert after this node 
      curr->next = newNode; 
      newNode->prev = curr; 
      newNode->next = NULL; 
      tail = newNode; 
      inserted = true; 
     } 
     // If we don't insert here, we iterate again 
     curr = curr->next; 
    } 
    else 
    { 
     // If the title is the same, or comes before the current title, insert before curr 
     newNode->prev = curr->prev; 
     newNode->next = curr; 
     curr->prev = newNode; 
     if (curr == head) 
     { 
      head = newNode; 
     } 
     inserted = true 
    } 
} 

Answer 2

Sie vergleichen die beiden Strings, aber der zweite scheint nie initialisiert zu werden. Vermutlich kopiert aSong.getTitle(title) den Titel des aktuellen Liedes in das title[] Array. Aber wann wird jemals etwas nach currTitle[] kopiert?

Also die Elemente currTitle[] sind Müll, und der Vergleich wird nicht funktionieren. Um dies zu beheben, vergleichen Sie den Titel des Songs, den Sie einfügen möchten, mit den Titeln der Songs, die sich bereits in der Liste befinden. Sie wollen wahrscheinlich etwas wie strcmp(title, curr->title).

Natürlich müssen Sie zuerst prüfen, ob ein Song existiert, bevor Sie den Vergleich durchführen. Überprüfen Sie zuerst, ob ein Song unter head existiert, und wenn nicht, fügen Sie den Song als Head-Song ein. Wenn es schon ein Lied an der Spitze gibt, vergleiche die beiden Titel und bestimme, ob das neue Lied der neue Kopf sein soll oder ob es irgendwo nach dem Kopf gehen soll. Der Rest der Logik sollte einfach sein.