Trace:
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
repds15:hausaufgaben_loes [2015/09/26 13:48] – [Bäume] 95.222.28.161 | repds15:hausaufgaben_loes [2015/10/04 16:24] – mario | ||
---|---|---|---|
Line 72: | Line 72: | ||
- Gib eine rekursive Implementierung von '' | - Gib eine rekursive Implementierung von '' | ||
+ | < | ||
+ | lookupRek(int priority, int wo) | ||
+ | { | ||
+ | if(wo <= n) | ||
+ | { | ||
+ | if (H[wo] == priority ) | ||
+ | print priority | ||
+ | else if (H[wo] > priority ) | ||
+ | lookupRek( priority, 2*wo); | ||
+ | if (H[wo+1] == priority ) | ||
+ | print priority | ||
+ | else if (H[wo+1] > priority ) | ||
+ | lookupRek( priority, 2*wo+1); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
- Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | ||
+ | '' | ||
+ | **Antwort**: | ||
+ | |||
- Erweitere die '' | - Erweitere die '' | ||
Line 78: | Line 97: | ||
- Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt. | - Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt. | ||
- Wir überlegen uns eine einfache Komprimierungsmöglichkeit: | - Wir überlegen uns eine einfache Komprimierungsmöglichkeit: | ||
+ | |||
+ | '' | ||
+ | |||
+ | '' | ||
===== Tag 1 ===== | ===== Tag 1 ===== | ||
==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== | ==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== | ||
Line 384: | Line 407: | ||
< | < | ||
+ | struct Knoten | ||
+ | { schluesseltyp schluessel; | ||
+ | | ||
+ | | ||
+ | ... }; | ||
</ | </ | ||
- | Bei einer statischen Datenstruktur sind auch Eltern-Arrays | + | Eltern-Arrays: Es kommt auf die geforderten Operationen an. Was spricht dagegen, ein Verzeichnisbaum (directory) als Eltern-Array zu speichern? Die Laufzeit der meisten Operationen (z.B. dir) ist O(n), |
+ | die Ermitllung des kompletten Pfades von der Wurzel aus O(1). | ||
* Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus? | * Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus? | ||
Line 502: | Line 531: | ||
* Was ist eine Kollision? | * Was ist eine Kollision? | ||
* Welche Laufzeit haben '' | * Welche Laufzeit haben '' | ||
+ | |||
+ | **Insert** | ||
+ | |||
+ | ^ case: | best | average | worst | | ||
+ | ^ mit Verkettung | ||
+ | ^ lineare Adressierung | O(1) | O(1)+$\lambda$ | ||
+ | ^ doppeltes Hashing | ||
+ | |||
+ | **Remove** | ||
+ | |||
+ | ^ case: | best | average | worst | | ||
+ | ^ mit Verkettung | ||
+ | ^ lineare Adressierung | O(1) | O(1)+$\lambda$ | ||
+ | ^ doppeltes Hashing | ||
+ | |||
+ | **Lookup** | ||
+ | |||
+ | ^ case: | best | average | worst | | ||
+ | ^ mit Verkettung | ||
+ | ^ lineare Adressierung | O(1) | O(1) | O(1) | | ||
+ | ^ doppeltes Hashing | ||
+ | |||
* Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$. | * Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$. | ||
* Fülle eine Wertetabelle für $f(x) := 3x \mod 11$ | * Fülle eine Wertetabelle für $f(x) := 3x \mod 11$ | ||
Line 561: | Line 612: | ||
else | else | ||
if (v.links == NULL und v.rechts == NULL) | if (v.links == NULL und v.rechts == NULL) | ||
- | laufffähiger Code in C++ | ||
// Basisfall: v ist ein Blatt | // Basisfall: v ist ein Blatt | ||
return 1 | return 1 | ||
Line 654: | Line 704: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | Der Code berücksichtigt nicht den Fall, daß es mehrere vollständige Teilbäume mit gleicher Knotenzahl geben kann. Hier wäre sinngemäß in der Rahmenprozedur zu ergänzen: | ||
+ | < | ||
+ | printMaxTree(Knoten) | ||
+ | if (Knoten == NULL) return | ||
+ | if (Knoten-> | ||
+ | else | ||
+ | if (zaehler = maximum) | ||
+ | printTree(Knoten) | ||
+ | else | ||
+ | printMaxTree(Knoten) | ||
+ | </ | ||
+ | |||
+ | |||
==== Datenstrukturen entwerfen ==== | ==== Datenstrukturen entwerfen ==== | ||
- Entwirf eine Wörterbuch-Datenstruktur, | - Entwirf eine Wörterbuch-Datenstruktur, |