Sortierung in der einfach-verketteten Listen

[DudiDudewitz]

Hallo liebe Community,

ich habe eine Funktion, geschrieben, die mir Fragen lexikalisch sortiert in die verkettete Liste einfügen soll. Leider funktioniert der Sortieralgorithmus noch nicht ganz. Ich bekomme nur die erste Frage ausgegeben.

Was mache ich falsch? Hier mein Code der Funktion

     public void addSorted(QuizFragen frage) {        //Wenn die Liste leer ist, füge den Knoten an Anfang an
        if (isEmpty()) {
            first = new Node (frage, first);
            return;
        }
        
        //Laufvariable erstellen
        Node runPointer = first;
        //Durchlaufen der Liste
        while (runPointer != null) {
            
            //Ergebnis aus dem Vergleich beider Fragen wird in die Variable gespeichert
            int res = String.valueOf(runPointer.data).compareTo(frage.getFrage());


            //Wenn der Wert aus res > 0 ist, dann vor dem aktuellen Knoten einfügen
             if (res > 0) {
                addOnPosition(frage, indexOf((QuizFragen)runPointer.data)-1);
                return;
            }    
                 //Wenn nicht, dann Liste weiter durchlaufen lassen
                runPointer = runPointer.next;
        }                
    }

 

[VfL_Freak]

Moin,

ich denke mal, Dein Problem ist, dass das return die while-Schleife beendet !

Gruß Klaus

 

[DudiDudewitz]

Hab es jetzt ohne return versucht, dann packt er mir ab der zweiten Frage, die Frage doppelt und weiterhin unsortiert in die Liste.

 

[Dompteur]

Ich denke, dass das return schon gepasst hat. Die Methode soll ja ein Element in der Liste einfügen. Wenn du die Position gefunden hast und das Element eingefügt wurde, hat sie ihren Job erledigt und darf verlassen werden.

Möglicherweise ist der Fehler gar nicht beim Einfügen, sondern woanders.
Kannst du alle Methoden, die die Liste bearbeiten, hier posten ?

Ist es ein Teil der Aufgabenstellung, dass du die sortierte Liste selbst programmieren musst ?

 

[DudiDudewitz]

Danke für die schnellen Antworten. Ich poste mal hier mal die komplette Klasse die ich geschrieben habe. Aus didaktischen Gründen müssen wir den Sortieralgorithmus selbst implementieren. D.h Collection.sort etc. dürfen wir nicht leider nicht benutzen. Danke für die Hilfe schon mal im Voraus

import java.util.NoSuchElementException;

public class SinglyLinkedList implements AbstractListType {
    //erster Knoten zeigt auf Null -> Liste ist leer
    private Node first = null;
    private Node last = null;
    
    //Fügt am Anfang der Liste eine neue Frage hinzu
    @Override
    public void addFirstQuestion(QuizFragen fragen) {
        first = new Node (fragen, first);
    }
    
    //Fügt am Ende der Liste eine neue Frage hinzu
    @Override
    public void addLastQuestion(QuizFragen fragen) {
        
        //neuen Knoten erzeugen
        last = new Node(fragen, null);
        
        //wenn noch kein Knoten vorhanden, so wird dieser Knoten zum ersten Knoten
        if (first == null) first = last;
        
        //letzten Knoten suchen
        Node runPointer = first;
        
        while (runPointer.next != null) {
            runPointer = runPointer.next;
        }
        // Knoten ans Ende anhängen
        runPointer.next = last;        
    }
        
    //Die Liste ist leer, wenn der erste Knoten auf nulll zeigt
    @Override
    public boolean isEmpty() {
        return first == null;
    }
    
    //Gibt die erste Frage aus der Liste aus
        @Override
        public QuizFragen getFirst() {
            if (isEmpty()) throw new NoSuchElementException();
            return (QuizFragen) first.data;
        }
        
    //Gibt die letzte Frage aus der Liste aus
        @Override
        public QuizFragen getLast() {
            
            //Fehler wenn die Liste leer ist
            if (first == null) throw new NoSuchElementException();    
            
            return (QuizFragen) last.data;
        }
        
