Verkettete Liste mit Bubble Sort sortieren (C++)?
Das Programm ist fast fertig. Benötige Hilfe mit dem Bubblesortunterprogramm.
1 Antwort
Vermutlich ist dir der grundsätzliche Algorithmus von Bubble Sort schon geläufig.
Dann müsstest du nur noch wissen, wie man auf je zwei aufeinander folgende Elemente einer verketteten Liste zugreift und wie man sie vertauscht.
Als erstes kommt man auf die Idee, den Pointer p am Anfang der Liste a[] loslaufen zu lassen und jeweils a[p] und a[a[p].next] zu vergleichen.
Aber wie vertauscht man diese beiden Elemente? Da es sich um eine verkettete Liste handelt, sollen sicherlich nicht die Inhalte der Elemente getauscht werden, sondern die Positionen innerhalb der Liste. (Die Inhalte zu tauschen wäre jetzt zwar ziemlich einfach, aber erstens ziemlich speicherzugriffsintensiv und zweitens nicht Sinn der Übung.)
Wir müssten also den Zeiger auf a[p] und auf a[p1] tauschen. (Hierbei ist p1 = a[p].next) Aber p ist eine Schleifenvariable und wir müssten den Zeiger vom Vorgänger von a[p] neu setzen. Und den Vorgänger von a[p] haben wir nicht mehr.
Also müssen wir den Vorgänger von a[p] auch noch irgendwie merken.
D. h. wir vergleichen nicht a[p] und a[p1], sondern a[p1] und a[p2], wobei p1 = a[p].next ist und p2 = a[p1].next. Dann können wir die Zeiger a[p].next und a[p1].next tauschen. Damit die Liste weiterhin eine anständig verkettete Liste und kein Lasso und ähnliches ergibt, müssen wir noch ein paar andere Indizes tauschen (kommst du darauf, welche?)
Hierbei haben wir den Spezialfall p = a_start, den Startpunkt. Hier müssen wir ja schon a[p] vergleichen, und ggf. die direkt verfügbare Variable a_start ändern.
Willst du damit sagen, dass dies eine passendere Antwort wäre:
Ja, so was gibts. Wird vermutlich regelmäßig als Hausaufgabe oder Klausuraufgabe gestellt.
Oder gleich ein fertiger Codeblock?
toll, eine ausführliche antwort auf eine nicht gestellt frage