Mittwoch, 15. April 2009

 

Verkettete Listen mit Java - Verschiedenes

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 gefprderten 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 den key).

Erstellen Sie für alle Funktionen passende Testfälle und fertigen Sie ggf. Skizzen an.

Labels: , ,


Kommentare:

Kommentar veröffentlichen

Abonnieren Kommentare zum Post [Atom]





<< Startseite

This page is powered by Blogger. Isn't yours?

Abonnieren Posts [Atom]