Sortieren einzelner kreisförmiger verknüpfter Liste

Question

Ich versuche die einzelne kreisförmige verknüpfte Liste nach jeder Änderung zu sortieren. Aber mein Code funktioniert nicht. Ich habe es auf der Auswahl Sortieralgorithmus basiert. Ich mache das schon seit Stunden, aber ich bekomme nicht den richtigen Code.

void editList(node *head, int value, int newValue) 
{ 
    node *traverser = head; 
    do { 
     traverser = traverser -> next; 
    }while(traverser -> data != value); 

    traverser -> data = newValue; 

    node *index; 
    node *selection; 
    node *temp = new node; 

    for(index = head; index -> next != head; index = index -> next) { 

     for(selection = head; selection -> next != head; selection = selection -> next) { 
      if(index -> data > selection -> data) { 
       temp -> data = index-> data; 
       index -> data = selection -> data; 
       selection -> data = temp -> data; 

      } 
     }//End of outer loop 

    }//End of sorting 

    return; 
}//End of editList() 

Answer 1

wenn der Quellcode analysiert vorgesehen, die Sortieralgorithmus vorgeschlagen wird, ist sehr nahe an der erwarteten ‚Auswahl Sortieralgorithmus‘.

Die beiden verschachtelten Schleifen sind vorhanden, machen aber unabhängige Funktionen.

Schritt 1 - Durchführen einer echten Nested-Schleife durch Einfügen der Bedingung von der ersten in die zweite Schleife.

Um die gesamte Liste zu sortieren, beginnt die Auswahl am nächsten Knoten des Index.

for(index = head; index -> next != head; index = index -> next) { 
    // start the selection from the index->next 
    for(selection = index->next; selection -> next != head; selection = selection -> next) { 
     if(index -> data > selection -> data) { 
      temp -> data = index-> data; 
      index -> data = selection -> data; 
      selection -> data = temp -> data; 

     } 
    }//End of outer loop 
}//End of sorting 

Bonus 1 - weil der Swap nur auf data Ebene durchgeführt wird, anstatt eine temporäre Knoten zu verwenden, nur eine ganze Zahl verwenden.

// use just an integer 
int temp; 
... 
temp = index-> data; 
index -> data = selection -> data; 
selection -> data = temp; 

Statt:

// allocated but never freed 
node *temp = new node; 
... 
temp -> data = index-> data; 
index -> data = selection -> data; 
selection -> data = temp -> data; 

Bonus 2 - für den ersten Suchteil die Knoten zu lokalisieren, die mit int value ersetzt werden, warum nicht die gleiche Schleifenstruktur unter Verwendung einer Nichts zu verhindern Endlosschleife, wenn kein Knoten den gesuchten Wert hat.

node *traverser; 
// a ending loop to search a value into a circular-list 
for(traverser = head; traverser->next != head; traverser = traverser -> next) { 
    if (traverser -> data == value) { 
     traverser -> data = newValue; 
     break; 
    } 
} 

Statt

node *traverser = head; 
do { 
    traverser = traverser -> next; 
}while(traverser -> data != value); 

traverser -> data = newValue;