Implementierung Listen-ADT

Diskutiere Implementierung Listen-ADT im Java Basics - Anfänger-Themen Bereich.

Bitte aktiviere JavaScript!
J

jono

Hallo,
ich habe folgendes Problem:
Java:
Implementieren Sie einen Listen-ADT anhand der Spezifikation "SortedList.asl".
Die Elemente in der Liste sollen stets aufsteigend sortiert sein.

Beachten Sie folgende Punkte:
- Das Nat in der Spezifikation muss als int in Java übersetzt werden.
- Alle Variablen und Methoden müssen public sein.
- In Node müssen die Variablen value und next heißen.
- In SortedList muss die Variable first heißen.
- Die Methodennamen müssen identisch mit den functions aus der Spezifikation sein.
- Das Verhalten innerhalb der Methoden muss dem Verhalten der equations aus der Spezifikation entsprechen.
- Sie dürfen keine imports oder sonstige vorgefertigte Typen wie z.B. Arrays verwenden. 
Bitte benutzen Sie folgendes Schema für die Dateinamen Ihrer Lösung: SortedList.java, Node.java.
Hier die Spezifikation:
Java:
specification SortedList
imports
  bool
  nat
sorts
  SortedList
constructors
  nil : -> SortedList  // Empty list
hidden constructors
  cons' : Nat x SortedList -> SortedList // Head element and tail list
functions
  cons : Nat x SortedList -> SortedList //add element to SortedList
  head : SortedList -> Nat? // Head element
  tail : SortedList -> SortedList? // SortedList without head
  isNil : SortedList -> Bool // Test for nil SortedList
  length : SortedList -> Nat // Number of elements in the SortedList
  append : SortedList x SortedList -> SortedList // Append two SortedLists
  last : SortedList -> Nat? // Last element
  init : SortedList -> SortedList? // SortedList without last
variables
  n : Nat
  n1 : Nat
  l : SortedList
  l1 : SortedList
