Kapitel 4Kapitel 4 DatenstrukturenDatenstrukturen

Information aus der realen Welt werden in einem informationsver-arbeitenden System als Daten abgelegt. Diese stellen also eine (vereinfachte) Abstraktion der Wirklichkeit dar und spiegeln in vielen Fällen die Strukturen der Wirklichkeit wider.In diesem Kapitel wird ein Überblick über die wichtigsten abstrakten Datenstrukturen gegeben, wobei dieser Begriff zum Begriff des „Datentyps“ erweitert wird.

Inhalt1. Datenstrukturen - Datentypen

2. Datentypen: Ein Überblick

3. Konkrete Datentypen

4. Abstrakte Datentypen

4.14.1 Datenstrukturen - DatentypenDatenstrukturen - Datentypen

In der Literatur wird meist der Begriff „Datenstruktur“ verwendet. In diesem Unterkapitel soll der Unterschied ziwschen diesem Begriff und dem Begriff des „Datentyps“ erläutert werden.

Inhalt1. Datenstrukturen

2. Datentypen

3. Variablen eines Datentyps

4.1.14.1.1 DatenstrukturenDatenstrukturen

In der Informatik werden Objekte der realen oder abstrakten Welt erfasst

Bei der Erfassung beschränkt man sich möglichst auf die für den weiteren Transport / Speicherung/Verarbeitung/Umsetzung notwendige Information

Zur internen Repräsentation werden diese Objekte abstrahiert Zur Abstraktion gehört die Erkennung von Strukturen - im Sinne einer

Aggregation. Also

Aus welchen Teilobjekten bestehen Objekte ? In welchem Verhältnis stehen die Teilobjekte zueinander ? Welches sind die „atomaren“ Teilobjekte ?

Anschließend werden diese Objekte typisiert. Typisierung ist die Einteilung von abstrakten internen Objekten in

Gruppen mit gleichen oder ähnlichen Eigenschaften.

4.1.24.1.2 DatentypenDatentypen

Typen sind also nicht die intern repräsentierten Objekte, sondern beschreiben die Eigenschaft einer Gruppe von Objekten.

Zu diesen Eigenschaften gehören: Struktur Wertebereich anwendbare Operatoren, Funktionen, Relationen Beziehungen zu anderen Typen interne Repräsentationsweise …

Einige Anmerkungen:: Der Begriff „Datentyp“ ist weitergehend als der Begriff „Datenstruktur“ In der Objektorientierten Programmierung wird statt „Datentyp“ auch der

Begriff „Klasse“ verwendet (Klassen beschreiben mehr Eigenschaften) Konkrete Repräsentanten eines Datentyps werden (u.a) „Variable“ oder

- bei oo-Sprachen - „Instanz“ genannt

Beispiel:

Imaginäre Zahlen

4.1.34.1.3 Variable eines DatentypsVariable eines Datentyps

Einen speziellen Repräsentanten eines Datentyps bezeichnet man als Variable. Die Festlegung, von welchem Datentyp eine Variable ist, bezeichnet man als Variablendeklaration.

Die Zuordnung eines Typs „Typ“ an eine Variable X wird (zunächst) wiefolgt notiert: X : Typ;

Eine Variable hat alle Eigenschaften eines Datentyps.Zusätzlich dazu hat eine Variable:

einen konkreten Wert. Der Wert muss aus dem Wertebereich des Datentyps sein (oder undefiniert) Die Zuweisung eines Wertes „Wert“ an eine Variable X sei (zunächst) wie

folgt notiert: X <- Wert;

einen konkreten Speicherplatz Dieser Speicherplatz ist so dimensioniert, dass die Struktur der Variable

abgebildet werden kann Dieser Speicherplatz wird (meist) implizit durch die Deklaration zugeordnet

Beispiel: x : Datentyp; // x ist vom Typ: „Datentyp“X <- 531; // Zuweisung von 531 an X

4.24.2 Datentypen: ÜberblickDatentypen: Überblick

Nachdem sich nun der Begriff des „Datentyps“ als Oberbegriff der „Datenstruktur“ erwiesen hat, konzentrieren wir uns im Rest des Kapitels auf wichtige Datentypen.In diesem Unterkapitel wird ein Klassifikationssystem für die in der Informatik verwendeten Datentypen aufgestellt und kurz erläutert

Inhalt1. Klassifikation der Datentypen

2. Erläuterung der Klassifikation

4.2.14.2.1 Klassifikation der DatentypenKlassifikation der Datentypen

Datentypen

IdealisierteAbstrakteKonkrete

Einfache StrukturiertePointer(Zeiger)

