Informatiker Board | Druckvorschau: Datenstruktur die 2.

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
--- Datenstruktur die 2. (http://www.informatikerboard.de/board/thread.php?threadid=2100)

Geschrieben von neuling96 am 23.01.2015 um 15:30:

Datenstruktur die 2.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

public class Queue<E> {
 private int size;
 private Entry<E> firstEntry;
 private Entry<E> lastEntry; 
public Queue() {
 this.firstEntry = null;
 this.lastEntry = null;
}
public int size() { 
return this.size;
} 
}
public class Entry<E> {
 private E element; 
private Entry<E> next;
public Entry(E o, Entry<E> next) {
 this.element = o;
 this.next = next;
}
public E getElement() { 
return this.element;
}
public void setElement(E element) { 
this.element = element;
}
public Entry<E> getNext() {
 return this.next;
}
public void setNext(Entry<E> next) {
 this.next = next;
}
}

) Die Methode public E get() gibt das erste Element (d.h. das Element, das momentan von allen Elementen am langsten¨ in der Liste gespeichert wird) der Liste aus und loscht¨ dieses Element aus der
Liste.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

public E get() {
Entry<E> currentEntry = this.firstEntry.getElement(); // hierweis unten 
if(currentEntry == null) {
throw new NullPointerException("empty queue");
} 
this.firstEntry = currentEntry.getNext();
 if(this.size == 1) {
this.lastEntry = null;
}
 this.size--;
return currentEntry.getElement(); 
}

eine weitere frage
ich hätte statt
Entry<E> currentEntry = this.firstEntry.getElement();

auch

Entry<E> currentEntry = this.firstEntry; schreiben können ,richtig??

Geschrieben von eulerscheZahl am 23.01.2015 um 17:02:

Entry<E> currentEntry = this.firstEntry.getElement(); ist falsch, da Entry<E> nicht der selbe Typ ist, wie E.
Du musst also Entry<E> currentEntry = this.firstEntry; schreiben.

Geschrieben von neuling96 am 23.01.2015 um 21:38:

stimmt !!

(c) Die Methode public boolean contains(E element) gibt true zuruck,¨ wenn das gegebene Element element in der Liste vorhanden ist, ansonsten false. Die Elemente sollen dabei auf Gleichheit getestet werden.
1. vorschlag

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

public boolean contains(E element) {
int i=0;
while(i<this.size) {
if(this.head.getElement().equals(element)) {
return true;
}this.head = this.head.getNext();
} 
return false;
 }

2. vorschlag

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

public boolean contains(E element) {
 Entry<E> currentEntry = this.firstEntry;
while(currentEntry != null) {
if(currentEntry.getElement().equals(element)) {
return true;
}
 currentEntry = currentEntry.getNext();
}
 return false; }

beide stimmen ?

Geschrieben von eulerscheZahl am 24.01.2015 um 08:28:

Der 2. sieht gut aus, der 1. ist furchtbar:
Hier wird this.head überschrieben und somit werden munter Einträge gelöscht, bis der gewünschte dabei ist. Eine Prüfung auf null findet auch nicht statt, sodass statt nie ein false zurückgegeben wird, sondern eine Exception geworfen.

Geschrieben von neuling96 am 24.01.2015 um 11:47:

Zitat:

Original von eulerscheZahl

Eine Prüfung auf null findet auch nicht statt, sodass statt nie ein false zurückgegeben wird, sondern eine Exception geworfen.

genau hierzu eine frage

und zwar

im while (i<this.size) wird damit nicht erreicht, dass man null gar nicht prüft, da while schon voher abbricht??

Geschrieben von eulerscheZahl am 24.01.2015 um 11:54:

Und wird irgendwo i erhöht oder beim Löschen (das nicht passieren sollte) this.size verringert? Nein!

Geschrieben von neuling96 am 24.01.2015 um 12:07:

wie siehts damit aus?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

public boolean contains(E element) {
int i=0;
Entry<E> currentEntry = this.firstEntry;
while(i<this.size) {
if(currentEntry.getElement().equals(element)) {
return true;
}
currentEntry = currentEntry.getNext();
i++;
} 
return false;
 }

Geschrieben von eulerscheZahl am 24.01.2015 um 12:12:

Sieht gut aus.

Hier noch eine Alternative ohne den Schleifenzähler:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

public boolean contains(E element) {
	Entry<E> currentEntry = this.firstEntry;
	while (currentEntry != null) {
		if (currentEntry.getElement().equals(element)) {
			return true;
		}
		currentEntry = currentEntry.getNext();
	}
	return false;
}

Geschrieben von neuling96 am 04.02.2015 um 15:18:

Die Methode public void put(E element) hangt¨ das gegebene Element element an das Ende der
Liste an.

Das ist der Lösungsvorschlag, hierzu eine frage

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

public void put(E element) {
Entry<E> entry = new Entry<E>(element, null) ;
if(this.size == 0) {
this.firstEntry = entry;
} else {
Entry<E> currentEntry = this.lastEntry;
 currentEntry.setNext(entry); //[B] was wenn th.lastEntry null ist?[/B]
} 
this.lastEntry = entry;
 this.size++; 
}

Geschrieben von eulerscheZahl am 04.02.2015 um 16:36:

Dann darfst du dich an einer NullPointerException erfreuen.
Dazu sollte es aber gar nicht erst kommen, da der Teil nur durchlaufen wird, wenn this.size > 0 ist. Somit gibt es auch einen lastEntry.

Geschrieben von neuling96 am 04.02.2015 um 16:47:

sagen wir this.size=1
this.firstEntry ungleich null aber this.lastEntry ist doch null?

dann würde man doch
folgendes ausführen

Entry<E> currentEntry = this.lastEntry;
currentEntry.setNext(entry);

und
NullPointerException erhalten?

Geschrieben von eulerscheZahl am 04.02.2015 um 16:50:

Aber davor, als size noch 0 war, wurde das gemacht:
this.lastEntry = entry;

Du solltest dir wirklich angewöhnen, den Code vernünfitg zu formatieren:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

public void put(E element) {
	Entry<E> entry = new Entry<E>(element, null);
	if (this.size == 0) {
		this.firstEntry = entry;
	} else {
		Entry<E> currentEntry = this.lastEntry;
		currentEntry.setNext(entry);
	}
	this.lastEntry = entry; //wird immer ausgeführt
	this.size++;
}