equations
  cons(n, nil) = cons'(n, nil)
  cons(n, cons'(n1, l)) = if(greater(n,n1)) then cons'(n1, cons(n, l)) else cons'(n, cons'(n1, l))
  head(cons'(n, l)) = n
  tail(cons'(n, l)) = l
  isNil(nil) = true
  isNil(cons'(n, l)) = false
  length(nil) = zero
  length(cons'(n, l)) = succ(length(l))
  append(l,nil) = l
  append(l, cons'(n, l1)) = append(cons(n,l),l1)
  last(cons'(n,l)) = if isNil(l) then n else last(l)
  init(cons'(n,l)) = if isNil(l) then nil else cons'(n, init(l))
Dazu habe ich bisher folgenden Quellcode:
Java:
public class SortedList {
	private Node first;
	private int n;
	private int n1;
	private SortedList l;
	private SortedList l1;

	public void cons() {
		if (l == null) {

		}
	}

	public int head() {
		return first.value;
	}

	public void tail() {
		first = first.next;
	}

	public boolean isNil() {
		if (first == null) {
			return true;
		}
		return false;
	}

	public int length() {
		
	}

	public void append() {

	}

	public int last() {
		if (l == null) {

		}

	}

	public void init() {

	}

}
Erstmal meine Frage, wie gehe ich das jetzt bei "cons" an, mit imports soll es ja nicht umgesetzt werden.
 
J

jono

Klasse Node:
Java:
public class Node {
	public int value;
	public Node next;
}
 
J

jono

Bei den anderen Methoden fällt es mir auch schwer. Bei "append" z.B. kann ich doch nicht einfach l+l1 schreiben.
Bei "length" gibt es ja auch keine spezielle Funktion die einem direkt die Länge einer Liste ausgibt. Kann mir jemand ein
Tipp geben wie ich das am besten angehe, da ich wirklich kein Plan habe, wie ich das machen soll. Stift und Zettel hilft mir
da auch nur bedingt weiter.
 
H

httpdigest

Ich denke nicht, dass die Variablen `n`, `n1`, `l` und `l1` als Instanzvariablen in `SortedList` implementiert werden sollen. Es sind Variablen, die in der Spezifikation benutzt werden, um den Zusammenhang von mehreren Dingen zu beschreiben.
Es sind aber sicherlich keine Instanzvariablen im Sinne der Java Klasse `SortedList`.
Die Variablen `n` und `n1` beschreiben den Wert eines Knotens (also quasi `Node.value`), denn ein `Node` selber wird in der Spezifikation nicht gebraucht.
 
J

jono

Ja, da war ich mir zunächst auch unsicher, dient ja eher der Semantik.
 
J

jono

@httpdigest Kannst du mir evtl. einen Tipp geben wie ich denn ein Element einer Liste hinzufügen kann?
Denn mit LinkedList ist es verboten, und ich weiß nicht wie ich eine Liste darstellen soll.
 
J

jono

Kannst du mir einen tipp geben wie ich eine das letzte element einer liste ausgebe ohne eine Arraylist zu benutzen ?
 
J

jono

Ja, den Tipp verstehe der ist auch schon sehr GUT. Frage mich nur durch welchen Code ich die Liste darstellen kann. First. Next oder was? Ich glaube nicht.
 
mihe7

mihe7

First. Next oder was? Ich glaube nicht.
1. In einer verketteten Liste kann jeder Knoten als Kopf einer verketteten Liste gesehen werden.
2. Um eine verkettete Liste anzugeben, reicht die Angabe des Kopfes.

Bei (k,n) ist k nichts anderes als das Kopfelement, n das diesem folgende Element (next).
 
J

jono

Okay, danke.
Java:
	public int last(int value) {
		Node n = new Node();
		n.value = value;
		if(first.next == null) {
			n = this.first;
		} else {
			last(first.next);
	}
Wie kann ich denn jetzt das letzte Element herausfiltern ..?
 
J

jono

Java:
last(first.next);
last wird hier rot unterstrichen logischerweise
 
mihe7

mihe7

In Node:

Java:
public int last() {
    if (next == null) {
        return value;
    } else {
        return next.last();
    }
}
 
J

jono

Gehört der Code in die Klasse Node? Dachte es gehört in die Klasse Sorted.List, da es so in den Programmierfolien der Fall war..
 
J

jono

Also nicht am Beispiel last, aber war dann dementsprechend eher naheliegend es in die Klasse Sorted.List zu implementieren.
 
mihe7

mihe7

Gehört der Code in die Klasse Node? Dachte es gehört in die Klasse Sorted.List, da es so in den Programmierfolien der Fall war..
Der Code würde in die Klasse Node gehören und dient dazu, Dir die grundsätzliche Idee zu zeigen. Du wirst es vermutlich in SortedList implementieren müssen. Das geht natürlich nicht 1:1, da musst Du Dir zusätzlich was überlegen (s. im ADT die "hidden constructors").
 
J

jono

Wenn ich jetzt daran denke, dass ich erst dachte die equations einfach in Code umzusetzen, und jetzt daran einen hidden constructor zu implementieren, weiß ich beim hidden constructor zwar welche Aufgabe er erfüllt, aber nicht wie ich diesen einbauen kann , denn
Java:
-versteckte Konstruktoren lassen nur das Einfügen weiterer Elemente in eine Menge zu, falls diese Elemente noch nicht in der Menge enthalten sind
-Aufruf von versteckten Konstruktoren nur indirekt durch öffentliche Funktionen gleichen Namens möglich
Problem: Wie kann ich mir das vorstellen, wenn es darum geht das letzte Element zu returnen. Da kann ich keinen Zusammenhang sehen im Sinne von Zulassen von Einfügen weiterer Elemente in eine Menge, falls diese noch nicht in der Menge enthalten sind, damit hat das last-Element doch nichts zu tun, weil es nicht um Einfügen geht?
Das habe ich aus der Vorlesungsfolie, klingt ziemlich abstrakt.
 
mihe7

mihe7

Naja, wenn Du last() als rekursive Methode in SortedList einbaust, brauchst Du ja die "nächste" SortedList und nicht den nächsten Node.
 
J

jono

Geht es nicht anders, denn sonst wäre es ja schon in den Vorlesungen behandelt worden.
 
mihe7

mihe7

Klar geht das anders: Du hangelst Dich in einer Schleife bis zum letzten Element durch die Liste.
 
J

jono

Man könnte es doch eigentlich auch so machen, dass man sagt, dass das größte Element das letzte sein muss, da die Liste ja aufsteigend sortiert ist?
 
J

jono

Ja und das Problem was ich habe ist, dass ich nicht weiß, wie ich das letzte Element anspreche wie du sagst über eine Schleife.
 
mihe7

mihe7

Man könnte es doch eigentlich auch so machen, dass man sagt, dass das größte Element das letzte sein muss, da die Liste ja aufsteigend sortiert ist?
Ob das letzte Element das größte ist, spielt für last() nicht die Rolle: das letze Element ist dasjenige, auf das kein weiterer Eintrag folgt.

Ja und das Problem was ich habe ist, dass ich nicht weiß, wie ich das letzte Element anspreche wie du sagst über eine Schleife.
Ich geb Dir noch einen Algorithmus an die Hand, den Code musst Du aber schon selbst hinbekommen:
Code:
letztesElement := erstes Element
so lange letztesElement nicht auf das letzte Element der Liste zeigt {
    letztesElement := das auf letztesElement folgende Element 
}
gib letztesElement zurück
 
J

jono

Wieso hast du dir letztesElement und erstesElement gleichgesetzt , verstehe das echt nicht.
 
J

jono

Den habe ich noch nicht, weil ich noch nicht drauf kam , wie ich das letzte Element anspreche ^^
 
J

jono

Wärst du so nett und kannst mir ein Hinweis geben, wie das letzte Element aufgerufen wird.
 
mihe7

mihe7

Auf das letzte Element wird nicht "aufgerufen", es wird mit dem Algorithmus ermittelt.
 
J

jono

Java:
so lange letztesElement nicht auf das letzte Element der Liste zeigt
Das meine ich, letzteElement habe ich initialisiert indem ich
Java:
Node last = first;
gesetzt habe und jetzt muss ich ja mit einem Zeiger auf das letzte Element zeigen.
Aber "das letzte Element" muss ja auch eine spezifische Bezeichnung haben als Code
oder nicht?
 
S

Snaer

Code:
letztesElement := erstes Element
so lange letztesElement nicht auf das letzte Element der Liste zeigt {
    letztesElement := das auf letztesElement folgende Element
}
gib letztesElement zurück
Korrigiere mich wenn ich falsch liege
Code:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) 
if(i.next=null)
Return i
 
mihe7

mihe7

Das meine ich, letzteElement habe ich initialisiert indem ich
Java:
Node last = first;
gesetzt habe
richtig.

und jetzt muss ich ja mit einem Zeiger auf das letzte Element zeigen.
Aber "das letzte Element" muss ja auch eine spezifische Bezeichnung haben als Code
last ist der Zeiger :)

Nachem @Snaer schon fast die Lösung angegeben hat:
Java:
Node last = first; // das erste Element könnte das letzte sein.
while (last.next != null) { // Wenn last aber noch nicht das letzte Element ist,
    last = last.next; // dann könnte das nächste Element das letzte sein
}
return last;
 
J

jono

Java:
	public int last() {
		Node last = first;
		while(last.next != null){
			last = last.next;
		}
		return last;
	}
Problem ist nur noch dass ein int zurückgegeben werden muss, wie mache ich das hier ?
 
J

jono

Ja das ist doch klar, habe den Methodennamen so umbenannt dann zeigt er keine Fehlermeldung mehr an .
 
mihe7

mihe7

Was daran falsch ist? Du kannst doch nicht einfach hergehen und sagen: gut, laut Aufgabe soll ich eine Zahl zurückgeben, aber das ist mir zu kompliziert, mache ich einfach etwas anderes draus.
 
J

jono

Wie soll ich das denn sonst machen^^? Das Problem ist ja, dass last oben wegen first vom Typ Node ist und last kann ich nicht den Datentyp Int zuordnen.
 
mihe7

mihe7

Ach, Du Sch... jetzt realisiere ich das erst: @jono... Du bist das :eek:

Das Problem ist ja, dass last oben wegen first vom Typ Node ist und last kann ich nicht den Datentyp Int zuordnen.
Deswegen solltest Du ja auch mal einen Blick in die Klasse Node werfen. Was könnte man da wohl sinnvollerweise zurückgeben?
 
J

jono

Doch habe ich ! Du hast auf Seite 2 return last angegeben, und wenn du das so schreibst dann dachte ich es auch so zu übernehmen.
Aber mit value ist immer noch eine Fehlermeldung, value ist noch rot gekringelt.
 
S

Snaer

Nachem @Snaer schon fast die Lösung angegeben hat:
Java:
Node last = first; // das erste Element könnte das letzte sein.
while (last.next != null) { // Wenn last aber noch nicht das letzte Element ist,
    last = last.next; // dann könnte das nächste Element das letzte sein
}
return last;
[/QUOTE]
Mir fällt auf das ich das i vermutlich durch last ersetzen hätte sollen damit die Initialisierung von Node last = first überhaupt einen Sinn macht.
Habe ich sonst noch einen Fehler gemacht?
 
mihe7

mihe7

Doch habe ich ! [...] Aber mit value ist immer noch eine Fehlermeldung, value ist noch rot gekringelt.
Wenn Du einen Plan hättest, dürftest Du keine Fehlermeldung erhalten. @jono, das ist keineswegs böse gemeint, aber Du zeigst mit jedem zweiten Kommentar, dass Du gar keine Grundlagen beherrschst. Du musst da echt dran arbeiten.

Was hast Du denn geschrieben? Vermutlich return value;?
 
mihe7

mihe7

Habe ich sonst noch einen Fehler gemacht?
Ja, mehrere. Ich habe das auch nur als "Lösung" akzeptiert, weil erkennbar war, was Du machen wolltest :)

Es geht um folgenden Code:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) 
if(i.next=null)
Return i
Durch die fehlenden Blöcke und Einrückungen ist das ziemlich unübersichtlich, daher schreibe ich das erstmal um:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) {
    if(i.next=null) {
        Return i
    }
}
Mal abgesehen von dem Tippfehler bzgl. "return" und dem fehlenden Semikolon am Ende der Anweisung, ist die Bedingung im if-statement eine Zuweisung und kein Vergleich. Hinzu kommt, dass ein abschließendes return (außerhalb der for-Schleife) fehlt. In der Bedingung prüfst Du auf 0, das kann nicht funktionieren, denn 0 ist ein int, während i.next ein Node ist. Du müsstest also auf null prüfen.

Berücksichtigt man diese Punkte, erhält man:

Java:
Node last = first;
for (Node i=first; i.next!=null;i=i.next) {
    if(i.next == null) {
        return i;
    }
}
return ???;
Jetzt kommen zwei weitere Punkte hinzu:
1. was Du schon selbst angemerkt hast: Du müsstest mit last und nicht mit i arbeiten.
2. Die Bedingung im if-Statement wird niemals true sein, da diese mit der Bedingung der while-Schleife genau gegenteilig überprüft wurde. Der Schleifenkörper wird nur ausgeführt, wenn i.next != null ist, folglich gilt im Schleifenkörper i.next==null gerade nicht.

Java:
Node last;
for (last = first; last.next != null; last = last.next) {
    ; // nichts zu tun
}
return last;
 
S

Snaer

Ja, mehrere. Ich habe das auch nur als "Lösung" akzeptiert, weil erkennbar war, was Du machen wolltest :)

Es geht um folgenden Code:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next)
if(i.next=null)
Return i
Durch die fehlenden Blöcke und Einrückungen ist das ziemlich unübersichtlich, daher schreibe ich das erstmal um:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) {
    if(i.next=null) {
        Return i
    }
}
Mal abgesehen von dem Tippfehler bzgl. "return" und dem fehlenden Semikolon am Ende der Anweisung, ist die Bedingung im if-statement eine Zuweisung und kein Vergleich. Hinzu kommt, dass ein abschließendes return (außerhalb der for-Schleife) fehlt. In der Bedingung prüfst Du auf 0, das kann nicht funktionieren, denn 0 ist ein int, während i.next ein Node ist. Du müsstest also auf null prüfen.

