Ansatz schwierigkeiten

Wo ist das Problem beim Vergleichen? Wirkt auf mich alles ligitim.

Beim Sortieren fehlt dir glaube ich immernoch das Verständnis einer verketteten Liste und du hast dir glaube ich noch nicht die Frage nach dem passenden Sortieralgorithmus überlegt.

Fangen wir beim Verständnis an:
Deine erste Variante zielt darauf ab die Werte der Liste untereinander zu tauschen. Dies ist natürlich theoretisch möglich, das wäre aber ungefähr so, also ob du in einer Autoschlange die Fahrer tauschst anstatt einen Fahrer mit seinem Auto vorfahren zu lassen. Ich will damit sagen eine solche Variante zu implementieren wäre bei einer verketteten Liste sehr unschön auch wenn theoretisch möglich.
Du solltest also darauf achten zum Vergleich die Werte (element) zu nehmen ("Wieviele Personen sitzen in dem Auto?") und beim Umhängen die Knoten ("In diesem Auto sitzen die Personen.").

Der Sortieralgorithmus:
Wikipedia liefert hier eine gute Übersicht (http://de.wikipedia.org/wiki/Sortierverfahren) welche die Verfahren einzeln erläutert. Es gibt hier Verfahren, welche wie oben erwähnt auf Vergleichen-Entfernen-Einfügen abzielen, Verfahren für welche du die Liste Splitten und Mergen müsstest (du müsstest hier also noch andere Methode und Konstruktoren erstellen) oder andere. Bei manchen steht sogar da, dass sich diese besonders gut zum Sortieren von verketteten Listen eignen. Ich empfehle dir dich damit auseinanderzusetzen.
 
Ich versteh das auch nicht mit dem Vergleichen

hier der classen-Kopf:

Java: 
public class MyPriorityQueue<E extends Comparable<E>> extends AbstractQueue<E> {

auch wenn ich sowas versuche zu implementieren funktionert nix:


Java: 
public class MyPriorityQueue<E extends Comparable<E>> extends AbstractQueue<E>implements Comparator<Vektor> {

Es sagt mir nur dass ich Vektor in E umwandeln soll. Und wenn ich das tu kann ich element.lenth() nicht asuführen. Bitte um hilfe. :(

Java: 
Node<E> a = first;
		Node<E> b = first.next;

		while (a != null) {
			while (b != null) {
				if (compare( a.element b.element) > 0) {
					// Tausch

					E temp = a.element;
					E temp2 = b.element;

					a.element = temp2;
					b.element = temp;

				}
				b = b.next;
			}
			a = a.next;
		}

ich glaub das ist richtig so ?
 
Zuletzt bearbeitet:
Comparable ist ein Interface, es wird also per implements eingebunden statt extends
Und warum willst du Comparator da drin haben?
 
Ich will es(Objekt=Vektor) eigentlich nur vegleichen können mit den entsprechenden Mitteln. Also brauch man dafür ja ein Comparator. Dachte ich mir so.
Wie soll ich vorgehen?
 
Willst du nur sagen können, ob die Inhalte von zwei MyPriorityQueue
komplett gleich sind (Antworten genau "Ja" oder "Nein")?
 
Ja, ich glaube schon.

hier ist ein vorgegebern Junit test vielleicht hilft das meine Frage zu beantworten:

Java: 
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;

import java.util.Iterator;
import java.util.NoSuchElementException;

import org.junit.Test;

public class MyPriorityQueueTest {

	@Test
	public void testShouldIterateThroughIntegerQueueWithoutComparator() {
		Integer actual[] = {1,3,2,5,7};
		
		MyPriorityQueue<Integer> mpq = new MyPriorityQueue<Integer>(actual.length);
		
		for (int i = 0; i < actual.length; i++) {
			mpq.offer(actual[i]);
		}
		
		Iterator<Integer> i = mpq.iterator();
		
		try {
			for (int j = 0; j < actual.length; j++) {
				i.next();
			}
			
		} catch (NoSuchElementException e) {
			fail("Iterator does not work: NoSuchElementException occured!");
		}
	}
	
	@Test
	public void testShouldIterateThroughIntegerQueueWithComparator() {
		Integer actual[] = {1,3,2,5,7};
		
		MyPriorityQueue<Integer> mpq = new MyPriorityQueue<Integer>(actual.length, new IntegerComparator());
		
		for (int i = 0; i < actual.length; i++) {
			mpq.add(actual[i]);
		}
		
		Iterator<Integer> i = mpq.iterator();
		
		try {
			for (int j = 0; j < actual.length; j++) {
				i.next();
			}
			
		} catch (NoSuchElementException e) {
			fail("Iterator does not work!");
		}
	}
	
	@Test
	public void testShouldIterateThroughQueue() {
		Vektor actual[] = {
				new Vektor(1, 2),
				new Vektor(1, 1),
				new Vektor(2, 2),
				new Vektor(2, 1),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 0)
			};
		
		MyPriorityQueue<Vektor> mpq = new MyPriorityQueue<Vektor>(actual.length, new VektorLengthComparator<Vektor>());
		
		for (int i = 0; i < actual.length; i++) {
			mpq.offer(actual[i]);
		}
		
		Iterator<Vektor> i = mpq.iterator();
		
		try {
			for (int j = 0; j < actual.length; j++) {
				i.next();
			}
			
		} catch (NoSuchElementException e) {
			fail("Iterator does not work!");
		}
	}
	
	@Test
	public void testShouldPollHighestPriorityWithComparator() {
		Vektor actual[] = {
				new Vektor(1, 2),
				new Vektor(1, 1),
				new Vektor(2, 2),
				new Vektor(2, 1),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 0)
			};
		
		MyPriorityQueue<Vektor> mpq = new MyPriorityQueue<Vektor>(actual.length, new VektorLengthComparator<Vektor>());
		
		for (int i = 0; i < actual.length; i++) {
			mpq.offer(actual[i]);
		}
		
		try {
			// assertEquals fuer vergleich von "double" benoetigt als dritten
			// Parameter einen "Unschaerfefaktor" fuer Rundungsfehler bei
			// Nachkommastellen
			assertEquals(new Vektor(0, 0).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(1, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 2).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 2).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(2, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(1, 2).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(2, 2).length(), mpq.poll().length(),0.001);
		} catch (NoSuchElementException e) {
			fail("Iterator does not work!");
		}
	}
	
	@Test
	public void testShouldPollHighestPriorityWithoutComparator() {
		Vektor actual[] = {
				new Vektor(1, 2),
				new Vektor(1, 1),
				new Vektor(2, 2),
				new Vektor(2, 1),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 0)
			};
		
		MyPriorityQueue<Vektor> mpq = new MyPriorityQueue<Vektor>(actual.length);
		
		for (int i = 0; i < actual.length; i++) {
			mpq.add(actual[i]);
		}
		
		try {
			// assertEquals fuer vergleich von "double" benoetigt als dritten
			// Parameter einen "Unschaerfefaktor" fuer Rundungsfehler bei
			// Nachkommastellen
			assertEquals(new Vektor(0, 0).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(1, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 2).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(0, 2).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(2, 1).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(1, 2).length(), mpq.poll().length(),0.001);
			assertEquals(new Vektor(2, 2).length(), mpq.poll().length(),0.001);
		} catch (NoSuchElementException e) {
			fail("Iterator does not work!");
		}
	}
	
	@Test(expected=NoSuchElementException.class)
	public void testShouldThrowExceptionIfIteratorIsUsedAfterQueuesEnd() {
		Vektor actual[] = {
				new Vektor(1, 2)
			};
		
		MyPriorityQueue<Vektor> mpq = new MyPriorityQueue<Vektor>(actual.length, new VektorLengthComparator<Vektor>());
		
		for (int i = 0; i < actual.length; i++) {
			mpq.offer(actual[i]);
		}
		
		Iterator<Vektor> i = mpq.iterator();
		
		assertEquals(new Vektor(1, 2), i.next());
		// This should cause an NoSouchElementException
		i.next();
	}
	
	@Test
	public void testSortArrayWithQueue() {
		Vektor actual[] = {
				new Vektor(1, 2),
				new Vektor(1, 1),
				new Vektor(2, 2),
				new Vektor(2, 1),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 1),
				new Vektor(0, 2),
				new Vektor(0, 0)
			};
		
		double expectedLength[] = {
				new Vektor(0, 0).length(),
				new Vektor(0, 1).length(),
				new Vektor(0, 1).length(),
				new Vektor(1, 1).length(),
				new Vektor(0, 2).length(),
				new Vektor(0, 2).length(),
				new Vektor(2, 1).length(),
				new Vektor(1, 2).length(),
				new Vektor(2, 2).length()
			};
		
		MyPriorityQueue<Vektor> mpq = new MyPriorityQueue<Vektor>(actual.length, new VektorLengthComparator<Vektor>());
		MyPriorityQueue.sort(actual, mpq);
		
		for (int i = 0; i < actual.length; i++) {
			assertEquals(expectedLength[i], actual[i].length(), 0.001);
		}
	}
}
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück