Lineare Listen: sortiertes Einfügen

[tar]

Hallo Freunde,

bin neu hier - und habe ein kleines Problemchen beim sortierten Einfügen mit linearen Listen.

Es liegt bspw. folgende Quellliste vor, die sortiert eingelesen werden soll:

3; susanne
5; bernd
1; hermann
4; klaus
2; fritz

Beim Einlesen prüft er nach Schlüssel (ob schon vorhanden) und an welcher Stelle er einfügen soll (Sortierung nach Schlüssel).

Ergebnis soll wie folgt aussehen:

1; hermann
2; fritz
3; susanne
4; klaus
5; bernd

Ergebnis sieht aber nach 1. Sortierung folgendermaßen aus:

1; hermann
3; susanne
4; klaus
5; bernd
2; fritz

Nach 2. Sortierung:

1; hermann
2; fritz
4; klaus
5; bernd
3; susanne

Nach 3. Sortierung wieder wie bei 1. Sortierung, usw.

Selbst eine Methode, die das letzte Element nach dem Kopfelement (head, also 1. Element) einfügen soll, funktioniert nicht. Ich weiß echt keinen Rat mehr.

Hier mal der Einfüge-Code, an dem es hängt (sonst funktioniert eigentlich alles)
Aufruf mit insert(lev);
lev = der Datentyp mit int key und String titel (Getter & Setter vorhanden):

	public void insert(LV lev) {
		ListEntry e = new ListEntry(lev);
		if (e == null) {
			return;
		}
		if (head == null) {
	        head = e;
	    }
	    else if (head.getLV().getKey()==e.getLV().getKey()) {
			System.out.println("Schlüssel existiert bereits.");
			System.out.println(" => Einfügen fehlgeschlagen!");
			return;
	    }
	    else if (head.getLV().getKey()>e.getLV().getKey()) {
	    	e.setNext(head);
	    	head = e;
	    }
	    else
	        insertRec(head, e);
	}

	public void insertRec(ListEntry head, ListEntry e) {
		ListEntry b = head.getNext();
		if (b == null) {
			head.setNext(e);
		}
		else if (b.getLV().getKey()==e.getLV().getKey()) {
			System.out.println("Schlüssel existiert bereits.");
			System.out.println(" => Einfügen fehlgeschlagen!");
		}
		else if (b.getLV().getKey()<e.getLV().getKey() && b.getNext()!=null) {
			insertRec(head.getNext(), e);
		}
		else {
			e.setNext(b);
			head.setNext(e);
		}
	}

Hier noch der Code, womit ich das nachträglich reparieren wollte (funktioniert nicht, Aufruf mit trick17(head); ):

	public void trick17(ListEntry e) {
		if (e==null || head.getNext().getNext()==e || head.getNext()==null || head.getNext().getNext()==null) {
			return;
		}
		else if (e.getNext()==null) {
			e.setNext(head.getNext().getNext());
			head.getNext().setNext(e);
		}
		else
			trick17(e.getNext());
	}

Danke und Gruß!

 

[nrg]

soll es zwingend selbst implementiert werden? wenn nein nehm doch einfach eine TreeMap

 

[tar]

Ja, ich muss es leider selbst implementieren.

 

[SlaterB]

wieso hat die insert()-Methode etwas mit fehlerhafter Sortierung zu tun,
oder sortierst du gar nicht extra sondern alles soll gleich richtig eingefügt werden?

verstehst du denn was deine insert-Methode macht, hast du das auch alles im laufenden Programm überprüft?
es ist doch sehr leicht, Ausgaben einzubauen a la
'starte Insert für Element .., vorheriger Stand der Liste: .................'
'vergleiche mit Head ..'
'bin nun bei Listenelement .., vergleiche wieder, Ergebnis des Tests = ..'
'Endergebnis: Element wurde eingefügt zwischen .. und .., eben weil ..'
'neue Liste = ...........................'