Berücksichtigt man diese Punkte, erhält man:

Java:
Node last = first;
for (Node i=first; i.next!=null;i=i.next) {
    if(i.next == null) {
        return i;
    }
}
return ???;
Jetzt kommen zwei weitere Punkte hinzu:
1. was Du schon selbst angemerkt hast: Du müsstest mit last und nicht mit i arbeiten.
2. Die Bedingung im if-Statement wird niemals true sein, da diese mit der Bedingung der while-Schleife genau gegenteilig überprüft wurde. Der Schleifenkörper wird nur ausgeführt, wenn i.next != null ist, folglich gilt im Schleifenkörper i.next==null gerade nicht.

Java:
Node last;
for (last = first; last.next != null; last = last.next) {
    ; // nichts zu tun
}
return last;
Okay danke für die Antwort, die fehlenden Simikolons und Schleifen kommen daher, dass ich es schnell übers Handy eingetippt habe, aber dennoch gut zu wissen das dort noch mehr Fehler drin sind.
 
J

JustNobody

Also bezüglich des Code von Snaer mit der for Schleife, habe ich da auch noch ein paar Anmerkungen. Mihe7 hat da schon sehr gut einiges zu geschrieben, aber der Ansatz ist durchaus interessant und korrekt ....

for Schleife: Aus meiner Sicht ist das die typische "Zählschleife", also dient dem durchzählen. Andere Verwendung sehe ich da eher nicht, weil ungewöhnlich. Aber das ist eine reine Präferenz und die Nutzung ist prinzipiell richtig!

