Java-Übungsaufgaben - Lösungsvorschlag

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Atlantaphoenix
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 31. Jan 2014 15:02

Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Atlantaphoenix »

Liebe Studierende,

ich habe mir die Mühe gemacht, zu jeder Aufgabe des Übungsblattes für jedes der vorgegebenen Datentypen, sofern nicht durch die Aufgabenstellung eingeschränkt (Array, PartiallyUsedArray, ListItem, binär-TreeNode, ternär-TreeNode, MultiWay-TreeNode), einen interativen und rekursiven Lösungsvorschlag zu erstellen. Alle daraus resultierenden Methoden sind in dem PDF-Dokument im Anhang zu finden.

Bei diesen Lösungen handelt es sich lediglich um inoffizielle Lösungsvorschläge, welche nicht von den Veranstaltern der Vorlesung „Algorithmen und Datenstrukturen“ erstellt oder überprüft wurden.

Alle Methoden wurden nach bestem Wissen und Gewissen implementiert und mithilfe eigens geschriebener JUnit-Tests zum Teil (!) getestet. Ich kann keine Garantie dafür geben, dass sich nicht möglicherweise doch einige (möglicherweise schwerwiegende) Fehler eingeschlichen haben und übernehme keine Verantwortung für entstandenen Schaden durch die Verwendung der Lösungsvorschläge bei unkritischem Übernehmen. (Gerade bei Bäumen ist besondere Vorsicht geboten, da AuD (damals noch GdI2) bei mir schon 2 Jahre her ist. Zwar habe ich mir noch einmal die aktuellen Folien angeschaut, es kann aber durchaus sein, dass ich die ein oder andere Regel nicht beachtet habe.)
Ebenso ist es möglich, dass die einzelnen Aufgaben auf eine andere Art und Weise gelöst werden können.

Die in dem Dokument enthaltenden Methoden sollten deshalb nicht als Musterlösung, sondern eher als Denkanstöße oder mögliche Lösungsideen betrachtet werden, welche stets kritisch zu hinterfragen sind.

Viele Grüße
Max


Alby407
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 19. Jul 2014 15:40

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Alby407 »

Woah, besten Dank dafür! :D

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von sqrt(2) »

Hallo,

mein Lösungsvorschlag für overwrite rekursiv im Vielwegbaum sieht wie folgt aus:

Code: Alles auswählen

public boolean overwrite(TreeNode<T> m, T k1, T k2) {
		for (int i = 0; i < m.numberOfKeys; i++) {
			if (m.theKeys[i] == k2) {
				m.theKeys[i] = k1;
				return true;
			} else if (m.theKeys[i] != null) {
				if (i == m.numberOfKeys - 1)
					// Betrachte immer den linken Nachfolger, außer beim letzten key. Hier wird der rechte Nachfolger zusätzlich betrachtet
					return overwrite(m.theSuccessors[i], k1, k2) || overwrite(m.theSuccessors[i + 1], k1, k2);
				else
					return overwrite(m.theSuccessors[i], k1, k2);
			} else
				return false;
		}
	}

mein Lösungsvorschlag für overwriteAll rekursiv im Vielwegbaum sieht wie folgt aus:

Code: Alles auswählen

	public boolean overwriteAll(TreeNode<T> m, T k1, T k2) {
		boolean b = false;
		for (int i = 0; i < m.numberOfKeys; i++) {
			if (m.theKeys[i] == k2) {
				m.theKeys[i] = k1;
				b = true;
			} else if (m.theKeys[i] != null) {
				if (i == m.numberOfKeys - 1)
					// Betrachte immer den linken Nachfolger, außer beim letzten key. Hier wird der rechte Nachfolger zusätzlich betrachtet
					b = overwrite(m.theSuccessors[i], k1, k2) || overwrite(m.theSuccessors[i + 1], k1, k2);
				else
					b = overwrite(m.theSuccessors[i], k1, k2);
			} else
				b = false;
		}
		return b;
	}

Deine Lösung konnte ich soweit nachvollziehen. Wollte mal einen anderen Lösungsvorschlag hinzufügen. Da ich lediglich mit Stift und Papier programmiere und den Code nur mit meinem "Verstand" teste, kann ich nicht 100% sagen ob das so funktioniert. Aber zumindest bin ich bis jetzt von dem Lösungsansatz überzeugt.


Ein kurzes Feedback würde mich freuen.



