Array list: insert at position

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Array list: insert at position

Beitrag von Rene Eichler »

Hallo Zusammen,

ich habe eine Frage bzgl. des Einfügens in eine Array list. Im Wiki wird gesagt, dass l die Position anzeigt, an der das neue Element eingefügt werden soll. Ich habe jetzt nicht ganz verstanden, was denn mit Position gemeint ist. Ist die Position abhängig von den belegten Feldern (n) im Array oder wird sie einfach von Anfang bis Ende durchgezählt (Sprich jede Stelle im Array).

Wenn ich beispielsweise eine ArrayList habe mit N = 5. Das erste Item ist bis n=2 belegt |X|X| | | | und ich möchte an Position 4 einfügen. Im Wiki wird gesagt, dass wenn sum + p.n < l ist, p auf das nächste Item springt. Wenn das Item hier im Beispiel aber das einzige ist, dann kann l nicht an 4 eingefügt werden, da sum + p.n = 2 < l ist. Was genau ist also die Position? Kann die Position nur zwischen 1,....,number() sein, wobei number() die Anzahl der BELEGTEN Felder ist?


VG

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Re: Array list: insert at position

Beitrag von Rene Eichler »

Ahh hab gerade gesehen, dass wir annehmen dürfen, dass l immer <= number() ist...

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Re: Array list: insert at position

Beitrag von Rene Eichler »

Ich habe dann doch noch eine Frage. Im Wiki unter 3. (Otherwise) Punkt 3 und 4. Geht man von p.n rückwärts bis zur Position m oder nur vorwärts? Falls man nur vorwärts geht, funktioniert das doch so nicht oder?

Beispiel: Wir haben ein Array mit N = 30 und dieses ist mit 20 Werten gefüllt (n = 20). Jetzt wollen wir an Position l=2 einfügen. Das m wird dann folgendermaßen gesetzt:

m = 2 - 0 +1 = 3

Nun gehen wir von p.n = 20 bis m (Geht nicht, weil m kleiner wie p.n). Demnach wird nichts verschoben und mit Punkt 5 das Element an Position m = 3 einfach überschrieben.

Könnte mir jemand auf die Sprünge helfen?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Array list: insert at position

Beitrag von Prof. Karsten Weihe »

Rene Eichler hat geschrieben:Ich habe dann doch noch eine Frage. Im Wiki unter 3. (Otherwise) Punkt 3 und 4. Geht man von p.n rückwärts bis zur Position m oder nur vorwärts? Falls man nur vorwärts geht, funktioniert das doch so nicht oder?
Ich frage einmal so herum: Wie müsste es aus Ihrer Sicht korrekt lauten?

KW

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Re: Array list: insert at position

Beitrag von Rene Eichler »

Das müsste wohl rückwärts sein, weil es sonst ja gar nicht funktioniert.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Array list: insert at position

Beitrag von Prof. Karsten Weihe »

Rene Eichler hat geschrieben:Das müsste wohl rückwärts sein, weil es sonst ja gar nicht funktioniert.
Irgendwie stehe ich gerade auf dem Schlauch ... in Punkt 1.3.4 des Induction Steps ist doch festgelegt, dass die Schleife rückwärts geht :?:

KW

LCH
Neuling
Neuling
Beiträge: 3
Registriert: 12. Sep 2015 14:16

Re: Array list: insert at position

Beitrag von LCH »

Für mich ließt sich das so:

Induction Step Implementation:
3.1.1 create new ListItem pointed at with p' //this new array is completely empty?
3.1.2. und 3.1.3 insert the new ListItem
3.1.4 (...) set p'.A[p.n/2 +j] und p.A[p.n/2 +j] = void //set second half of p and p' empty ... (second half of p is lost? and p' is already completely empty??)
3.1.5 set p.n und p'.n = p.n/2 //adjust the n

sollte in 3.1.4 nicht sowas stehen wie:
set p'.A[j] = p.A[p.n/2 +j] then set p.A[p.n/2 +j] void ? //trage das erste element in p nach der hälfte um in p'

bekir
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 16. Okt 2014 20:35

Re: Array list: insert at position

Beitrag von bekir »

LCH hat geschrieben:Für mich ließt sich das so:

Induction Step Implementation:
3.1.1 create new ListItem pointed at with p' //this new array is completely empty?
3.1.2. und 3.1.3 insert the new ListItem
3.1.4 (...) set p'.A[p.n/2 +j] und p.A[p.n/2 +j] = void //set second half of p and p' empty ... (second half of p is lost? and p' is already completely empty??)
3.1.5 set p.n und p'.n = p.n/2 //adjust the n

sollte in 3.1.4 nicht sowas stehen wie:
set p'.A[j] = p.A[p.n/2 +j] then set p.A[p.n/2 +j] void ? //trage das erste element in p nach der hälfte um in p'
Dasselbe habe ich mich gerade auch gefragt. Beim Split wird die hintere Hälfte des vollen Arrays nicht in das neue Array kopiert, sondern einfach mit null überschrieben.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Array list: insert at position

Beitrag von Prof. Karsten Weihe »

Ich habe jetzt 3.4 gefixt, da war ein mathematischer Ausdruck anscheinend verloren gegangen, habe ich wieder eingefügt. Ein Beitrag in diesem Thread hatte ja auch schon in ungefähr diese Richtung Vermutungen angestellt.

Sind damit alle in diesem Thread angesprochenen Probleme gefixt, oder habe ich etwas übersehen / nicht verstanden?

KW

Antworten

Zurück zu „Archiv“