das Programm kann dir genau sagen was es tut und auf jedes Fehlverhalten kannst du die Regeln ändern

 

[tar]

oder sortierst du gar nicht extra sondern alles soll gleich richtig eingefügt werden?

exakt!

Ich habe auch noch eine Extra-Sortiermethode, die die vorhandene Liste in ein Array knallt, dort das kleinste Element (nach Sortierkriterium) rausholt, den bisherigen head = null setzt und dann das kleinste Element zuerst sortiert einfügt und die restlichen Elemente in dem Array danach sortiert einfügt (hier eben insert nach key, habe auch noch insert nach title - dabei genau das identische Problem wie beim Einfügen nach Key).

Hier nochmal der komplette Aufbau, wenn es was nützt:

import java.io.*;
import java.util.StringTokenizer;

public class Ha2LinList {
	private Ha2ListEntry head;
	static final String file = "ha2.txt";
	int ha2anz;
	Ha2ListEntry[] feld;

	public Ha2LinList() {
		head = null;
		ha2anz = 0;
	}

//... load()
//... save()

	public void insert(Ha2LV lv) {
		Ha2ListEntry e = new Ha2ListEntry(lv);
		if (e == null) {
			return;
		}
		if (head == null) {
	        head = e;
	        ha2anz++;
	    }
	    else if (head.getLV().getKey()==e.getLV().getKey()) {
			System.out.println("Schlüssel existiert bereits.");
			System.out.println(" => Einfügen fehlgeschlagen!");
			return;
	    }
	    else if (head.getLV().getKey()>e.getLV().getKey()) {
	    	e.setNext(head);
	    	head = e;
	    	ha2anz++;
	    }
	    else
	        insertRec(head, e);
	}

	public void insertRec(Ha2ListEntry head, Ha2ListEntry e) {
		Ha2ListEntry b = head.getNext();
		if (b == null) {
			head.setNext(e);
			ha2anz++;
		}
		else if (b.getLV().getKey()==e.getLV().getKey()) {
			System.out.println("Schlüssel existiert bereits.");
			System.out.println(" => Einfügen fehlgeschlagen!");
		}
		else if (b.getLV().getKey()<e.getLV().getKey() && b.getNext()!=null) {
			insertRec(head.getNext(), e);
		}
		else {
			e.setNext(b);
			head.setNext(e);
			ha2anz++;
		}
	}

	public void insertTitle(Ha2LV lv) {
		Ha2ListEntry e = new Ha2ListEntry(lv);
	    if (head == null) {
	        head = e;
	        ha2anz++;
	    }
	    else if (head.getLV().getTitel().compareTo(e.getLV().getTitel())>0) {
	    	e.setNext(head);
	    	head = e;
	    	ha2anz++;
	    }
	    else
	        insertTitleRec(head, e);
	}

	public void insertTitleRec(Ha2ListEntry head, Ha2ListEntry e) {
		Ha2ListEntry b = head.getNext();
		if (b == null) {
			head.setNext(e);
			ha2anz++;
		}
		else if (b.getLV().getTitel().compareTo(e.getLV().getTitel())<0 && b.getNext()!=null) {
			insertTitleRec(head.getNext(), e);
		}
		else {
			e.setNext(b);
			head.setNext(e);
			ha2anz++;
		}
	}

	public void trick17(Ha2ListEntry e) {
		if (e==null || head.getNext().getNext()==e || head.getNext()==null || head.getNext().getNext()==null) {
			return;
		}
		else if (e.getNext()==null) {
			e.setNext(head.getNext().getNext());
			head.getNext().setNext(e);
		}
		else
			trick17(e.getNext());
	}
// ...
  	public void fillFeld(Ha2ListEntry[] feld) {
		int i;
		Ha2ListEntry tmp = head;
		for (i=0; i<ha2anz; i++) {
			feld[i] = tmp;
			tmp = tmp.getNext();
		}
	}

