Datenstrukturen, Listen und Bäume - htw-dresden.desobe/Prog1_Jg17/Vo/12_Datenstruk_Listen... ·...

Peter Sobe 1

Datenstrukturen,Listen und Bäume

Inhalt:

Datenstrukturen – Definition und Arten

Dynamische lineare Datenstrukturen: lineare, verkettete Liste

Nichtlineare dynamische Datenstrukturen:Binärbaum

Die Umsetzung einfacher Datenstrukturen im Speicher des Rechners erfolgt mit bislang bekannten Mitteln:Strukturen, Felder und mehrdimensionale Felder (Matrizen)

Datenstrukturen - Definition

Eine Datenstruktur beschreibt die Art der Organisation der Daten

im Speicher des Rechners während der Verarbeitung

auf Speichermedien (Festplatte, Band, CD, DVD, FlashRAM u.ä.)

Die Daten werden dabei in Elemente aufgeteilt. Die einzelnen Elemente werden in regelmäßige Relationen gesetzt, z.B. eine Vorgänger- und Nachfolger-Relation.

Peter Sobe 2

Datenstrukturen - Definition

Aus www.computerlexikon.com:

Als Datenstruktur bezeichnet man das Konstrukt in einem Programm (bzw. im Speicher), das Daten auf eine gewisse Weise speichert. Durch den speziellen Aufbau einer Datenstruktur versucht man gewünschte Funktionen besonders effizient zu implementieren, wobei man zumeist entweder auf geringen Speicherbedarf oder hohe Geschwindigkeit hin optimiert.

Durch eine falsche Datenstruktur für ein Problem, kann ein Programm um ein Vielfaches länger für die Lösung benötigen als eines, das auf eine für das Problem besser geeignete Daten-struktur zurückgreift.

Peter Sobe 3

Datenstrukturen - DefinitionAus wikipedia:

In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung geeignet zu ermöglichen. Datenstrukturen sind daher nicht nur durch die enthaltenen Daten charakterisiert, sondern vor allem durch die Operationen auf diesen Daten, die Zugriff und Verwaltung realisieren.Die Definition von Datenstrukturen erfolgt durch die Angabe einer konkreten Spezifikation zur Datenhaltung und der dazu nötigen Operationen. Diese konkrete Spezifikation legt das allgemeine Verhalten der Operationen fest und abstrahiert damit von der konkreten Implementierung der Datenstruktur.

Peter Sobe 4

Datenstrukturen

Für viele Anwendungen ist die Wahl einer geeigneten Datenstruktur eine wesentliche Entscheidung

Frage: Wie organisiert man die Daten im Speicher, damit sie günstig verarbeitet werden können? Günstig kann heißen:

Programmcode zur Verarbeitung einfach und kurz

wenig Anweisungen (schneller, weniger Prozessorbelastung)

inhaltlich verwandte Elemente stehen nah beieinander (schneller)

Geringer Speicherbedarf

Beispiele:

• Lineares Feld mit sortierten Elementen, z.B. für Telefonbucheinträge

• Baumstruktur mit Verweisen auf Vater- und Mutterelemente zur Nachbildung von Stammbäumen

• Netzstruktur, z.B. mit Struktur einer elektrischen SchaltungPeter Sobe 5

Datenstrukturen - Arten Lineare Strukturen

Felder – eindimensional indizierte Strukturen

Listen, Warteschlangen, Stapel

Zirkulare Strukturen

einfache Ringe

vermaschte Ringe

Mehrdimensional indizierte Strukturen

Bäume

Allgemeiner Baum

Binärbaum ( Darstellung als Feld möglich)

Netze (allgemeine Graphen)

Hash-StrukturenPeter Sobe 6

Peter Sobe 7

Dynamische Speichertechnik (1)

Unter dynamischer Speichertechnik versteht man die Bildung neuer Speicherplätze auf der Basis von Standarddatentypen und deklarierten Strukturen zur Laufzeit. Es wird Speicherplatz zur Laufzeit bereitgestellt und darauf ein neues Element einer Datenstruktur initialisiert.Dieses neue Element wird mit bereits vorhandenen Elementen in der Datenstruktur in Beziehung gesetzt. Ebenso können auch zur Laufzeit Elemente aus der Datenstruktur herausgelöst werden und deren Speicherplatz wieder freigegeben werden.

Im Gegensatz werden die bisher benutzen Variablen und Felder als statische Datenstrukturen angesehen. Die Sichtbarkeit und der belegte Speicherplatz wird durch ihre Deklaration im globalen Kontext des Programms oder innerhalb Funktionen bestimmt.

Peter Sobe 8

Dynamische Speichertechnik (2)

Zur Realisierung solcher dynamischer Strukturen werden zwei Technologien benötigt:

1. Die dynamische Speicherallokation und –freigabe

2. Die Verwendung der Zeigertechnik zum dynamischen Herstellen und Lösen von Verbindungen von Elementeninnerhalb der Datenstruktur

Die vom Programmierer geschaffene Organisation der Daten (also wo welches Element im Speicher steht und wie es mit den anderen Elementen in Beziehung gesetzt wird) wird durch Datenstrukturen beschrieben.

Dynamische Speichertechnik (3)Die dynamische Speicherallokation und –freigabe wird in C mit den Funktionen

void *malloc(size_t size); // gibt die Anfangsadr. des// allokierten Bereichs zurück

void free(void *addresse);

durchgeführt, die in <alloc.h> zu finden sind.Es werden size Bytes allokiert und die Adresse dieses Speicher-bereiches zurückgegeben. Ist der Rückkehrwert NULL, ist nicht genügend Speicher vorhanden. Ist die Größe in Bytes bekannt, kann diese direkt als Argument übergeben werden, sonst empfiehlt sich die Verwendung von sizeof(x), welche die notwendige Größe in Bytes für das Element x ermittelt.

Bei der Speicherfreigabe mit free ist nur die Adresse des Speicherbereichs anzugeben.

Peter Sobe 9

Dynamische lineare DatenstrukturenDynamisches Feld (Wiederholung):

eine eindimensionale Datenstruktur

Elemente werden durch Zahlenindex angesprochen

Feld kann wachsen und schrumpfen – durch dynamische Speichertechnik (in C: malloc(), realloc(), free())

Lineare Liste:

eine eindimensionale Datenstruktur

Liste kann wachsen und schrumpfen

Effizientes Einfügen neuer Elemente und Löschen

(kein Zahlenindex zum Zugriff)

Weitere lineare Datenstrukturen: Warteschlange, Stapel

Peter Sobe 10

Element

Lineare Liste

Element 1 Element 2 Element 3

struct list_element{ float f; char position[STRLEN];struct list_element *next;

};typedef struct list_element list_elem_t;…list_elem_t *anker = NULL;

Listenelement

11Peter Sobe

Zeigertechnik bei linearen Listen

Die Verwendung der Zeigertechnik zum dynamischen Herstellen und Lösen von Verbindungen von Objektenund der Datenstruktur erfordert in C den Einsatz des Verbundtyps struct{...}, da die Zeiger in das zu verbindende Objekt einbezogen werden müssen.

Da das Objekt selbst eine Struktur ist, muss demzufolge der Zeiger auf die nächste Struktur auch vom gleichen Strukturtyp sein, z.B.

struct list_element{ float f;// weitere Elementestruct list_element *next; // Zeiger auf Nachfolger-Element

};

12Peter Sobe

Lineare Liste - Definition

Eine Liste ist eine verkettete Folge von Elementen,die aus Standarddatentypen zusammengesetzt sind und für die gilt:

1. Es gibt genau ein Listenelement, das keinen Vorgänger hatund Listenanfang heißt. Auf dieses Element zeigt der Listenanker.

2. Es gibt genau ein Listenelement, das keinen Nachfolger hatund Listenende heißt.

3. Die übrigen Listenelemente haben genau einen Vorgänger und genau einen Nachfolger.

4. Alle Listenelemente sind vom Listenanker aus durchNachfolgerbildung in endlich vielen Schritten erreichbar.

13Peter Sobe

Operationen mit Listen

Als typische Operationen mit Listen gelten:

• Erzeugen und Einketten eines Listenelements

• Traversieren einer Liste

• Ausketten und Löschen eines Listenelements

• Suchen eines Listenelements

Weitere:

Anhängen einer Liste an eine Liste

…

14Peter Sobe

Erzeugen und Einketten eines neuen Elements

list_elem_t *erzeuge( list_elem_t x ){

list_elem_t *neu;neu= (list_elem_t*) malloc(sizeof list_elem_t); *neu=x; return neu;

}

Aufruf:

list_elem_t daten = {23.5, “Waldhausen“, NULL};

list_elem_t *ne = erzeuge(daten);

…einfuegen( pos, ne);

15Peter Sobe

Einketten eines Listenelements

void einfuegen(list_elem_t *pos, list_elem_t *neu){

/* pos zeigt auf das Listenelement, hinter dem das Listenelement neu eingekettet werden soll */

neu->next=pos->next; pos->next = neu;

}

Noch nicht berücksichtigt: Einfügen in leere Liste und Einfügen an erster Position

16

Einketten eines Listenelements

Vorher:

Wirkung der Funktion:neu

posSchritt 2: pos->next = neu;

Schritt 1: neu->next= pos->next;

17

pos

Vorteil: Es muss keine Umverteilung der Elemente im Speicher erfolgen.

Ausketten und Löschen eines Listenelements

void ausketten(list_elem_t *pos){

/* pos zeigt auf Element vor dem auszukettenden Element */list_elem_t *h;h=pos->next;pos->next=(pos->next)->next; free(h);

}

Gesonderte Behandlung erforderlich, wenn erstes Element auszukettenist und wenn einziges (letztes) Element ausgekettet wird.

Peter Sobe 18

Ausketten und Löschen eines ListenelementsVorher:

Wirkung der Funktion:

Schritt 3: free(h);

pos

Schritt 1: h = pos->next;

Schritt 2: pos->next = pos->next->next;

Peter Sobe 19

pos

h

Suchen eines Listenelements

list_elem_t* suche(list_elem_t *anker, char *suchpos) { list_elem_t *a; a=anker; while (a!=NULL) {if (strcmp(a->posítion, suchpos)==0)

return a; else /*Element a gefunden*/

a=a->next; } return NULL;

}

a a=a->nextPeter Sobe 20

Traversieren einer Liste

void traverse( list_elem_t *anker, void (*f)(list_elem_t *e) ) { list_elem_t *a; a=anker; while (a!=NULL) {/* mache etwas mit dem aktuellen Element */(*f)(a); /* hier können auch direkt auszuführende */

/* Anweisungen stehen */ a=a->next;

} }

Peter Sobe 21

Einsatz linearer Liste: Stapel und Warteschlange

Stapel (engl. Stack)

Datenstruktur mit Operationen:

PUSH - Auflegen eines Elements

POP - Abnehmen eines Elements

IS_EMPTY – Abfrage, ob Stapel leer ist

Ein Stapel setzt die LIFO Strategie um: Last In First Out

Ein Stapel kann günstig mit einer linearen Liste realisiert werden.

Peter Sobe 22

Einsatz linearer Liste: Stapel und Warteschlange

Warteschlange (engl. Queue)

Datenstruktur mit Operationen:

ENQUEUE - Einfügen eines Elements am Ende

DEQUEUE - Entnehmen eines Elements vom Anfang

IS_EMPTY – Abfrage, ob Warteschlange leer ist

Eine Warteschlange setzt die FIFO Strategie um: First In First Out

Eine Warteschlange kann ebenfalls günstig mit einer linearen Liste realisiert werden.

Peter Sobe 23

Nichtlineare dynamische Datenstrukturen

Eine nichtlinear verkettete Menge von Elementen (Objekten),die aus Standarddatentypen zusammengesetzt sind, nennt man nichtlineare dynamische Datenstruktur.

Solche Strukturen sind vor allem:

Bäume (Binärbäume, allg. Bäume)typisch für diese Strukturen ist die Anordnung als Hierarchie

Graphen (kreisfreie Graphen, allgemeine Graphen)allgemeine Graphen können netzartige Strukturen beschreiben (z.B. Straßen- und Schienenwege,elektrische Schaltungen, soziale Vernetzungen)

Peter Sobe 24

Nichtlineare dynamische Datenstrukturen

Viele Anwendungsalgorithmen basieren auf solchen nichtlinearen Strukturen.

Bei netzartigen Graphstrukturen müssen diese Algorithmen mit erschöpfendem Durchsuchen aller Möglichkeiten arbeiten. Das erfordert programmseitig spezielle Hilfen (globale stacks).

Bei Hierarchien (Bäume) reicht die einfache Rekursivität aus.Bei vielen Sonderfällen in Hierarchien nutzt man die s.g. Teile-und-Herrsche-Algorithmen. Diese Algorithmen teilen den aktuellen Bearbeitungsraum in Teilbearbeitungsräume und wenden dann den gleichen Algorithmus rekursiv auf die Teile an (herrschen), solange bis eine weitere Teilung nicht mehr sinnvoll ist.

Beispiel: Binärbäume

Peter Sobe 25

Binärbaum über Knotenmenge VB0= (W0, B0L ,B0R) (W0, , )

Bx= (Wx, BxL ,BxR) (Wx, , )

mit W0,B0 , Wx,Bx , ε V und als leeres Element

Indizes werden durch Aneinandereihung gebildet, z.B.

x=0L → xL = 0LL, x=0R → xL = 0RL usw.

Ein Baum ist entweder ein einzelner Knoten oder ein als Wurzel dienender Knoten, der mit einer Menge von Bäumen verbunden ist. (beim Binärbaum mit zwei Teilbäumen verbunden)

Wurzel B0

Rechter TeilbaumB0R

Linker TeilbaumB0L

Peter Sobe 26

Binärer Baum und Rekursion (1)

Verschiedene Strategien zum Traversieren des Baums

Preorder:1. Besuche die Wurzel des Baumes2. Besuche den linken Teilbaum3. Besuche den rechten Teilbaum

Peter Sobe 27

Binärer Baum und Rekursion (2)

1

2

3 4

5

6 7

Verschiedene Strategien zum Traversieren des Baums

Inorder (Symmetrische Strategie):1. Besuche den linken Teilbaum2. Besuche die Wurzel3. Besuche den rechten Teilbaum

Peter Sobe 28

Binärer Baum und Rekursion (3)

1

2

3

4

5

6

7

Verschiedene Strategien zum Traversieren des Baums

Postorder:1. Besuche den linken Teilbaum2. Besuche den rechten Teilbaum3. Besuche die Wurzel

Peter Sobe 29

Binärer Baum und Rekursion (4)

1 2

3

4 5

6

7

Strategien zum Traversieren des Baums (Fortsetzung)

Alle bisherigen Verfahren besuchen entweder tiefe Knoten oder links stehende Knoten zuerst.

Bei Suchbäumen werden Lösungen u.U. erst spät gefunden.

Level-Order-Traversierung:

Besuche die Knoten “von links nach rechts“ innerhalb einerEbene, danach die jeweils tiefere Ebene.

Diese Reihenfolge wird nicht durch Zeiger in innerhalb der Baumstruktur unterstützt

Diese Reihenfolge wird auch nicht durch Rekursion unterstützt

Peter Sobe 30

Binärer Baum und Rekursion (5)

31Peter Sobe

Binärer Baum mit sortierten Daten (1)

ID

Baum-Elemente:

Daten Zeiger-links

Zeiger-rechts

15 …

8 … 20 …

4 … 12 … 17 … 23 …

Zeiger auf Baum-Wurzel:

NULL-Zeiger, wenn Nachfolge-Elemente nicht vorhanden:

32Peter Sobe

Binärer Baum mit sortierten Daten (2)

Suchen eines Elements mit ID=x im sortierten Binärbaum:

Knoten = WurzelAufsuchen Knoten: falls ID==x dann gefunden, Ende falls x<ID: Verfolge Zeiger-links falls x>ID: Verfolge Zeiger-rechts

Nach „Verfolge“ wird der jeweilige Knoten nach o.g. Regel besucht, solange bis Knoten mit ID gefunden oder ein Verfolgen auf den NULL-Zeiger trifft. Dann ist

das gesuchte Element im Baum nicht vorhanden.

33Peter Sobe

Bewertung Binärbaum

Beispiel: 15

8 20

4 12 17 23

2 6 10 14 16 19 21 26

im Bild allgemein Berechnung

Anzahl Ebenen 4 e KonstruktionsparameterAnzahl Elemente 15 n = 2e-1Schritte zum Finden eines Elements

4 (inkl. Zugriff auf Wurzel)

s=e s =

Wurzel