Gruß (:

Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Malou »

Hey Max, super, dass du es hochgeladen hast, ist sehr hilfreich!

Jedoch bin ich nicht sicher, ob wir wirklich für die erste Aufgabe (Zugriff auf einzelne Schlüsselwerte 1.) davon ausgehen sollten, dass ein Baum unsortiert ist (Wir haben ja gar nicht ausführlich in der Vorlesung gesehen, wie man mit einem Stack in java umgeht, oder hab ich etwas verpasst?).

Warum bist du davon ausgegangen?

LG

Malou

Atlantaphoenix
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 31. Jan 2014 15:02

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Atlantaphoenix »

Hi Malou,

ich bin deshalb davon ausgegangen, weil laut der Aufgabenstellung die binäre Suche nur für die beiden Versionen von Arrays zu implementieren ist. Für diese Methoden ist ein zusätzlicher Comparator notwendig.
Da bei den Bäumen kein Comparator gegeben ist, kann hier nicht überprüft werden, ob das entsprechend übergebene Element an die jeweilige Stelle eingesetzt werden kann.

Da ich aber das anfangs überlesen hatte, habe ich auch find-Methoden gebaut, die auf sortierten Suchbäumen arbeiten (und zusätzlich entsprechend den Comparator bekommen):

Code: Alles auswählen

// Iterativ mit Binärbaum und Comparator
public boolean find(TreeNodeB<T> wurzel, T element, Comparator<T> comp) {
	if (wurzel == null)
		return false;
	Stack<TreeNodeB<T>> stack = new Stack<TreeNodeB<T>>();
	stack.push(wurzel);
	while (!stack.isEmpty()) {
		TreeNodeB<T> aktElement = stack.pop();
		int compare = comp.compare(aktElement.key, element);
		if (compare == 0)
			return true;
		else if (compare > 0 && aktElement.left != null)
			stack.push(aktElement.left);
		else if (compare < 0 && aktElement.right != null)
			stack.push(aktElement.right);
	}
	return false;
}

// Iterativ mit Ternärbaum und Comparator
public boolean find(TreeNodeT<T> wurzel, T element, Comparator<T> comp) {
	if (wurzel == null)
		return false;
	Stack<TreeNodeT<T>> stack = new Stack<TreeNodeT<T>>();
	stack.push(wurzel);
	while (!stack.isEmpty()) {
		TreeNodeT<T> aktElement = stack.pop();
		int compare1 = comp.compare(aktElement.key1, element);
		int compare2 = 1;
		if (aktElement.key2 != null)
			compare2 = comp.compare(aktElement.key2, element);
		if (compare1 == 0 || compare2 == 0)
			return true;
		else if (compare1 > 0 && aktElement.left != null)
			stack.push(aktElement.left);
		else if (compare1 < 0 && compare2 > 0 && aktElement.middle != null)
			stack.push(aktElement.middle);
		else if (aktElement.right != null)
			stack.push(aktElement.right);
	}
	return false;
}

// Iterativ mit Vielwegbaum und Comparator
public boolean find(TreeNodeV<T> wurzel, T element, Comparator<T> comp) {
	if (wurzel == null)
		return false;
	Stack<TreeNodeV<T>> stack = new Stack<TreeNodeV<T>>();
	stack.push(wurzel);
	while (!stack.isEmpty()) {
		TreeNodeV<T> aktElement = stack.pop();
		int low = 0;
		int high = aktElement.numberOfKeys - 1;
		while (high >= low) {
			int mid = (low + high) / 2;
			int compare = comp.compare(aktElement.theKeys[mid], element);
			if (compare < 0)
				low = mid + 1;
			else if (compare > 0)
				high = mid - 1;
			else
				return true;
		}
		if (aktElement.theSuccessors[low] != null)
			stack.push(aktElement.theSuccessors[low]);
	}
	return false;
}

// Rekursiv mit Binärbaum und Comparator
public boolean find(TreeNodeB<T> wurzel, T element, Comparator<T> comp) {
	if (wurzel == null)
		return false;
	int compare = comp.compare(wurzel.key, element);
	if (compare == 0)
		return true;
	else if (compare > 0)
		return find(wurzel.left, element);
	else
		return find(wurzel.right, element);
}

// Rekursiv mit Ternärbaum und Comparator
public boolean find(TreeNodeT<T> wurzel, T element, Comparator<T> comp) {
	if (wurzel == null)
		return false;
	int compare1 = comp.compare(wurzel.key1, element);
	int compare2 = comp.compare(wurzel.key2, element);
	if (compare1 == 0 || compare2 == 0)
		return true;
	else if (compare1 > 0)
		return find(wurzel.left, element);
	else if (compare1 < 0 && compare2 > 0)
		return find(wurzel.middle, element);
	else
		return find(wurzel.right, element);
}

// Rekursiv mit Vielwegbaum mit Comparator
public boolean find(TreeNodeV<T> wurzel, T element, Comparator<T> comp) {
	if (wurzel == null)
		return false;
	int result = containsKey(wurzel, element, 0, wurzel.numberOfKeys - 1, comp);
	if (wurzel.numberOfKeys > result && wurzel.theKeys[result] != null
			&& comp.compare(wurzel.theKeys[result], element) == 0)
		return true;
	else if (wurzel.theSuccessors[result] == null)
		return false;
	else
		return find(wurzel.theSuccessors[result], element, comp);
}

public int containsKey(TreeNodeV<T> knoten, T element, int low, int high, Comparator<T> comp) {
	if (low > high)
		return low;
	int mid = (low + high) / 2;
	int compare = comp.compare(knoten.theKeys[mid], element);
	if (compare < 0)
		return containsKey(knoten, element, mid + 1, high, comp);
	else if (compare > 0)
		return containsKey(knoten, element, low, mid - 1, comp);
	else
		return mid;
}
Viele Grüße
Max

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von yokop »

Ich stell die Frage einfach mal hier:
Mir ist noch nicht ganz klar, nach welchen Bedingungen bei den Programmieraufgaben beim Vielwegsuchbaum eingefügt wird.

Beispiel bei diesem inoffiziellen Lösungsvorschlag bei insert Vielwegsuchbaum rekursiv: (wurzel.theSuccessors == null)
Was mich verwirrt, ist, dass in der Spezifikation über die Datenstrukturen steht, dass "theKey und theSuccessors niemals null sind",
und zugleich "die Komponenten von theKeys im Bereich 0...numberOfKeys nicht null sind" und "die Komponenten von theSuccessors im Bereich 0..numberOfKeys nicht null sind". Damit müsste doch theoretisch (wurzel.theSuccessors == null) nie zu true ausgewertet werden, solange i <= numberOfKeys ? Ich habe das dann so gelöst, dass numberOfKeys == 0 seien muss, um an dieser Stelle einzufügen ?

Wie ist das also von der Aufgabenstellung her gedacht ? Habe ich etwas übersehen ? :oops:

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

yokop hat geschrieben: Was mich verwirrt, ist, dass in der Spezifikation über die Datenstrukturen steht, dass "theKey und theSuccessors niemals null sind",
und zugleich "die Komponenten von theKeys im Bereich 0...numberOfKeys nicht null sind" und "die Komponenten von theSuccessors im Bereich 0..numberOfKeys nicht null sind". Damit müsste doch theoretisch (wurzel.theSuccessors == null) nie zu true ausgewertet werden, solange i <= numberOfKeys ?

Ja, sollte so sein. (wobei der Bereich bei theKeys nur bis numberOfKeys-1 geht, nicht bis numberOfKeys). Welches Problem sehen Sie damit?

KW

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von yokop »

Man muss ja irgendwie prüfen, ob das Element an einer neuen Stelle eingefügt werden soll oder nicht,
so wie ich das verstanden habe, muss also (theSuccessors.numberOfKeys == 0) sein, da eben beispielsweise (wurzel.theSuccessors == null) keine hinreichende Bedingung ist.
Ist es von der Aufgabenstellung her gewollt, dass man das Element in ein schon bereits vorhandenes (besetztes) Blatt einfügt oder soll das Element mit einem neuen Knoten an ein Blatt angefügt werden ? Bei erstem ist mir dann nicht klar, nach welchen Kriterien beispielsweise die Rekursion terminiert und eingefügt werden soll.

Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Malou »

Hey Max,

Danke für deinen Code mit Comparator. Wenn du aber einen sortieren Baum hast, brauchst du ja den Stack nicht mehr, ich bin dann so vorgegangen:

Code: Alles auswählen

public boolean find(TreeNode<T>, T key, Comparator <T> compare){
	while(node!= null){
		if(comp.compare(node.key, key) == 0)
			return true;
		if(comp.compare(node.key, key) >0)
			node = node.left;
		else
			node = node.right
	}
	return false
}
Für den unsortierten Baum habe ich mich das Leben allerdigns ein bisschen schwer gemacht und habe diesen Satz aus dem Übungsblatt sehr ernst genommen:
Hinweis: Die Ihnen aus der Vorlesung bekannte Methode traverse für binäre Suchbäume ilustriert[sic] das Muster für iterative Implementationen von Methoden, die den ganzen Baum durchlaufen sollen.
Deine Methode ist deutlich einfacher, aber ich wollte mal einen Lösungsvorschlag für diesen Ansatz posten. Es sind sicherlich Fehler drin, wäre es möglich mich zu korrigieren falls einer die sieht? danke im Voraus!

Hier ist mein code:

Code: Alles auswählen

public boolean find (TreeNode <T> root, T key){

	Object[] firstElem = {0, root};
	Stack<Object[]> stack = new Stack<Object[]>();
	stack.push(firstElem);
	
	while(!stack.isEmpty()){
	
		Object[] currElem = stack.peek();
		TreeNode <T> currNode = currElem[1];
		int seenChildren = currElem[0];
		
		if(currNode.key.equals(key))
			return true;
			
		if(seenChildren == 0)
			if(currNode.left != null)
				Object[] newElem = {0, currNode.left};
				stack.push(newElem);
			else
				seenChildren = 1;
		
		else if(seenChildren == 1)
			if(currNode.right != null)
				Object[] new Elem = {0, currNode.right};
				stack.push(newElem);
			else
				seenChildren = 2;
		else
			stack.pop();
			currElem = stack.peek();
			currElem[0] += 1;
	}
	return false;
}
Malou

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

yokop hat geschrieben: Ist es von der Aufgabenstellung her gewollt, dass man das Element in ein schon bereits vorhandenes (besetztes) Blatt einfügt oder soll das Element mit einem neuen Knoten an ein Blatt angefügt werden ?
Ich sehe, dass die Spezifikation von Vielweg(such)bäumen im Java-Übungsblatt eine kleine Lücke enthält: Bei einem Blatt sind natürlich alle Komponenten von theSuccessors gleich null. Dann müsste es klappen?

Ich sammle in den nächsten Tagen noch weitere Korrekturen und gebe dann Version 03 der Java-Übungsaufgaben heraus.

KW

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von yokop »

Ja, danke :D

regis
Neuling
Neuling
Beiträge: 1
Registriert: 30. Aug 2016 16:40

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von regis »

Hey Max,
Vielen Dank für deine Lösungsvorschläge zu den Aufgaben, die helfen echt weiter.
Würdet du auch deine JUnit-Tests hier teilen? So könnte man sich ein Bild machen ob der eigene geschriebene Code stimmen würde.

Vielen im Voraus
Régis

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von sqrt(2) »

Atlantaphoenix hat geschrieben: Liebe Studierende, (...)
Sehr schöne Ausarbeitung, ich habe jetzt alle Aufgaben einmal durchgearbeitet. Viele Ansätze waren ähnlich, aber bei der einen oder anderen Aufgabe ist deine Ausarbeitung eine hilfreiche Unterstützung. Dankeschön.

n0rdi
Neuling
Neuling
Beiträge: 2
Registriert: 4. Sep 2016 12:21

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von n0rdi »

Code: Alles auswählen

public boolean remove(TreeNodeB<T> wurzel, T element) {
if (wurzel == null)
return false;
Stack<TreeNodeB<T>> stack = new Stack<TreeNodeB<T>>();
stack.push(wurzel);
while (!stack.isEmpty()) {
TreeNodeB<T> aktElement = stack.pop();
if (aktElement.key.equals(element)) {
if (aktElement.left == null && aktElement.right == null)
aktElement = null;
else if (aktElement.left != null && aktElement.right == null)
aktElement = aktElement.left;
else if (aktElement.left == null && aktElement.right != null)
aktElement = aktElement.right;
else {
TreeNodeB<T> maxNode = getMaxNode(aktElement.right);
aktElement.key = maxNode.key;
maxNode = null;
}
return true;
}
if (aktElement.left != null)
stack.push(aktElement.left);
if (aktElement.right != null)
stack.push(aktElement.right);
}
return false;
}
public TreeNodeB<T> getMaxNode(TreeNodeB<T> wurze
Wird das Element wirklich durch den code aktElement = null und aktElement = aktElement.left bzw. right gelöscht, da ja eigentlich nur der Pointer verschoben oder gelöscht wird?

Methode Binärbaum Iterativ remove.

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

n0rdi hat geschrieben: Wird das Element wirklich durch den code aktElement = null und aktElement = aktElement.left bzw. right gelöscht
Was genau meinen Sie mit "gelöscht"?

KW

Antworten

Zurück zu „AuD: Programmieraufgaben“