Boolean(Wahrheitswert)

Integer(Ganzzahl)

Char (Zeichen)

Enumeration (Aufzählung)

Ordinale Real(Fließkomma)

Array (Feld)

Record (Verbund)

Union(Variantenverb.)

...

4.2.24.2.2 Erläuterung der KlassifikationErläuterung der Klassifikation

Idealisierte Datentypen aus der Mathematik bekannte Datentypen: , , , ,...ℕ ℤ ℝ ℂ Variablen dieser Typen sind oft nicht endlich darstellbar (Bsp: 2) In einem Computer-Algebra-System symbolisch darstellbar (Bsp: 2^( 1/2))

Konkrete Datentypen in einem Rechner von Hard- oder Software bereitgestellte Datentypen entweder vordefiniert oder durch den Benutzer definierbar

Abstrakte Datentypen verbergen ihren inneren Aufbau vor dem Benutzer bestehen aus beliebigen Strukturen über konkrete/idealisierte Datentypen,

sowie aus Zugriffsfunktionen bzw. Prozeduren Beispiel: Baum

2 12 15

79

6 61

13

insert (Element)

delete (Element)

search (Element)

4.34.3 Konkrete DatentypenKonkrete Datentypen

Die am häufigsten abstrahierten Objekte der realen Welt sind, zumindest was die für eine weitere Verarbeitung notwendigen Informationen betrifft, einfach strukturiert und lassen sich demnach mit konkreten Datentypen abbilden.Dieses Unterkapitel gibt einen Überblick über alle konkreten Datentypen und beschreibt diese.

Inhalt1. Einfache Datentypen

2. Strukturierte Datentypen

3. Zeiger-Datentypen

4. Beispiel: Kombinierte Datentypen

4.3.14.3.1 Einfache: boolean (Wahrheitswert)Einfache: boolean (Wahrheitswert)

zur Darstellung von Wahrheitswerten Wertebereich: true, false

intern in manchen Programmiersprachen als 1 bzw 0 dargestellt

Operatoren: und, oder, nicht, Vergleiche, ... Operatoren entsprechend der bool‘schen Algebra oft auch allgemeine arithmentische Operationen möglich Vorsicht vor Integer-Arithmetik mit boolean-Variablen

Notation: type booleanVar = boolean;

Beispiel: type switch = boolean;switch = false; // = 0switch = not(switch); // = not(0) = 1switch = switch and not(switch); // = 1 and 0 = 0switch = switch or not (switch); // = 0 or 1 = 1

4.3.14.3.1 Einfache: integer (Ganzzahl)Einfache: integer (Ganzzahl)

zur Darstellung ganzer Zahlen mit oder ohne Vorzeichen Wertebereich: Unterschiedlich

unsigned integer: Ganze Zahlen ohne Vorzeichen ( 0... 65535 ) oft 16 bit bzw. 32 bit als shortInt bzw. longint bezeichnet Vorsicht: 16 bit Integer ist verdammt wenig ((± 32267)

Speicherplatz ist nicht mehr teuer benutzen Sie longInt

(Ausnahmen bestätigen die Regel)

Operatoren: Grundrechenarten, Vergleiche Operatoren entsprechend der „klassischen“ Algebra

Notation: type integerVar = integer;

Beispiel: type i = integer;i = 1; // = 1i = i + 32;´ // = 1 + 32 = 33i = i / 17; // = 33 / 17 = 1 !i = i + 65535; // bei unsigned Int.: Fehler

!

4.3.14.3.1 Einfache: char (Zeichen)Einfache: char (Zeichen)

zur Darstellung von Zeichen Vorsicht: Typischerweise wird die ASCII-Codierung

zugrundegelegt,kann aber auch Unicode sein

Wertebereich: Alle Zeichen Intern codiert als ASCII oder - neuerdings immer öfter - als Unicode

ASCII: 8 Bit (7 benutzt), Unicode: 16 Bit Intern oft als integer repräsentiert

Operationen: Vergleich oft auch allgemeine arithmentische Operationen möglich Vorsicht vor Integer-Arithmetik mit boolean-Variablen

Notation: type charVar = char;

Beispiel: type symbol = char;symbol = „A“; // = „A“symbol = symbol + 32;´ // = „A“ + 32 = „a“symbol = symbol - 128; // = „a“ - 128 =

Fehler

4.3.14.3.1 Einfache: enum (Aufzählung)Einfache: enum (Aufzählung)

zur Darstellung endlicher benutzerdefinierter Wertebereich Es ist guter Stil, Mengen mit (garantiert) kleiner Mächtigkeit (<10) als

enum-Type zu deklarieren, anstatt sie z.B. als Integer zu kodieren. Intern werden enum-Werte oft als integer abgelegt

Operatoren: Vergleich oft auch allgemeine arithmentische Operationen möglich Vorsicht vor Integer-Arithmetik mit enum-Variablen

Notation: type enumVar = enum { Wertemenge };

Beispiel: type ampelfarbe = enum {rot,gelb,gruen} ;ampelfarbe = gruen; // = gruenampelfarbe = ampelfarbe +1 ; ´ // = gruen + 1 = gelbampelfarbe = ampelfarbe +1 ; ´ // = gelb + 1 = rotampelfarbe = ampelfarbe +1 ; ´ // = rot + 1 = Fehler

!

4.3.14.3.1 Einfache: real (Fließkomma)Einfache: real (Fließkomma)

zur näherungsweisen Darstellung reeller Zahlen Wertebereich: Unterschiedliche Genauigkeiten und Wertebereiche

Wertebereich entspricht typischerweise der IEEE 754 Norm, also: Float: 32 bit Double: 64 bit

Operationen: Grundrechenarten, erweiterte Arithmetik, Vergleich Notation: type realVar = real;

Beispiel: //--- Variable-declaration --------------------------

type pi, flaeche, radius = real; // all real !

//--- Initialisation --------------------------------pi = 3,141; // needs not to be more accurateradius = 5; // might be changed by user

//--- Computation of surface ------------------------flaeche = 2 * pi * (radius ^ 2); // common formula

4.3.24.3.2 Strukturierte: Array (Feld)Strukturierte: Array (Feld)

Arrays sind eine Aggregationen von Daten des gleichen Typs(des „Basistyps“)

Die Grenzen des Arrays sind (meist) statisch bestimmt

Operation: Auswahl Die Auswahl eines Datenelemtes über erfolgt über einen ganzzahligen Index

über den (Auswahl-)Operator „ [ ] “ Vorsicht: Zugriff außerhalb des deklarierten Bereiches führt zu Fehlern

Notation: type ArrayVar = array[min .. max] of Datentyp

Beispiele Eindimensionales array: type Vektor = array[1..4] of real

Zweidimensionales array: type Matrix = array[1..3] of array[1..2] of real

Operator m : Matrix; v : Vektor;v[3] <- 5,03; v[4] <- 4,12;m[1][2] <- v[3] * 12 - v[4];

4.3.24.3.2 Strukturierte: Record (Verbund)Strukturierte: Record (Verbund)

Verbunde sind Aggregationen von Daten möglicherweise unter-schiedlichen Typs

manchmals auch „structure“ oder „struct“ genannt

Operation: Auswahl Die Auswahl erfolgt durch Angabe den des Komponentennamens

(durch einen Punkt vom Variablennamen getrennt) Notation: type recordVar = record

{ komponent1 : type1; ...}

Beispiel: type Datum = record{ d : Datum; tag : Integer; d.monat <- 10; monat : Integer; d.tag <- 20; }

4.3.24.3.2 Strukturierte: Variant Record (Variantenverb.)Strukturierte: Variant Record (Variantenverb.)

Verbunde, deren Struktur mögliche Alternativen zulassen manchmals auch „union“ genannt lassen „Varianten“ eines Record-Types zu

Operation: Auswahl (wie bei records über Punkt-Operator) Notation: type varrecVar = record {

komponent1 : type1; ...; case variant (var1,...) of { var1: {Typedefs}; ... }}

Beispiel: type human = record { adam,eva:human; name : array [1..20] of char; adam.sex <- m;

case sex (m,f) of { eva.sex <- f; f: {IQ: integer}; eva.IQ <- 132; m: {muscle: real}; // in cm adam.muscle <- 20,5;}

tagged type

4.3.34.3.3 Pointer (Zeiger)Pointer (Zeiger)

Zeiger-Datentypen sind durch folgende Eigenschaften gekennzeichnet: Die Struktur ist identisch der eines Integer-Datentyp (alos oft 16,32,... Bit) Der Wertebereich ist der des Adressbereiches eines Rechnersystems,

der zusätzliche Wert „nil“ bezeichnet einen ungültigen Zeiger. Operatoren sind:

Erzeugen eines Zeigers (Referenzierung) Zugriff auf verwiesenen Bereich (Dereferenzierung)

Notation: pointerVar : ^Type;

Beispiel: x : ^Integer; // Deklarationy : Integer; z : Integer; // Deklarationen

y <- 5; // Initialisierung der Variablen y x <- ^y; // Referenzieren: x ist Zeiger auf yx^ <- 2; // Derefenzierung: das worauf x zeigt wird zu 2z <- y; // Variable z bekommt den Wert von Variable y zugewiesen.// z hat jetzt den Wert 2

Bsp.: x : ^Integer; // Deklarationy : Integer; // Deklaration

y <- 5; // Initialisierung der Variablen y

x <- ^y; // Referenzieren: x ist Zeiger auf

y

x^ <- 2; // Derefenzierung: das worauf x zeigt

x <- 2; // Zuweisung ohne Dereferenzierung !

4.3.34.3.3 Pointer: BeispielPointer: Beispiel

nil 01 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

nil 51 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

23 51 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

2 21 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

23 21 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

Vorsicht:Werte oft undefiniert

4.3.34.3.3 Pointer: Dynamische DatentypenPointer: Dynamische Datentypen

Mit einfacher Datentypen und mit den konkreten Datentypen „Liste“ und „Verbund“ lassen sich nur statische Struktur aufbauen

d.h. Strukturen, deren Speicherbedarf beliebig aber fest sind Bem.: Die Beliebigkeit ist begrenzt durch die Gesamtspeicherkapazität

Mit Zeiger-Datentypen lassen sich Strukturen aufbauen, die sich dynamisch auf- und abbbauen lassen

d.h. Strujturen, deren Speicherbedarf sich dynamisch verändern kann Bem.: Auch hier ist die Beliebigkeit begrenzt durch die Gesamtspeicher-

kapazität Beispiel: knoten = record

{ symbol : char; links : ^knoten; // 1 rechts : ^knoten; // 0}

B

C E D A

Huffman(Bsp. aus Kap.2)

4.3.44.3.4 Beispiel: Kombinierte DatentypenBeispiel: Kombinierte Datentypen

Um nun beliebig komplexe Strukturen der „realen“ Welt in einem Rechensystem abbilden zu können, kann man die vorgestellten Datentypen beliebig miteinander Kombinieren

Beispiel.:

Person : record { Date : record {

surname : array [1..20] of char; year : integer;

forename : array [1..20] of char; month : enum (jan,feb,...};

birthday : Date; day : integer;

next : ^Person; }

previous : ^Person;

}

Datenstrukturen

4.44.4 Abstrakte DatentypenAbstrakte Datentypen

Grundsätzlich lassen sich alle Objekte der realen Welt ausschließlich mit Hilfe einfacher Datentypen abbilden. Diese Abbildung ist aber meist „unnatürlich“, weil sie die Struktur realer Objekte nicht ausrei-chend berücksichtigt. Abhilfe schaffen hier strukturierte Datentypen, die allerdings grundsätzlich nur endliche Objektmengen repräsen-tieren können. Hier schaffen Zeigertypen Abhilfe.

Kann man nun mit diesen Mitteln Strukturen realer Objekt natürlich abbilden, so fehlen diesen Datentypen einige der Eigenschaften, die Datentypen von Datenstrukturen unterscheiden, dies sind insb.

Operationen und Beziehungen zu anderen Typen.

Einen vertieften Einblick in die bunte Welt abstrakter Datentypen bietet die Vorlesung des 2. Semesters

4.54.5 Zusammenfassung des KapitelsZusammenfassung des Kapitels

Wir sind damit auch an die Grenzen dessen gelangt, was in dieser Vorlesung über die „Statik“ von Objekten gesagt werden soll und wenden uns einem noch spannenderem Themenbereich zu ;-)

Datentypen

IdealisierteAbstrakteKonkrete

Einfache StrukturiertePointer(Zeiger)

Boolean(Wahrheitswert)

Integer(Ganzzahl)

Char (Zeichen)

Enumeration (Aufzählung)

Ordinale Real(Fließkomma)

Array (Feld)

Record (Verbund)

Union(Variantenverb.)

...

Übung 4.1Übung 4.1

1. Beschreiben Sie Gemeinsamkeiten und Unterschiede von „Datenstruktur“, „Datentyp“ und „Variable“.

2. Was sind die Vor- und Nachteile von Arrays gegenüber verketteten Listen

3. Definieren Sie einen Datentyp für das Objekt „Schachspiel“. Berücksichtigen Sie dabei:

1. Beide Namen der Spieler

2. Alle Züge

3. Den Gewinner

4. Betrachten Sie den Stundenplan auf meiner Homepage1. Skizzieren Sie einen Datentyp für das Objekt „Stundenpläne“

2. Welchen Speicherplatz benötigt eine Variable dieses Typs ?

3. An welchen Stellen sehen Sie Alternativen zu Ihrer Typdefinition ?