|
Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99 |
5. Übung - abzugeben am 10. 11. 1998 in Ihrer Übungsgruppe
5.a.1 Theorie
Gegeben sei eine Hashtabelle mit der Länge 7.
Vervollständigen Sie folgende Tabellen - verwenden Sie dabei das
Doppelhash-Verfahren nach der Quotientenmethode.
Berechnungstrace:
Formel:
fi(k) = (f0(k) + i*c) MOD p
Hash-Tabelle:
5.a.2 Theorie
Vergleichen Sie lineare und quadratische Kollisionsstrategien
mit dem Verfahren aus Beispiel a.1 und erläutern Sie Vor- und
Nachteile. Welche Strategie erweist sich im obigen Beispiel als
die günstigste? Halten Sie dieses Ergebnis für repräsentativ?
Ist der sich ergebende Belegungsfaktor ein optimaler/plausibler
Wert?
5.b Programm
Ändern Sie Ihr Programmbeispiel 4a+4b wie in der Übung besprochen.
Stellen Sie auch von linearer Kollisionsstrategie auf Quotientenmethode um.
Zeigen Sie im Kommentar genau, welche Änderungen dazu notwendig sind.
Was ist zu ändern, wenn Sie auf quadratische Kollisionsstrategie umstellen wollen
(Beschreibung/Kommentar)?
5.c Theorie
Zur Speicherung einer Adjazenzmatrix für
ungerichtete Graphen gibt es unter anderem folgende
Möglichkeiten:
- rechteckige Matrix (ungepackt oder
gepackt): ein Byte bzw. ein Bit zur Speicherung einer
Kantenmöglichkeit (TRUE/FALSE)
- dreieckige Matrix (gepackt): ein Bit zur
Speicherung einer Kantenmöglichkeit
- Hash-Tabelle: ein LONGINT (4 Byte) zur
Speicherung einer Kante (Knotennummern zweier adjazenter Knoten)
- Adjazenzlisten: werden wir in Zukunft kennenlernen
Vergleichen Sie diese vier Möglichkeiten
hinsichtlich ihres Platzbedarfs.
Knotenanzahl: |
50 |
500 |
5.000 |
Kantenanzahl (angenommen):
| 70 |
700 |
8.000.000 |
Normale Adjazenzmatrix (rechteckig) |
Bytes |
Bytes |
Bytes |
Gepackte Adjazenzmatrix (rechteckig) |
Bytes |
Bytes |
Bytes |
Gepackte Dreiecks-Adjazenzmatrix |
Bytes |
Bytes |
Bytes |
Hashing |
Bytes |
Bytes |
Bytes |
- Wie groß ist die maximale Kantenzahl eines Graphens mit N Knoten?
- Warum/Wann kann die Verwendung einer Hashtabelle für die
Berechnung von Wegematrizen (Warshall-Algorithmus) ungünstig sein?
Last modified:
hoermanseder@fim.uni-linz.ac.at 98-11-02