Linked List Invariante im Wiki falsch?

CJo
Neuling
Neuling
Beiträge: 8
Registriert: 6. Sep 2013 15:25

Linked List Invariante im Wiki falsch?

Beitrag von CJo »

Hallo,

ich habe mich mit Linked List beschäftigt und bin auf folgendes Problem gestoßen: Die Invariante zum "Insert at position" besagt, das p auf i+1 zeigt, während im Video zum Algorithmus gesagt wurde das p auf i zeigt. Nun steht bei der Break condition das l = i+1 sein muss. l ist der Wert der dem Algorithmus sagt an welcher Position das neue Element einzufügen ist, nehme ich mal an.
Angenommen, das was im Wiki zur Inv. und BC stimmt:
Mit l = 2 = 1+1 würde p ebenfalls auf Position 2 zeigen. Dann würde nach Induktionsstep das Element aber an Position 3 eingefügt werden und nicht wie von l gefordert an Pos. 2. Habe ich da irgendetwas missverstanden oder stimmt der Eintrag im Wiki nicht?
Muss ich dann, obwohl ein Eintrag im Wiki nicht stimmt, trotzdem den Algorithmus anhand dieser Invariante durchführen? Habe ich dann die Gewissheit, dass die Tutoren das auch nicht als falsch bewerten?
Bedeutet dass i>= 0, dass p auf Position i+1 zeigt, dass p nur in der 0. also vor der ersten Iteration auf das Head-Element der Liste zeigt?

Danke im voraus.

Liebe Grüße.

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Linked List Invariante im Wiki falsch?

Beitrag von robertH »

Wie http://wiki.algo.informatik.tu-darmstad ... r_sequence zu lesen ist, soll das neue Element an Position l + 1 also hinter das Element, welches sich an Position l befindet, eingefügt werden.

CJo
Neuling
Neuling
Beiträge: 8
Registriert: 6. Sep 2013 15:25

Re: Linked List Invariante im Wiki falsch?

Beitrag von CJo »

Dann bedeutet l=1, dass das Element an Position 2 eingefügt werden soll, aber auch das i = 0 ist, da 0 + 1 = l ist. Meinem Verständnis nach ist eine "0. Iteration" nur eine Vorkehrung in der die Invariante zu gelten hat, aber in der nichts durch die Methode passieren kann, wie zB. das Einfügen eines neuen Listenelements. Erst in der 1. Iteration "passiert" dann etwas, aber dann kann das Element nicht mehr an Position 2 eingefügt werden oder wird ein Element in der 0. Iteration eingefügt?

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: Linked List Invariante im Wiki falsch?

Beitrag von derJan2 »

Die "0. Iteration" ist immer das, was in der Induction Basis steht. Also das, was vor den eigentlichen Iterationen aus dem Induction Step passiert.

Für l=1 soll das neue Element hinter dem bisherigen 1. Element eingefügt werden. Zunächst kommt die Induction Basis: Da l nicht 0 ist, wird p:=first gesetzt. Dann kommt der Induction Step: Da bisher keine "normale Iteration" abgelaufen ist, gilt i=0 und somit i+1=1=l. Daher wird nun das neue Element hinter das Element first gesetzt und der Algorithmus terminiert. Da die Terminierung durch die erfüllte Bedingung i+1=l ausgelöst wurde, ist dies die Abbruchbedingung.

Gruß, derJan2

CJo
Neuling
Neuling
Beiträge: 8
Registriert: 6. Sep 2013 15:25

Re: Linked List Invariante im Wiki falsch?

Beitrag von CJo »

Danke für die Antwort, also terminiert der Algorithmus nach der 0. Iteration?

Antworten

Zurück zu „Archiv“