Jetzt kommen zwei weitere Punkte hinzu:
1. was Du schon selbst angemerkt hast: Du müsstest mit last und nicht mit i arbeiten.
2. Die Bedingung im if-Statement wird niemals true sein, da diese mit der Bedingung der while-Schleife genau gegenteilig überprüft wurde. Der Schleifenkörper wird nur ausgeführt, wenn i.next != null ist, folglich gilt im Schleifenkörper i.next==null gerade nicht.
Also diesbezüglich kann ich auch als Alternative anbieten:
zu 1. Da die lokale Variable last nur initialisiert aber nie verwendet wird, kann diese einfach gelöscht werden. Dadurch entfällt die erste Zuweisung. (Aber die Variable in der for Schleife kann man ja umbenennen....)
zu 2. Ja, mir ist das als "doppelte Prüfung" aufgefallen. Die Konsequenz daraus kann dann aber auch sein, dass man den Vergleich in der Bedingung der for Schleife komplett entfernt.
Java:
for (Node last = first; ; last = last.next) {
    if (last.next == null) return last;
}
Ein return am Ende brauchte ich nicht, denn das wäre in meinen Augen auch unreachable code gewesen. Die for Schleife hat ja kein break und damit wird diese nicht verlassen.

Das war halt auch eine Option, die ich bei dem Code gesehen hätte, auch wenn ich für meine Person immer zu der while Schleife greifen würde ....
 
J

jono

Jetzt habe ich noch Probleme bei der append und init Methode.
Java:
public void init() {
        if (first.next == null) {
            first = null;
            last = null;

        } else {
            last.init.next = null;
            last = last.init;
        }
        length--;

    }
Prinzipiell ist das ja schonmal korrekt, jedoch wird mir last rot unterstrichen, kann ich auch hier wieder
Node last = first anwenden, was ich eigentlich für sinnvoll halte?
 
J

JustNobody

Ähm, kannst Du einmal beschreiben, was init genau machen soll? Eine leere Liste initialisieren?
Was ist denn first, last und length bei einer leeren Liste, nachdem die Liste initialisiert wurde?
 
J

jono

Java:
Was ist denn first, last und length bei einer leeren Liste, nachdem die Liste initialisiert wurde?
Weiß gerade nicht worauf dich da bei mir beziehst, bzw. was du mir damit sagen willst.
 
L

Luca H

Jetzt habe ich noch Probleme bei der append und init Methode.
Java:
public void init() {
        if (first.next == null) {
            first = null;
            last = null;

        } else {
            last.init.next = null;
            last = last.init;
        }
        length--;

    }
Prinzipiell ist das ja schonmal korrekt, jedoch wird mir last rot unterstrichen, kann ich auch hier wieder
Node last = first anwenden, was ich eigentlich für sinnvoll halte?
Du musst last initialisieren also bei mir klappts mit
Code:
Node last;
 
L

Luca H

ich hätte allerdings auch eine frage undzwar bei der Methode
Code:
    public void cons(int value) {
        Node newElem = new Node();
        newElem.value = value;

        if (this.first == null) {
            this.first = newElem;
        } else {
            Node tmp = this.first;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newElem;
        }
    }
bekomme ich folgenden Fehler

