Diese Kapitel setzten voraus das sie die Kapitel der Zeiger verstanden haben. Falls nicht nehmen sie diese Themen durch sonst macht diese und die nächsten Kapitel keinen Sinn. Für den einen mag das Kapitel Pointer (Zeiger) unangenehm sein und für anderen sind es wieder die Strukturen. In den nächsten Kapiteln werden wir beides Vermischen. Was auf dem ersten Blick kompliziert aussehen mag und vielleicht auch ist wird Ihnen wenn sie es beherrschen eine ziemliche Erleichterung sein. Ich gehe sogar soweit zu sagen das wenn sie diesen Teil des Kurses beherrschen werden sie wohl keine weiteren Probleme mehr haben mit der Sprache C. Strukturen dieser Art werden Ihnen übrigens in C++ auch wieder begegnen.

In dem Kapitel "Dynamische Speicherzuweisung" haben wir den Umgang mit dynamisch zugeordneten Speicher mit Zeigern kennen gelernt. Dynamisch heißt das wir Speicher zur Laufzeit des Programms allozieren (herstellen). Und der Hauptsinn liegt liegt daran das man Zeiger auf Strukturen konstruiert und diese Strukturen beinhalten wiederum Zeiger. Und das ist eigentlich alles, das Grundprinzip aller dynamischen Datenstrukturen in C. Beginnen wir jetzt mit diesem Kapitel.

Zuerst benötigen wir eine Grundstruktur. Wir machen ein Art Angestellten-Liste...

#include <stdio.h> struct datum { int tag; int monat; int jahr; }; struct angestellt{ char name[20]; char vorname[20]; struct datum alter; struct datum eingest; long gehalt; };

Dies sollten sie noch kennen und es sollte Ihnen keine Problem bereiten zu verstehen. Nun wollen wir unsere Struktur erweitern....

#include <stdio.h> 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; };

Nun wird ihnen als das...

struct angestellt *next;

...am Ende der Struktur angestellt aufgefallen sein. Das Besondere an dem Zeiger ist das es ein Zeiger auf eine Variable ist, die den selben Typ wie die Struktur selbst, nämlich struct angestellt. Mit diesem einen Zeiger können wir nun die einzelnen Strukturen miteinander verketten. Dies geschieht mit dem next - Zeiger der immer auf das nächste Element, in unserem Fall auf die nächste Struktur zeigt. Natürlich müssen wir zuvor für das nächste Element einen Speicherplatz zuweisen. Aber dazu kommen wir noch. Nun benötigen wir auch ein Ende der Kette. Dazu benutzen wir den next - Zeiger und lassen diesen auf NULL zeigen...

struct angestellt *next = NULL;

Somit würde das bildlich folgendermaßen aussehen....

Ich sage es nochmals lassen sie sich nicht verwirren von struct angestellt *next. Dieser Zeiger zeigt nicht auf sich selbst sondern nur auf das nächste Element vom selben Typ (Sie wissen doch noch: Zeiger dereferenzieren eine Adresse und keinen Wert). In unserem Fall zeigt er erst mal auf NULL da wir ja noch keine Daten eingegeben haben.

Sie haben ja bereits gelernt wie man auf die einzelnen Elemente der Struktur zugreifen kann. Wir haben z.B. genommen...

struct angestellt a;

...und anschließend mit a.name, a.vorname oder a.alter usw. zugegriffen. Genauso funktioniert es auch wenn anstatt einer Strukturvariablen einen Zeiger auf eine Struktur zur Verfügung stellen...

struct angestellt *structzeiger;

Der Zugriff auf den einzelnen Elementen sieht nun ähnlich aus....

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

Diese Art von Zugriff mit einem Zeiger auf die einzelnen Variablen einer Struktur haben sie ja in den Kapiteln zuvor schon ein paar mal gesehen. Nun ist diese Art und Weise auf die einzelnen Elemente zuzugreifen weniger schön und nicht so leserlich. So haben die Compilerbauer anstatt der oben gezeigten Schreibweise einen Operator geschaffen der eine Kombination von Dereferenzierung und Elementzugriff ist. Nämlich den...

->

...Operator. Da der -> - Operator die Form von einem Zeiger hat ist dies auch noch einfacher zu lesen. Somit ergibt sich aus unserer Struktur folgende Schreibweise um auf die einzelnen Elemente zuzugreifen....

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

Diese Schreibweise ist gleich zu (*structzeiger).name . Aber die Schreibweise mit dem -> - Operator ist eigentlich die die jeder verwendet. Also werden wir diese auch verwenden. Und ich finde diese lässt sich auch leichter lesen.

Kommen wir wieder zurück zu unserer Struktur. Theoretisch sind wir jetzt in der Lage mit unsere Struktur einen Datensatz nach dem anderen zu hängen. Aber was machen wir wenn wir den Datensatz ausgeben oder sortieren wollen. Woher soll unser Programm denn wissen wo es Anfangen soll. Und deshalb benötigen wir wie bei einer Kette eben einen Anfang bzw. eine Aufhänger. Somit benötigen einen weiteren Zeiger auf unsere Struktur angestellt die auf dem Anfang zeigt....

struct angestellt *anfang;

Da wir zu Beginn des Programms ja noch keinen Datensatz eingegeben haben lassen wir den Zeiger anfang auch auf NULL zeigen. Somit sieht unsere Struktur folgendermaßen aus....

/*Download:xxx.c*/ #include <stdio.h> 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;

Nun wollen wir eine Funktion schreiben bei der wir Adresssätze aneinander hängen können. Zuerst der Funktionskopf...

/*Download:kette1.c*/ #include <stdio.h> #include <string.h> #include <stdlib.h> 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; /*Wir hängen einen Datensatz an oder geben eine 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 List gibt. Wir suchen das Element auf dem unser Zeiger *anfang zeigt. Falls *anfang immer noch auf NULL zeigt bekommt *anfang die Adresse unseres 1.Elementes und ist somit der Kopf (Anfang) unserer Liste*/ if(anfang == NULL) { /*Wir reservieren Speicherplatz für unser Struktur für das erste Element der Liste*/ if((anfang =(struct angestellt *)malloc(sizeof(struct angestellt))) == NULL) fprintf(stderr,"Kein Speicherplatzt vorhanden für anfang\n"); 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 1.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 =(struct angestellt *) malloc(sizeof(struct angestellt))) == NULL) fprintf(stderr,"Kein Speicherplatz für letztes Element\n"); 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() { char nam[20],vorn[20]; int atag,amon,ajahr,eintag,einmon,einjahr; long gehalt; printf("Name........................: "); gets(nam) printf("Vorname.....................: "); gets(vorn); printf("Alter...........(tt.mm.jjjj): "); scanf("%d.%d.%d",&atag,&amon,&ajahr); printf("Eingestellt am..(tt.mm.jjjj): "); scanf("%d.%d.%d",&eintag,&einmon,&einjahr); printf("Monatsgehalt................: "); scanf("%ld",&gehalt); anhaengen(nam,vorn,atag,amon,ajahr,eintag,einmon,einjahr,gehalt); } int main() { while(1) eingabe(); return 0; }

Somit haben wir eine Funktion mit der wir eine Eingabe machen und eine die die Eingabe übernimmt. Wichtig ist bei der Funktion anhaengen() folgende Zeile...

zeiger=zeiger->next;

Wir gehen mal davon aus das wir bereits ein Element eingegeben haben und das nächste somit das 2.Element ist. Wenn sie jetzt unserem zeiger auf die Struktur angestellt nicht die Adresse von zeiger->next übergeben hätten, würden sie einfach immer wieder die erste Struktur die sie eingegeben haben überschreiben. Des weiteren ist ebenfalls wichtig damit sie die nächsten Daten eingeben....

zeiger->next=NULL;

Damit wird es überhaupt erst möglich wenn sie wieder neue Daten eingeben das die while - Schleife überhaupt funktioniert...

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

Sonst würde unsere while - Schleife mit der Abfrage ob unser Zeiger zeiger der auf next zeigt und dieser next - Zeiger niemals abbrechen da niemals auf NULL gezeigt würde. Ich hoffe das war verständlich genug.

Sehen wir uns das ganze mal bildlich an. Nehmen wir mal an wir haben 3 Personen eingegeben...

Hier sehen sie das unser Strukturzeiger anfang immer auf das 1.Element der Liste zeigt. Der Strukturzeiger next im letzten Element zeigt immer auf NULL und zeigt somit das Ende der Kette an. Nun überlegen sie mal wie wir es zum Beispiel anstellen das 2.Element der Liste zu löschen? Den Speicherplatz geben wir mit der Funktion free(zeiger) frei! Falls wir das 1.Element der Liste löschen so ist dies nicht allzu schwierig. In dem Fall bräuchten wir nur einen Zeiger vom typ struct angestellt auf anfang->next zeigen lassen (2.Element). Dann mittels free(anfang) den Speicher freigeben und unseren Zeiger anfang auf die Adresse zeigen lassen die wir zuvor unserem neuen Zeiger mittels anfang->next übergeben haben. Sehen wir uns bildlich mal an wie wir das 1.Element loswerden....

/*Funktion zum löschen einer Datei*/ 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;

...wir gehen davon aus das das 1.Element das von uns gesuchte ist. Hier der momentane Stand...

Nun folgt...

free(anfang);

Damit geben wir den Speicherplatz frei auf den unser Zeiger anfang zeigt...

Wenn wir jetzt alles so ließen könnten wir unsere Kette vergessen. Denn wenn unser Programm die Adresse vom Anfang der Kette nicht mehr weiß macht der Rest der Kette auch keinen Sinn mehr. Aber unser Zeiger zeiger zeigt auf dem Anfang unserer Kette. Somit brauchen wir nur noch die Adresse unseres Zeiger zeiger an den Zeiger anfang übergeben....

anfang=zeiger;

Somit haben wir wieder den Anfang unserer Kette.....

Was aber wenn wir irgendwo in der Mitte eine Datei entfernen wollen? Dazu benötigen wir nochmals einen Zeiger mehr. Einer der auf die Adresse zeigt das vor dem zu Löschenden Element ist und einen der auf nächste Element des zu Löschenden Elementes zeigt. Somit haben wir dann....

struct angestellt *zeiger, *zeiger1;

Nur noch schnell mal zusammenfassen wie die Funktion bisher aussieht...

/*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 vor- handen ist*/ zeiger=anfang;

Somit hätten wir folgende "Grundstellung"...

Wir gehen jetzt einfach mal davon aus das unser gesuchtes Element zum löschen das 2. ist (im Bild). Somit sieht der weitere Code so aus....

while(zeiger->next != NULL) { zeiger1=zeiger->next; /*Ist die Adresse von zeiger1 der gesuchte Namen?*/ if(strcmp(zeiger1->name,wen) == 0) { /*Falls ja dann.....*/

...und bildlich kann man sich das dann so vorstellen...

Wir gehen jetzt davon mal aus das der Inhalt auf den zeiger1 zeigt der von uns gesuchte ist. Achtung jetzt wird es etwas schwieriger. Da wir ja nun den Inhalt auf den zeiger1 zeigt löschen wollen, benötigen wir für den next - Zeiger unserer Struktur auf die zeiger zeigt auch wieder eine Adresse damit die Kette nicht reiß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");
}

Zuerst kommen wir zu der Zeile....

zeiger->next=zeiger1->next;

Das heißt jetzt genau in Worten der Zeiger zeiger der auf die Adresse der nächsten (next) Datenstruktur zeigt (zu dem jetzigen Zeitpunkt zeigt zeiger->next ja noch auf das zu löschende Element auf das der Zeiger zeiger1 zeigt) jetzt die Adresse bekommt auf der der next - Zeiger des zu löschenden Elements (zeiger1) zeigt. Bildlich ist das vielleicht einfacher...

Man sagt auch wir hängen das zu löschende Element aus. Jetzt können wir mittels...

free(zeiger1);

...unser Element löschen. Und hätten somit folgendes finale Bild...

Jetzt benötigen wir nur noch eine Funktion zum ausgeben der Liste, was die einfachste Funktion darstellt. Wir lassen dabei einen Zeiger auf den Anfang der Liste zeigen und testen mittels...

while(zeiger != NULL)

...so lange bis unser Zeiger zeiger auf NULL zeigt. Hier die Funktion...

void ausgabe() { struct angestellt *zeiger; 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 das gesamte Programm inklusive der main - Funktion....

/*Download:kette2.c*/ #include <stdio.h> #include <string.h> #include <stdlib.h> 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; /*Wir hängen einen Datensatz an oder geben eine 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 List gibt. Wir suchen das Element auf dem unser Zeiger *anfang zeigt. Falls *anfang immer noch auf NULL zeigt bekommt *anfang die Adresse unseres 1.Elementes und ist somit der Kopf (Anfang) unserer Liste*/ if(anfang == NULL) { /*Wir reservieren Speicherplatzt für unser Struktur für das erste Element der Liste*/ if((anfang =(struct angestellt *)malloc(sizeof(struct angestellt))) == NULL) fprintf(stderr,"Kein Speicherplatzt vorhanden für anfang\n"); 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 1.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 =(struct angestellt *) malloc(sizeof(struct angestellt))) == NULL) fprintf(stderr,"Kein Speicherplatz für letztes Element\n"); 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; zeiger->gehalt=g; zeiger->next=NULL; //Wir terminieren wieder unsere Datenstruktur } } /*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 vor- handen ist*/ zeiger=anfang; while(zeiger->next != NULL) { zeiger1=zeiger->next; /*Ist die Adresse von zeiger1 der gesuchte Namen?*/ 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 löschen vorhanden!!!\n"); } /*Funktion zum Ausgeben der Dateien*/ void ausgabe() { struct angestellt *zeiger; 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() { char nam[20],vorn[20]; int atag,amon,ajahr,eintag,einmon,einjahr; long gehalt; fflush(stdin); printf("Name........................: "); gets(nam); printf("Vorname.....................: "); gets(vorn); printf("Alter...........(tt.mm.jjjj): "); scanf("%d.%d.%d",&atag,&amon,&ajahr); printf("Eingestellt am..(tt.mm.jjjj): "); scanf("%d.%d.%d",&eintag,&einmon,&einjahr); printf("Monatsgehalt................: "); scanf("%ld",&gehalt); anhaengen(nam,vorn,atag,amon,ajahr,eintag,einmon,einjahr,gehalt); } int main() { int wahl; char dname[20]; do{ printf("1 : Eingabe\n"); printf("2 : Ausgabe\n"); printf("3 : Namen löschen\n"); printf("9 : Ende\n"); printf("Ihre Wahl : "); scanf("%d",&wahl); switch(wahl) { case 1 : eingabe(); break; case 2 : ausgabe(); break; case 3 : printf("Welchen Namen wollen sie löschen : "); scanf("%s",dname); loesche(dname); break; case 9 : break; default: printf("Falsche Eingabe!!!\n"); } }while(wahl != 9); return 0; }

Zugegeben dem Programm fehlen noch einige Optionen und die Optik lässt sehr zu wünschen. Daher werden wir Schritt für Schritt das Programm erweitern. Doch dies werde ich im 2. Teil der Linearen Listen machen.