	public void sortKey() {
		if (ha2anz<=1) {
			return;
		}
		else {
			feld = new Ha2ListEntry[ha2anz];
			fillFeld(feld);
			sortFeldKey(feld);
			trick17(head);
		}
	}

	public void sortFeldKey(Ha2ListEntry[] feld) {
		// finde kleinstes Element und lösche es aus dem feld
		Ha2ListEntry k = feld[0];
		int cnt = ha2anz;
		int pos = 0;
		int i;
		for (i=1;i<cnt;i++) {
			if (k.getLV().getKey()>feld[i].getLV().getKey()) {
				k=feld[i];
				pos=i;
			}
		}
		head = null;
        ha2anz = 0;
		insert(feld[pos].lv);
		head.setNext(null);
		feld[pos]=null;
		// erzeuge neue sortierte liste
		for (i=0;i<cnt;i++) {
			if (feld[i]!=null) {
				insert(feld[i].lv);
			}
		}
	}

	public void sortTitle() {
		if (ha2anz<=1) {
			return;
		}
		else {
			feld = new Ha2ListEntry[ha2anz];
			fillFeld(feld);
			sortFeldTitle(feld);
		}
	}

	public void sortFeldTitle(Ha2ListEntry[] feld) {
		// finde kleinstes Element und lösche es aus dem feld
		Ha2ListEntry k = feld[0];
		int cnt = ha2anz;
		int pos = 0;
		int i;
		for (i=1;i<cnt;i++) {
			if (k.getLV().getTitel().compareTo(feld[i].getLV().getTitel())>0) {
				k=feld[i];
				pos=i;
			}
		}
		head = null;
        ha2anz = 0;
		insertTitle(feld[pos].lv);
		head.setNext(null);
		feld[pos]=null;
		// erzeuge neue sortierte liste
		for (i=0;i<cnt;i++) {
			if (feld[i]!=null) {
				insertTitle(feld[i].lv);
			}
		}
	}
// ...

verstehst du denn was deine insert-Methode macht, hast du das auch alles im laufenden Programm überprüft?

Ja, habe sie ja selbst geschrieben. Ich verstehe nur nicht, wieso sie nicht das macht, was ich will, wenn alles nach Schema-F drin steht.

Ich habe absolut keine Ahnung, wie ich hier den Fehler selbst aufspüren soll.

Einzelne Befehle überprüfen kann ich bei rekursiven Methoden wohl schlecht und die IF-Anfragen sind mMn absolut logisch.

Das ganze Ding verwirrt mich einfach nur noch. :roll:

Gruß!

 

[tar]

Die Idee ist eigentlich folgende:

Ich lese Datensätze über eine Datei ein (oder einzeln per Eingabe) - beides funktioniert.

Dann sollte er sie eigentlich schon gleich nach Key sortiert in die Liste knallen - funktioniert nicht.

Also füge ich diese Datensätze erstmal stupide nacheinander ein (append) - funktioniert.

Um eine Sortierung hinzukriegen, kopiere ich die vorhandene Reihenfolge in ein Array (sort...feld), suche dort nach Kriterium (key oder titel) das kleinste Element (k). Ich setze den bisherigen head = null (zerstöre also damit die vorhandene Liste) und füge dann einfach alle Elemente mit insert-Methode (key oder titel) ein, beginnend mit k (kleinstem element).

Das Suchen nach kleinstem könnte man sich evtl sogar sparen, ist aber nun drin...

Und genau das geht halt nicht perfekt.

Gruß!

 

[SlaterB]

> Einzelne Befehle überprüfen kann ich bei rekursiven Methoden wohl schlecht

klar, das log wird dann 100 Zeilen lang, aber das macht nix,
je kürzer die verwendeten Beispiele, desto übersichtlicher, deins ist schon gut wenn da bereits der Fehler auftritt
(und nicht erst beim 400. Insert )

> Das ganze Ding verwirrt mich einfach nur noch.

eben, dem abhelfen