JUnit version 4.12
.E
Time: 0.004
There was 1 failure:
1) test(PublicTests)
java.lang.AssertionError: expected:<5> but was:<9>
at org.junit.Assert.fail(Assert.java:88)
at org.junit.Assert.failNotEquals(Assert.java:834)
at org.junit.Assert.assertEquals(Assert.java:645)
at org.junit.Assert.assertEquals(Assert.java:631)
at PublicTests.test(PublicTests.java:15)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
 
S

Snaer

Java:
for (Node last = first; ; last = last.next) {
    if (last.next == null) return last;
}
Die Funktion der last Methode sieht ja so aus :
"last : SortedList -> Nat? // Last element "
Sprich wenn die Liste leer ist fehlt dann nicht noch ein entsprechender Rückgabewert?
Sprich wenn ich eine leere Liste haben sollte, ist first.next bzw in dem Beispiel auch gleichzeitig last.next == null und anschließend gebe ich last aus. Ist das aber auch genug für die angegebene Funktion oder muss man auch noch eine if Anweisung einbauen, die den Fall berücksichtigt, dass die Liste von Beginn an leer sein könnte und es dementsprechend kein letztes Element gibt?

Zudem tue ich mich gerade noch bei der cons Methode schwer:
"constructors nil : -> SortedList // Empty list
hidden constructors cons' : Nat x SortedList -> SortedList // Head element and tail list
functions cons : Nat x SortedList -> SortedList //add element to SortedList
equations cons(n, nil) = cons'(n, nil) cons(n, cons'(n1, l)) = if(greater(n,n1)) then cons'(n1, cons(n, l)) else cons'(n, cons'(n1, l)) "

Meine bisherigen Ansätze sahen so aus
Code:
public void cons(int n) { // Hinzufuegen eines elements
        Node n1 = new Node();
        if(first==null) {
            first.value=n;
            first.next=null;
        }
        if(n<first.value) { // n kleiner als erstes Element bsp 5 kleiner 9
            n1=first;        // speicher first in n1 (n1 =9)
            first.value=n;     // speicher n in first   (first = 5)
            first.next=n1;        // first next zeigt auf n1 also 9
            
        }
        if (n>first.value) { // n ist groesser als first beispiel 7 groesser als 5
            n1.value=n;     // speicher n in n1
            first.next= n1;  // n1 soll hinter first gespeichert werden
        }
    }
Bei diesem bekomme ich jedoch eine Nullpointer Exception
"
There was 1 failure:
1) test(PublicTests)
java.lang.NullPointerException
at SortedList.cons(SortedList.java:14)
at PublicTests.test(PublicTests.java:12)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)"
und:
Code:
public void cons(int n) { // Hinzufuegen eines elements
        Node n1 = new Node();
        n1.value = n;
        if (first == null) // Liste ist null n1 wird Kopfelement
            first = n1;
        else {
            Node i;
            while (first.next != null) {
                if (n1.value != n) {
                    if (n1.value > n) { // Wenn n1 > n ist soll n1 head werden
                        n1.next = first;
                        n1.value = n;
                        first = n1;
                    }
                    if (n1.value < n) { // Wenn n1<n ist soll n1 hinten eingefuegt werden
                        n1.value = n;
                        n1.next = null;
                        while (first.next != null) {
                            first = first.next;
                        }
                        first.next = n1;
                    }
                }
                first=first.next;
            }
        }
    }
Dabei wird zwar das erste Element eingefügt allerdings wird die Liste anscheinend nicht richtig sortiert.

"There was 1 failure:
1) test(PublicTests)
java.lang.AssertionError: expected:<5> but was:<9>"

Da bislang niemand den Test gezeigt hat tue ich das eben mal :
Code:
import static org.junit.Assert.*;

import org.junit.Test;

public class PublicTests {

    @Test
    public void test() {
        SortedList sList = new SortedList();
        
        //Teste cons
        sList.cons(9);
        sList.cons(5);
        sList.cons(7);
        assertEquals(5, sList.first.value);
        assertEquals(7, sList.first.next.value);
        assertEquals(9, sList.first.next.next.value);
        
        
        //Teste append
        SortedList sList2 = new SortedList();
        sList2.cons(6);
        sList2.cons(8);
        sList2.cons(4);

        sList.append(sList2);
        assertEquals(4, sList.first.value);
        assertEquals(5, sList.first.next.value);
        assertEquals(6, sList.first.next.next.value);
        assertEquals(7, sList.first.next.next.next.value);
        assertEquals(8, sList.first.next.next.next.next.value);
        assertEquals(9, sList.first.next.next.next.next.next.value);
        
    }

}
 
mihe7

mihe7

Code:
Eine SortedList l:

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
        

l.init():

first     next      next
----> [3] ----> [5] ----> nil


l.cons(4)

first     next      next      next
----> [3] ----> [4] ----> [5] ----> nil
 
S

Snaer

Code:
Eine SortedList l:

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
       

l.init():

first     next      next
----> [3] ----> [5] ----> nil


l.cons(4)

first     next      next      next
----> [3] ----> [4] ----> [5] ----> nil
Ja das ist verständlich, nur verstehe ich nicht ganz wieso bei mir die Einordnung nicht funktioniert.
Wäre es vielleicht eine Möglichkeit mittels einer Zählschleife die Liste zu durchlaufen und dann anschließend einzufügen?
Also quasi first.next.next für den 3. Index der Liste?
Und sorry falls das eine dumme Frage ist, aber ich verstehe die Implementation von hidden constructors nicht ganz.
So wie es uns erklärt wurde bzw wie ich es verstanden habe, dienen hidden constructors dazu um z.b das hinzufügen eines Wertes zu kontrollieren.
Allerdings wurde in den Beispiel Folien die wir bekommen haben nie ein hidden constructor selbst implementiert sondern alles in der normalen Methode erledigt.
 
