13.3    Kontrollfragen und Aufgaben

1. Was sind verkettete Listen?

2. Welchen Vorteil haben verkettete Listen gegenüber Arrays?

3. Was sind doppelt verkettete Listen?

4. Welcher Fehler wurde hier beim Löschen des Knotens gemacht?

   01  void loescheKnoten( int val ) {
   02    KnotenPtr_t hilfZeiger1;
   03    KnotenPtr_t hilfZeiger2;
   04    if( anfang != NULL ) {
   05      if( anfang->wert == val ) {
   06        hilfZeiger1 = anfang->next;
   07        free(anfang);
   08        anfang = hilfZeiger1;
   09      }
   10      else {
   11        hilfZeiger1 = anfang;
   12        while( hilfZeiger1->next != NULL ) {
   13          hilfZeiger2 = hilfZeiger1->next;
   14          if( hilfZeiger2->wert == val ) {
   15            hilfZeiger1 = hilfZeiger2->next;
   16            free(hilfZeiger2);
   17            break;
   18          }
   19          hilfZeiger1 = hilfZeiger2;
   20        }  // Ende while
   21      }  // Ende else
   22    }  // Ende if
   23  }

5. Ändern Sie die Funktion einfuegenKnoten() aus Listing verkettete_liste.c ab, damit die neuen Elemente in der Liste sortiert eingefügt werden. Verhindern Sie außerdem, dass doppelte Einträge eingefügt werden. Ein Tipp, wie Sie vorgehen können:

   • Überprüfen Sie, ob überhaupt etwas in der Liste vorhanden ist, und fügen Sie das erste Element ein.

   • Jetzt können Sie die einzelnen Knoten durchlaufen und prüfen, ob der aktuelle Wert größer oder kleiner ist als der neu hinzuzufügende Wert (die Reihenfolge entscheiden Sie selbst). Haben Sie den passenden Knoten gefunden, müssen Sie das Element …

   • … am Ende einfügen (wenn NULL erreicht ist).

   • … auf doppelte Werte prüfen und nicht einfügen.

   • … am Anfang einfügen (wenn nicht weiter als bis zum Anfang iteriert wurde).

   • … irgendwo dazwischen einfügen.

6. Erweitern Sie das Programm verkettete_liste.c um eine Funktion zum Suchen eines Knotens mit einem bestimmten Wert in der Liste.

Bis jetzt waren Ihre Daten immer flüchtig und spätestens verloren, wenn Sie das Programm beendet haben. Im nächsten Kapitel werden wir Ihnen deshalb zum Schluss noch erklären, wie Sie flüchtige Daten sichern können. Es geht also um das Arbeiten mit Dateien. Nur mit diesen können Sie Ihre Strukturen und Listen auch auf einem Datenträger ablegen.