Datenstruktur

Neue Frage »

Auf diesen Beitrag antworten »
neuling96 Datenstruktur

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:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:

Gegeben folgende Klasse zur Modellierung einer sortierten Liste:
public class
SortierteListe<E
extends
Comparable<E>> {
private int
size;
private
Entry<E> head;
public
SortierteListe() {
this
.head =
null
;
}
public
E get(
int
index) {
if
(index < 0 || index >=
this
.size) {
throw new
IndexOutOfBoundsException("Index: " + index
+ ", Size: " +
this
.size);
}
Entry<E> currentEntry =
this
.head;
while
(index > 0) {
currentEntry = currentEntry.getNext();
index--;
}
return
currentEntry.getElement();
}
public int
size() {
return this
.size;
}
private static 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;
}
}
}



a)
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
public void indexof(E element) {
int i=0;
while(i<this.size) {
Entry<E> x= new Entry(element, this.head);
if(x.getElement().equals(element)){
return i;
break;
}else{
this.head=x.getnext();
i++;
}
}
}


b)
code:
1:
2:
3:
4:
5:
6:
7:
pubic vloid add(E elment) {
Entry<E> x= new Entry(element, this.head);
this.head= x;
this,size++;
}

c kommt heute oder morgen
 
Auf diesen Beitrag antworten »
eulerscheZahl

Zum Glück kann eclipse den Code formatieren, das kann man doch so nicht vernünftig lesen!

Zitat:
pubic vloid add(E elment)

darf ich um mehr Konzentration bitten?

Ich habe dir ein paar Kommentare ergänzt.
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:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
public class SortierteListe<E extends Comparable<E>> {
	private int size;
	private Entry<E> head;

	public SortierteListe() {
		this.head = null;
	}

	public E get(int index) {
		if (index < 0 || index >= this.size) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ this.size);
		}
		Entry<E> currentEntry = this.head;
		while (index > 0) {
			currentEntry = currentEntry.getNext();
			index--;
		}
		return currentEntry.getElement();
	}

	public int size() {
		return this.size;
	}

	public int indexof(E element) {
		int i = 0;
		while (i < this.size) {
			Entry<E> x = new Entry(element, this.head); // bei der Suche sollst
														// du keine neuen
														// Objekte erzeugen
			if (x.getElement().equals(element)) {
				return i;
			} else {
				this.head = x.getNext(); // damit löschst du die Liste, weil du
											// den Kopf überschreibst und somit
											// keine Referenz mehr auf ihn hast
				i++;
			}
		}
		return -1; // Wert zurückgeben, wenn nichts gefunden
	}

	public void add(E element) {
		Entry<E> x = new Entry(element, this.head);
		this.head = x;
		this.size++;
		// du sollst es sortiert einfügen, nicht an die Spitze setzen
	}

	private static 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;
		}
	}
}
Auf diesen Beitrag antworten »
neuling96

oh je, ich dachte wenn ich den code kopiere wird es passen unglücklich
ich hoffe das passt besser!
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
public int indexof(E element) {
		int i = 0;
		Entry<E> x = this.head;
while (i < this.size) {
			 
			if (x.getElement().equals(element)) {
				return i;
			} else {
				x = x.getNext(); 
											
				i++;
			}
		}
		return -1; 
	}

Auf diesen Beitrag antworten »
neuling96

// du sollst es sortiert einfügen, nicht an die Spitze setzen
ich dachte, wenn ich ein element in einer liste einfüge, dann immer an der spitze?
an welcher sollte ich den einfügen?
 
Auf diesen Beitrag antworten »
eulerscheZahl

"Wobei dir Eigenschaft der Sortierung erhalten bleiben soll"
Sagt dir der Begriff linked List bzw. verkettete Liste etwas? Das hast du hier nämlich vorliegen. Und in dieser Liste sind die Einträge sortiert.

code:
1:
2:
3:
4:
5:
6:
7:
SortierteListe<Integer> list = new SortierteListe<Integer>();
list.add(3);
list.add(5);
list.add(4);
list.add(3);
list.add(2);
System.out.println(list.printList()); //die Methode habe ich schnell selbst geschrieben, also bitte kein "das wird mir rot unterringelt"

liefert 2 3 3 4 5
Auf diesen Beitrag antworten »
neuling96

Wir haben es heute das Thema behandelt, aber viel verstanden habe ich nicht
ich versuch mal die
b)
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
public void add(E element){
Entry<T> x= this.head;
while (x.compareto(element)<0){
x=x.getNext();
}
element.setnext(x);
x.setElement(o);
this.size++;
}

Auf diesen Beitrag antworten »
neuling96

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

public void add(E element) {
Entry<E> currentEntry = this.head;
if(currentEntry == null) {
this.head = new Entry<E>(element, null);
this.size++;
return;
}
while (currentEntry.getNext().getElement().compareTo(element) < 0)){
x=x.getNext();
}
Element<E> enter=new Element<E>(element, x.getnext()){
x.setnext(enter);
this.size++;
}

Auf diesen Beitrag antworten »
neuling96

public void add(E element) {
Entry<E> currentEntry = this.head;
if(currentEntry == null) {
this.head = new Entry<E>(element, null);
this.size++;
return;
}
while (currentEntry.getNext().getElement().compareTo(element) < 0)){
currentEntry=currentEntry.getNext();
}
Element<E> enter=new Element<E>(element, currentEntry.getnext()){
currentEntry.setnext(enter);
this.size++;
}

[/code]
Auf diesen Beitrag antworten »
eulerscheZahl

Element<E> enter - und was ist Element jetzt aus einmal für ein Datentyp?
while (currentEntry.getNext().getElement().compareTo(element) < 0)) warum gehen hier mehr Klammern zu als auf?
currentEntry.getnext() Java ist case sensitive.
Auf diesen Beitrag antworten »
neuling96

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
public void add(E element) {
Entry<E> currentEntry = this.head;
if(currentEntry == null) {
this.head = new Entry<E>(element, null);
this.size++;
return;
}
while (currentEntry.getNext().getElement().compareTo(element) < 0){
currentEntry=currentEntry.getNext();
}
Entry<E> enter=new Element<E>(element, currentEntry.getnext()){
currentEntry.setnext(enter);
this.size++;
}

currentEntry.getnext() Java ist case sensitive. ??
was bedeutet das ?

ich habe eine frage hier zu

Entry<E> currentEntry = this.head;
this.head = null;


currentEntry zeigt auf this.head( hat eine Referenz die auf das Objekt zeigt)
und

wenn ich this.head=null; setzte

hat es doch auch Auswirkung auf currentEntry ??

heißt das jetzt currentEntry zeigt auch auf null??
Auf diesen Beitrag antworten »
neuling96

machen wir schrittweise die c)

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
public void slice(E min, E max) {
if(this.head == null) {
return;
}
Entry<E> currentEntry = this.head;
this.head = null;
this.size = 0;
while( currentEntry.getElement().compareTo(min) < 0) {
currentEntry = currentEntry.getNext();
}
if(currentEntry.getElement().compareTo(max) <= 0) {
this.head = currentEntry;
this.size++;
}
while( currentEntry.getNext().getElement().compareTo(max) <= 0) {
currentEntry = currentEntry.getNext();
this.size++;
}
currentEntry.setNext(null);
}
Auf diesen Beitrag antworten »
eulerscheZahl

Zitat:
currentEntry.getnext() Java ist case sensitive. ??
was bedeutet das ?

es heißt getNext, mit großem N.
Auch den Datentyp "Element" hast du nicht komplett ausgebessert.
Auch wenn ich mich wiederhole: teste das erst mit dem Compiler, ich will hier nicht immer auch solche Selbstverständlichkeiten hinweisen müssen.

Wenn man die Fehler behebt und mit oben von mit gegebenem Beispielcode testen will, erhält man eine NullPointerException.
Du nimmst einfach an, dass der es immer einen nächsten Eintrag gibt.
currentEntry.getNext().getElement() klappt nicht, wenn currentEntry.getNext() null liefert.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
public void add(E element) {
	if (this.head == null || element.compareTo(this.head.getElement()) < 0) {
		Entry<E> newHead = new Entry<E>(element, this.head);
		this.head = newHead;
	} else {
		Entry<E> current = this.head;
		while (current.getNext() != null
				&& current.getNext().getElement().compareTo(element) < 0) {
			current = current.getNext();
		}
		Entry<E> x = new Entry<E>(element, current.getNext());
		current.setNext(x);
	}
	this.size++;
}


Zur c)
wenn max >= dem letzten Eintrag in der sortierten Liste ist, hast du wieder eine NullPointerException verursacht.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »