Ansatz schwierigkeiten

julia123

Erfahrenes Mitglied
hi,

ich hab hier die Aufgabe:
Implementieren Sie eine eigene Warteschlange als Ableitung von AbstractQueue die eine verkettete Liste als
Datenspeicher nutzt

So sieht mein Ansatz aus. Alles was ich auskommentiert hab ist das was ich hinein gefügt habe.
Code:
import java.util.AbstractQueue;
import java.util.Iterator;

/**
 * Instanzen dieser Klasse realisieren Prioritaetswarteschlangen beschraenkter
 * Kapazitaet.
 * 
 * @param <E>
 *            Der Typ der Elemente muss Comparable sein.
 */
public class MyPriorityQueue<E extends Comparable<E>> extends AbstractQueue<E> {
	// ToDo Ihre Datenstruktur verkettete Liste

//	private int nodeCount = 0;
//	private Node<E> first;

//	private static class Node<E> { // unser Knoten
//		E element;
//		Node<E> next; 

//		Node(E data) {
//			this.element = element;
//		}
//	}

	private int capacity; // maximale Groesse
	private int size = 0; // aktuelle Groesse

//	@SuppressWarnings("unchecked")  
//	private E[] s = (E[]) new Object[capacity];

	/**
	 * Erzeugt eine Prioritaetswarteschlange.
	 * 
	 * @param capacity
	 *            die Kapazitaet der Warteschlange.
	 * @throws IllegalArgumentException
	 *             falls capacity <= 0
	 */
	public MyPriorityQueue(int capacity) throws IllegalArgumentException {
//		if (capacity <= 0) {
//			throw new IllegalArgumentException();
//		}
//		this.capacity = capacity;
//		// Initialisierung Ihrer Datenstruktur
//		@SuppressWarnings("unchecked")
//		E[] s = (E[]) new Object[this.capacity];
	}

	/*
	 * (non..Javadoc)
	 * 
	 * Inserts the specified element into this queue if it is possible to do so
	 * immediately without violating capacity restrictions.
	 */
	@Override
	public boolean offer(E e) {
		// Auto..generated method stub
//		if (capacity >= size) {
//			s[this.size] = e;
//			size++;
//			return true;

//		} else {
//			return false;
		}

	}


Hier diesen Teil:
Code:
//	private static class Node<E> { // unser Knoten
//		E element;
//		Node<E> next; 

//		Node(E data) {
//			this.element = element;
//		}
//	}

Hab ich aus dem einem Skript. Bei dem eine Verketteteliste implementiert wurde. Ganz verstanden hab ich den auch nicht. Ok. Es dient als Knoten. Dass das letzte Element ermittelt. Was mich bisschen stört ist dass " Node<E> next; " . Das versteh ich nicht ganz.
Hier nochmal der Teil aus meinem Skript um mich besser verstehen zukönnen:

Code:
public class MyLinkedList<E> {
			private static class Node<E> {
				E data;
				Node<E> next;

				Node(E data) {
					this.data = data;
				}
			}

			private int nodeCount = 0;
			private Node<E> first;

			public int size() {
				return nodeCount;
			}
		}

Vielen Dank schon mal******
 

HonniCilest

Erfahrenes Mitglied
next ist einfach das nächste Listenelement und next ist beim letzten Listenelement natürlich null. Wegen dieser Verkettung spricht man von einer verketteten Liste. data entspricht dem Inhalt des Listenelementes.
 

julia123

Erfahrenes Mitglied
danke,

dass mit dem Node also der Verkettung hab ich verstanden! Übrigents hab ich in der methode ein fehler. "date = element".

Jedoch komm ich immer noch nicht weiter.
Ich hab ja die Aufgabe :

Ihre Datenstruktur verkettete Liste

zur implementieren. Dawürde ich jetzt einfach die Klasse - Node einfügen also so:

Code:
public class MyPriorityQueue<E extends Comparable<E>> extends AbstractQueue<E> {
	// Ihre Datenstruktur verkettete Listen

	// Linklist
	private static class Node<E> {
		public E element;

		public Node<E> next;

		public Node(E element) {
			this.element = element;

		}

	}

	private Node<E> first;// hier das ist die Objektvariabel um mit arbeiten zu können.Dann in der Klasse

Ich glaube das hab ich so richtig gelöst. Naja ich würde am liebsten einfach Linkledlist implementieren. Und dann später in der Methode offer einfach nur add() einfügen aber ich denke das ist aus der Aufgabenstellung nicht erlaubt. Dabin ich mir aber nicht sicher.


Aber jetzt kommt mein wirkliches Problem mit dem ich einfach nicht anfangen. Da bitte ich echt um Hilfe.
Der Konstruktor:

Code:
public MyPriorityQueue2(int capacity) throws IllegalArgumentException {
		if (capacity <= 0) {
			throw new IllegalArgumentException();
		}
		this.capacity = capacity;
		// TODO Initialisierung Ihrer Datenstruktur

	}
Das ist mein Problem:
// TODO Initialisierung Ihrer Datenstruktur
Was meint man damit ich kenn Inizalisierung von zb Werten also wen ich 123 hab würde ich so was schrieben : int a = 123;
Ich denke so was ist auch hier gewollte.Wahrscheinlichkeit macht das auch Sinn, für mein späteres agieren. Aber ich komm da echt nicht weiter. Bitte um hilfe!
 

sheel

I love Asm
Übrigents hab ich in der methode ein fehler. "date = element".
Und wo soll diese Anweisung stehen?
Jedenfalls wird der Fehler wohl sein, dass es bei dir keine Variable date gibt...

Jedoch komm ich immer noch nicht weiter.
Ich hab ja die Aufgabe :
...
zur implementieren. Dawürde ich jetzt einfach die Klasse - Node einfügen also so:

Code:
public class MyPriorityQueue<E extends Comparable<E>> extends AbstractQueue<E> {
	// Ihre Datenstruktur verkettete Listen

	// Linklist
	private static class Node<E> {
		public E element;

		public Node<E> next;

		public Node(E element) {
			this.element = element;

		}

	}

	private Node<E> first;// hier das ist die Objektvariabel um mit arbeiten zu können.Dann in der Klasse

Ich glaube das hab ich so richtig gelöst.
Schaut gut aus.

Aber jetzt kommt mein wirkliches Problem mit dem ich einfach nicht anfangen. Da bitte ich echt um Hilfe.
Der Konstruktor:

Code:
public MyPriorityQueue2(int capacity) throws IllegalArgumentException {
		if (capacity <= 0) {
			throw new IllegalArgumentException();
		}
		this.capacity = capacity;
		// TODO Initialisierung Ihrer Datenstruktur

	}
Das ist mein Problem:
// TODO Initialisierung Ihrer Datenstruktur
Was meint man damit ich kenn Inizalisierung von zb Werten also wen ich 123 hab würde ich so was schrieben : int a = 123;
Ich denke so was ist auch hier gewollte.Wahrscheinlichkeit macht das auch Sinn, für mein späteres agieren. Aber ich komm da echt nicht weiter. Bitte um hilfe!
Das "private Node<E> first;" braucht irgendeinen Startwert, das soll da hin.
Je nachdem, wie du später das Einfügen etc. in die Queue programmierst,
kann das zB. null sein (wenn die Einfügemethode damit umgehen kann, dass null "leer" bedeutet)
 

julia123

Erfahrenes Mitglied
Code:
public class MyPriorityQueue2<E extends Comparable<E>> extends AbstractQueue<E> {
	// Ihre Datenstruktur verkettete Listen

	// Linklist
	private static class Node<E> {
		public E element;

		public Node<E> next;

		public Node(E element) {
			this.element = element;

		}

	}

	private Node<E> first;

	private int capacity; // maximale Groesse
	private int size = 0; // aktuelle Groesse

	/**
	 * Erzeugt eine Prioritaetswarteschlange.
	 * 
	 * @param capacity
	 *            die Kapazitaet der Warteschlange.
	 * @throws IllegalArgumentException
	 *             falls capacity <= 0
	 */
	public MyPriorityQueue2(int capacity) throws IllegalArgumentException {
		if (capacity <= 0) {
			throw new IllegalArgumentException();
		}
		this.capacity = capacity;
		// Initialisierung Ihrer Datenstruktur
		this.first = null;// hier bin ich mir nicht sieher this.first oder
							// einfach nur first

	}

	/*
	 * (nonJavadoc)
	 * 
	 * @see java.util.Queue#offer(java.lang.Object)
	 */
	@Override
	public boolean offer(E e) {

		if (first == null) {
			first = new Node<E>(e);
			return true;
		} else {

			// hier sortieren
	                Node<E> l = first;
			Node<E> k = first;
			while (l.next != null) {
				l = l.next;// verweiss auf das nexte
				while (k.next != null) {
					k = k.next;// verweiss auf das nexte
					if(l.next==k.next){
						
					}

				}

			}

			}

Das einfügen also offer hab ich ansich verstanden. Ich hänge leider am sortieren. Ich wollte hier jetzt beim sortieren eine art Selektionsort implementieren. Ich weiss jedoch nicht wie es anstellen soll dass, die zweite Schleife beim übernexten element anfängt .

Dann hab ich auch noch eine zweiter Variante:

Code:
// hier sortiert
Node<E> l = first;
			int i = 0;
			@SuppressWarnings("unchecked")
			E[] s = (E[]) new Object[size];

			while (l.next != null) {
				s[i] = (E) l.next;// bin mir nicht sicher was hier passiert
				l = l.next;
				i++;

			}

                         sort(s); // hier kommt bei mir ein Fehler: "The method sort(E[], Comparator<? super E>) in the type                              //MyPriorityQueue2<E> is not applicable for the 
                                     //  arguments (E[])"


Und so sieht meine sort Funktion aus:

Code:
	public static class MyStringlengthComperator implements Comparator<String> {
		public int compare(String obj1, String obj2) {
			return obj1.length() - obj2.length();
		}
	}

	public static <E extends Comparable<E>> void sort(E[] array,
			Comparator<? super E> c) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length - 1; j++) {
				if (c.compare(array[j], array[j + 1]) > 0) {
					E temp = array[j + 1];
					array[j + 1] = array[j];
					array[j] = temp;
				}
			}
		}
	}

vielen leiben dank schon mal
 

HonniCilest

Erfahrenes Mitglied
Hallo Julia,

ich möchte dich nochmal bitten Java-Tags anstatt Code-Tags zu verwenden, es macht die ganze Sache leserlicher.
- Zu dem Kommentar betreffend this.first: Ist egal, persönlich würde ich es jedoch nur schreiben, wenn es wirklich notwendig ist.
- Wenn du ein Element in die Liste einfügst, dann ist die Liste ja bereits sortiert. Ich entnehme, dass Lange Strings später in der Warteschlange kommen sollen, richtig? Beim Einfügen in eine verkettete Liste muss dein "selektierter" Knoten das Vorgängerelemente um zu vergleichenden Knoten sein. Du sagst also: Solange der Nachfolgerknoten vom selektierten Knoten nicht null ist (sel.next != null) vergleiche Einfügeknoten mit Nachfolgerkonten. Falls Einfügeknoten kleiner Nachfolgerknoten (einf.element < sel.next.element), dann ist der Nachfolgeknoten nun der Nachfolgeknoten vom Einfügeknoten (einf.next = sel.next.element) und der Nachfolgeknoten von dem selektierten Knoten ist nun der Einfügeknoten (sel.next = einf). Nach dem Einfügen kann man die Schleife natürlich verlassen. Die Inhalte in der Klammern stehen nur zur Versinnbildlichung. Von der Array-Geschichte würde ich abraten, verfolge deinen ersten Ansatz weiter.
Edit: Bitte auch Sonderfälle betrachten: Einfügeelement ist kleiner das Kleinste und Größer als das Größte.
 
Zuletzt bearbeitet:

julia123

Erfahrenes Mitglied
Ich hab mir das anderes überlegt. Ich wollte eigentlich erst das Element einfügen. Egal wie groß oder klein es ist. (ja Priorität ist die länge. Vektor länge um genau zu sein.)
Dann hätte ich schon mal alle Elemente.
Und die möchte ich dann sortieren. Wenn das so möglich ist.
Einfügeelement ist kleiner das Kleinste und Größer als das Größte.
Dann hätte ich dann dieses Problem nicht.

Dann hnäge ich immer noch am geleichen Problem. Wie kann ich einmal bei Knoten = 0 (das wäre ja dann sowas wie l.next != null, das ist mir klar.) Anfangen und wie kann ich bei Knoten = 1 anfangen um diese dann zu vergleichen.
Ich spiele grade mit dem gedanken mit size() was zu machen.

Dann hab ich noch das Problem mit dem Vergleich wie kann ich die Elemente vergleichen. Es handelt sich ja um Vektoren. Die Funktion dazu hab ich ja.

Dann hätte ich noch eine erweiterte Frage. Angenmmen ich erstelle ein Iterator. Dieser hat ja die Methoden hashnext , next.
Next wäre ja peek. Ich glaube das kann man implementieren.
Aber was ist mit hashnext da druchläft er ja alle. Das würde ja heißen poll(). Aber poll() löscht ja wiederum alle folgende.
Ich hoffe ich hab mich nicht zu dumm ausgedrückt :( .



ps: Wie heißen die Java-code hab die auf die schnelle nicht gefunden. Werde diese entsprechend für die Zukunft nutzen!
 

HonniCilest

Erfahrenes Mitglied
Ich weiß garnicht, ob es für die Java-Tags einen Button gibt, ich tippe es immer :) Einfach das Wort Code in den eckigen Klammern durch Java ersetzen.

OK, selbst wenn du im nachhinein sortieren möchtest würde ich zu keinem Zeitpunkt ein Array verwenden. Die Verkettung lässt es auf eine einfache Weise zu diese Verkettung zu ändern, d.h. die Reihenfolge zu ändern.

Mit Vergleich von Knoten, Ausschneiden eines Knotens und Einfügen eines Knoten nach einem anderen Konten kannst du mit verschiedenen Sortieralgorithmen dein sort implementieren.
Vergleichen: Ich glaube das schaffst du ganz alleine.
Ausschneiden: Beim Ausschneiden ist next vom Vorgängerelement nun next vom ausgeschnittenen Element (was null sein kann, wenn das ausgeschnittene Element das Letzte war). next vom ausgeschnittenen Element ist nun null.
Einfügen:
Wird es an die erste stelle eingefügt ist first nun next vom ausgeschnittenen Element und das ausgeschnittene Element nun first.
Beim Einfügen an die letzte Position ist next vom letzten Element nicht mehr null sondern das Einfügelement.
Beim Einfügen in die Mitte ist das Nachfolgeelement nun next vom Einfügeelement und das Einfügelement ist nun next vom Vorgängerelement.

Klingt kompliziert ist es aber nicht!
 

sheel

I love Asm
OT: Es gibt keinen speziellen Button für Java-Tags.
Ich kenn 22 verschiedene Sprachtags, für alle ein Button wäre zu viel.
 

julia123

Erfahrenes Mitglied
Ich hab mal versucht das ganze entwas zu realisieren.
Probleme:
-An sich ob das überhaupt so Sinn macht und die Schleifen richtig sind.
-Im Komentar hab ich das 2 Problem hinterlegt.
Java:
Node<E> l = first;
		Node<E> prev = first.next;
		while (l.next != null) {
			while (prev != null) {
				if (MyStringlengthComperator.compare(l.element, prev.element)) {
					
					//Tausch: bin mir nicht sicher 
					E a = l.element;
					l.element = prev.element;
					prev.element = l.element;
					//Tausch: oder so :
					Node<E> temp = l.next;
					l.next = prev.next;
					prev.next = l.next;
						
				}
				prev = prev.next;
			}
			l = l.next;
		}

Das vergleichen bekomme ich auch nocht wirklich hin: (Problem 3)
Java:
//mein comperatro 
public static class MyStringlengthComperator implements Comparator<E> {
		public int compare(E element, E element2) {
			return element.length() - element2.length();
		}
	}

public class Vektor implements Comparable<Vektor> {

	private int x, y;

	public Vektor(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public double length() {
		return Math.sqrt(x * x + y * y);
	}

	@Override
	public int compareTo(Vektor o) {
		if (this.length() < o.length()) {
			return -1;
		} else if (this.length() > o.length()) {
			return 1;
		} else {
			return 0;
		}
	}

	@Override
	public String toString() {
		return "Vektor [x=" + x + ", y=" + y + "]";
	}

}


PS: diesmal mit JAVA-Code ^^