Hilfe bei verknüpfter Liste - Linkedlist

[Neuling0211]

Hi Leute,

Wie man am Titel an schon sehen kann sitze ich ziemlich in der Patsche. Ich lese mir die Aufgabe noch und nöcher durch und verstehe nur Bahnhof. Den Leuten in meinem Kurs geht es genauso und wir müssen sie bis nächste Woche gelöst bekommen..
Hier im Forum sollte es den Profis unter euch doch vor keine große Aufgabe stellen:

1)
Gegeben seien folgende zwei Klassen List und Node zur Repräsentation von einfach-verketteten
linearen Listen mit int-Werten:
public class Node {
private int val;
private Node next;
public Node(int val) {…}
public Node(int val, Node next)
{…}
…
} // Node
public class LinkedList {
private Node head;
public LinkedList () { … }
…
} // LinkedList

Vervollständige die beiden Konstruktoren und implementiere in der Klasse List folgende
Methoden:
Ø void prepend(int val): fügt den Wert val vorne in die Liste ein
Ø void append(int val): fügt den Wert val hinten in die Liste ein
Ø boolean sorted(): stellt fest, ob die Werte der Knoten der Liste aufsteigend sortiert sind
Ø void insert(int val): fügt den Wert val in eine sortierte Liste an der richtigen Stelle ein,
sodass die neue Liste wieder sortiert ist
Ø boolean delete(int val): Löscht den Wert val aus der Liste. Bei mehrfachem Vorkommen des
Wertes sollen alle Knoten mit Wert val aus der Liste gelöscht werden
Ø String toString(): liefert eine Zeichenkette mit den Werten der Knoten, durch Beistriche
voneinander getrennt

____________________________________________________________________

Puhhh Ja uns Anfänger geht es so.. tja. Bitte kann mir jemand mit konkreten Lösungen helfen, aber wenns geht so, dass es nicht mega Profi-like aussieht, da würde der Kursleiter verdacht schöpfen.. Wer Mitleid mit uns hat, bitte HELFEN!!

 

[Javinner]

Bitte kann mir jemand mit konkreten Lösungen helfen, aber wenns geht so, dass es nicht mega Profi-like aussieht, da würde der Kursleiter verdacht schöpfen

Nichts täte ich lieber! Hier steht alles drin und weil wir dabei sind, auch hier solltest du mal schauen

 

[DrZoidberg]

Wenn du auf Google nach "java verkettete liste" suchst. Findest du gleich mehrere Beispiele, die du nur geringfügig ändern musst.

 

[Xyz1]

Ø void insert(int val): fügt den Wert val in eine sortierte Liste an der richtigen Stelle ein,
sodass die neue Liste wieder sortiert ist

Das ist ungenau, weil nicht steht, was passieren soll, wenn in eine unsortierte Liste eingefügt werden soll.

Der Rest ist süpi.

 

[Neuling0211]

@DerWissende Danke für deine Hilfe, ich habe wohl vergessen dass ich die Dateien hochlade, die wir als Angabe für die Übung mit dazubekommen haben. Das sind 4 Dateien, ich füge sie der Reihe nach ein

 

[Neuling0211]

Es sind 4 Klassen die erste heißt AlgoDat_UE3_TestApplication:

