Doubly Linked Lists

Aufgabe

Eine doppelt verkettete Liste (engl. doubly linked list) besteht aus Knoten, die jeweils zwei Zeiger enthalten:
einen Zeiger auf den nächsten Knoten sowie einen Zeiger auf den vorherigen Knoten.
Dadurch kann man sowohl vorwärts als auch rückwärts durch die Liste laufen.

In dieser Aufgabe sollen Sie ein bereitgestelltes Codegerüst vervollständigen, das:

1. eine doppelt verkettete Liste implementiert,
2. Elemente am Ende der Liste einfügt,
3. Elemente in der Liste sucht,
4. Elemente aus der Liste löscht,
5. die Liste vorwärts und rückwärts ausgibt,
6. die gesamte Liste freigibt,
7. und ein Kommandozeilen-Menü bereitstellt, durch das der Benutzer diese Operationen auswählen kann.

Ziel dieser Aufgabe ist es, Zeigeroperationen, dynamische Speicherverwaltung (malloc, free) und Datenstrukturdesign zu üben.

Aufgabenmaterial

Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen.

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(void)
{
    // Menü nur einmal ausgeben
    printf(
        "(1) Zahl einfügen\n"
        "(2) Liste vorwärts ausgeben\n"
        "(3) Liste rückwärts ausgeben\n"
        "(4) Wert suchen\n"
        "(5) Wert löschen\n"
        "(6) gesamte Liste löschen\n"
        "(0) Programm beenden\n"
    );

    while (true)
    {
        // Benutzerauswahl abfragen
        int choice = get_int("> ");

        // Operationen auswerten
        switch (choice)
        {
            case 1:
                // Zahl einfügen
                break;
            case 2:
                // Liste vorwärts ausgeben
                break;
            case 3:
                // Liste rückwärts ausgeben
                break;
            case 4:
                // Wert suchen
                break;
            case 5:
                // Wert löschen
                break;
            case 6:
                // gesamte Liste löschen
                break;
            case 0:
                // gesamte Liste löschen
                printf("Programm wird beendet.\n");
                return 0;
            default:
                printf("Ungültige Auswahl. Bitte erneut versuchen.\n");
        }
    }
}

Anforderungen

Sie sollen ein vollständiges C-Programm selbst entwickeln, das die folgenden Punkte erfüllt.

1. Strukturdefinition

Definieren Sie eine Struktur node, die wie folgt aufgebaut ist:

typedef struct node
{
    int value;
    struct node *next;
    struct node *prev;
} node;

2. Verwaltung der Liste

Im Programm sollen Sie folgende Zeiger nutzen:

node *head = NULL; // zeigt auf den ersten Knoten  
node *tail = NULL; // zeigt auf den letzten Knoten

Der Benutzer soll über ein Menü verschiedene Operationen auswählen können:

(1) Zahl einfügen  
(2) Liste vorwärts ausgeben  
(3) Liste rückwärts ausgeben  
(4) Wert suchen  
(5) Wert löschen  
(6) gesamte Liste löschen  
(0) Programm beenden

3. Einfügen eines Knotens am Ende

Bevor ein neuer Knoten eingefügt wird, soll der Nutzer nach dem gewünschten Wert gefragt werden. Dieser Wert wird anschließend an die Funktion insert_end(int value) übergeben, welche einen neuen Knoten am Ende einfügt.

Beim Einfügen eines neuen Wertes müssen Sie:

• Unterscheiden ob die Liste (nicht) leer ist.
• Speicher für einen neuen Knoten mit malloc() anfordern
• value, prev und next korrekt setzen

void insert_end(int value);

4. Suchen eines Wertes

Bevor die Suchfunktion aufgerufen wird, soll der Nutzer nach dem Wert gefragt werden, den er in der Liste finden möchte. Der eingegebene Wert wird anschließend an die Funktion search(int value) übergeben, die überprüft, ob sich dieser Wert in der Liste befindet.

Beim Suchen eines Wertes müssen Sie die Liste von head aus durchlaufen und eine entsprechende Ausgabe erzeugen. Die Funktion search(int value) selbst soll nichts ausgeben. Sie gibt nur true oder false zurück. Die Ausgabe werfolt anschließedn in der aufrufenden Funktion, abhängig vom Rückgabewert.

Falls der gesuchte Wert enthalten ist, soll folgendes ausgegeben werden:

Wert X wurde gefunden.

Falls der Wert nicht gefunden wurde:

Wert X nicht in der Liste.

Hinweis: Schreiben Sie für die Suchoperation eine eigene Funktion search() und behandeln sie die Ausgabe in der Aufrufenden Funktion.

bool search(int value);

5. Löschen eines Knotens

Auch hier wird der Nutzer zuerst gefragt, welcher Wert gelöscht werden soll. Der eingegebenen Wert wird anschließend an die Funktion delete_value(int value) übergeben, die versucht, den entsprechenden Knoten zu finden und zu löschen.

Beim Löschen eines Knotens müssen Sie folgende Fälle korrekt behandeln:

1. Knoten ist der einzige Knoten der Liste
2. Knoten ist der erste Knoten
3. Knoten ist der letzte Knoten
4. Knoten befindet sich in der Mitte
5. Knoten befindet sich nicht in der Liste → Liste bleibt unverändert

Die Funktion gibt true zurück, wenn ein Knoten gelöscht wurde. false soll zurückgegeben werden, webb der wert nicht in der Liste enthalten ist.

bool delete_value(int value);

6. Ausgeben der Liste

Das Programm soll sowohl das vorwärts als auch das rückwärts ausgeben unterstützen. Je nach Auswahl des Nutzers wird entweder print_forward() oder print_backward() aufgerufen.

Vorwärts

Die Funktion print_forward() durchläuft die Liste beginnend beim head und gibt die Werte in dieser Reihenfolge aus.

Beispiel:

4 7 10

void print_forward(void);

Rückwärts

Die print_backward() Funktion startet beim tail und gibt die Werte entsprechend rückwärts aus.

Beispiel:

10 7 4

void print_backward(void);

7. Löschen der gesamten Liste

Wenn der Nutzer die Option wählt die gesamte Liste zu löschen, soll die Funktion clear_list() aufgerufen werden. In dieser Funktion wird die komplette Liste gelöscht, indem alle Knoten nacheinander freigegeben werden. Dabei muss darauf geachtet werden, dass keine Memory Leaks entstehen.

void clear_list(void);

8. Beispielinteraktion

Eine mögliche Interaktion könnte wie folgt aussehen:

1
Zahl: 5

1
Zahl: 9

2
Vorwärts: 5 9

3
Rückwärts: 9 5

4
Wert suchen: 9
Gefunden.

5
Wert löschen: 5
5 gelöscht.

2
Vorwärts: 9