    //Zählt alle Fragen in der Liste
    @Override
    public int questionCount() {
        //gibt 0 aus, wenn die Liste leer ist
        if (isEmpty()) return 0;
        
        Node runPointer = first;
        int size = 0;
        //Setze den runPointer ein Knoten weiter solange bis der runPointer auf null zeigt -> letztes Element und erhöhe size um 1
        while (runPointer != null) {
            runPointer = runPointer.next;
            size++;
        }
        //Gibt die Anzahl der Elemente wieder
        return size;
    }
    
    //Gibt die Frage an der Position n aus
    @Override
    public QuizFragen getQuestion(int n) {
        //Prüfen ob die Liste leer ist
        if (isEmpty()) throw new NoSuchElementException("Die Liste ist leer!");
        
        Node runPointer = first;
        int position = 0;
        
        //Solange der runPointer nicht auf null zeigt, prüfe ob die position mit n gleich ist, 
        //wenn ja, gebe das Objekt aus, wenn nein, position und runPointer um 1 erhöhen        
        while (runPointer != null) {
            
            if(position == n) return (QuizFragen) runPointer.data;
            
            position++;
            runPointer = runPointer.next;
        }
        //Fehler wenn am Ende der Liste kein Ergebnis vorliegt
        throw new NoSuchElementException();
    }
    
    //Gibt eine zufällige Frage aus
    @Override
    public QuizFragen randomQuestion() {
        //Zufallsvariable wird aus anhand der Gesamtfragen in der Liste erstellt
        int random = (int)( Math.random() * questionCount());
        //Gibt die Frage an Stelle der Zufallsvariable aus
        QuizFragen fragetmp = (getQuestion(random));
        delete(fragetmp);
        return fragetmp;
        
    }
    
    
    
    //Innere Klasse Node
    private class Node {
        //Referenz auf das Datenobjekt
        Object data;
        //Referenz auf den nächsten Knoten
        Node next;
        
        //Konstruktor für die Klasse Node 
        private Node (Object data, Node next) {
            this.data = data;
            this.next = next;
        }
        
        public Object getData () {
            return data;
        }
        
        public void setDataa (Object data) {
            this.data = data;
        }
        
        public Node getNext() {
            return next;
        }
        
        public void setNext (Node next) {
            this.next = next;
        }
    }






    @Override
    public void delete(QuizFragen fragen) {
        
        if (first == null) {
            
        } else if (first.data.equals(fragen)) {
            first = first.next;
        } else {
            Node runPointer = first;
            while (runPointer.next != null && !runPointer.next.data.equals(fragen)) {
                runPointer = runPointer.next;
            }
            if (runPointer != null) {
                runPointer.next = runPointer.next.next;
            }
            
        }
        
    }


    @Override
    public void addSorted(QuizFragen frage) {
        //Wenn die Liste leer ist, füge den Knoten an Anfang an
        if (isEmpty()) {
            first = new Node (frage, first);
            return;
        }
        
        //Laufvariable erstellen
        Node runPointer = first;
        //Durchlaufen der Liste
        while (runPointer != null) {
            
            //Ergebnis aus dem Vergleich beider Fragen wird in die Variable gespeichert
            int res = String.valueOf(runPointer.data).compareTo(frage.getFrage());


            //Wenn der Wert aus res > 0 ist, dann vor dem aktuellen Knoten einfügen
             if (res > 0) {
                addOnPosition(frage, indexOf((QuizFragen)runPointer.data)-1);
                return;
            }    
                 //Wenn nicht, dann Liste weiter durchlaufen lassen
                runPointer = runPointer.next;
        }
                        
    }
    
    //Fügt an einer bestimmten Position in der Liste eine Frage ein
    @Override
    public void addOnPosition(QuizFragen fragen, int index) {
    
        Node runTemp = new Node(fragen, null);
        Node current = first;
        
        for (int i =1; i < index && current.getNext() != null; i++) {
            current = current.getNext();
        }
        runTemp.setNext(current.getNext());
        current.setNext(runTemp);
    }


