Rotieren von Zahlentriples einer abstrakten Liste mit Pointern

FaultyBrain

Mitglied
Hallo!

Es geht um eine Uni Aufgabe, an der ich mir schon den Kopf zerbreche.
In einer abstrakten Liste mit Elementen, die einen key-Wert besitzen und einen next-Pointer auf das nächste Element, soll in jedem Triple der erste und der dritte Wert rotiert werden.

So soll aus 1;2;3;4;5;6;7; z.B. 3;2;1;6;5;4;7 werden

Meine Idee war, die Elemente jedes Triples zwischenzuspeichern, den Pointer des ersten Elementes dann auf das vierte zu setzen, den des zweiten auf das erste usw.

Allerdings schaffe ich es nicht, die zwischengespeicherten Elemente richtig in die List einzufügen
So würde zwar 3->2->1 und 6->5->4 zwischengespeichert werden, aber in einem Schleifendurchlauf kann ich keinen Pointer zwischen zB 1->6 setzen

Man könnte natürlich jedes erste Element an vierter stelle einfügen und anschließend jedes 1+3*n te Element löschen, aber vielleicht hat ja jemand eine Idee, wie man das ganze effizient in EINER Schleife lösen kann ;)???:L

Danke schonmal
 

FaultyBrain

Mitglied
aha, und wieso nicht?


angenommen ich speichere die Elemente 1->2->3 temporär und setze die Pointer um: 3->2->1->4->5->6
Im nächsten Schleifendurchlauf wird dann 4->5->6 zwischengespeichert und ich kann nicht mehr auf die 1 zugreifen.
Und wenn ich der 1 direkt die 6 als nächstes Element zuweise, läuft meine Schleife nicht mehr über die Elemente 4 und 5.

Vielleicht habe ich auch einfach einen Denkfehler :D
 

FaultyBrain

Mitglied
Dann merk wir die "1"doch für den nächsten Schleifendurchlauf....


Dann komme ich auch nicht weiter. Dann habe ich wieder kein Element, dessen Pointer auf die 1 weist...

Eine weiter Lösung wäre, alle Elemente in einem Array zu speichern und jedes Tripel zu vertauschen und die Pointer neu zu setzen. Das stelle ich mir aber nicht sonderlich effizient vor.
 

FaultyBrain

Mitglied
verstehst du mein Problem?

angenommen ich sage p=first und lasse es über p = p.next.next.next laufen

tmp1 = p. // tmp1.next = p.next.next.next
tmp2 = p.next. // tmp2.next = tmp1
tmp3 = p.next.next. // tmp3.next = tmp2
first = tmp3 falls p = first und ansonsten? müsste tmp1.next = tmp3 des nächsten "Schleifendurchlaufs" sein, welches noch garnicht existiert.

Und speichere ich tmp1 = tmp4 des ersten Durchlaufes, um im nächsten durchlauf zu sagen tmp4.next = tmp3 , so kann ich nicht mehr auf tmp2 des ersten Durchlaufes zugreifen um tmp2.next = tmp4 zu setzen, da tmp2.next=tmp1 sein muss. Somit müsste ich in einer unendlichen Liste unendlich Elemente zwischenspeichern:bahnhof:
 
Zuletzt bearbeitet:

stg

Top Contributor
Dann komme ich auch nicht weiter. Dann habe ich wieder kein Element, dessen Pointer auf die 1 weist...

Die "1" hast du doch vorher schon wieder in die List gepackt. Der ist es herzlichst egal, was auf sie verweist. Du musst dir nur die "1" merken, um im nächsten Schleifendurchlauf den Nachfolger der "1" richtig zu setzen.
 

FaultyBrain

Mitglied
Die "1" hast du doch vorher schon wieder in die List gepackt. Der ist es herzlichst egal, was auf sie verweist. Du musst dir nur die "1" merken, um im nächsten Schleifendurchlauf den Nachfolger der "1" richtig zu setzen.

das habe ich verstanden :) Aber um mir die 1 zu "merken" muss ich doch eine Kopie von ihr erstellen. Und nur dieser Kopie kann ich dann den richtigen Nachfolger zuweisen, oder habe ich da eine Möglichkeit übersehen?
Und dann gibt es kein Element, welches auf die Kopie weist.
 

FaultyBrain

Mitglied
Habe jetzt eine Lösung:

Anstatt neue Element zu erstellen, einfach die Werte von Element 1 und 3 jedes Triples zwischenspeichern und tauschen.
Die Schleife über jedes Triple laufen lassen, solange bis ein Element oder Element.next oder Element.next.next = null ist :bloed:
 

Neue Themen


Oben