Arrayproblem

[Inf3rnus]

Ich verzweifle hier allmählich....kann es denn sein das ich so blöd bin?
Anfangs dache ich das sei ein einfach zu lösendes Problem, für mich hat es sich jedoch nach langen probieren als doch recht harte Nuss herausgestellt.

Folgendes Problem:

Ich habe ein 2 Dimensionales Array bei dem der erste Index den Punkt in einer 2 Dimensionalen Ebene beschreibt und der 2te die jeweilige Koordinate.

also das sieht dann so aus

char array [100] [2];

[100] = 100 Mögliche Punkte in der 2D Ebene
[2] = Speichert die X bzw. Y-Koordinaten ([0] = Y-Koord. [1] = X-Koord.)

Ich möchte nun den vordersten Punkt ändern zB( X-Koord. um 1 erhöhen)
und dann alle weiteren Punkte in den jeweiligen vorangegangenen verschieben.
Also zB:

Punkt X-Koord. Y-Koord. neue X-Koord. neue Y-Koord.
-----------------------------------------------------------------------
1 3 3 4 3
2 2 3 3 3
3 1 3 2 3
4 0 3 1 3


Ich hoffe ihr konntet halbwegs verstehen was ich meine.

mfg Inf3rnus

[eViL_oNe]

dies würde ich rein prinzipiell mit einer anderen Datenstruktur als mit einem Array angehen. Zuerst definieren wir uns ein Datenobjekt für einen Punkt, der im Prinzip aus zwei Werten (X und Y) besteht.

Das Verschiebeproblem ist mit einem Array oder einem auf einem Array basierenden Struktur prinzipiell bedingt schwer und vor allem fehleranfällig und langsam lösbar. Besser wäre etwa eine doppelt verkettete Liste. Hier muss man zum verschieben nach links einfach ein Element aus der Liste entfernen und hinten ein neues hinzufügen, beim Verschieben nach rechts an der Wunschposition ein neues hinzufügen und das letzte Element wegschmeissen

Wir brauchen also neben einem Punkt einen Punktknoten, der sich aus 3 Werten zusammensetzt:

Punkt
linker Knoten
rechter Knoten

nun sollte man irgendwo einen Verweis auf das erste und das letzte Element hinterlegen, mit OOP geht das natürlich recht einfach: man definiert sich einfach eine Containerklasse. Die jeweiligen Listenenden bekommen als Wert für linker/rechter Knoten ein NIL (oder null in vielen Sprachen)

Einfüge- und Löschoperationen sind auf diese Struktur sehr effizient. Das Suchen nach Elementen ist kaum weniger effizient als in einem indizierten Container wie einem Array. Lediglich der Direktzugriff auf ein Element ist äusserst diffizil -> hier muss man durch die Struktur iterieren, bis man die gewünschte Elementnummer erreicht hat. Mit etwas Zusatzaufwand lässt sich aber eine zusätzliche Indexstruktur ablegen!

[DarkTom]

Ich würde hier sogar zu einer Ringliste tendieren, bei der der Nachfolger des letzten Elements wieder das erste ist. Wir sparen uns den extra Zeiger auf das Ende, da wir dies als Vorgänger des Kopfelements bekommen und die gewünschte Aktion ist nur:

Zeiger vom Kopfelement auf dessen Vorgänger umbiegen.
Dessen Inhalt ändern in die modifizierte Version des alten Kopfelements.


Das ganze wiederum lässt sich auch relativ einfach mit einem Array realisieren. Alles was wir zusätzlich brauchen ist eine Variable kopfIndex, die den Index angibt, an dem sich der Kopf befindet. Der ist jetzt nicht mehr immer an der Stelle 0. Und immer, wenn wir vom Kopf ausgehend über die Elemente iterieren, müssen wir halt von Index n-1 auf Index 0 springen.

Damit ergibt sich deine Aktion zu:idx = kopfIndex
kopfIndex = kopfIndex - 1
IF kopfIndex < 0 THEN kopfIndex = n-1
array[kopfIndex][0] = array[idx][0] + 1
array[kopfIndex][1] = array[idx][1]