[
public class AlgoDat_UE3_TestApplication extends AlgoDat_UE3_TestOutput {

public static void main(String[] args) {

System.out.println("===================================================");
System.out.println(" Test der LinkedList (Uebung3) ");
System.out.println("===================================================");
System.out.println();

// Aufrufe der einzelnen Tests der jeweiligen Klassen

testPrepend();
testAppend();
testSorted();
testInsert();
testDelete();
testDuplicate();
testMerge();
}

static void testPrepend() {
testStarted("Methode prepend(int val)");

LinkedList list = new LinkedList();
test(1, "prepend()", "Liste ist leer", list.toString());

list.prepend(10);
list.prepend(8);
list.prepend(5);
list.prepend(4);
list.prepend(2);
list.prepend(1);
test(2, "prepend()", "1, 2, 4, 5, 8, 10", list.toString());

list.prepend(1);
list.prepend(0);
test(3, "prepend()", "0, 1, 1, 2, 4, 5, 8, 10", list.toString());

testFinished("Methode prepend(int val)");
}

static void testAppend() {
testStarted("Methode append(int val)");

LinkedList list = new LinkedList();
test(1, "append()", "Liste ist leer", list.toString());

list.append(1);
list.append(2);
list.append(4);
list.append(5);
list.append(8);
list.append(10);
test(2, "append()", "1, 2, 4, 5, 8, 10", list.toString());

list.append(20);
list.append(10);
test(3, "append()", "1, 2, 4, 5, 8, 10, 20, 10", list.toString());

testFinished("Methode append(int val)");
}

static void testSorted() {
testStarted("Methode sorted()");

LinkedList list = new LinkedList();
test(1, "sorted()", "false", ""+ list.sorted());

list.prepend(5);
list.append(8);
list.append(10);
list.prepend(4);
list.prepend(2);
list.prepend(1);
test(2, "sorted()", "true", ""+ list.sorted());

list.append(0);
list.prepend(10);
test(3, "sorted()", "false", ""+ list.sorted());
test(4, "sorted()", "10, 1, 2, 4, 5, 8, 10, 0", list.toString());

testFinished("Methode sorted()");
}

static void testInsert() {
testStarted("Methode insert(int val)");

LinkedList list = new LinkedList();
list.prepend(5);
list.append(8);
list.append(10);
list.prepend(4);
list.prepend(2);

list.insert(1);
test(1, "insert()", "1, 2, 4, 5, 8, 10", list.toString());

list.insert(6);
test(2, "insert()", "1, 2, 4, 5, 6, 8, 10", list.toString());

list.insert(9);
test(3, "insert()", "1, 2, 4, 5, 6, 8, 9, 10", list.toString());

testFinished("Methode insert(int val)");
}

static void testDelete() {
testStarted("Methode delete(int val)");

LinkedList list = new LinkedList();
list.prepend(5);
list.append(8);
list.append(10);
list.prepend(4);
list.prepend(2);
list.prepend(1);
test(1, "delete()", "1, 2, 4, 5, 8, 10", list.toString());

list.delete(1);
test(2, "delete()", "2, 4, 5, 8, 10", list.toString());

list.insert(1);
list.delete(4);
list.delete(10);
test(3, "delete()", "1, 2, 5, 8", list.toString());

testFinished("Methode duplicate(int val)");
}

static void testDuplicate() {
testStarted("Methode delete(int val)");

LinkedList list = new LinkedList();
test(1, "duplicate()", "Liste ist leer", list.duplicate().toString());

list.prepend(5);
list.append(8);
list.append(10);
list.prepend(4);
list.prepend(2);
list.prepend(1);
test(2, "duplicate()", "1, 2, 4, 5, 8, 10", list.duplicate().toString());

list.append(0);
list.prepend(10);
test(3, "duplicate()", "10, 1, 2, 4, 5, 8, 10, 0", list.duplicate().toString());

testFinished("Methode duplicate()");
}

static void testMerge() {
testStarted("Methode merge(LinkedList list)");

LinkedList list1 = new LinkedList();
list1.append(1);
list1.append(4);
list1.append(8);
test(1, "merge()", "1, 4, 8", list1.toString());

LinkedList list2 = new LinkedList();
list2.append(2);
list2.append(5);
list2.append(10);
test(2, "merge()", "2, 5, 10", list2.toString());

list1.merge(list2);
test(3, "merge()", "1, 2, 4, 5, 8, 10", list1.toString());
test(4, "merge()", "Liste ist leer", list2.toString());

testFinished("Methode merge(LinkedList list)");
}

}
]

 

[Neuling0211]

Die Zweite: AlgoDat_UE3_TestOutput:

[
public class AlgoDat_UE3_TestOutput {

// Methoden der Klasse

/* * *
* Mit dieser Methode kann der Beginn eines Tests gekennzeichnet werden
* Zusätzlich wird die getestete Klasse oder Methode angegeben
*/
public static void testStarted(String testTyp) {
System.out.println("----------------------------------------------");
System.out.println(" Testbeginn der " + testTyp);
}

/* * *
* Mit dieser Methode kann das Ende eines Tests gekennzeichnet werden
* Zusätzlich wird die getestete Klasse oder Methode angegeben
*/
public static void testFinished(String testTyp) {
System.out.println();
System.out.println(" Testende der " + testTyp);
System.out.println("----------------------------------------------");
System.out.println();
}

/* * *
* Methode vergleicht das erwartete Ergebnis mit dem tatsächlich und
* liefert eine Rückmeldung, ob die Methode funktioniert
*/
public static void test(int i, String action, String expected, String result) {
System.out.println();
System.out.println("* Test " + i + ": " + action);
System.out.println(" Erwartete Antwort: " + expected);
System.out.println(" Ergebnis: " + result);
if (expected.equals(result)) {
System.out.println(" ===> Methode funktioniert");
} else {
System.out.println(" ===> Methode funktioniert nicht");
}
}

}
]

 

