Verkettete Listen (Zeiger in Strukturen)

Bevor wir in das Thema der dynamischen Datenstrukturen einsteigen, hier noch etwas neue C-Syntax:

Gegeben sei

struct note {
 int tonhoehe;
 double dauer;
 ...
};

Dann gibt es natuerlich auch:

struct note * np;

Wenden wir die bisher bekannten Syntagmen an, müßten wir, um an das Feld tonhoehe des Objektes zu kommen, auf das np zeigt, schreiben:

(*np).tonhoehe

Dafür gibt es in C eine Abkürzung:

np -> tonhoehe

Allgemein: p -> f bedeutet: Das Feld f der Struktur, auf die p zeigt.

Kombinieren wur einiges, was wir bisher wissen, dann kommen wir zu ganz interessanten Datenstrukturen:

1. Eine Zeigervariable kann ein Feld innerhalb einer Struktur sein.
2. Eine Zeigervariable kann auf Strukturen zeigen.
3. Eine Zeigervariable als Feld einer Struktur kann auf eine Struktur gleichen Typs zeigen
4. Strukturen können dynamisch alloziert werden.

Damit können wir also deklarieren:

struct item {
  struct item * next;
  int daten;
};

struct list {
struct item * start;
struct item * end;
};

und damit Datenstrukturen wie in Abb. 2 dargestellt aufbauen. Dabei werden alle Objekte vom Typ struct item dynamisch und anonym erzeugt, der Zugriff erfolgt lediglich über Objecte vom Typ struct list.

Abbildung 11.2: Eine Verkettete Liste

pwd

Eine solche Datenstruktur gehört zu den sog. dynamischen Datenstrukturen, und ist eine einfach verkettete Liste

Solche Datenstrukturen haben den Vorteil, daß man nicht bereits zu Beginn des Programms festlegen muß, wieviel Elemente man denn nun braucht. Sie können (daher der Name) während des Programmablaufs dynamisch wachsen oder schrumpfen. Hier sind einige Funktionen, die wichtige Aufgaben übernehmen:

void error (char * meldung)
{
  fprintf(stderr,"%s\n",meldung); /* gib Meldung auf Fehlerkanal aus */
  exit(1);                        /* beende Programm */
}

/* fuege ein neues Datenelement mit Inhalt "datum" an den Anfang der
   Liste */

void einfuegen_am_anfang (int datum, struct list * liste)
{
  /* erzeuge dynamisch ein neues Listenelement */
  struct liste * neues_element = malloc(sizeof(struct item));

  neues_element -> daten = datum; /* kopiere Nutzdaten */
  /* das ehemals erste Element wird der Nachfolger des neu erzeugten */
  neues_element -> next = liste -> start; 

  if(!liste -> start) /* es gab bisher gar kein element in der Liste */
    liste -> end = neues-element; /* also ist das neue element auch
                                     gleich das letze Element */

  liste -> start = neues_element; /* und das erste sowieso */
}

/* f"uge ein neues Datenelement mit Inhalt "datum" ans Ende der Liste */
void einf"ugen_am_ende (int datum, struct list * liste)
{
  /* erzeuge dynamisch ein neues Listenelement */
  struct list * neues_element = malloc(sizeof(struct elem));

  neues_element -> daten = datum; /* kopiere Nutzdaten */
  neues_element -> next = NULL; /* beim letzten Element immer */

  if(!liste -> start) /* es gab bisher gar kein element in der Liste */
    liste -> start = neues_element; /* setze erstes */
  else              /* es gibt bereits mindestens ein Element */
    /* dann wird das neue Element der Nachfolger des bisher letzten */
    liste -> end -> next = neues_element; 
  liste -> end = neues_element; /* setze listenende */
}


/* erzeuge ein neues element und fuege es hinter ein gegebenes ein */
void einfuegen_vorher(int datum, struct list *liste, struct item *vorg)
{
  /* erzeuge dynamisch ein neues Listenelement */
  struct list * neues_element = malloc(sizeof(struct liste);

  neues_element -> daten = datum;        /* kopiere Nutzdaten */
  neues_element -> next  = vorg -> next; /* setze nachfolger  */
  vorg -> next = neues_element;          /* setze neuen nachf. des vorg.*/
  if (list -> start == vorg)             /* neues erstes elem */
   list -> start = neues_elem;
}

/* loesche ein gegebenes Element aus einer Liste, liefere den Inhalt
   des Datenfeldes zurueck */
int delete_item (struct item * elem, struct list * liste)
{
   struct item * cursor = liste -> start; /* der "Wanderzeiger" */
   int result = elem -> daten;
   
   if (liste -> start == elem){     /* ist es direkt das erste Element? */
     liste -> start = elem -> next; /* dann ist der Nachfolger die neue Nr1 */
     if(! liste -> start)           /* wars auch das letzte? */
        liste -> end = NULL;        /* dann ist die Liste leer */
   }
   else{   
     /* suche den Vorgaenger */
     while(cursor && cursor -> next != elem)
      cursor = cursor -> next;
     if(!cursor) /* am Ende der liste, Element nicht gefunden */
       error("Element nicht in der Liste");
     cursor -> next = elem -> next; /* Entferne Element aus Kette */
     if (elem == liste -> end)      /* wars das letzte Element? */
       liste -> end = cursor;       /* dann ist jetzt der Vorgaenger
                                                           letzter */
   }
   free(elem); /* Gib den belegten Speicher wieder frei */
   return result;
}

/* liefere das n-te datenelement der Liste (0 = erstes!) */

int gib_datum(struct list * liste, int n)
{
  struct item * cursor = liste -> start;
  
  while(n-- && cursor){
    cursor = cursor -> next;
  }
  if(!cursor)
    error("Element nicht in der Liste")
  return cursor -> daten;
}