Matura: Softwareentwicklung & Informationssysteme

1.2.-3. Statische und dynamische Datenstrukturen / Verkettete Listen

Statische Datenstruktur

• Größe einer statischen Datenstruktur kann zur Laufzeit nicht geändert werden
• Beispiel: Arrays & Structs
• Struct Beispiel

Dynamische Datenstruktur

• Dynamisch heißt, dass zur Laufzeit des Programms Speicher vom Heap alloziert (zugewiesen) wird.
• Bsp: verkettete Listen, Ringstruktur, Bäume
• Jeder Speicherblock, der reserviert wurde, muss auch händisch freigegeben werden!
• Methoden:
  • void *malloc(size_t size)
    • belegt einen size Bytes großen, zusammenhängenden Bereich und liefert die Anfangsadresse davon zurück.
    • Rückgabewert: NULL bei Fehler, sonst Zeiger auf Anfangsadresse des res. Speicherblocks
  • void *calloc(size_t n, size_t size);
    • n: Anzahl an zu reservierenden Objekte
    • size: Größe eines Objekts
    • Wie malloc(), nur mit Anzahl
  • void free(void ptr*)
    • der Speicherbereich, der mit malloc/calloc belegt wurde, wird freigegben
    • ist ptr ein NULL-Pointer, passiert nichts
    • ist ptr kein/ein falscher Zeiger => undefiniertes Verhalten
  • void *realloc (void *ptr, size_t size);
    • Ermöglicht Größenänderung
    • der durch ptr adressierte Speicherbereich
      • wird freigeben
      • der ursprüngliche Block bleibt erhalten
      • falls möglich wird der neue Block hinten angehängt
      • sonst wird der gesamte Block umkopiert
    • Rückgabewert: NULL bei Fehler, sonst wird ein Zeiger auf den Speicherblock mit size Byte Größe
    • Wird für ptr ein NULL Zeiger verwendet, so funktioniert realloc() wie malloc()
      • ptr = malloc(100*sizeof(int)); = ptr = realloc(NULL, 100*sizeof(int));
    • Wenn man den Speicher vergrößern möchte, so muss man die ursprüngliche Größe mit der Erweiterung zusammenzählen

int block = 256;
ptr = malloc(block * sizeof(int));
...
block += block;
// Speicher für 512 int-Elemente reservieren
ptr = realloc(ptr, block*sizeof(int));

Einfach verkettete Liste

• Reihe von Strukturvariablen dynamisch erzeugen
• In der Struktur Zeiger auf nächste Struktur

typedef struct data {
  char name[MAX];
  char vorname[MAX];
  struct data *next;
}DATA;

• Neues Element anlegen

DATA *first = NULL;
first = malloc (sizeof(DATA));
if (first!=NULL)
  first->next = NULL;

• Zweites Element hinzufügen und anhängen

DATA *help = NULL;
help = malloc (sizeof(DATA));
if (help!=NULL) {
    help->next = NULL;
    first->next = help;
}

• Für jedes weitere Element:
  • Zeiger auf aktuelles (und letztes) Element merken
  • first zeigt immer auf erstes Element
    • Verlust von first -> Kette verloren
  • prev zeigt auf vorletztes Element
  • akt zeigt auf aktuelles/zuletzt hinzugefügtes Element
• Hinzufügen eines Elements
  • akt->next = help->next;
  • help->next = akt;
• Löschen eines Elements
  • akt->next = help->next;
  • free (help);
  • VORSICHT beim Löschen des ersten Elements!
• Tipps zur Vereinfachung
  • Lege zu Beginn ein first-Element an (global?)
  • Lösche das first-Element erst beim Programmende
  • Im first-Element sind keine Daten
• Bessere Erklärung mit Schritten ab Folie 21
• Beispiel

Doppelt verkettete Liste

• Vorteil: schnelleres Navigieren durch Liste
• In der Struktur Zeiger auf nächste & vorherige Struktur

typedef struct data {
  char name[MAX_LEN];
  char vorname[MAX_LEN];
  struct data *next;
  struct data *prev;
}DATA;

• Einfügen von Element

help = malloc (sizeof(DATA));
help->next = elem->next;
help->prev = elem;
elem->next->prev = help;
elem->next = help;

• Löschen von Element

elem->prev->next=elem->next;
elem->next->prev = elem->prev;
free (elem);

• Bessere Erklärung mit Schritten ab Folie 80
• Beispiel

Ringstruktur

• Spezialfall einer verketteten Liste
• Letztes Element ist mit ersten verbunden
• gibt keinen Startknoten
• Element löschen (einfach verkettet)

akt=elem->next;
elem->next = akt->next; // oder: elem->next->next;
free(akt);

• Element erzeugen (doppelt verkettet)

elem=malloc(sizeof(DATA));
elem->next = elem;
elem->pref = elem;

• Element einfügen (doppelt verkettet)

akt=malloc(sizeof(DATA));
akt->next=elem->next;
akt->prev=elem;
elem->next->prev = akt;
elem->next = akt;

• Bessere Erklärung mit Schritten ab Folie 98

Queue/Stack

• Nicht in Helmlfolien erklärt
• Queue: First In, First Out
  • Siehe Online
• Stack: Last In, First Out
  • Siehe Online