[Neuling0211]

3. LinkedList:

[
public class LinkedList {

// Attribut der Klasse
private Node head;

// Konstruktor der Klasse

public LinkedList() {
// Implementierung des Konstruktors
}

// Methoden der Klasse

public void prepend(int val) {
// Methode fügt den Wert val am Beginn der Liste ein
}

public void append(int val) {
// Methode fügt den Wert val am Ende der Liste ein
}

public boolean sorted() {
// Methode überprüft, ob eine Liste sortiert ist
}

public void insert(int val) {
// Methode fügt den Wert val an der richtigen Stelle in eine sortierte Liste ein
}

public boolean delete(int val) {
// Methode löscht den Knoten mit dem Wert val aus der Liste
}

public String toString() {
// Methode liefert eine Zeichenkette mit den Werten der Knoten
}


// Zusätzliche Funktionalität für die LinkedList

public LinkedList duplicate() {
// Methode liefert ein Duplikat der Liste
}

public void merge(LinkedList list) {
// Methode fügt eine Liste in sortierter Reihenfolge in eine andere ein
}

}
]

 

[Neuling0211]

4. Node:

[

public class Node {

// Attribute der Klasse
private int val; // Speicherung beliebiger Daten vom Typ integer
private Node next; // Referenzvariable zum Speichern eines Verweises auf den nächsten Knoten

// Konstruktoren der Klasse
public Node(int val) {
// Implementierung des Konstruktors
}

public Node(int val, Node next) {
// Implementierung des Konstruktors
}

// Methoden der Klasse

]

 

[DrZoidberg]

Und wie weit bist du schon gekommen? Womit genau hast du Schwierigkeiten?
Konzentriere dich erst mal auf eine Methode. Die einfachste ist "prepend". Damit würde ich anfangen. Dann "append" und dann "toString".

 

[MoxxiManagarm]

Manchen hilft es sich die verkettete Liste Bildlich vorzustellen.

Denk z.B. an einen Zug mit verschiedenen Waggons (Node). Jeder Zugteil hat eine Nummer (val). Der Zug hat ein Zughaus (LinkedList) von der aus man stets das den ersten Waggon (head) sehen kann. Für Operationen an diesem Zug gibt es einen Zugführer (dynamischer Zeiger). Von jedem Waggon kann man nur den nächsten Waggon (next) sehen, der Rest ist verdeckt. Der letzte Waggon sieht nichts mehr (null)

Nun Stell dir die Operationen bildlich vor und versuche sie zu interpretieren:
Ø void prepend(int val): fügt den Wert val vorne in die Liste ein
Der neue Zugteil muss zwischen Zughaus und dem bisher ersten Waggon eingefügt werden. Der alte erste Waggon wird dann nur noch vom neuen ersten Waggon gesehen. Das Zughaus sieht nun den neuen Waggon.

Ø void append(int val): fügt den Wert val hinten in die Liste ein
Der letzte Waggon sieht nun den neuen Waggon. Hinter dem neuen Waggon gibt es keinen anderen Waggon den er sehen könnte.

Ø boolean sorted(): stellt fest, ob die Werte der Knoten der Liste aufsteigend sortiert sind
Der Zugführer läuft ausgehend vom Anfang des Zuges nach hinten und überprüft die Nummernreihenfolge.

Ø String toString(): liefert eine Zeichenkette mit den Werten der Knoten, durch Beistriche
voneinander getrennt
Der Zugführer läuft ausgehend vom Anfang des Zuges nach hinten. Er notiert sich jede Zugnummer und schreibt zwischen jede den Beistrich.

Ø void insert(int val): fügt den Wert val in eine sortierte Liste an der richtigen Stelle ein,
sodass die neue Liste wieder sortiert ist
// versuchs selbst zu verbildlichen

Ø boolean delete(int val): Löscht den Wert val aus der Liste. Bei mehrfachem Vorkommen des
Wertes sollen alle Knoten mit Wert val aus der Liste gelöscht werden
// versuchs selbst zu verbildlichen

 

[Xyz1]

ich habe wohl vergessen dass ich die Dateien hochlade, die wir als Angabe für die Übung mit dazubekommen haben. Das sind 4 Dateien, ich füge sie der Reihe nach ein

Das muss alles wohlgeformt hier eingefügt werden. Sonst schaue ich mir das nicht an.
Und danke für die Blumen.

Achso - wie das geht steht in meiner Siggi.