Hallo zusammen,
bin in 3 semester Informatik.
ich habe eine Übung in Algorithmen und Datenstrukturen erhalten.
Aufgabe:
Ich muss die Minimum-Vorrangwarteschlangen welche mit Prioritäten eines beliebigen Typs P, der Comparable implementiert ist und zusätzlichen Daten eines beliebigen Typs D durch Binomial-Halden als generische Java-Klasse BinHeap<P extends Comparable<? super P>, D> mit folgenden öffentlichen Konstruktoren und Methoden Implementieren:
// Leere Halde erzeugen.
BinHeap ()
// Ist die Halde momentan leer?
boolean isEmpty ()
// Größe der Halde, d. h. Anzahl momentan gespeicherter Einträge liefern.
int size ()
// Enthält die Halde den Eintrag e?
boolean contains (Entry<P, D> e)
// Neuen Eintrag mit Priorität p und zusätzlichen Daten d // zur Halde hinzufügen und zurückliefern.
Entry<P, D> insert (P p, D d)
// Priorität des Eintrags e auf p verändern.
boolean changePrio (Entry<P, D> e, P p)
// Einen Eintrag mit minimaler Priorität liefern.
Entry<P, D> minimum ()
// Einen Eintrag mit minimaler Priorität liefern und aus der Halde entfernen.
Entry<P, D> extractMin ()
// Eintrag e aus der Halde entfernen.
boolean remove (Entry<P, D> e)
// Inhalt der Halde zu Testzwecken ausgeben.
void dump ()
HABE BEREITS DEN CODE BISSLE GROB ANGEFANGEN UND AUSKOMMENTIERT
was am einfachsten ist.
ich versteh einige maßen was ich machen muss, aber das Umsetzen in code fällt mir schwer
Bin schon die ganze zeit damit beschäftigt und kann es immer noch nicht umsetzen.
Könnt ihr mir helfen beim Coden?
Liebe Grüße und danke im Voraus
Hier is der code und die Aufgabe habe ich angehängt
/ Als Binomial-Halde implementierte Minimum-Vorrangwarteschlange
// mit Prioritäten eines beliebigen Typs P (der die Schnittstelle
// Comparable<P> oder Comparable<P'> für einen Obertyp P' von P
// implementieren muss) und zusätzlichen Daten eines beliebigen Typs D.
class BinHeap <P extends Comparable<? super P>, D> {
// Eintrag einer solchen Warteschlange bzw. Halde, bestehend aus
// einer Priorität prio mit Typ P und zusätzlichen Daten data mit
// Typ D.
// Wenn der Eintrag momentan tatsächlich zu einer Halde gehört,
// verweist node auf den zugehörigen Knoten eines Binomialbaums
// dieser Halde.
public static class Entry <P, D> {
// Priorität, zusätzliche Daten und zugehöriger Knoten.
private P prio;
private D data;
private Node<P, D> node;
// Eintrag mit Priorität p und zusätzlichen Daten d erzeugen.
private Entry (P p, D d) {
prio = p;
data = d;
}
// Priorität bzw. zusätzliche Daten liefern.
public P prio () { return prio; }
public D data () { return data; }
}
// Knoten eines Binomialbaums innerhalb einer solchen Halde.
// Neben den eigentlichen Knotendaten (degree, parent, child,
// sibling), enthält der Knoten einen Verweis auf den zugehörigen
// Eintrag.
private static class Node <P, D> {
// Zugehöriger Eintrag.
private Entry<P, D> entry;
// Grad des Knotens.
private int degree;
// Vorgänger (falls vorhanden; bei einem Wurzelknoten null).
private Node<P, D> parent;
// Nachfolger mit dem größten Grad
// (falls vorhanden; bei einem Blattknoten null).
private Node<P, D> child;
// Zirkuläre Verkettung aller Nachfolger eines Knotens
// bzw. einfache Verkettung aller Wurzelknoten einer Halde,
// jeweils sortiert nach aufsteigendem Grad.
private Node<P, D> sibling;
// Knoten erzeugen, der auf den Eintrag e verweist
// und umgekehrt.
private Node (Entry<P, D> e) {
entry = e;
e.node = this;
}
// Priorität des Knotens, d. h. des zugehörigen Eintrags
// liefern.
private P prio () { return entry.prio; }
}
}
// Interaktives Testprogramm für die Klasse BinHeap.
class BinHeapTest {
public static void main (String [] args) throws java.io.IOException {
// Leere Halde mit Prioritäten des Typs String und zugehörigen
// Daten des Typs Integer erzeugen.
// (Die Implementierung muss aber nachträglich auch mit anderen
// Typen funktionieren.)
BinHeap<String, Integer> heap = new BinHeap<String, Integer>();
// Array mit allen eingefügten Einträgen, damit sie später
// für remove und changePrio verwendet werden können.
// Achtung: Obwohl die Klasse BinHeap ebenfalls Typparameter
// besitzt, schreibt man "BinHeap.Entry<String, Integer>" und
// nicht "BinHeap<String, Integer>.Entry<String, Integer>".
// Achtung: "new BinHeap.Entry [100]" führt zu einem Hinweis
// über "unchecked or unsafe operations"; die eigentlich "korrekte"
// Formulierung "new BinHeap.Entry<String, Integer> [100]"
// führt jedoch zu einem Übersetzungsfehler!
BinHeap.Entry<String, Integer> [] entrys = new BinHeap.Entry [100];
// Anzahl der bis jetzt eingefügten Einträge.
int n = 0;
// Standardeingabestrom System.in als InputStreamReader
// und diesen wiederum als BufferedReader "verpacken",
// damit man bequem zeilenweise lesen kann.
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
// Endlosschleife.
while (true) {
// Inhalt und Größe der Halde ausgeben.
heap.dump();
System.out.println(heap.size() + " entry(s)");
// Eingabezeile vom Benutzer lesen, ggf. ausgeben (wenn das
// Programm nicht interaktiv verwendet wird) und in einzelne
// Wörter zerlegen.
// Abbruch bei Ende der Eingabe oder leerer Eingabezeile.
System.out.print(">>> ");
String line = r.readLine();
if (line == null || line.equals("")) return;
if (System.console() == null) System.out.println(line);
String [] cmd = line.split(" ");
// Fallunterscheidung anhand des ersten Worts.
switch (cmd[0]) {
case "+": // insert prio
// Die laufende Nummer n wird als zusätzliche Daten
// verwendet.
entrys[n] = heap.insert(cmd[1], n);
n++;
break;
case "-": // remove entry
heap.remove(entrys[Integer.parseInt(cmd[1])]);
break;
case "?": // minimum
BinHeap.Entry<String, Integer> e = heap.minimum();
System.out.println("--> " + e.prio() + " " + e.data());
break;
case "!": // extractMin
e = heap.extractMin();
System.out.println("--> " + e.prio() + " " + e.data());
break;
case "=": // changePrio entry prio
heap.changePrio(entrys[Integer.parseInt(cmd[1])], cmd[2]);
break;
}
}
}
}
bin in 3 semester Informatik.
ich habe eine Übung in Algorithmen und Datenstrukturen erhalten.
Aufgabe:
Ich muss die Minimum-Vorrangwarteschlangen welche mit Prioritäten eines beliebigen Typs P, der Comparable implementiert ist und zusätzlichen Daten eines beliebigen Typs D durch Binomial-Halden als generische Java-Klasse BinHeap<P extends Comparable<? super P>, D> mit folgenden öffentlichen Konstruktoren und Methoden Implementieren:
// Leere Halde erzeugen.
BinHeap ()
// Ist die Halde momentan leer?
boolean isEmpty ()
// Größe der Halde, d. h. Anzahl momentan gespeicherter Einträge liefern.
int size ()
// Enthält die Halde den Eintrag e?
boolean contains (Entry<P, D> e)
// Neuen Eintrag mit Priorität p und zusätzlichen Daten d // zur Halde hinzufügen und zurückliefern.
Entry<P, D> insert (P p, D d)
// Priorität des Eintrags e auf p verändern.
boolean changePrio (Entry<P, D> e, P p)
// Einen Eintrag mit minimaler Priorität liefern.
Entry<P, D> minimum ()
// Einen Eintrag mit minimaler Priorität liefern und aus der Halde entfernen.
Entry<P, D> extractMin ()
// Eintrag e aus der Halde entfernen.
boolean remove (Entry<P, D> e)
// Inhalt der Halde zu Testzwecken ausgeben.
void dump ()
HABE BEREITS DEN CODE BISSLE GROB ANGEFANGEN UND AUSKOMMENTIERT
was am einfachsten ist.
ich versteh einige maßen was ich machen muss, aber das Umsetzen in code fällt mir schwer
Bin schon die ganze zeit damit beschäftigt und kann es immer noch nicht umsetzen.
Könnt ihr mir helfen beim Coden?
Liebe Grüße und danke im Voraus
Hier is der code und die Aufgabe habe ich angehängt
/ Als Binomial-Halde implementierte Minimum-Vorrangwarteschlange
// mit Prioritäten eines beliebigen Typs P (der die Schnittstelle
// Comparable<P> oder Comparable<P'> für einen Obertyp P' von P
// implementieren muss) und zusätzlichen Daten eines beliebigen Typs D.
class BinHeap <P extends Comparable<? super P>, D> {
// Eintrag einer solchen Warteschlange bzw. Halde, bestehend aus
// einer Priorität prio mit Typ P und zusätzlichen Daten data mit
// Typ D.
// Wenn der Eintrag momentan tatsächlich zu einer Halde gehört,
// verweist node auf den zugehörigen Knoten eines Binomialbaums
// dieser Halde.
public static class Entry <P, D> {
// Priorität, zusätzliche Daten und zugehöriger Knoten.
private P prio;
private D data;
private Node<P, D> node;
// Eintrag mit Priorität p und zusätzlichen Daten d erzeugen.
private Entry (P p, D d) {
prio = p;
data = d;
}
// Priorität bzw. zusätzliche Daten liefern.
public P prio () { return prio; }
public D data () { return data; }
}
// Knoten eines Binomialbaums innerhalb einer solchen Halde.
// Neben den eigentlichen Knotendaten (degree, parent, child,
// sibling), enthält der Knoten einen Verweis auf den zugehörigen
// Eintrag.
private static class Node <P, D> {
// Zugehöriger Eintrag.
private Entry<P, D> entry;
// Grad des Knotens.
private int degree;
// Vorgänger (falls vorhanden; bei einem Wurzelknoten null).
private Node<P, D> parent;
// Nachfolger mit dem größten Grad
// (falls vorhanden; bei einem Blattknoten null).
private Node<P, D> child;
// Zirkuläre Verkettung aller Nachfolger eines Knotens
// bzw. einfache Verkettung aller Wurzelknoten einer Halde,
// jeweils sortiert nach aufsteigendem Grad.
private Node<P, D> sibling;
// Knoten erzeugen, der auf den Eintrag e verweist
// und umgekehrt.
private Node (Entry<P, D> e) {
entry = e;
e.node = this;
}
// Priorität des Knotens, d. h. des zugehörigen Eintrags
// liefern.
private P prio () { return entry.prio; }
}
}
// Interaktives Testprogramm für die Klasse BinHeap.
class BinHeapTest {
public static void main (String [] args) throws java.io.IOException {
// Leere Halde mit Prioritäten des Typs String und zugehörigen
// Daten des Typs Integer erzeugen.
// (Die Implementierung muss aber nachträglich auch mit anderen
// Typen funktionieren.)
BinHeap<String, Integer> heap = new BinHeap<String, Integer>();
// Array mit allen eingefügten Einträgen, damit sie später
// für remove und changePrio verwendet werden können.
// Achtung: Obwohl die Klasse BinHeap ebenfalls Typparameter
// besitzt, schreibt man "BinHeap.Entry<String, Integer>" und
// nicht "BinHeap<String, Integer>.Entry<String, Integer>".
// Achtung: "new BinHeap.Entry [100]" führt zu einem Hinweis
// über "unchecked or unsafe operations"; die eigentlich "korrekte"
// Formulierung "new BinHeap.Entry<String, Integer> [100]"
// führt jedoch zu einem Übersetzungsfehler!
BinHeap.Entry<String, Integer> [] entrys = new BinHeap.Entry [100];
// Anzahl der bis jetzt eingefügten Einträge.
int n = 0;
// Standardeingabestrom System.in als InputStreamReader
// und diesen wiederum als BufferedReader "verpacken",
// damit man bequem zeilenweise lesen kann.
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
// Endlosschleife.
while (true) {
// Inhalt und Größe der Halde ausgeben.
heap.dump();
System.out.println(heap.size() + " entry(s)");
// Eingabezeile vom Benutzer lesen, ggf. ausgeben (wenn das
// Programm nicht interaktiv verwendet wird) und in einzelne
// Wörter zerlegen.
// Abbruch bei Ende der Eingabe oder leerer Eingabezeile.
System.out.print(">>> ");
String line = r.readLine();
if (line == null || line.equals("")) return;
if (System.console() == null) System.out.println(line);
String [] cmd = line.split(" ");
// Fallunterscheidung anhand des ersten Worts.
switch (cmd[0]) {
case "+": // insert prio
// Die laufende Nummer n wird als zusätzliche Daten
// verwendet.
entrys[n] = heap.insert(cmd[1], n);
n++;
break;
case "-": // remove entry
heap.remove(entrys[Integer.parseInt(cmd[1])]);
break;
case "?": // minimum
BinHeap.Entry<String, Integer> e = heap.minimum();
System.out.println("--> " + e.prio() + " " + e.data());
break;
case "!": // extractMin
e = heap.extractMin();
System.out.println("--> " + e.prio() + " " + e.data());
break;
case "=": // changePrio entry prio
heap.changePrio(entrys[Integer.parseInt(cmd[1])], cmd[2]);
break;
}
}
}
}
