3/1, Folie 1 © 2010 Prof. Steffen Lange - HDa/FbI - Datenstrukturen Kapitel 3: Elementare Datenstrukturen / Anwendungen Gliederung 1.Motivation / Grundlagen

3/1, Folie 1 © 2010 Prof. Steffen Lange - HDa/FbI - Datenstrukturen

Kapitel 3: Elementare Datenstrukturen / Anwendungen

Gliederung

1. Motivation / Grundlagen2. Sortierverfahren3. Elementare Datenstrukturen / Anwendungen4. Bäume / Graphen5. Hashing6. Algorithmische Geometrie



Einleitung

„unser“ Blick auf Datenstrukturen

• Menge der zu verwaltenden Objekte• Menge der zu unterstützenden Operationen

... werden charakterisiert durch

• Warteschlangen (/* Queues */)• Kellerspeicher (/* Stacks */) • Prioritätswarteschlangen (/* Priority Queues */)

einfache Beispiele



• Menge von zu verwaltenden Objekten• Objekte können hinzugefügt bzw. entfernt werden• zeitliche Reihenfolge des Einfügens ist entscheidend

Aufgabenstellung

FIFO-Prinzip ... (/* first in, first out */)

LIFO-Prinzip ... (/* last in, first out */)

Warteschlange

Kellerspeicher

Implementierungsvarianten

• Array von Objekten• verkettete Liste von Objekten

Warteschlangen / Kellerspeicher



• Erzeugen einer leeren Warteschlange bzw. eines leeren Kellerspeichers(/* create(Q) bzw. create(S) */)

• Einfügen eines Objekts o in eine Warteschlange Q bzw. einen Kellerspeicher S (/* insert(Q,o) bzw. insert(S,o) */)

• Test, ob eine Warteschlange Q bzw. ein Kellerspeicher S leer ist(/* empty?(Q) bzw. empty?(S) */)

• Zugriff auf das zuerst in die Warteschlange Q bzw. das zuletzt in den Kellerspeicher S eingefügte Objekt (/* access(Q) bzw. access(S) */)

• Entfernen des zuerst in die Warteschlange Q bzw. des zuletzt in den Kellerspeicher S eingefügte Objekt (/* delete(Q) bzw. delete(S) */)

Operationen




• mindestens zwei Möglichkeiten• Möglichkeit 1 (/* implementierungsabhängig */)

• festlegen, wie die Objekte intern verwaltet werden (/* etwa mit Hilfe eines Arrays oder einer verketteten Liste */)

• „ausprogrammieren“ der Operationen

• Möglichkeit 2 (/* implementierungsunabhängig */)

• gewünschte Eigenschaften der Operationen formal beschreiben; de facto wird das „Zusammenspiel“ zwischen den Operationen festgelegt

Beschreibung der Operationen

offen: Welche Beschreibungsmittel verwendet man hier?





Randbedingungen (/* implementierungsabhängig */)

• die zu verwaltenden Objekte werden in einem Array gespeichert (/* damit ist klar, daß die Anzahl der zu verwaltenden Objekte a priori beschränkt ist */)

• über die Indizes kann man auf die aktuell verwalteten Objekte zugreifen• die Anzahl der verwalteten Objekte ist von Relevanz (/* wird sich

„gemerkt“, um die Operationen einfacher zu realisieren */)



Warteschlangen

Realisierung 1 (/* ungeschickt */)

• Array queue zum Verwalten von maximal n Objekten• Variable anz, um sich die Anzahl der verwalteten Objekte zu merken

• create(Q): Anlegen eines Arrays queue der Größe n; anz = 0

• empty?(Q): if ( anz == 0 ) return(true) else return(false)

• insert(Q,o): ++anz; queue[anz] = o

• access(Q): return(queue[1])

• delete(Q): for ( i = 1; i <= anz; ++i ) { queue[i] = queue[i+1]; };--anz

... insert(), access() und delete() bedürfen noch eines Tests auf Anwendbarkeit



Warteschlangen


• Operation delete() benötigt die Zeit O(n) • alle anderen Operationen benötigen die Zeit O(1)

Verbesserungsmöglichkeit, um alle Operationen in Zeit O(1) zu realisieren:

• der Index des zuerst gespeicherten Objekts ändert sich (/* muß sich aber explizit „gemerkt“ werden */)

5 3 2

2 5 3

(/* Realisierung 1 */)

(/* Realisierung 2 */)



Warteschlangen

Realisierung 2 (/* geschickter */)

• Array queue zum Verwalten von maximal n Objekten• Variable anz, um sich die Anzahl der verwalteten Objekte zu merken• Variable first, um sich den Index des zu erst eingefügten Objekts zu

merken

• create(Q): ...; anz = 0; first = 1

• insert(Q,o): ++anz; z = first+anz-1; if ( z <= n ) queue[z] = o else queue[z-n] = o

• delete(Q): if ( first == n) first = 1 else ++first




Warteschlangen

Beschreibung (/* implementierungsunabhängig */)


... wählen bedingte Gleichungen (/* Theorie der Abstrakte Datentypen */)

empty?(create(Q)) = trueempty?(insert(Q,o)) = false

empty?(Q) = true access(insert(Q,o)) = oempty?(Q) = false access(insert(Q,o)) = access(Q)

empty?(Q) = false delete(insert(Q,o)) = insert(delete(Q),o)empty?(Q) = true delete(insert(Q,o)) = Q



Kellerspeicher

Realisierung

• Array stack zum Verwalten von maximal n Objekten• Variable anz, um sich die Anzahl der verwalteten Objekte zu merken

• create(S): Anlegen eines Arrays stack der Größe n; anz = 0

• empty?(S): if ( anz = 0 ) return(true) else return(false)

• insert(S,o): ++anz; stack[anz] = o

• access(S): return(stack[anz])

• delete(S): --anz




Kellerspeicher

Realisierung

• alle Operationen benötigen die Zeit O(1)



Kellerspeicher

Beschreibung (/* implementierungsunabhängig */)


... wählen bedingte Gleichungen (/* Theorie der Abstrakte Datentypen */)

empty?(create(S)) = trueempty?(insert(S,o)) = false

access(insert(S,o)) = o

delete(insert(S,o)) = S



Stacks

• Realisierung rekursiver Funktionen • Auswertung arithmetischer Ausdrücke

• nur binäre Operationen• vollständig geklammerte Ausdrücke

Anwendungen von Kellerspeichern

Beispiele

Auswertung arithmetischer Ausdrücke (/* Randbedingungen */)



Stacks

Infix-Notation

(x+y)((x*y)+z)((x*(x+y))+z)

Klammern in der Infix-Notation dienen zur „Repräsentation“ von Prioritätenvon Operatoren (/* hier machen wir uns das Leben „einfacher“ */)

Postfix-Notation

xy+xy+z*xxy+*z+

Auswertung arithmetischer Ausdrücke

Grundlagen (/* Infix- versus Postfix-Notation */)



Stacks

... Auswertung gemäß Baumstruktur (/* aufbauen + auswerten */)

((x*(x+y))+z)

+

val(z)*

+

val(y)val(x)

val(x)


Auswertung eines arithmetischen Ausdrucks in Infix-Notation



Stacks


Aufgabenstellung

• gegeben ein vollständig geklammerter arithmetischer Ausdruck in Infix-Notation (/* falls nicht, so müssen die Klammern gemäß der Prioritäten der Operatoren eingefügt werden */)

• gesucht ist der Wert des Ausdrucks (/* ... die Werte der auftretenden Variablen sind bekannt */)

Herangehensweise

• Schritt 1: Umwandlung von Infix-Notation in Postfix-Notation• Schritt 2: Auswertung des Ausdrucks in Postfix-Notation



Stacks

von links nach rechts durchlaufen; unter Verwendung eines Stacks auswerten

2 2 2 2 10 10 11

2 2 5 1

3


Auswertung eines arithmetischen Ausdrucks in Postfix-Notation

2 2 3 + * 1 +

Ausgabe: 11

Auszuwertender Ausdruck: ((2*(2+3))+1)



Stacks

von links nach rechts durchlaufen; unter Verwendung eines Stacks auswerten

a a a a d d f

a a c e

b

a = val(x)b = val(y)

e = val(z)f = d+e

c = a+bd = a+c

Abkürzungen:


Auswertung eines arithmetischen Ausdrucks in Postfix-Notation

x x y + * z +

Ausgabe: f

Auszuwertender Ausdruck: ((x*(x+y))+z)



Stacks

• führe create(S) aus• arithmetischen Ausdruck von links nach rechts durchlaufen

• falls das aktuelle Zeichen z ein Operand ist, so führe insert(S,val(z)) aus

• falls das aktuelles Zeichen z ein Operator ist, so bestimme a = access(S), führe delete(S) aus, bestimme b = access(S), führe delete(S) aus, berechne c = z(a,b) und führe insert(S,c) aus

• falls der Ausdruck vollständig gelesen wurde, so gib access(S) aus


Regeln für Schritt 2



Stacks

* * * * * * + +

+ +

Ausgabe:


von links nach rechts durchlaufen; unter Verwendung eines Stacks ausgeben

Umwandlung von Infix-Notation in Postfix-Notation

x x y + * z +

( ( x * ( x + y ) ) + z )



Stacks

• führe create(S) aus• arithmetischen Ausdruck von links nach rechts durchlaufen

• falls das aktuelle Zeichen z das Zeichen “(“ ist, so ignoriere z • falls das aktuelle Zeichen z ein Operand ist, so gebe z aus• falls das aktuelle Zeichen z ein Operator ist, so führe

insert(S,z) aus• falls das aktuelles Zeichen z das Zeichen “)“ ist, so bestimme

y = access(S), gib y aus und führe delete(S) aus


Regeln für Schritt 2



Stacks

Prioritätswarteschlangen

• Menge von zu verwaltenden Objekten, wobei jedem Objekt eine „Priorität“ zugeordnet ist

• Objekte können hinzugefügt bzw. entfernt werden • in der verwalteten Menge will man schnell ein Objekt mit der

höchsten Priorität bestimmen können

Aufgabenstellung

... betrachten Varianten der Realisierung mit Hilfe eines Arrays, d.h. die Anzahl der zu verwaltenden Objekte ist a priori begrenzt



Stacks


Operationen

• Erzeugen einer leeren Prioritätswarteschlange P(/* create(P) */)

• Einfügen eines Objekts o in eine Prioritätswarteschlange P(/* insert(P,o) */)

• Zugriff auf ein Objekt in der Prioritätswarteschlange P mit minimaler Priorität, wobei dieses Objekt gleichzeitig aus P gestrichen werden soll (/* acc_del(P) */)

• Erzeugen einer Prioritätswarteschlange P, die alle Objekte einer Objektmenge O enthält (/* init(P,O) */)



Stacks


Anwendungen

• Steuerung von Druckerwarteschlangen (/* den Benutzern werden Gruppen zugeordnet, ... */)

• als zugrunde liegende Datenstruktur diverser Algorithmen (/* sehen wir später */)



Stacks



• Array pqueue zum Verwalten von maximal n Objekten• Variable anz, um sich die Anzahl der verwalteten Objekte zu merken

• create(P): Anlegen eines Arrays pqueue der Größe n; anz = 0

• insert(P,o): ++anz; pqueue[anz] = o

• acc_del(P): bestimme i mit p(pqueue[i]) ist maximal;return(queue[1]);for ( j = i; j < anz; ++j ) { pqueue[j] = pqueue[j+1]; }; --anz

• init(P,O): führe erst create(P) und dann „nacheinander“ für jedes Objekt o O die Operation insert(P,o) aus

... insert(), acc_del() und init() bedürfen noch eines Tests auf Anwendbarkeit



Stacks



• Operationen create(P) und insert(P,o) gehen in Zeit O(1)• Operationen acc_del(P) und init(P,O) benötigen Zeit O(n)

Verbesserungsmöglichkeit

• Array pqueue zum Verwalten von maximal n Objekten• Variable anz, um sich die Anzahl der verwalteten Objekte zu merken• das Array pqueue, in dem die Objekte verwaltet werden, bildet einen

Heap (/* Ordnung der Objekte bzgl. der zugehörigen Prioritäten */)



Stacks


Beispiel

• O = { a,b,c,d,e,f,g } • p(a) = p(g) = 5, p(b) = 1, p(c) = p(e) = p(f) = 3, p(d) = 2

a

e g

d b f c

Ein Knoten o mit den Söhnen ol und or hat die Heap-Eigenschaft, falls p(o) ≥ p(ol) und p(o) ≥ p(or) gilt.

... jeder Knoten muß die Heap- Eigenschaft haben

a e g d b f c



insert()-Operation

• ++anz; pqueue[anz] = o• auf dem Weg von pqueue[1] zu pqueue[anz] das neue Objekt o an

die richtige Position „steigen“ lassen

... geht in Zeit O(log(n))


a

g f

c e b

a

g f

c e b d

d

g a

c e b f

a g f c e b a g f c e b d d g a c e b f




acc_del()-Operation

• y = pqueue[1]; pqueue[1] = pqueue[anz]; --anz• Objekt an Position pqueue[1] an die richtige Position „sinken“ lassen;

return(y)

... geht in Zeit O(log(n))

a e g d b f c


a

e g

d b f c

c

e g

d b f

g

e c

d b f

c e g d b f g e c d b f




init()-Operation

• Array pqueue mit allen Objekten in O initialisieren (/* ohne die Ordnung bzgl. der Prioritäten zu beachten */)

• Array pqueue wie in Phase 1 von HeapSort in einen Heap überführen (/* Ordnung absteigend bzgl. der Prioritäten */)

... geht in Zeit O(n)

a b c d e f g d a g b e f c



a

b c

d e f g

d

a g

b e f c

Documents

3/1, Folie 1 © 2010 Prof. Steffen Lange - HDa/FbI - Datenstrukturen Kapitel 3: Elementare Datenstrukturen / Anwendungen Gliederung 1.Motivation / Grundlagen