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 13.1 (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. Hier ist 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, mit der man in der Liste einen Knoten mit einem bestimmten Wert suchen kann.

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 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.