Programmieren mit Harald R. Haberstroh

Diese Aufgabe enthält mehrere Übungsbeispiele zu Listen. Es sollen verschiedenste Aufgabenstellungen mit verketteten Listen gelöst werden, um das Verständnis mit Beispielen zu vertiefen.
Welche Daten in den Listen gespeichert werden ist meist nicht so wichtig. Verwenden Sie Strings oder ganze Zahlen, wenn nichts anderes angegeben wird.
Erstellen Sie jeweils eine Klasse public class Liste, wie in Verkettete Listen beschrieben mit den in der jeweiligen Aufgabenstellung geforderten Methoden. Für die Datenelemente erzeugen Sie eine Klasse public class Data, welche einen ganzzahligen Wert (int key) und einen String (String value) aufnehmen kann.

1. Am Ende einer (einfach verketteten) Liste einfügen und löschen.

Schreiben Sie die Funktionen

void append(Data data);   /* anhängen */
void delEnd();            /* entfernen des letzten Elements */

Skizzieren Sie mehrere Listenbeispiele und entwickeln sie passende Testfälle (leere Liste, ein Element, 2 Elemente, 3 oder mehr Elemente).

2. Sortiertes Einfügen in eine doppelt verkettete Liste

Schreiben Sie eine Funktion

void insert_sort(Data data);

welche ein Element sortiert nach key in die doppelt verkettete Liste einfügt (Vorwärts- und Rückwärtsverkettung).

3. Löschen eines bestimmten Elements

Schreiben Sie eine Funktion

boolean del(Data data);

welche ein Element mit dem gesuchten Inhalt löscht (meist wird nur ein key verwendet, hier können Sie aber einfach die Daten verwenden). del() soll true liefern, wenn das Element gefunden und gelöscht wurde.

4. Ändern eines Elements in einer einfach verketteten Liste

Schreiben Sie eine Funktion

void change(Data old, Data newdata);

welche ein Element old aus der Liste nimmt, es durch die Werte von newdata ersetzt und dieses Element dann wieder an geeigneter Stelle einfügt, sodass die Liste nach diesem Aufruf wieder sortiert ist (normalerweise betrifft das Enfernen und Wiedereinfügen nur denkey).
Erstellen Sie für alle Funktionen passende Testfälle und fertigen Sie ggf. Skizzen an.

5. Sortiertes Einfügen

Erstellen Sie ein Java-Programm, welches Namen von der Standardeingabe liest und sortiert in eine einfach verkettete Liste einträgt. Bei EOF wird dann die Liste auf der Standardausgabe ausgegeben.

Machen Sie zwei Varianten:

1. Iteratives sortiertes Einfügen und iteratves Ausgeben
2. Rekursives sortieres Einfügen und rekursives Ausgeben

Labels: Aufgabe, Java, PR2