mihe7

mihe7

nur verstehe ich nicht ganz wieso bei mir die Einordnung nicht funktioniert.
Weil Ihr Euch das nicht richtig überlegt.

Geh mal von folgender Liste aus:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
Sagen wir mal, Du möchtest die 7 einfügen. Dann kann man das Problem in zwei Teile aufteilen: 1. finde den richtigen Knoten. 2. füge den neuen Knoten ein.

Welches wäre der richtige Knoten? Der mit der 5.

Warum? Weil wir einen Knoten immer nur hinter einen anderen hängen können und der Wert des auf die 5 folgenden Knotens größer als der einzufügende Wert ist. Ohne Berücksichtigung von Sonderfällen wandern wir also durch die Liste, bis der Wert des Nachfolgerknotens größer als der einzufügende Wert ist.

Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
       ^
       next.value == 5 < 7 --> also weiter        

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                 ^
                 next.value == 8 > 7 --> richtige Stelle
An der Stelle können wir also das neue Element einfügen. Wir können sagen, dass der Nachfolger des neuen Element gleich dem aktuellen Nachfolger sein muss:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                           ^
                     [7]---+
                        next
Außerdem muss der aktuelle Nachfolger das neue Element sein:
Code:
first     next                next
----> [3] ----> [5]       [8] ----> nil
                 |         ^
                 +-->[7]---+
                 next   next
Sonderfälle gibt es drei:
1. Das Element muss am Ende der Liste eingefügt werden. Hier ist die Bedingung der Schleife entsprechend zu erweitern.
2. Das Element muss am Anfang einer Liste eingefügt werden.
3. Das Element muss in eine leere Liste eingefügt werden.

Die Fälle 2 und 3 werden gleich behandelt: der Nachfolger des einzufügenden Elements wird der Knoten, auf den first zeigt und first muss hinterher auf das neue erste Element zeigen.
 
S

Snaer

Weil Ihr Euch das nicht richtig überlegt.

Geh mal von folgender Liste aus:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
Sagen wir mal, Du möchtest die 7 einfügen. Dann kann man das Problem in zwei Teile aufteilen: 1. finde den richtigen Knoten. 2. füge den neuen Knoten ein.

Welches wäre der richtige Knoten? Der mit der 5.

Warum? Weil wir einen Knoten immer nur hinter einen anderen hängen können und der Wert des auf die 5 folgenden Knotens größer als der einzufügende Wert ist. Ohne Berücksichtigung von Sonderfällen wandern wir also durch die Liste, bis der Wert des Nachfolgerknotens größer als der einzufügende Wert ist.

Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
       ^
       next.value == 5 < 7 --> also weiter       

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                 ^
                 next.value == 8 > 7 --> richtige Stelle
An der Stelle können wir also das neue Element einfügen. Wir können sagen, dass der Nachfolger des neuen Element gleich dem aktuellen Nachfolger sein muss:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                           ^
                     [7]---+
                        next
Außerdem muss der aktuelle Nachfolger das neue Element sein:
Code:
first     next                next
----> [3] ----> [5]       [8] ----> nil
                 |         ^
                 +-->[7]---+
                 next   next
Sonderfälle gibt es drei:
1. Das Element muss am Ende der Liste eingefügt werden. Hier ist die Bedingung der Schleife entsprechend zu erweitern.
2. Das Element muss am Anfang einer Liste eingefügt werden.
3. Das Element muss in eine leere Liste eingefügt werden.

Die Fälle 2 und 3 werden gleich behandelt: der Nachfolger des einzufügenden Elements wird der Knoten, auf den first zeigt und first muss hinterher auf das neue erste Element zeigen.
Die Logik dahinter verstehe ich, jedoch frage ich mich wie ich möglichst einfach den passenden Index in der Liste ansprechen kann.
Meine einzige Idee wie ich an den dritten Index kommen kann ist first.next.next oder mittels einer Schleife jedoch wüsste ich nicht wie ich diese schreiben kann, außer wenn ich in den letzten Index erreichen möchte.
Oder würde das so funktionieren :
Code:
while (n> first.next){
first.next = first.next.next;
}
 
S

Snaer

Was willst Du denn mit einem Index?
Nun ja angenommen ich habe eine Liste in der bereits 3, 4, 8, und 9 gespeichert sind und in diese soll nun die 7 gespeichert werden.
Dann muss ich ja die Liste durch laufen bis ich raus finde wo die 7 hingehört also zwischen die 4 und die 8.
Index ist vielleicht der falsche Begriff dafür, aber ich meine eben die Stelle in der Liste bzw der richtige Knoten für den neuen Wert.
 
S

Snaer

Naja ich würde es entweder mithilfe einer For Schleife machen
Code:
for (Node i = first ; i != null; i = i.next){

}
Oder mithilfe einer while schleife
Code:
while (first.next != null){
first=first.next
}
Bei beiden Varianten durchlaufe ich die Liste ja allerdings bis ich am letzten Element angekommen bin. Ich müsste ja dann einen Weg finden, um diesen neuen Wert mit jedem Platz der Liste zu vergleichen nur weiß ich allerdings nicht wie ich die einzelnen Stellen der Liste ansprechen kann.
 
