Datenstrukturen und Algorithmen, welchen Rang hat Header?

Neo

Erfahrener Schreiberling

Posts: 322

Date of registration: Jul 24th 2005

Location: Hannover

Occupation: Informatik

1

Friday, October 14th 2005, 10:25pm

Welchen Rang hat eigentlich der header in der Knotenbasierten Implementierung eines Vektors?

Go to the top of the page

migu

free rider

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

2

Friday, October 14th 2005, 10:49pm

RE: Datenstrukturen und Algorithmen, welchen Rang hat Header?

Quoted

Original von Neo
Welchen Rang hat eigentlich der header in der Knotenbasierten Implementierung eines Vektors?

Header und Trailer haben keinen Rang, weil sie keine Elemente des Vektors darstellen. Erst ein neu hinzugefügtes Element besitzt einen Rang. Header und Trailer sind zwar genauso vom Typ DNode wie Elementknoten, in ihnen ist item aber leer (vgl. Folien 1.12 bis 1.14).

tar: Anlegen eines leeren Archivs wird feige verweigert.

Go to the top of the page

Neo

Erfahrener Schreiberling

Posts: 322

Date of registration: Jul 24th 2005

Location: Hannover

Occupation: Informatik

3

Friday, October 14th 2005, 10:58pm

nodeAtRank

Kennt einer diesen Algorithmus?

algorithm nodeAtRank(int r): DNode :
// Hilfsmethode, um den Knoten zu finden,
// dessen Element den gegebenen Rang r hat
DNode v <- header.getNext();
for i <- 1 to r do
v <- v.getNext();
return v .

Frage dazu:
Angenommen Rang r = 1. Wird die for-Schleife dann ausgeführt oder übersprungen?

This post has been edited 1 times, last edit by "Neo" (Oct 14th 2005, 10:59pm)

Go to the top of the page

migu

free rider

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

4

Friday, October 14th 2005, 11:06pm

RE: nodeAtRank

Quoted

Original von Neo
Angenommen Rang r = 1. Wird die for-Schleife dann ausgeführt oder übersprungen?

Sie wird genau einmal ausgeführt.
Das kannst du dir relativ leicht klarmachen, wenn du schaust, dass v am Anfang eine Referenz auf Element mit Rang 0 ist (also das erste Element des Vektors). Wollen wir das Element mit Rang 1 haben, müssen wir "v <- v.getNext()" in der Schleife genau einmal ausführen.

Bei r = 0 wird die Schleife in der Tat nie ausgeführt. Das gilt in diesem Pseudocode allgemein für den Fall, dass der Wert links von "to" größer als der rechts von "to" ist. Bei "downto" ist es umgekehrt.

tar: Anlegen eines leeren Archivs wird feige verweigert.