verkettete Listen

[c-fuzzi]

Hallo,

den nötigen Hintergrund (bis auf malloc) für die verketteten Listen in c habe ich einigermaßen verstanden.

Ich habe mir bereits alle Erklärungen für die verketteten Listen die ich gefunden habe durchgelesen und nicht verstanden.

Deshalb suche ich hier um Hilfe.

Ich habe hier einen Link auf ein PDF mit einem Beispielcode, zu welchem ich Fragen habe:

https://www.mathematik.uni-marburg.de/~graef/C/Listen.pdf

Frage 1:

in der Struktur DATEN steht die Zeile: struct DATEN *next;

Worauf zeigt dieser Zeiger jetzt genau?

In der Erklärung steht: // Zeiger auf nächstes Listenelement

Was ist hier jetzt ein Listenelement? Die Struktur?

Frage 2:

ein wenig weiter unten steht die Zeile:

Start = (struct DATEN * ) malloc(sizeof(DATEN));

Was genau passiert hier?

Wäre toll, wenn das jemand verständlich für einen Anfänger erklären könnte!

Vielen Dank!

Gruß

[DirkB]

c-fuzzi schrieb:

den nötigen Hintergrund .. für die verketteten Listen in c habe ich einigermaßen verstanden.

Das passt nicht zu deiner ersten Frage.
Ja, ein Listenelement ist ein Speicherbereich, in dem die struct abgelegt ist.

Mit malloc kannst du Speicher anfordern. Dieser wird von einem großen Bereich (dem Heap) genommen.
Das brauchst du, wenn du beim programmieren noch nicht weißt, wieviel Speicher du beim Programmlauf brauchst.

Du besorgst dir also nacheinader immer wieder Speicher für eine struct und verbindest diese über Zeiger.

Das ist wie bei einer Schnitzeljagd. Am nächsten Ziel bekommst du die Information, wo du dann hin musst.

Zu deinem verlinkten Code.
Der steckt voller Fehler und Nichtwissen.

void main () // main hat immer den Rückgabetyp int

while (gets(aktuell->Name) != NULL) { // gets ist sowas von unsicher. Wird nicht mehr verwendet.
...
// das Enter von scanf abfangen (was passiert wenn man getchar() vergisst -> siehe Skript 7-9 Programm a)
getchar(); // da hat jemand die Möglichkeiten von scanf nicht verstanden

malloc kann auch fehlschlagen. Diesen Fall muss man abfangen. Wo ist die Fehlerbehandlung?

Meine Meinung zu dem Tutorial:

[c-fuzzi]

Danke dir soweit.

Also, da ich schon erfolgreich mit Zeiger, Strukturen, Arrays usw. gearbeitet habe, hätte ich schon von mir behauptet diese Elemente zu kennen. Natürlich gibt es für mich immer noch neue Situationen, wo ich nicht weiterkomme.

Wie eben hier, hier wird mit Zeigern auf Strukturen gezeigt, damit komme ich nicht klar...

Da der Code so schlecht war, habe ich hier mal einen anderen Ausschnitt (anderer Code):

/* 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;

Also wenn ich es richtig verstanden habe, dann zeigt der Zeiger *next auf die nächste Struktur des gleichen Typs. Jetzt frage ich mich, wenn die Struktur angestellt deklariert wird und das Programm auf Zeile 19 stößt:
struct angestellt *next;

Wurde dann die nächste Struktur des gleichen Typs bereits deklariert? Oder ist das dann nicht notwendig?

[DirkB]

Der Compiler sieht erstmal nur, dass da ein Zeiger gewünscht ist. Die struct kennt er zumindest den Namen nach (aus Zeile 13). Mehr braucht er da nicht.

Und ein Zeiger belegt nur Speicheplatz für einen Zeiger und nicht soviel, wie die Daten auf die er verweist.

In Zeile 13 gibst du dem Compiler auch nur den Datentyp bekannt. Da wird noch kein Speicher belegt.

Speicher verbrauchst du erst bei einer Definition.

struct angestellt Mitarbeiter;

Hier für eine struct . (Du hast in den Zeilen 22, 23 aber Zeiger auf die struct. Da hast du nur Speicher für die Zeiger verbraucht. Speicher für die struct musst du erst noch besorgen - mit malloc .

[c-fuzzi]

ok und der Zeiger *next, muss dieser next heißen? Zeigt er dadurch auf die nächste Adresse, oder wie wird das festgelegt?

[DirkB]

c-fuzzi schrieb:

ok und der Zeiger *next, muss dieser next heißen?

Nein. Kannst du benennen wie du willst. Aber next hört sich ganz vernünftig an.
Es wir auch succ für successor benannt.

c-fuzzi schrieb:

Zeigt er dadurch auf die nächste Adresse, oder wie wird das festgelegt?

Indem du (als Programmierer) im Programm die Adresse für die nächste struct (bekommst du vom malloc) da einträgst.

Die Verwaltung der Zeiger ist das Kunststück bei einer Liste.
Wenn du Elemente in der Mitte einfügst oder entfernst musst du darauf achten welches next du gerade hast.
Denn du kannst so auch auf das übernächste Element zugreifen.

puts(anfang->next->next->name);

Aber man hat meist einen Zeiger auf die struct, die man gerade bearbeitet.
An das letze Element kommt man z.B:

struct angestellt *aktuell;
struct angestellt *anfang;
// sei die Liste gefüllt

aktuell = anfang;
while (aktuell->next != NULL)
  aktuell = aktuell->next;
// jetzt zeigt aktuell auf den letzten Listeneintrag. Und du kannst etwas an das Ende anhängen

[c-fuzzi]

ok und in dem oben genannten code von mir stehen ganz unten folgende 2 Zeilen:

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

Also werden hier die beiden Zeiger einfach auf NULL gesetzt.

Wenn man normal einen Zeiger einen anderen Wert zweißt, wird das beispielsweiße so gemacht:

Zeiger = Null;

Warum steht hier: struct angestellt *next = NULL; ???

(Gut bei dem Zeiger anfang ist das klar, weil dieser noch nicht deklariert wurde).

Edit:

Ich würde noch gerne wissen, ob bei der folgenden verketteten Liste jede neue Struktur nach den bereits vorhandenen Strukturen "erstellt" wird.

Ist das richtig?

Hier noch der komplette Quellcode:

/* 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;
}