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 17:30] – [Datenstrukturen entwerfen] 95.222.28.63 | repds15:hausaufgaben_loes [2015/10/04 16:24] – mario | ||
---|---|---|---|
Line 75: | Line 75: | ||
lookupRek(int priority, int wo) | lookupRek(int priority, int wo) | ||
{ | { | ||
- | if(2*wo <= n) | + | if(wo <= n) |
{ | { | ||
- | if (H[2*wo] == priority ) | + | if (H[wo] == priority ) |
print priority | print priority | ||
- | else if (H[2*wo] > priority ) | + | else if (H[wo] > priority ) |
lookupRek( priority, 2*wo); | lookupRek( priority, 2*wo); | ||
- | if (H[2*wo+1] == priority ) | + | if (H[wo+1] == priority ) |
print priority | print priority | ||
- | else if (H[2*wo+1] > priority ) | + | else if (H[wo+1] > priority ) |
lookupRek( priority, 2*wo+1); | lookupRek( priority, 2*wo+1); | ||
} | } | ||
Line 89: | Line 89: | ||
</ | </ | ||
- Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | ||
- | + | '' | |
- | < | + | **Antwort**: |
- | Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant? | + | |
- | </ | + | |
- Erweitere die '' | - Erweitere die '' | ||
Line 100: | Line 98: | ||
- 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 614: | 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 707: | 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, |