    @Override
    public int indexOf(QuizFragen frage) {
        
        Node runPointer = first; //Start am Anfang der Liste
        
        int i = 0; //Laufvariable 
        
        //Suchen solange das gesuchte Element nicht gefunden wurde
        
        for (; !runPointer.data.equals(frage) && runPointer != null; i++) {
            runPointer = runPointer.next;
        }
        
        if (i==questionCount()) return -1; //Wenn nichts gefunden wurde
        
        return i; //Gibt die Stelle an der das Element ist
    }
}

 

[Dompteur]

Kannst du jetzt noch den Code hinzufügen, an dem du die Liste befüllst.
Wenn ich das recht verstanden habe, hast du ja ein Element hinzugefügt und dann die Liste ausgegeben. Dabei ist dann das Problem aufgetaucht, dass die Liste nicht den Inhalt hatte, den du erwartet hast.

Ideal wäre also folgender Ablauf:
* Ausgabe der Liste
* Element einfügen
* Ausgabe der Liste

 

[DudiDudewitz]

Danke, dass du dir die Zeit für meinen Code genommen hast! Ich habe zum Testen eine JUnit Testklasse geschrieben. Da wird erstmal geprüft ob die Liste leer ist, dann werden drei Fragen der Liste hinzugefügt, danach wird nochmal geschaut ob die Fragen tatsächlich der Liste beigefügt wurden. Zum Schluss wird der Sortieralgorithmus geprüft ob die Frage auch an der richtigen Stelle steht. Bis zum letzten Testcase werden alle Test bestanden, der letzte fällt dann durch. Verglichen wird dabei lediglich nur der Fragentext. Wenn es alles richtig ist, müsste doch die Frage qf7 an erster Stelle stehen oder?

//Fragen für den Tescase
SingleChoiceFrage qf = new SingleChoiceFrage("\nWenn das Wetter gut ist, wir der Bauer bestimmt den Eber, das Ferkel und..?", 50,
            new QuizAntworten("...einen drauf machen", "A", false), 
            new QuizAntworten("...die Nacht durchzechen", "B", false),
            new QuizAntworten("...die Sau rauslassen", "C", true), 
            new QuizAntworten("...auf die Kacke hauen", "D", false));

SingleChoiceFrage qf3 = new SingleChoiceFrage("\nNatürlich spielten musikalische Menschen auch im...?", 300,
            new QuizAntworten("...Westsaxo Fon", "A", false), 
            new QuizAntworten("...Nordklari Nette", "B", false), 
            new QuizAntworten("...Südpo Saune", "C", false),
            new QuizAntworten("...Ostblock Flöte", "D", true));

SingleChoiceFrage qf7 = new SingleChoiceFrage("\nMaul Dreyer profitierte Anfang des Jahres von...?", 4000,
            new QuizAntworten("...Oettingers Sattelstange", "A", false), 
            new QuizAntworten("...Veltins Fahrradkette", "B", false), 
            new QuizAntworten("...Diebels Vorderreifen", "C", false),
            new QuizAntworten("...Becks Rücktritt", "D", true));

//Testcases

