Lösungen der Übungsaufgaben

B.12 Antworten und Lösungen zu Kapitel 13

Verkettete Listen sind dynamische Datenstrukturen, in denen eine unbestimmte Anzahl von gleichen Speicherobjekten gespeichert werden kann. Diese Speicherobjekte sind oft Zeiger oder Strukturen, können aber auch primitive Datentypen sein. Die einzelnen Elemente in verketten Listen werden auch als Knoten bezeichnet. Die einzelnen Knoten werden mithilfe von Zeigern als Komponenten von demselben Typ auf das jeweils nächste Speicherobjekt realisiert. Ein solcher Zeiger wird innerhalb eines Knotens definiert. Dadurch wird sichergestellt, dass jedes Speicherobjekt zumindest einen Zeiger auf seinen Nachfolger enthält. So können einzelne Elemente ein- oder angehängt werden. Wie das Einfügen und Aushängen realisiert und ob eine einfach verkettete oder doppelt verkettete Liste verwendet wird, hängt vom Anwendungsfall ab.
Verkettete Listen müssen im Gegensatz zu Arrays nicht nacheinander im Speicher abgelegt werden. Der Vorteil daran ist, dass das Löschen und Einfügen von Elementen in einer konstanten Zeit realisiert werden kann, wenn das Einfügen von Elementen immer am Anfang oder am Ende einer Liste stattfindet. Im Gegensatz zu Arrays muss bei einer Liste hierzu nur der Verweis auf die Adresse des Anfangs oder des Endes geändert werden. Bei Arrays müssten hier unter Umständen ganze Blöcke verschoben werden, wenn Sie nach einiger Zeit keine unbelegten Plätze im Array haben möchten. Allerdings sind der Aufwand und auch der Speicherverbrauch für ein Element in der Liste etwas größer. Zum einen werden für ein Element immer auch zusätzliche Verweise auf die einzelnen Nachfolger gespeichert, zum anderen muss die richtige Verkettung programmtechnisch sichergestellt werden. Der Nachteil von verketteten Listen ist aber auch, dass die Suche nach Daten zum Löschen oder Einfügen bei längeren Listen erhebliche Zeit beanspruchen kann, weil die Liste immer vom Anfang an durchlaufen (iteriert) werden muss. Dies ist allerdings auch bei unsortierten Arrays der Fall. Auch das Einfügen des ersten und letzten Elements muss gesondert behandelt werden, was unter Umständen zu Fehlern führen kann. Ob Sie also Arrays oder verkettete Listen verwenden, hängt somit vom Anwendungsfall ab.
Bei den doppelt verketteten Listen besitzt jedes einzelne Element (jeder Knoten) neben einem Zeiger auf den Nachfolger auch einen Zeiger auf den Vorgänger. Der Vorteil ist hier, dass Sie beim Suchen von Elementen die Liste von Anfang bis zum Ende, aber auch umgekehrt vom Ende bis zum Anfang durchlaufen können.
Hier handelt es sich um einen oft gemachten Fehler in Zeile (15). Dort wurde der gefundene Knoten nicht richtig »ausgehängt«. hilfsZeiger1 zeigt hier auf die Adresse des nächsten Elements von hilfsZeiger2. Wenn Sie den Speicher mit free() freigeben, ist die verkettete Liste ab der Position hilfsZeiger2 zerrissen, und auf die dahinterliegenden Daten kann nicht mehr zugegriffen werden. Bildlich können Sie sich das bis zur Zeile nach free() wie in Abbildung B.1 vorstellen.

Abbildung B.1 Die verkettete Liste ist nicht mehr intakt. Der next-Zeiger nach dem ersten Knoten verweist auf einen nicht mehr gültigen Speicherbereich, der mit free() freigegeben wurde.

Hierzu der Codeausschnitt, jetzt mit fett hervorgehobener Korrektur:
```
10        ...
11        hilfZeiger1 = anfang;
12        while( hilfZeiger1->next != NULL ) {
13          hilfZeiger2 = hilfZeiger1->next;
14          if( hilfZeiger2->wert == val ) {
15            hilfZeiger1->next = hilfZeiger2->next;
16            free(hilfZeiger2);
17            break;
18          }
19          hilfZeiger1 = hilfZeiger2;
20        }
21        ...
```

Zugegeben, diese Aufgabe war nicht einfach. Das Einfügen am Anfang und am Ende der Liste dürfte für Sie noch einfach gewesen sein. Schwieriger war wahrscheinlich das Einfügen von Elementen in der Mitte der Liste. Sie sehen nachfolgend eine Musterlösung mit der neuen Funktion einfuegenKnoten(), die Elemente sortiert in die Liste einfügt.

00  // kap013/loesung001.c
...
01  void einfuegenKnoten( KnotenPtr_t neu ) {
02    KnotenPtr_t hilfZeiger;
03    KnotenPtr_t hilfZeiger2;
04    if( anfang == NULL ) {
05      anfang = neu;
06      neu->next = NULL;
07    }
08    else {
09      hilfZeiger = anfang;
10      while(hilfZeiger != NULL &&
           (neu->wert > hilfZeiger->wert) )  {
11        hilfZeiger = hilfZeiger->next;
12      }
13      // am Ende einfügen - Ende-Zeiger wäre sinnvoller
14      if(hilfZeiger == NULL) {
15        hilfZeiger = anfang;
16        while(hilfZeiger->next != NULL) {
17          hilfZeiger=hilfZeiger->next;
18        }
19        hilfZeiger->next = neu;
20        neu->next  = NULL;
21      }
22      // auf doppelte Werte hin prüfen
23      else if( neu->wert == hilfZeiger->wert ) {
24        printf("Wert ist bereits vorhanden!!\n");
25      }
26      // am Anfang einfügen
27      else if( hilfZeiger == anfang ) {
28        neu->next = hilfZeiger;
29        anfang    = neu;
30      }
31      // irgendwo einfügen
32      else {
33        hilfZeiger2 = anfang;
34        while(hilfZeiger2->next != hilfZeiger) {
35          hilfZeiger2=hilfZeiger2->next;
36        }
37        neu->next = hilfZeiger2->next;
38        hilfZeiger2->next = neu;
39      }
40    }
41  }

Diese Aufgabe dürfte leichter zu lösen gewesen sein als die letzte Aufgabe. Im Grunde ähnelt die Funktion, die Sie hier erstellen müssen, der Funktion knotenAuflisten(), in der alle Elemente in der Liste ausgegeben werden. Nur müssen Sie hier die einzelnen Elemente überprüfen und dann gegebenenfalls einen Hinweis ausgeben, ob das Element in der Liste vorhanden ist oder nicht. Es folgt eine Musterlösung, inklusive der main()-Funktion, die die Funktion sucheKnoten() testet:

// kap013/loesung002.c
...
void sucheKnoten( int val ) {
  KnotenPtr_t hilfZeiger = anfang;
  while( hilfZeiger != NULL ) {
    if(hilfZeiger->wert == val ) {
      printf("Wert %d gefunden\n", hilfZeiger->wert);
      return;
    }
    hilfZeiger = hilfZeiger->next;
  }
  printf("%d ist in der Liste nicht vorhanden\n", val);
}

int main(void) {
  int wahl = 0, val = 0;
  do {
    printf(" -1- Neues Element hinzufuegen\n");
    printf(" -2- Element loeschen\n");
    printf(" -3- Alle Elemente auflisten\n");
    printf(" -4- Element suchen\n");
    printf(" -5- Programmende\n");
    printf(" Ihre Auswahl : ");
    if( scanf("%d", &wahl) != 1 ) {
      printf("Fehlerhafte Auswahl\n");
      wahl = 0;
      dump_buffer(stdin);
    } 
    switch( wahl ) {
      case 1 : neuerKnoten(); break;
...
      case 4 : if( anfang == NULL ) {
                 printf("Liste ist leer!\n");
               }
               else {
                 printf("Gesuchter Wert : ");
                 if( scanf("%d", &val) != 1 ) {
                   printf("Fehler bei der Eingabe\n");
                 }
                 else {
                   sucheKnoten( val );
                 }
               }
               break;
    }
  }
  while( wahl != 5 );
  return EXIT_SUCCESS;
}