nachdem ich mich gestern mit der falschen aufgabe befasst habe hier die richtige die aber nicht so ganz will:
hoffe da blickt einer von euch noch durch und kann mir helfen
Code:
/**
* Gruppe 6
* In einer Prioritätswarteschlange werden Elemente (hier: Zeichenketten) in
* Verbindung mit einer verwaltet. Das erste Element in solch einer Warteschlange
* ist das Element mit der höchsten Priorit Methoden sollen zur Verf¨ugung stehen:
*
* - Bestimmung des ersten Elements
* - Löschen des ersten Elements
* - Einfügen eines Elementes in Verbindung mit einem Prioritätswert
* - Ermittlung der Priorität zu einem Element
* - Ausgabe aller Elemente gemäß des Prioritätswerts
*
* Implementieren Sie eine Klasse zur Repräsentation von Prioritätswarteschlangen.
* Erstellen Sie einfaches Testprogramm, mit dem Sie Elemente in eine Warteschlange
* einfügen, Elemente aus der Warteschlange löschen und dabei die Veränderung der
* Warteschlange durch Ausgabe darstellen.
*
* @author ^^
* @version 0.1 alpha 06.06.2006
*/
public class PriorityQueue {
/**
* element wird eingetragen
*
* @param priority die priorität
* @param item das element
*/
public void add(int priority, Object item) {
if (size == heap.length)
lengthen();
int index;
for (index = size++; index != 0; index = parent(index)) {
Pair parent = heap[parent(index)];
if (parent.priority >= priority)
break;
heap[index] = parent;
}
heap[index] = new Pair(priority, item);
}
/**
* vorderste element wird geliefert
*
* @return das vorderste element
* @exception EmptyQueueException leere warteschlange
*/
public Object getFirst() throws EmptyQueueException {
if (isEmpty())
throw new EmptyQueueException();
return heap[0].value;
}
/**
* löschen und anzeigen des vordersten element
*
* @return das vorderste element
* @exception EmptyQueueException leere warteschlange
*/
public Object remove() throws EmptyQueueException {
if (isEmpty())
throw new EmptyQueueException();
if (size == heap.length / 2)
shorten();
Pair result = heap[0];
Pair last = heap[--size];
int index = 0;
for (; ; ) {
Pair left = leftChild(index) >= size ? null : heap[leftChild(index)];
Pair right = rightChild(index) >= size ? null : heap[rightChild(index)];
if (last.before(left) && last.before(right))
break;
if (!left.after(right)) {
heap[index] = left;
index = leftChild(index);
}
else {
heap[index] = right;
index = rightChild(index);
}
}
heap[index] = last;
return result.value;
}
/**
* hier wird gezeigt on die prioritätswarteschlange leer ist
* @return die antwort
*/
public boolean isEmpty() {
return size == 0;
}
/**
* anzahl der elemente werden gezeigt
* @return anzahl der elemente
*/
public int size() {
return size;
}
/**
* alle elemente werden entfernt
*/
public void clear() {
size = 0;
heap = new Pair[1];
}
/**
* elementeanzahl
*/
private int size = 0;
/**
* Die Elemente als Heap organisiert.
*/
private Pair[] heap = new Pair[1];
/**
* Vergrößert den Speicherplatz.
*/
private void lengthen() {
Pair[] copy = new Pair[size * 2];
System.arraycopy(heap, 0, copy, 0, size);
heap = copy;
}
/**
* Schrumpft den Speicherplatz.
*/
private void shorten() {
if (size == 0)
return;
Pair[] copy = new Pair[size];
System.arraycopy(heap, 0, copy, 0, size);
heap = copy;
}
/**
* Liefert den Index des linken Kindknotens.
* @return den Index des linken Kindknotens
*/
private static int leftChild(int index) {
return 2 * index + 1;
}
/**
* Liefert den Index des rechten Kindknotens.
* @return den Index des rechten Kindknotens
*/
private static int rightChild(int index) {
return 2 * (index + 1);
}
/**
* Liefert den Index des Elternknotens.
* @return den Index des Elternknotens
*/
private static int parent(int index) {
return (index - 1) / 2;
}
/**
* Klasse für Paare.
*/
private static class Pair {
public final int priority;
public final Object value;
public Pair(int priority, Object value) {
this.priority = priority;
this.value = value;
}
public boolean before(Pair other) {
return other == null || priority > other.priority;
}
public boolean after(Pair other) {
return other != null && priority < other.priority;
}
}
}
class PriorityQueueTest {
public static void main(String[] args) {
System.out.println("Prioritätswarteschlangentest");
PriorityQueue queue = new PriorityQueue();
for (; ; ) {
System.out.println("h <Priorität> <Element>: Hinzufügen");
System.out.println("e: Entfernen");
System.out.println("a: Anzeigen");
System.out.println("z: Beenden");
switch (Keyboard.readChar()) {
case 'h':
case 'H':
queue.add(Keyboard.readInt(), new Integer(Keyboard.readInt()));
Keyboard.readln();
break;
case 'e':
case 'E':
if (queue.isEmpty())
System.out.println("Warteschlange leer");
else
System.out.println("Element: " + queue.remove());
Keyboard.readln();
break;
case 'a':
case 'A':
if (queue.isEmpty())
System.out.println("Warteschlange leer");
else
System.out.println("Element: " + queue.getFirst());
Keyboard.readln();
break;
case 'z':
case 'Z':
return;
}
}
}
}hoffe da blickt einer von euch noch durch und kann mir helfen