@Test
    public void testAddSorted () {
        
        //neue Liste wird erstellt 
        AbstractListType list = new SinglyLinkedList();
        
        //Liste leer?
        assertTrue(list.isEmpty());
        
        //Zu testende Methode
        list.addSorted(qf);
        list.addSorted(qf7);
        list.addSorted(qf3);
        
        
        //Wurden die Elemente hinzugefügt?
        assertFalse(list.isEmpty());
        assertTrue(list.questionCount() == 3);
        
        //Fragen sortiert beigefügt?
        assertTrue(list.getQuestion(0).equals(qf7));

 

[Dompteur]

Ich habe eine Stelle gefunden, die du kontrollieren könntest.
Zeile 180 aus deinem Posting von 15:28:

            //Ergebnis aus dem Vergleich beider Fragen wird in die Variable gespeichert
            int res = String.valueOf(runPointer.data).compareTo(frage.getFrage());

Das funktioniert nur, wenn die toString() Methode von SingleChoiceFrage (bzw. einer der Basisklassen) die Frage zurückliefert.
Prüf also bitte, ob die toString-Methode passt oder hänge folgende Ausgabe an:

System.out.println ("numPointer.data = " + String.valueOf(runPointer.data));
System.out.println ("frage = " + frage.getFrage().toString() );
System.out.println ("Vergleichsergebnis = " + res );
System.out.println ("-----" );

 

[DudiDudewitz]

Du hast vollkommen recht! Der Aufruf von runPointer.data liefert mir ein Objekt und nicht den String dahinter. Ich schau mir das morgen früh wieder an und melde mich wieder. Hier ist die Ausgabe der Konsole. Danke für den Tipp!

 numPointer.data = SingleChoiceFrage@439f5b3dfrage = 
Natürlich spielten musikalische Menschen auch im...?
Vergleichsergebnis = 73

 

[DudiDudewitz]

Guten Morgen. Ich habe jetzt meine Methode umgeschrieben, so dass die Fragen miteinander verglichen werden. Leider werden die Fragen immer noch nicht sortiert. Ich denke, da ist irgendwas mit dem Index faul.

Hier mein umgeschriebener Code

@Override
	public void addSorted(QuizFragen frage) {
		//Wenn die Liste leer ist, füge den Knoten an Anfang an
		if (isEmpty()) {
			first = new Node (frage, first);
			return;
		}
		
		//Laufvariable erstellen
		Node runPointer = first;
		int index = 0;
		//Durchlaufen der Liste
		while (runPointer != null) {
			
			
			
			//Ergebnis aus dem Vergleich beider Fragen wird in die Variable gespeichert
			int res = String.valueOf(getQuestion(index).getFrage()).compareTo(frage.getFrage());
			
			System.out.println ("numPointer.data = " + String.valueOf(getQuestion(index).getFrage()));
			System.out.println ("frage = " + frage.getFrage().toString() );
			System.out.println ("Vergleichsergebnis = " + res );
			System.out.println ("-----" );
		
			//Wenn der Wert aus res > 0 ist, dann vor dem aktuellen Knoten einfügen
			 if (res < 0) {
				 runPointer = runPointer.next;
				 index++;
	
			}	else if (res > 0) {
				if (index == 0) {
					addOnPosition(frage, index);
				} else {
					addOnPosition(frage, (index)-1);
				}
				if ( res == 0) {
					addOnPosition(frage, index+1);
				}
				
				System.out.println(index);
				return;
			 	
			}
		}
						
	}

Und hier die Ausgabe der Konsole nach dem Hinzufügen von zwei Fragen

numPointer.data = 
Wenn das Wetter gut ist, wir der Bauer bestimmt den Eber, das Ferkel und..?
frage = 
Maul Dreyer profitierte Anfang des Jahres von...?
Vergleichsergebnis = 10
-----
0
numPointer.data = 
Wenn das Wetter gut ist, wir der Bauer bestimmt den Eber, das Ferkel und..?
frage = 
Natürlich spielten musikalische Menschen auch im...?
Vergleichsergebnis = 9
-----
0

 

[Dompteur]

Immerhin sind wir einen Schritt weiter ;-)
In der Methode "addOnPosition" hast du etwas vergessen :
Die Instanzvariable "first" wird nicht angepasst, wenn dein neuer Eintrag in der Liste ganz vorne hin soll.

In der Methode "addSorted" hast du einen neuen Fehler eingebaut:
Das if (res == 0) kann nie zutreffen, da er in einem if (res < 0) Block steht.

 

[DudiDudewitz]

Sry, stehe gerade etwas aufm Schlauch. Wie genau kann ich denn die Instanzvariable anpassen?

 

[Dompteur]

Indem du in addOnPosition folgendes am Anfang einfügst:

if (index < 1) {
  first = new Node (fragen, first);
} else {
  ... die bisherige Logik
}

Das kann man zwar auch schöner machen, aber so sollte zumindest dieser Fehler weg sein.

 

[DudiDudewitz]

Das war auch der Fehler! Jetzt funktioniert alles. Vielen Dank für die Hilfe!!