Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
Vorwort des Gutachters
1 Einstieg in C
2 Das erste Programm
3 Grundlagen
4 Formatierte Ein-/Ausgabe mit »scanf()« und »printf()«
5 Basisdatentypen
6 Operatoren
7 Typumwandlung
8 Kontrollstrukturen
9 Funktionen
10 Präprozessor-Direktiven
11 Arrays
12 Zeiger (Pointer)
13 Kommandozeilenargumente
14 Dynamische Speicherverwaltung
15 Strukturen
16 Ein-/Ausgabe-Funktionen
17 Attribute von Dateien und das Arbeiten mit Verzeichnissen (nicht ANSI C)
18 Arbeiten mit variabel langen Argumentlisten – <stdarg.h>
19 Zeitroutinen
20 Weitere Headerdateien und ihre Funktionen (ANSI C)
21 Dynamische Datenstrukturen
22 Algorithmen
23 CGI mit C
24 MySQL und C
25 Netzwerkprogrammierung und Cross–Plattform-Entwicklung
26 Paralleles Rechnen
27 Sicheres Programmieren
28 Wie geht’s jetzt weiter?
A Operatoren
B Die C-Standard-Bibliothek
Stichwort

Buch bestellen
Ihre Meinung?

Spacer
<< zurück
C von A bis Z von Jürgen Wolf
Das umfassende Handbuch
Buch: C von A bis Z

C von A bis Z
3., aktualisierte und erweiterte Auflage, geb., mit CD und Referenzkarte
1.190 S., 39,90 Euro
Rheinwerk Computing
ISBN 978-3-8362-1411-7
Pfeil 21 Dynamische Datenstrukturen
Pfeil 21.1 Lineare Listen (einfach verkettete Listen)
Pfeil 21.1.1 Erstes Element der Liste löschen
Pfeil 21.1.2 Ein beliebiges Element in der Liste löschen
Pfeil 21.1.3 Elemente der Liste ausgeben
Pfeil 21.1.4 Eine vollständige Liste auf einmal löschen
Pfeil 21.1.5 Element in die Liste einfügen
Pfeil 21.2 Doppelt verkettete Listen
Pfeil 21.3 Stacks nach dem LIFO-(Last-in-First-out-)Prinzip
Pfeil 21.4 Queues nach dem FIFO-Prinzip
Pfeil 21.5 Dynamisches Array mit flexiblen Elementen

In diesem Kapitel werden die Themen Strukturen, Zeiger und dynamische Speicherverwaltung vermischt. Was auf den ersten Blick ein wenig kompliziert aussieht – und es auch manches Mal ist –, erweist sich, sobald Sie es beherrschen, als eine enorme Erleichterung.

21 Dynamische Datenstrukturen


Rheinwerk Computing - Zum Seitenanfang

21.1 Lineare Listen (einfach verkettete Listen) Zur nächsten ÜberschriftZur vorigen Überschrift

In Kapitel 14, »Dynamische Speicherverwaltung«, habe ich den Umgang mit dynamisch zugeordnetem Speicher näher erläutert. »Dynamisch« heißt, dass zur Laufzeit des Programms Speicher vom Heap alloziert wird.

Der Hauptsinn von dynamischen Datenstrukturen besteht darin, dass eine Struktur mit einem Zeiger vom Typ der Struktur selbst definiert wird. Gehen wir einmal von folgender Struktur einer Angestelltenliste aus:

struct datum {
   int tag;
   int monat;
   int jahr;
};

struct angestellt{
   char name[20];
   char vorname[20];
   struct datum alter;
   struct datum eingest;
   long gehalt;
};

Eine solche Struktur wurde ja bereits behandelt und stellt somit nichts Neues mehr dar. Jetzt soll diese Struktur erweitert werden:

struct datum {
   int tag;
   int monat;
   int jahr;
};

struct angestellt {
   char name[20];
   char vorname[20];
   struct datum alter;
   struct datum eingest;
   long gehalt;
   struct angestellt *next;
};

Folgende Zeile dürfte Ihnen am Ende der Struktur angestellt aufgefallen sein:

struct angestellt *next;

Das Besondere an diesem Zeiger ist, dass er ein Zeiger auf eine Adresse ist, die denselben Typ wie die Struktur selbst (struct angestellt) beinhaltet. Mit diesem Zeiger können somit einzelne Strukturen miteinander verkettet werden. Der next-Zeiger verweist immer auf die Adresse des nächsten Elements, das wiederum eine Struktur mit denselben Elementen und ebenfalls wieder einen weiteren Zeiger beinhaltet. Sie können dabei eine gewisse Ähnlichkeit mit den Arrays von Strukturen erkennen – wobei hier das nächste Element mithilfe eines Zeigers statt mit dem Indizierungsoperator angesprochen wird und Sie zuvor noch für das nächste Element einen Speicherplatz reservieren müssen. Außerdem wird noch ein Ende für die Kette benötigt. Dazu verwenden Sie einfach den next-Zeiger und übergeben diesem einen NULL-Zeiger:

struct angestellt *next = NULL;

Somit würde die Struktur angestellt aussehen wie in Abbildung 21.1 dargestellt.

Abbildung 21.1 Eine Struktur für eine einfach verkettete Liste

Nochmals: Der Zeiger struct angestellt *next zeigt nicht auf sich selbst, sondern auf eine Adresse des nächsten Elements vom selben Typ. (Zur Erinnerung: Zeiger dereferenzieren eine Adresse und keinen Wert.) In diesem Beispiel wird zunächst auf NULL verwiesen, da noch keine Daten eingegeben wurden.

In Kapitel 15, »Strukturen«, habe ich bereits gezeigt, wie Sie auf die einzelnen Elemente einer Struktur zugreifen können, zum Beispiel:

struct angestellt a;

Anschließend wird mit a.name, a.vorname oder a.alter usw. auf die einzelnen Strukturelemente zugegriffen. Ähnlich funktioniert dies, wenn nicht mit einer Strukturvariablen, sondern mit Zeigern auf eine Struktur gearbeitet wird:

struct angestellt *structzeiger;

Der Zugriff auf die einzelnen Elemente der Struktur sieht dann so aus:

(*structzeiger).name
(*structzeiger).vorname
(*structzeiger).alter

Diese Schreibweise ist allerdings nicht allzu lesefreundlich und birgt die Gefahr, Fehler zu machen. Zum Glück haben die Compiler-Bauer einen extra Operator geschaffen, der eine Kombination aus Dereferenzierung und Elementzugriff ist:

->

Da der ->-Operator die Form eines Zeigers hat, ist dieser auch noch einfacher zu lesen. Somit ergibt sich folgende Schreibweise für den Zugriff auf die einzelnen Strukturelemente:

structzeiger->name
structzeiger->vorname
structzeiger->alter

Theoretisch könnten Sie jetzt einen Datensatz nach dem anderen anhängen. Aber irgendwann wollen Sie den Datensatz auch wieder ausgeben oder sortieren. Deshalb benötigt die Kette einen Anfang, d. h. eine Anfangsadresse, mit der die Liste beginnt. Also ist ein weiterer Zeiger der Struktur angestellt erforderlich, in dem sich die Anfangsadresse befindet:

struct angestellt *anfang;

Da zu Beginn des Programms noch kein Datensatz eingegeben wurde, verweist dieser Zeiger zunächst auch auf NULL. Bisher sieht die Struktur demnach so aus:

struct datum {
   int tag;
   int monat;
   int jahr;
};

struct angestellt {
    char name[20];
    char vorname[20];
    struct datum alter;
    struct datum eingest;
    long gehalt;
    struct angestellt *next;
};

struct angestellt *next   = NULL;
struct angestellt *anfang = NULL;

Jetzt folgt eine Funktion, mit der Sie Adresssätze aneinanderhängen können. Die Funktion anhaengen() ist sehr ausführlich kommentiert:

/* linear_list1.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 20

struct datum {
   int tag;
   int monat;
   int jahr;
};

struct angestellt {
   char name[MAX];
   char vorname[MAX];
   struct datum alter;
   struct datum eingest;
   long gehalt;
   struct angestellt *next;
};

struct angestellt *next = NULL;
struct angestellt *anfang=NULL;

/* Wir hängen einen Datensatz an oder geben einen neuen ein:
 * n=name,v=vornam,at=alter.tage,am=alter.monat,aj=alter.jahr
 * eint=eigestellt tag,einm=eingestellt monat,einj=eingest.
 * Jahr  g=gehalt */

void anhaengen(char *n, char *v, int at, int am, int aj,
                int eint, int einm, int einj, long g) {
   /* Zeiger zum Zugriff auf die einzelnen Elemente
    * der Struktur*/
   struct angestellt *zeiger;

  /* Wir fragen ab, ob es schon ein Element in der Liste
   * gibt. Wir suchen das Element, auf das unser Zeiger
   *  *anfang zeigt. Falls *anfang immer noch auf NULL zeigt,
   *  bekommt *anfang die Adresse unseres 1. Elements und ist
   *  somit der Kopf (Anfang) unserer Liste. */
   if(anfang == NULL) {
      /* Wir reservieren Speicherplatz für unsere Struktur
       * für das erste Element der Liste. */
      if((anfang =
       malloc(sizeof(struct angestellt))) == NULL) {
         fprintf(stderr, "Kein Speicherplatz vorhanden "
                         "fuer anfang\n");
         return;
      }
      strcpy(anfang->name, n);
      strcpy(anfang->vorname, v);
      anfang->alter.tag = at;
      anfang->alter.monat = am;
      anfang->alter.jahr = aj;
      anfang->eingest.tag = eint;
      anfang->eingest.monat = einm;
      anfang->eingest.jahr = einj;
      anfang->gehalt = g;
      /* Somit haben wir unseren Anfang der Liste. Von nun an
       * zeigt der Zeiger anfang immer auf das Element vor ihm.
       * Da dies aber jetzt das 1. Element der Liste war, zeigt
       * der Zeiger anfang auf den Zeiger next. next zeigt am
       * Ende immer wieder  NULL. */
      anfang->next=NULL;
   }
   /* Es scheint schon mindestens ein Element in der Liste
    * vorhanden zu sein, da der Anfang nicht == NULL ist.
    * Jetzt suchen wir so lange nach dem nächsten Element,
    * bis der *next-Zeiger auf NULL zeigt. Somit haben wir
    * das Ende der Liste gefunden und können einen neuen
    * Datensatz anhängen. */
   else {
      zeiger=anfang; /* Wir zeigen auf das 1. Element. */
      while(zeiger->next != NULL)
         zeiger=zeiger->next;
      /* Wir reservieren einen Speicherplatz für das letzte
       * Element der Liste und hängen es an. */
      if((zeiger->next =
       malloc(sizeof(struct angestellt))) == NULL) {
          fprintf(stderr,"Kein Speicherplatz fuer das "
                         "letzte Element\n");
          return;
      }
      zeiger=zeiger->next; /* zeiger auf neuen Speicherplatz */
      strcpy(zeiger->name,n);
      strcpy(zeiger->vorname,v);
      zeiger->alter.tag=at;
      zeiger->alter.monat=am;
      zeiger->alter.jahr=aj;
      zeiger->eingest.tag=eint;
      zeiger->eingest.monat=einm;
      zeiger->eingest.jahr=einj;
      /* Wir terminieren wieder unsere Datenstruktur. */
      zeiger->gehalt=g;
      zeiger->next=NULL;
   }
}

/* Funktion zur Eingabe der Daten */
void eingabe(void) {
   char nam[MAX],vorn[MAX];
   int atag,amon,ajahr,eintag,einmon,einjahr;
   long gehalt;
   printf("Name........................: ");
   fgets(nam, MAX, stdin);
   printf("Vorname.....................: ");
   fgets(vorn, MAX, stdin);
   printf("Alter...........(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&atag,&amon,&ajahr);
   printf("Eingestellt am..(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&eintag,&einmon,&einjahr);
   printf("Monatsgehalt................: ");
   scanf("%ld",&gehalt);
   getchar();
   /* eingegebenen Datensatz hinten anhängen */
   anhaengen(nam, vorn, atag, amon, ajahr, eintag,
    einmon, einjahr, gehalt);
}

int main(void) {
   while(1)
      eingabe();
   return EXIT_SUCCESS;
}

Zuerst wird die Funktion eingabe() zur Eingabe der einzelnen Daten aufgerufen. Diese eingegebenen Variablen werden anschließend als Argument an die Parameter der Funktion anhaengen() übergeben. Bei der Funktion ist die Zeile

zeiger=zeiger->next;

sehr wichtig. Es wird davon ausgegangen, dass bereits ein Element eingegeben wurde und das nächste somit das zweite Element in der Liste ist. Wenn jetzt zeiger nicht auf die Adresse von zeiger->next verweisen würde, wäre dies zwar kein syntaktischer Fehler, aber es würde immer wieder die erste Struktur überschrieben werden.

Mit der folgenden Zeile wird es überhaupt erst möglich, dass die while-Schleife funktioniert, um wieder neue Daten einzugeben:

zeiger->next=NULL;

Sonst würde die while-Schleife mit der Abfrage, ob zeiger auf next zeigt, niemals korrekt abbrechen, da niemals auf NULL verwiesen würde:

while(zeiger->next != NULL)
   zeiger=zeiger->next;

Dies soll jetzt bildlich dargestellt werden. Es wurden bereits zwei Personen eingegeben. Somit sind folglich zwei Datensätze vorhanden (siehe Abbildung 21.2).

Abbildung 21.2 Eine verkettete Liste mit zwei Datensätzen

Hier erkennen Sie auch, dass der Strukturzeiger anfang immer auf das erste Element der Liste zeigt. Der Strukturzeiger next im letzten Element zeigt immer auf NULL und zeigt somit immer das Ende der Kette an.

Als Nächstes soll eine Funktion erstellt werden, mit der Sie einzelne Elemente in der Liste löschen können. Der Speicherplatz wird dabei wie üblich mit der Funktion free() freigegeben.


Rheinwerk Computing - Zum Seitenanfang

21.1.1 Erstes Element der Liste löschen Zur nächsten ÜberschriftZur vorigen Überschrift

Falls das erste Element in der Liste gelöscht werden soll, ist dies nicht allzu schwierig. Dabei muss nur ein Zeiger vom Typ struct angestellt auf die Adresse von anfang->next zeigen (zweites Element). Anschließend kann mit free(anfang) der Speicher freigegeben werden. Zum Schluss bekommt der Zeiger anfang die Adresse des Zeigers anfang->next. So werden Sie in der Praxis das erste Element in der Liste los:

/* Funktion zum Löschen */
void loesche(char *wen) {
   struct angestellt *zeiger;

   /* Ist überhaupt ein Element vorhanden? */
   if(anfang != NULL) {
      /* Ist unser 1. Element das von uns gesuchte (wen[])? */
      if(strcmp(anfang->name,wen) == 0) {
         zeiger=anfang->next;

Es sei jetzt der Fall gegeben, dass das erste Element in der Liste das momentan gesuchte ist, das gelöscht werden soll. Somit ergibt sich im Augenblick folgender Zustand:

Abbildung 21.3 Ein Zeiger auf das nächste Element vom Anfang

Jetzt folgt der Aufruf:

free(anfang);

Damit wird der Speicherplatz freigegeben, auf den der Zeiger anfang verweist:

Abbildung 21.4 Speicherplatz des ersten Elements wird freigegeben.

Wenn Sie es jetzt hierbei belassen, sind die restlichen Daten der Kette wohl verloren, da es keinen Anfang mehr gibt. Es muss noch die Adresse des Zeigers zeiger an den Zeiger anfang übergeben werden:

anfang=zeiger;

Damit ergibt sich das folgende finale Bild:

Abbildung 21.5 Der Zeiger des ersten Elements bekommt eine neue Adresse.


Rheinwerk Computing - Zum Seitenanfang

21.1.2 Ein beliebiges Element in der Liste löschen Zur nächsten ÜberschriftZur vorigen Überschrift

Das erste Element in der Liste zu löschen war nicht schwer. Anders sieht es aus, wenn ein Element irgendwo in der Liste entfernt werden muss. Dafür wird ein Zeiger mehr benötigt: einer, der auf die Adresse verweist, die sich vor dem zu löschenden Element befindet, und ein weiterer Zeiger, der auf das nächste Element nach dem zu löschenden Element zeigt. Hier folgt eine kurze Zusammenfassung der bisherigen Funktion loesche():

/* Funktion zum Löschen */
void loesche(char *wen) {
   struct angestellt *zeiger, *zeiger1;

   /* Ist überhaupt ein Element vorhanden? */
   if(anfang != NULL) {
      /* Ist unser 1. Element das von uns gesuchte (wen[])? */
      if(strcmp(anfang->name,wen) == 0) {
         zeiger=anfang->next;
         free(anfang);
         anfang=zeiger;
      }
      else {
         /* Es ist nicht das 1. Element zu löschen. Wir suchen in
          * der weiteren Kette, ob das zu löschende Element vor-
          * handen ist. */
         zeiger=anfang;

Daraus ergibt sich momentan folgende »Grundstellung«:

Abbildung 21.6 Auf der Suche nach dem zu löschenden Element

Es wird der Einfachheit halber davon ausgegangen, dass das gesuchte Element das zweite in der Liste sei (siehe Abbildung 21.6). Das Stückchen Quellcode, das nach einem bestimmten Namen in der Liste sucht, sieht folgendermaßen aus:

         while(zeiger->next != NULL) {
            zeiger1=zeiger->next;

            /* Ist die Adresse von zeiger1 der gesuchte Name? */
            if(strcmp(zeiger1->name,wen) == 0) {
               /* Falls ja, dann ... */

Bildlich ergibt sich daraus folgender Stand:

Abbildung 21.7 Element zum Löschen gefunden

Die Adresse, auf die zeiger1 zeigt, ist das gesuchte Element in der Liste, das gelöscht werden soll. Bevor Sie jetzt den Speicherplatz freigeben können, benötigt das Element in der Liste, auf das zeiger verweist, eine Adresse für den next-Zeiger, damit die Kette nicht abreißt:

               zeiger->next=zeiger1->next;
               free(zeiger1);
               break;
            }
            zeiger=zeiger1;
         }  /* Ende while */
      }     /* Ende else */
   }        /* Ende if(anfang != NULL) */
   else
      printf("Es sind keine Daten zum Löschen vorhanden!!!\n");
}

Sehen wir uns dies etwas genauer an:

zeiger->next=zeiger1->next;

In Worten: Der Zeiger zeiger, der auf die Adresse der nächsten (next) Datenstruktur zeigt (zum jetzigen Zeitpunkt zeigt zeiger->next ja noch auf das zu löschende Element, auf das der Zeiger zeiger1 zeigt), bekommt jetzt die Adresse, auf die der next-Zeiger des zu löschenden Elements (zeiger1) verweist. Anhand einer Grafik ist das einfacher zu verstehen:

Abbildung 21.8 Das zu löschende Element wird ausgehängt.

So wird das zu löschende Element ausgehängt. Jetzt kann der Speicherplatz freigegeben werden:

free(zeiger1);

Somit ergibt sich folgendes Bild:

Abbildung 21.9 Der Speicherplatz des zu löschenden Elements wurde freigegeben.


Rheinwerk Computing - Zum Seitenanfang

21.1.3 Elemente der Liste ausgeben Zur nächsten ÜberschriftZur vorigen Überschrift

Die Funktion zur Ausgabe der einzelnen Elemente in der Liste lässt sich recht einfach erstellen. Zuerst übergeben Sie einem Zeiger die Anfangsadresse der Liste und durchlaufen mit

while(zeiger != NULL)

die Liste so lange, bis der Zeiger zeiger auf NULL verweist – was das Ende der Liste darstellt. Hier sehen Sie die komplette Funktion zur Ausgabe der verketteten Liste:

void ausgabe(void) {
   struct angestellt *zeiger = anfang;

   printf("||====================================="
          "==================||\n");
   printf("|%10cName%10c |Geburtsdatum|"
   "Eingestellt|Gehalt|\n",' ',' ');
   printf("||====================================="
   "==================||\n");

   while(zeiger != NULL) {
      printf("|%12s,%-12s| %02d.%02d.%04d|"
             "%02d.%02d.%04d|%06ld|\n",
         zeiger->name,zeiger->vorname,zeiger->alter.tag,
         zeiger->alter.monat,zeiger->alter.jahr,
         zeiger->eingest.tag,zeiger->eingest.monat,
         zeiger->eingest.jahr,zeiger->gehalt);
         printf("|-----------------------------------"
                "----------------------|\n");
         zeiger=zeiger->next;
   }
}

Und jetzt sehen Sie das gesamte Programm inklusive der main()-Funktion:

/* linear_list2.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 20

struct datum{
   int tag;
   int monat;
   int jahr;
};

struct angestellt{
   char name[MAX];
   char vorname[MAX];
   struct datum alter;
   struct datum eingest;
   long gehalt;
   struct angestellt *next;
};

struct angestellt *next   = NULL;
struct angestellt *anfang = NULL;

/* Wir hängen einen Datensatz an oder geben einen neuen ein:
 * n=name,v=vornam,at=alter.tage,am=alter.monat,aj=alter.jahr
 * eint=eigestellt tag,einm=eingestellt monat,
 * einj=eingest. Jahr g=gehalt */

void anhaengen(char *n, char *v, int at, int am, int aj,
                int eint, int einm, int einj, long g) {
   /* Zeiger zum Zugriff auf die einzelnen Elemente
    * der Struktur */
   struct angestellt *zeiger;

  /* Wir fragen ab, ob es schon ein Element in der Liste
   * gibt. Wir suchen das Element, auf das unser Zeiger
   *  *anfang zeigt. Falls *anfang immer noch auf NULL zeigt,
   *  bekommt *anfang die Adresse unseres 1. Elements und ist
   *  somit der Kopf (Anfang) unserer Liste. */
   if(anfang == NULL) {
      /* Wir reservieren Speicherplatz für unsere Struktur
       * für das erste Element der Liste. */
      if((anfang =
       malloc(sizeof(struct angestellt))) == NULL) {
         fprintf(stderr, "Kein Speicherplatz vorhanden "
                         "für anfang\n");
         return;
      }
      strcpy(anfang->name, n);
      strcpy(anfang->vorname, v);
      anfang->alter.tag = at;
      anfang->alter.monat = am;
      anfang->alter.jahr = aj;
      anfang->eingest.tag = eint;
      anfang->eingest.monat = einm;
      anfang->eingest.jahr = einj;
      anfang->gehalt = g;
      /* Somit haben wir unseren Anfang der Liste. Von nun an
       * zeigt der Zeiger anfang immer auf das Element vor ihm.
       * Da dies aber jetzt das 1. Element der Liste war, zeigt
       * der Zeiger anfang auf den Zeiger next. next zeigt am
       * Ende immer wieder auf NULL. */
      anfang->next=NULL;
   }
   /* Es scheint schon mindestens ein Element in der Liste
    * vorhanden zu sein, da der Anfang nicht == NULL ist.
    * Jetzt suchen wir so lange nach dem nächsten Element,
    * bis der *next-Zeiger auf NULL zeigt. Somit haben wir
    * das Ende der Liste gefunden und können einen neuen
    * Datensatz anhängen. */
   else {
      zeiger=anfang; /* Wir zeigen auf das 1. Element. */
      while(zeiger->next != NULL)
         zeiger=zeiger->next;
      /* Wir reservieren einen Speicherplatz für das letzte
       * Element der Liste und hängen es an. */
      if((zeiger->next =
       malloc(sizeof(struct angestellt))) == NULL) {
          fprintf(stderr,"Kein Speicherplatz für das "
                         "letzte Element\n");
          return;
      }
      zeiger=zeiger->next; /* zeiger auf neuen Speicherplatz */
      strcpy(zeiger->name,n);
      strcpy(zeiger->vorname,v);
      zeiger->alter.tag=at;
      zeiger->alter.monat=am;
      zeiger->alter.jahr=aj;
      zeiger->eingest.tag=eint;
      zeiger->eingest.monat=einm;
      zeiger->eingest.jahr=einj;
      /* Wir terminieren wieder unsere Datenstruktur. */
      zeiger->gehalt=g;
      zeiger->next=NULL;
   }
}

/* Funktion zum Löschen einer Datei */
void loesche(char *wen) {
   struct angestellt *zeiger, *zeiger1;

   /* Ist überhaupt ein Element vorhanden? */
   if(anfang != NULL) {
      /* Ist unser 1. Element das von uns gesuchte (wen[])? */
      if(strcmp(anfang->name,wen) == 0) {
         zeiger=anfang->next;
         free(anfang);
         anfang=zeiger;
      }
      else {
         /* Es ist nicht das 1. Element zu löschen.
          * Wir suchen in der weiteren Kette, ob das zu
          * löschende Element vorhanden ist. */
         zeiger=anfang;
         while(zeiger->next != NULL) {
            zeiger1=zeiger->next;
            /* Ist die Adresse von zeiger1
             * der gesuchte Name? */
            if(strcmp(zeiger1->name,wen) == 0) {
               /* Falls ja, dann ... */
               zeiger->next=zeiger1->next;
               free(zeiger1);
               break;
            }
            zeiger=zeiger1;
         } /* Ende while */
      }    /* Ende else */
   }       /* Ende if(anfang != NULL) */
   else
      printf("Es sind keine Daten zum Loeschen vorhanden!!!\n");
}

/* Funktion zum Ausgeben der Dateien */
void ausgabe(void) {
   struct angestellt *zeiger = anfang;

   printf("||====================================="
          "==================||\n");
   printf("|%10cName%10c |Geburtsdatum|"
   "Eingestellt|Gehalt|\n",' ',' ');
   printf("||====================================="
   "==================||\n");

   while(zeiger != NULL) {
      printf("|%12s,%-12s| %02d.%02d.%04d|"
             "%02d.%02d.%04d|%06ld|\n",
         zeiger->name,zeiger->vorname,zeiger->alter.tag,
         zeiger->alter.monat,zeiger->alter.jahr,
         zeiger->eingest.tag,zeiger->eingest.monat,
         zeiger->eingest.jahr,zeiger->gehalt);
         printf("|-----------------------------------"
                "----------------------|\n");
         zeiger=zeiger->next;
   }
}

/* Funktion zur Eingabe der Daten */
void eingabe(void) {
   char nam[MAX],vorn[MAX];
   int atag,amon,ajahr,eintag,einmon,einjahr;
   long gehalt;
   char *ptr;
   printf("Name........................: ");
   fgets(nam, MAX, stdin);
   ptr = strrchr(nam, '\n');
   *ptr = '\0';
   printf("Vorname.....................: ");
   fgets(vorn, MAX, stdin);
   ptr = strrchr(vorn, '\n');
   *ptr = '\0';
   printf("Alter...........(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&atag,&amon,&ajahr);
   printf("Eingestellt am..(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&eintag,&einmon,&einjahr);
   printf("Monatsgehalt................: ");
   scanf("%ld",&gehalt);
   getchar();
   anhaengen(nam, vorn, atag, amon, ajahr, eintag,
      einmon, einjahr, gehalt);
}

int main(void) {
   int wahl;
   char dname[MAX];

   do {
      printf("\n1 : Eingabe\n");
      printf("2 : Ausgabe\n");
      printf("3 : Namen loeschen\n");
      printf("9 : Ende\n");
      printf("Ihre Wahl : ");
      scanf("%d",&wahl);
      getchar();
      switch(wahl) {
         case 1 : eingabe();
                  break;
         case 2 : ausgabe();
                  break;
         case 3 : printf("Der Name zum Loeschen: ");
                  fgets(dname, MAX, stdin);
                  loesche(strtok(dname, "\n"));
                  break;
         case 9 : break;
         default: printf("Falsche Eingabe!!!\n");
      }
   } while(wahl != 9);
   return EXIT_SUCCESS;
}

Dem Programm fehlen noch einige Optionen, und die Optik lässt auch sehr zu wünschen übrig. Auf den nächsten Seiten wird dieses Programm noch erheblich ausgebaut.


Rheinwerk Computing - Zum Seitenanfang

21.1.4 Eine vollständige Liste auf einmal löschen Zur nächsten ÜberschriftZur vorigen Überschrift

Auch die Funktion, mit der alle Elemente einer Liste auf einmal gelöscht werden können, ist nicht schwierig zu implementieren. Hier der Quellcode:

void loesche_alles(void) {
   struct angestellt *zeiger, *zeiger1;

   /* Ist überhaupt eine Liste zum Löschen vorhanden? */
   if(anfang != NULL) {
      /* Es ist eine vorhanden. */
      zeiger=anfang->next;
      while(zeiger != NULL) {
         zeiger1=anfang->next->next;
         anfang->next=zeiger1;
         free(zeiger);
         zeiger=zeiger1;
      }
      /* Jetzt löschen wir erst den Anfang der Liste. */
      free(anfang->next);
      free(anfang);
      anfang=NULL;
      printf("Liste erfolgreich geloescht!!\n");
   }
   else
      fprintf(stderr,"Keine Liste zum Loeschen vorhanden!!\n");
}

Zuerst wird überprüft, ob überhaupt eine Liste zum Löschen vorhanden ist. Anschließend bekommt der Zeiger zeiger die Adresse des zweiten Elements (siehe Abbildung 21.10).

Abbildung 21.10 Zeiger auf das nächste Element vom Anfang

Jetzt wird mit

anfang->next=zeiger1;

dem next-Zeiger des ersten Elements die Adresse übergeben, auf die zeiger1 verweist (siehe Abbildung 21.11).

Abbildung 21.11 Zu löschendes Element aushängen

Hiermit wurde das Element mit der Adresse, auf die der Zeiger zeiger zeigt, ausgehängt. Jetzt kann der Speicher freigegeben werden:

free(zeiger);

Mit free(zeiger) geben Sie den Speicher für das Element in der Liste endgültig frei. Jetzt bekommt noch der Zeiger zeiger die Adresse von zeiger1, damit die Liste weiterhin ordentlich verkettet bleibt. Somit sieht es nun folgendermaßen aus (siehe Abbildung 21.12).

Abbildung 21.12 Speicherplatz wurde freigegeben.

Es geht wieder von Neuem in der while-Schleife los, wie im Folgenden bildlich ohne weitere Kommentare dargestellt ist (siehe Abbildung 21.13).

Abbildung 21.13 Den Zeiger wieder auf das nächste Element vom Anfang setzen, dann aushängen und Speicherplatz freigeben

Die Abbruchbedingung für die while-Schleife wäre nun erreicht. Der Zeiger zeiger verweist jetzt auf NULL. Am Ende muss nur noch der Anfang gelöscht werden:

free(anfang->next);
free(anfang);
anfang=NULL;

Zur Sicherheit wird dem Zeiger auf das erste Element noch der NULL-Zeiger übergeben, da selbst dann, wenn der Speicher freigegeben ist, der Zeiger anfang immer noch auf die ursprüngliche Speicherstelle zeigt. Dabei kann es leicht zu Programmierfehlern kommen.


Rheinwerk Computing - Zum Seitenanfang

21.1.5 Element in die Liste einfügen topZur vorigen Überschrift

Nun folgt eine Funktion zum sortierten Einfügen eines neuen Elements in die Liste. Die Elemente (Nachnamen) sollen alphabetisch eingefügt werden. Dazu gibt es folgende vier Möglichkeiten, die beim Einfügen eines neuen Elements auftreten können:

1. Es ist noch kein Element in der Liste vorhanden, und das eingegebene ist das erste Element.
2. Das eingegebene Element ist das größte und wird somit hinten angehängt.
3. Das eingegebene Element ist das kleinste und wird ganz an den Anfang eingefügt.
4. Die letzte Möglichkeit ist gleichzeitig auch die schwierigste. Das Element muss irgendwo in der Mitte eingefügt werden.

Die folgende Funktion überprüft, welche der Möglichkeiten zutrifft, und führt dann entsprechende Arbeiten aus. Zuerst der Funktionskopf:

void sortiert_eingeben(char *n, char *v, int at, int am,
                      int aj, int et, int em, int ej, long geh) {
   struct angestellt *zeiger, *zeiger1;

Jetzt muss überprüft werden, ob überhaupt ein Element in der Liste vorhanden ist:

   if(anfang == NULL)
      anhaengen(n,v,at,am,aj,et,em,ej,geh);

Falls noch kein Element in der Liste vorhanden ist, wird die Funktion anhaengen() mit entsprechenden Argumenten aufgerufen.

Es befindet sich bereits mindestens ein Element in der Liste. Somit beginnt die Suche danach mit:

   zeiger=anfang;
   while(zeiger != NULL && (strcmp(zeiger->name,n) < 0))
      zeiger=zeiger->next;

Die einzelnen Elemente in der Liste werden so lange durchlaufen, bis entweder das Ende erreicht ist (zeiger == NULL) oder bis das neue Element größer oder gleich dem Namen ist, auf den der zeiger verweist. Auf jeden Fall wird die Schleife unterbrochen. Jetzt muss überprüft werden, warum die Schleife abgebrochen wurde. Zuerst wird nachgesehen, ob keine Übereinstimmung stattgefunden hat, und das neue Element somit ganz hinten angehängt wird:

   if(zeiger == NULL)
      anhaengen(n,v,at,am,aj,et,em,ej,geh);

In diesem Fall ist das neue Element das größte und wird mit der Funktion anhaengen() am Ende angefügt.

Die nächste Möglichkeit: Das neue Element ist das kleinste und muss ganz an den Anfang der Liste platziert werden:

   else if(zeiger == anfang) {
      anfang=malloc(sizeof(struct angestellt));
      strcpy(anfang->name,n);
      strcpy(anfang->vorname,v);
      anfang->alter.tag=at;
      anfang->alter.monat=am;
      anfang->alter.jahr=aj;
      anfang->eingest.tag=et;
      anfang->eingest.monat=em;
      anfang->eingest.jahr=ej;
      anfang->gehalt=geh;
      anfang->next=zeiger;
   }

Dies sieht bildlich folgendermaßen aus:

else if(zeiger == anfang)

Abbildung 21.14 Ein neues Element wird am Anfang eingefügt.

anfang=malloc(sizeof(struct angestellt));

Abbildung 21.15 Für das neue Element wird Speicherplatz reserviert.

anfang->next=zeiger;

Abbildung 21.16 Das neue Element wird am Anfang eingefügt.

Jetzt fehlt noch die schwierigste Möglichkeit: Das Element muss irgendwo in der Mitte eingefügt werden:

   else {
      zeiger1=anfang;

      /* Wir suchen das Element, das vor dem Zeiger
       * zeiger steht. */
      while(zeiger1->next != zeiger)
         zeiger1=zeiger1->next;

      zeiger=malloc(sizeof(struct angestellt));
      strcpy(zeiger->name,n);
      strcpy(zeiger->vorname,v);
      zeiger->alter.tag=at;
      zeiger->alter.monat=am;
      zeiger->alter.jahr=aj;
      zeiger->eingest.tag=et;
      zeiger->eingest.monat=em;
      zeiger->eingest.jahr=ej;
      zeiger->gehalt=geh;

      /* Wir fügen das neue Element ein. */
      zeiger->next=zeiger1->next;
      zeiger1->next=zeiger;
   }

Als Beispiel wird ein neues Element zwischen dem zweiten und dem dritten Element eingefügt. Bildlich ergibt sich dadurch folgender Stand (siehe Abbildung 21.17).

Abbildung 21.17 Ein Zeiger befindet sich eine Position hinter dem neuen Element, das eingefügt werden soll.

Der Zeiger zeiger verweist somit auf das dritte Element. Jetzt wird mit

      while(zeiger1->next != zeiger)
         zeiger1=zeiger1->next;

die Adresse des Elements ermittelt, das vor dem Zeiger zeiger steht:

Abbildung 21.18 Ein Zeiger befindet sich jetzt vor dem einzufügenden Element.

Für das neue Element wird jetzt zunächst Speicherplatz benötigt:

zeiger=malloc(sizeof(struct angestellt));

Abbildung 21.19 Speicherplatz für das neu einzufügende Element reservieren

Nun muss das neue Element in die Liste eingehängt werden. Dies geschieht in zwei Schritten: Der next-Zeiger des neuen Elements bekommt die Adresse, auf die auch der next-Zeiger von zeiger1 verweist:

zeiger->next=zeiger1->next;

Es ergibt sich folgendes Bild:

Abbildung 21.20 So lassen Sie den »next«-Zeiger des neuen Elements auf die Adresse des »next«-Zeigers seines Vorgängers verweisen.

Jetzt muss noch der next-Zeiger von zeiger1 auf die Adresse des neuen Elements zeigen:

zeiger1->next=zeiger

Abbildung 21.21 So lassen Sie den »next«-Zeiger des Vorgängers auf das neue Element verweisen.

Hier sehen Sie die vollständige Funktion sortiert_eingeben():

void sortiert_eingeben(char *n, char *v, int at, int am, int aj,
                        int et, int em, int ej, long geh) {
   struct angestellt *zeiger, *zeiger1;

   /* Ist es das 1. Element der Liste? */
   if(anfang==NULL)
      anhaengen(n,v,at,am,aj,et,em,ej,geh);
   /* Es ist nicht das 1. Element. Wir suchen so lange, bis das
    * gesuchte Element gefunden wird oder wir auf NULL stoßen */
   else {
      zeiger=anfang;
      while(zeiger != NULL && (strcmp(zeiger->name,n) < 0))
         zeiger=zeiger->next;
      /* Falls der Zeiger auf NULL zeigt, können wir unser
       * Element hinten anhängen, da unser neues Element das
       * "größte" zu sein scheint. */
      if(zeiger==NULL)
         anhaengen(n,v,at,am,aj,et,em,ej,geh);
      /* Ist unser neues Element das kleinste und somit
       * kleiner als das 1. Element, so müssen wir es an
       * den Anfang setzen. */
      else if(zeiger==anfang) {
         anfang=malloc(sizeof(struct angestellt));
         if(NULL == anfang) {
            fprintf(stderr, "Kein Speicher\n");
            return;
         }
         strcpy(anfang->name,strtok(n, "\n"));
         strcpy(anfang->vorname,strtok(v, "\n"));
         anfang->alter.tag=at;
         anfang->alter.monat=am;
         anfang->alter.jahr=aj;
         anfang->eingest.tag=et;
         anfang->eingest.monat=em;
         anfang->eingest.jahr=ej;
         anfang->gehalt=geh;
         anfang->next=zeiger;
            }
         /* Die letzte Möglichkeit ist, dass wir das Element
          * irgendwo in der Mitte einfügen müssen. */
         else {
            zeiger1=anfang;
            /* Wir suchen das Element, das vor dem
             * Zeiger zeiger steht. */
            while(zeiger1->next != zeiger)
               zeiger1=zeiger1->next;
            zeiger=malloc(sizeof(struct angestellt));
            if(NULL == zeiger) {
               fprintf(stderr, "Kein Speicher");
               return;
            }
            strcpy(zeiger->name,strtok(n, "\n"));
            strcpy(zeiger->vorname,strtok(v, "\n"));
            zeiger->alter.tag=at;
            zeiger->alter.monat=am;
            zeiger->alter.jahr=aj;
            zeiger->eingest.tag=et;
            zeiger->eingest.monat=em;
            zeiger->eingest.jahr=ej;
            zeiger->gehalt=geh;
            /* Wir fügen das neue Element ein. */
            zeiger->next=zeiger1->next;
            zeiger1->next=zeiger;
         } //Ende else
      } //Ende else
}

Das Programm wird in den nächsten Abschnitten noch verwendet und erweitert. Den kompletten Quellcode des Programms bis hierher (linear_list3.c) können Sie von https://www.rheinwerk-verlag.de/2132 herunterladen oder – noch besser – Sie versuchen diese Funktion selbst einzubauen.



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen. >> Zum Feedback-Formular
<< zurück
  
  Zum Katalog
Zum Katalog: C von A bis Z

 C von A bis Z
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchtipps
Zum Katalog: C/C++






 C/C++


Zum Katalog: Einstieg in C






 Einstieg in C


Zum Katalog: Schrödinger programmiert C++






 Schrödinger
 programmiert C++


Zum Katalog: C++ Handbuch






 C++ Handbuch


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Rheinwerk Verlag GmbH 2009
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Rheinwerk Computing]

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de