Programmieren in C

Dynamische Listen / Bäume

Hochschule Fulda – FB AI

Sommersemester 2014

http://c-ai.rz.hs-fulda.de

Peter Klingebiel, HS Fulda, DVZ

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 2

Dynamische Listen 1

• Häufig ist die Anzahl der zu speichernden und zu bearbeitenden Daten erst zur Laufzeit des Programms bekannt

• Felder ungeeignet: müssen zur Compilezeit oder in Blöcken dimensioniert werden

dynamische Datenstrukturen– einfach verkettete Listen– doppelt verkettete Listen – Bäume– usw.

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 3

Dynamische Listen 2

• Beispiel: einfach verkettete Liste/* Datentyp f. einfach verkettete Liste */ typedef struct _slist { int value; /* Daten */ struct slist *next; /* Nachfolger */} slist;

• Beispiel: doppelt verkette Liste/* Datentyp f. doppelt verkettete Liste */typedef struct _dlist { int value; /* Daten */ struct dlist *prev; /* Vorgaenger */ struct dlist *next; /* Nachfolger */} dlist;

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 4

Dynamische Listen 3

• Objekte der Listentypen werden zur Laufzeit – alloziertslist *insert(slist *llp, int value){ slist *nlp; nlp = (slist *) malloc(sizeof(slist));

– besetzt bzw. initialisiert nlp-> value = value; nlp->next = NULL;

– und in die Liste eingehängt if(llp) llp->next = nlp; return(nlp);}

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 5

Dynamische Listen 4

• Einfache Liste: Erzeugung 1. Element

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 6

Dynamische Listen 5

• Einfache Liste: 2. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 7

Dynamische Listen 6

• Einfache Liste: 3. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 8

Dynamische Listen 7

• Einfache Liste: 4. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 9

Dynamische Listen 8

• Einfache Liste: 5. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 10

Dynamische Listen 9

• Einfache Liste: Verkettung zum Ringpuffer

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 11

Dynamische Listen 10

• Erstes Element wird oft Wurzel, Anker oder Kopf der Liste genannt

• Durchlaufen der Liste i.d.R. von der Wurzel der Liste ausslist *root, *slp;for(slp = root; slp; slp = slp->next) printf("%d\n", slp->value);

• Wird das letzte Listenobjekt mit der Wurzel verlinkt Ringpuffer

• Sortieren bei Erzeugen der Liste möglich

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 12

Dynamische Listen 11

• slist.c - einfach verkettete Liste

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 13

Dynamische Listen 12

• sortlist.c - einfach verkettete sortierte Liste

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 14

Dynamische Listen 13

• Doppelte Liste: Erzeugung 1. Element

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 15

Dynamische Listen 14

• Doppelte Liste: 2. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 16

Dynamische Listen 15

• Doppelte Liste: 3. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 17

Dynamische Listen 16

• Doppelte Liste: 4. Element und Verkettung

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 18

Dynamische Listen 17

• Doppelte Liste: Verkettung zum Ringpuffer

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 19

Dynamische Listen 18

• dlist1.c - doppelt verkettete Liste

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 20

Dynamische Listen 19

• dlist2.c - doppelt verk. Liste als Ringpuffer

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 21

Dynamische Listen 20

• Binäre Bäume

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 22

Dynamische Listen 21

• wordcount.c - sortierter binärer Baum