Wie man eine verlinkte Liste mit bubble-sort?
Ich versuche, mit bubble-sort in der Reihenfolge zu Sortieren, eine verknüpfte Liste. Ich benutze curr und trail um die traverse durch die Liste. curr soll einen Schritt Voraus sein Weg immer. Das ist mein code bisher:
void linked_list::sort ()
{
int i,j=0;
int counter=0;
node *curr=head;
node *trail=head;
node *temp=NULL;
while (curr !=NULL)
{
curr=curr->next; //couting the number of items I have in my list.
counter++; //this works fine.
}
curr=head->next; //reseting the curr value for the 2nd position.
for (i=0; i<counter; i++)
{
while (curr != NULL)
{
if (trail->data > curr->data)
{
temp=curr->next; //bubble sort for the pointers.
curr->next=trail;
trail->next=temp;
temp=curr; //reseting trail and curr. curr gets back to be infront.
curr=trail;
trail=temp;
if (j==0) //i'm using j to determine the start of the loop so i won't loose the head pointer.
{
head=trail;
}
}
j++;
trail=curr;
curr=curr->next; //traversing thru the list. nested loop.
}
trail=head;
curr=trail->next;
curr->next=trail->next->next; //traversing thru the list. outer loop.
j=0;
}
}
Was vermisse ich hier?
Und was genau ist das problem?
Sie dürfen
Sie dürfen
std::swap
, und entfernen Sie temp
. BTW, sollten Sie diese Frage im code-review-Bereich.InformationsquelleAutor Reboot_87 | 2013-10-22
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ihnen fehlen mehrere Dinge; das wichtigste ist, verknüpfte Listen sind keine arrays, und als solche können Sie nicht einfach tun, bestimmte algorithmen mit beiden abwechselnd. Mit, bitte beachten Sie Folgendes:
next
zu springen).Nun nehmen Sie einen Blick auf die folgenden deutlich anderen Ansatz. Es ist etwas in, ist von größter Bedeutung für das Verständnis des gesamten Algorithmus, aber ich werde speichern Sie es für die nach dem code :
Dies ist völlig anders, als Sie wahrscheinlich erwartet. Der Zweck dieser einfachen übung ist es, festzustellen, dass wir Bewertung Daten, aber wir sind eigentlich Sortierung Zeiger. Beachten Sie, dass außer für
p
, das ist immer der Kopf der Liste, wir verwenden keine zusätzlichen Zeiger auf Knoten. Stattdessen verwenden wir Zeiger-zu-Zeiger zu manipulieren, die Zeiger begraben in der Liste.Zeigen, wie dieser Algorithmus funktioniert, die ich geschrieben habe eine kleine test-app, die macht, eine zufällige Liste von Integer-zahlen, dann stellt sich die oben lose auf der genannten Liste. Ich habe auch geschrieben, eine einfache print-Dienstprogramm zum drucken der Liste von jedem Knoten an das Ende.
Habe ich auch geändert, der ursprüngliche Algorithmus um den Druck nach jedem Durchgang, swaps etwas:
Beispiel-Ausgabe
Ein Weiteres Beispiel
Beachten Sie, wie, sobald wir ein bereits sortiert segment Links in unserem stetig abnehmenden Quelle-Liste, sind wir fertig.
Zusammenfassung
Ich stark beraten, zu Fuß durch den oben beschriebenen Algorithmus mit einem debugger, um besser zu verstehen, wie es funktioniert. In der Tat, empfehle ich, dass bei den meisten algorithmen sowieso, aber algorithmen, die eine pointer-to-pointer-Aktionen kann ein wenig entmutigend sein, bis Sie verstehen, wie mächtig die wirklich sind. Dies ist nicht der einzige Weg, um diese Aufgabe zu erfüllen, sondern ist ein intuitiver Ansatz, wenn man bedenkt, wie verketteten Listen verwaltet werden, und wie alles, was Sie wirklich tun, ändern der gespeicherten Werte in Pointer in vorhersagbaren stellen.
Es bedeutet, bis die Zeiger angesprochen, die von der pp Zeiger-auf-Zeiger ist NULL. Denken Sie daran, Zeiger sind nichts anderes als Variablen konzipiert, halten Sie eine Adresse als Wert hat. Ein Zeiger auf Zeiger ist nur eine weitere Ebene der Dereferenzierung. I. e. Es enthält die Adresse eines Zeigers, die möglicherweise halten sich die Adresse von etwas. Ich check die Zeiger angesprochen
pp
durch dereferenzieren, also*pp
Ist das eigentlich bubble-sort? Da bist du nicht vergleichen angrenzende Paare
InformationsquelleAutor WhozCraig
Grundsätzlich, hier ist eine überarbeitete Sortieren. Sie hatten meist die richtige Idee. Vor allem Sie versaut das tauschen der Pointer für die Knoten. Hier ist ein überarbeiteter Algorithmus, der ist etwas einfacher. Auf die äußere Schleife ist eine
for
die Anzahl der Elemente in der Liste. Dann die innere Schleife ist das pushen von Werten an das Ende der Liste schrittweise. Wir verfolgen zwei Zeigertrail
undcurr
. Und wir vergleichencurr
undcurr->next
.InformationsquelleAutor pippin1289
Ich denke, das ist, was Sie suchen:
InformationsquelleAutor Daniel Gi
Bubble-sort-array mit leicht modifiziert werden, um bubble-sort mit verlinkten Liste
InformationsquelleAutor josepainumkal
Hier ist die Java-Implementierung des Bubble-Sort-auf Verlinkten Liste:
InformationsquelleAutor Pratik Patil