mihe7

mihe7

Bei der zweiten Variante fehlt Dir die Referenz auf das aktuelle Element (in der ersten Variante ist das Dein i).
Java:
Node i = first;
while (i.next != null) {
    i = i.next;
}
Du solltest die Referenz aber nicht "i" nennen; ein aussagekräftiger Name wäre besser.

nur weiß ich allerdings nicht wie ich die einzelnen Stellen der Liste ansprechen kann.
Über die Referenz i, die auf das jeweils aktuelle Element zeigt?
 
S

Snaer

Was schwebt dir für ein aussagekräftigerer Name denn vor?

Also kann ich dann mithilfe von i eine if Anweisung bauen und den Wert entsprechend einfügen ?
Code:
Code:
Node i = first;
while (i.next != null) {
    i = i.next;
    if (n < i)
    n.next = i;
    i.init = n;
}
Geht das so in die richtige Richtung oder müsste ich eventuell noch eine Hilfsvariable deklarieren um einen Wert in dieser zunächst zu speichern ?
 
mihe7

mihe7

Was schwebt dir für ein aussagekräftigerer Name denn vor?
current wäre doch eine Möglichkeit.

Geht das so in die richtige Richtung
Es geht bei der Schleife nur darum, i an die richtige Stelle zu positionieren. Du musst also nur die Schleifenbedingung anpassen. Aktuell stellst Du schon mal sicher, dass Du nicht über das Ende der Liste hinaus läufst. Bis zum Eintreffen welcher Situation musst Du denn i auf die nächste Stelle positionieren?
 
S

Snaer

Aso ja dann
Code:
Node i = first;
while (i.next > n ) {
    i = i.next;
    if(i.next < n)
    i.next = n;
}
Sprich ich durchlaufe die Liste solange bis ich einen Wert finde der kleiner ist als n und füge es dann dort ein.
Bzw müsste ich es so machen solange i.next < n da die Liste ja aufsteigend sortiert wird
 
mihe7

mihe7

1. i und i.next sind Referenzen auf Node-Objekte. Die kannst Du nicht einfach mit einem int vergleichen, das hatten wir heute schon einmal...
2. läufst Du jetzt ggf. über das Ende hinaus.
3. "müsste ich es so machen solange i.next < n da die Liste ja aufsteigend sortiert wird" - vom Prinzip richtig.

Java:
public void cons(int value) { // Hinzufuegen eines elements
    // ... hier kommt noch mehr ...

    Node current = first;
    while (current.next != null && current.next.value < value) {
       current = current.next;
    }

    // an der Stelle zeigt current auf den Knoten, hinter dem
    // der neue Knoten eingefügt werden muss...
}
EDIT: den Vergleich auf <= korrigiert: < reicht.
 
S

Snaer

1. i und i.next sind Referenzen auf Node-Objekte. Die kannst Du nicht einfach mit einem int vergleichen, das hatten wir heute schon einmal...
Sorry mein Fehler ich meine natürlich n.value.
Ich nehme mal an mit dem Kommentar hier kommt noch mehr spielst du auf die Möglichkeit an, dass die Liste auch leer sein kann und ich in diesem Fall das Element einfach hinzufügen kann ohne diese zu durchlaufen.
 
S

Snaer

Wenn current auf den Knoten zeigt hinter dem der neue Knoten eingefügt werden muss verstehe ich es dann richtig das dann quasi so aussieht ?
Ich will den Wert 5 einfügen.
Current wäre z.B 3 .next.value zeigt dann auf 4 und hinter eben dieser 4 muss ich dann meine Zahl einfügen also sprich die 5?
Code:
current.next.next = n.value;
Muss ich dann wirklich mehrere .next aneinander hängen um diesen Knoten anzusprechen oder denke ich da gerade völlig falsch ?
 
mihe7

mihe7

Ich nehme mal an mit dem Kommentar hier kommt noch mehr spielst du auf die Möglichkeit an, dass die Liste auch leer sein kann und ich in diesem Fall das Element einfach hinzufügen kann ohne diese zu durchlaufen.
Ja. Ggf. erstellst Du am Anfang auch schon das einzufügende Node-Objekt.

verstehe ich es dann richtig das dann quasi so aussieht ?
Nein. Und wieder: Node-Objekte vs int...
 
S

Snaer

Nein. Und wieder: Node-Objekte vs int...
Also ich meinte es nicht als bloße Zahlen sondern eher
Das Kopfelement 3 mit Tail auf Kopf 4. Die 5 wäre kleiner als der kopf Wert welcher ja in der Klasse Node als int value deklariert ist also muss dann der Tail von 4 auf die 5 zeigen, um diese einzufügen und wenn die Liste anschließend leer sein sollte zeigt Tail von 5 auf null.
 
mihe7

mihe7

Bevor das hier ausartet:
Java:
public void cons(int n) { // Hinzufuegen eines elements
    Node toInsert = new Node();
    toInsert.value = n;

    if (first == null || first.value >= n) {
        toInsert.next = first;
        first = toInsert;
        return;
    }

    Node current = first;
    while (current.next != null && current.next.value <= value) {
       current = current.next;
    }
    toInsert.next = current.next;
    current.next = toInsert;
}
 