[Inf3rnus]

@ evil_one

Ich verstehe schon was du meinst, aber da das ganze nicht OOP ist und in normalen C realisiert wird denke ich das ich bei Arrays bleibe anstatt Listen etc. zu verwenden, vl. hab ich dich aber auch nur falsch verstanden, dann tut mir das natürlich Leid

@ DarkTom

Ich verstehe deine Grundidee des Rings jedoch habert es ein wenig am Code den du geschrieben hast.

idx = kopfIndex
kopfIndex = kopfIndex - 1
IF kopfIndex < 0 THEN kopfIndex = n-1
array[kopfIndex][0] = array[idx][0] + 1
array[kopfIndex][1] = array[idx][1]

einmal Grundsätzlich die was folgende Zeile bedeutet:

array[kopfIndex][0] = array[idx][0] + 1
was genau macht das + 1 da hinten??? Ist das eine (ich glaub dein Code ist Basic) schreibweise oder funktioniert sowas auch in C?

Ich hoffe ihr könnt mir meine dumme Fragerei verzeihen und noch ein weiteres mal helfen ;)

mfg Inf3rnus

[eViL_oNe]

auch in C kann man das ganze wohlgeformt lösen (abgesehen davon, dass man auch in C objektorientiert programmieren könnte, auch wenn das mit etwas Zusatzaufwand verbunden ist ;)). Dann erstellt man sich halt structs statt Klassen -- eine Struktur für eine verkettete Liste oder einen Ring findet man in jedem C-Buch ;)

[DarkTom]

Das soll Pseusocode sein. Ich hatte keinen spezielle Programmiersprache im Sinn, wobei ich aber davon ausging, dass Arrays bei 0 beginnen. Realisierbar sollte das in jeder iterativen Programmiersprache sein, die Arrays kennt, definitiv auch in C.

Ich nummeriere die Zeilen mal durch und erläutere dann.
1) idx = kopfIndex
2) kopfIndex = kopfIndex - 1
3) IF kopfIndex < 0 THEN kopfIndex = n-1
4) array[kopfIndex][0] = array[idx][0] + 1
5) array[kopfIndex][1] = array[idx][1]
1) Ich speichere mir das alte Kopfelement, da ich ja dessen Daten verändern möchte.
2) + 3) Das frühere letzte Element wird nicht mehr gebraucht, dafür brauche ich ein neues Kopfelement. Also kann ich das recyclen. Das bisherige Kopfelement rückt an Platz 2.
4) Das neue Kopfelement soll ja das alte sein, bei dem die x-Koordinate um eins erhöht ist. Daher die "+1".
5) Die y-Koordinate hingegen wird nur kopiert.

[Inf3rnus]

Verstehe tut mir leid für meine blöde Frage.
Muss jedoch sagen das ich diese Definition schon selbst wusste mir geht es darum wie ich wenn ich vorne eines hinzufüge und das letzte wegfällt nun mit einer for-oder anderen Schleife es so durchlaufen kann, dass jetzt alle restlichen um eines nach hinten verschoben werden.
Ich erkläre noch mal ganz kurz wie es bei mir nun genau aussieht denke das kam etwas falsch rüber, wofür ich mich entschuldigen möchte, oder ich verstehe einfach deine Art der Definition nicht.

Also mein Array sieht folgendermaßen aus:

das Element [0][0] ist das Ende also der hinterste/letzte Punkt und von dem die Y-Achse
das Element [0][1] beschreibt die X-Achse des letzten Punktes

Nach oben hin kann es max. 100 Punkte mit zugehöriger X und Y-Koordinate geben also [100][0/1]

Das Kopfelement ist also demnach [n][0/1] wobei n <= 100 sein muss
da ich mit 3 Punkten beginne und ein jeweiliges hinzufügen mitzähle ist also n bekannt.

nun habe ich zB folgende Werte gespeichert:

[0][0] = 3 [0][1] = 3
[1][0] = 3 [1][1] = 4
[2][0] = 3 [2][1] = 5
[3][0] = 3 [3][1] = 6

Dies entspricht also einer geraden von dem Punkt (3,3) aus, zu dem Punkt (3,6)
Der Kopf der mit n bzw. n-1 beschrieben wird (da ja 3 Punkte im Array von 0 bis 2 entsprechen) soll nun in jede beliebe Richtung verschoben werden können außer in die Richtung in der bereits ein Punkt vorhanden ist.
Also demnach X+1 oder Y+1 oder Y-1 nicht aber X-1 wo bereits ein Punkt steht.
Alle anderen Pukte müssen dann um eines nach hinten verschoben werden wenn [n][0/1] neue Koordinaten bekommen.
Wenn wir davon ausgehen das der neue Punkt X+1 verschoben ist, kommen wir zu folgenden Bild:

[0][0] = 3 [0][1] = 4
[1][0] = 3 [1][1] = 5
[2][0] = 3 [2][1] = 6
[3][0] = 3 [3][1] = 7

Rot ist der neu hinzugefügte Wert

Der vorher letzte Wert also P(3,3) ist hinten rausgworfen worden.

Wie gesagt vl. hast du das alles schon gewusst und ich nur deine Antwort nicht verstanden, wenn dem so ist, bitte schick mir ne kleine Visuelle Darstellung des Arrays im vorher/nachher Vergleich, dann vesteh ich vl. besser was du meinst ;)

mfg Inf3rnus

[DarkTom]

Hör auf, dich für "dumme Fragen" zu entschuldigen ... es gibt keine dummen Fragen. :)

Grundsätzlich hatte ich dich schon verstanden. Nur, dass für mich die Liste vom Kopf aus in eine andere Richtung ging. Aber das ist Geschmackssache, ich passe mich im Folgenden deiner Richtung an. Wichtig ist, dass bei mir der Kopf seine Position ändert und nicht immer bei n liegt. Darum muss ich mir die Position des Kopfes zusätzlich speichern.

Ich nehme mal dein Beispiel. Das könnte so aussehen, wie bei dir:

a)
kopfIndex = 3
[0][0] = 3 [0][1] = 3
[1][0] = 3 [1][1] = 4
[2][0] = 3 [2][1] = 5
[3][0] = 3 [3][1] = 6


oder auch

b)
kopfIndex = 1
[0][0] = 3 [2][1] = 5
[1][0] = 3 [3][1] = 6
[2][0] = 3 [0][1] = 3
[3][0] = 3 [1][1] = 4

In beiden Fällen erhälst du das gleiche, wenn du beginnend beim kopfIndex die Koordinaten ausgibst und dabei sobald du den Rand des Arrays erreichst am anderen Ende weitermachst. Die betrachteten Indizes in den beiden Fällen sind:

a) 3, 2, 1, 0
b) 1, 0, 3, 2


Mit der Vorgehensweise, die oben schon mal beschrieb mit der Änderung in Zeilen 2 und 3 für die Richtung 2) kopfIndex = kopfIndex + 1
3) IF kopfIndex > n THEN kopfIndex = 0erhalten wir in den beiden Fällen:

a)
kopfIndex = 0
[0][0] = 3 [0][1] = 7
[1][0] = 3 [1][1] = 4
[2][0] = 3 [2][1] = 5
[3][0] = 3 [3][1] = 6


und

b)
kopfIndex = 2
[0][0] = 3 [2][1] = 5
[1][0] = 3 [3][1] = 6
[2][0] = 3 [0][1] = 7
[3][0] = 3 [1][1] = 4

Der Vorteil daran ist, dass nicht viele Daten durch die Gegend kopiert werden müssen. Wir verschieben einfach die Stelle, die wir als Kopf betrachten.

[Inf3rnus]

Ah, jetzt verstehe ich was du meinst, wow das ist ja ein genialer Einfall, auf so etwas simples und gleichzeitig gutes wär ich wohl nie gekommen ;)
Nun dann werd ich mich mal dran setzen und versuchen deinen Vorschlag/Einfall zu implementieren.

Danke nochmals für alles!

mfg Inf3rnus