S

Snaer

Bevor das hier ausartet:
Java:
public void cons(int n) { // Hinzufuegen eines elements
    Node toInsert = new Node();
    toInsert.value = n;

    if (first == null || first.value >= n) {
        toInsert.next = first;
        first = toInsert;
        return;
    }

    Node current = first;
    while (current.next != null && current.next.value <= value) {
       current = current.next;
    }
    toInsert.next = current.next;
    current.next = toInsert;
}
Könntest du mir den letzten Schritt erläutern?
Ein Listen Objekt besteht ja aus einem Kopf in meinem Fall dann value und einem Tail in meinem Fall dann next.
Ich verstehe es gerade so das zum Beispiel der Tail von 5 auf den Tail von 4 zeigt, und der Tail von 4 auf den Kopf von 5.
Aber wäre das dann nicht nur im Kreis und würde nicht mit mehreren Elementen funktionieren?
Ich sehe das der Code zwar so funktioniert allerdings verstehe ich es noch nicht ganz.
 
J

jono

Kannst du bitte auch mal sagen, was jetzt genau mit current.next.value gemeint ist?
 
J

JustNobody

Kannst du bitte auch mal sagen, was jetzt genau mit current.next.value gemeint ist?
Überleg doch selbst einmal in Ruhe. Sowas solltest Du selbst erkennen können!

Was ist current in dem Code?
Was ist dann next bei current?
Und wenn Du das weisst:Was ist denn bei current.next dieses value?

Könntest du mir den letzten Schritt erläutern?
Ein Listen Objekt besteht ja aus einem Kopf in meinem Fall dann value und einem Tail in meinem Fall dann next.
Ich verstehe es gerade so das zum Beispiel der Tail von 5 auf den Tail von 4 zeigt, und der Tail von 4 auf den Kopf von 5.
Aber wäre das dann nicht nur im Kreis und würde nicht mit mehreren Elementen funktionieren?
Ich sehe das der Code zwar so funktioniert allerdings verstehe ich es noch nicht ganz.
Wenn es eine sortierte Liste ist, dann sollte das Element mit der 5 nie auf das Element von 4 zeigen, denn dann wäre es doch nicht sortiert.
Mein Tipp:Spiel das doch alles einmal richtig auf einem Zettel durch!
 
L

Luca H

Bevor das hier ausartet:
Java:
public void cons(int n) { // Hinzufuegen eines elements
    Node toInsert = new Node();
    toInsert.value = n;

    if (first == null || first.value >= n) {
        toInsert.next = first;
        first = toInsert;
        return;
    }

    Node current = first;
    while (current.next != null && current.next.value <= value) {
       current = current.next;
    }
    toInsert.next = current.next;
    current.next = toInsert;
}
vielen dank nun klappt diese methode bei mir, jedoch wird jz die append Methode als falsch angemerkt

Code:
    public void append(SortedList l1) {
        if (!l1.isNil())
            if (first == null) {
                first = l1.first;

            } else {
                Node i;
                for (i = first; i.next != null; i = i.next)
                    ;
                i.next = l1.first;
            }

    }
und folgender Fehler wird angezeigt, es wäre nett wenn mir jemand einen Denkanstoß geben könnte

JUnit version 4.12
.E
Time: 0.004
There was 1 failure:
1) test(PublicTests)
java.lang.AssertionError: expected:<4> but was:<5>
at org.junit.Assert.fail(Assert.java:88)
at org.junit.Assert.failNotEquals(Assert.java:834)
at org.junit.Assert.assertEquals(Assert.java:645)
at org.junit.Assert.assertEquals(Assert.java:631)
at PublicTests.test(PublicTests.java:27)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
 
J

JustNobody

Ja, und ich will niemandem zu nahe treten, aber dann gibt @mihe7 mehr oder weniger auf und gibt die Lösung und dann gibt es da auch noch massive Verständnisprobleme? Wenn es an den Grundlagen fehlt: Die müsst ihr euch erarbeiten - ich denke, dass @mihe7 da wenig Übungsbedarf hat. Und wie immer gilt da:Übung macht den Meister!

Und wenn es Probleme gibt beim Verständnis der Aufgabe:Malt euch das auf! Das muss man nicht alles direkt im Kopf haben ... aber dann malt es euch auf! Was für Instanzen gibt es? Was sind da jeweils die Inhalte? Dann klappt es auch mit dem Verständnis!
 
L

Luca H

//Teste append SortedList sList2 = new SortedList(); sList2.cons(6); sList2.cons(8); sList2.cons(4); sList.append(sList2); assertEquals(4, sList.first.value); assertEquals(5, sList.first.next.value); assertEquals(6, sList.first.next.next.value); assertEquals(7, sList.first.next.next.next.value); assertEquals(8, sList.first.next.next.next.next.value); assertEquals(9, sList.first.next.next.next.next.next.value);
Der Fehler ist in Zeile 27 bei AssertEquals (4...) also demnach fügt der Code die 6,8,4 ein aber wenn er dann die Listen vergleicht kommt die Fehlermeldung. Das würde ja an sich bedeuten, dass meine Liste nicht Sortiert ist und die Zahlen nur angehangen wurden oder? Bis dato hat der code ja noch keinen Fehler angezeigt.
 
Thema: 

Implementierung Listen-ADT

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben