end

 Datenstruktur

 39 views
of 37
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Kapitel 5: Von Datenstrukturen zu Abstrakten Datentypen 5.1 Zur Erinnerung: Datenstrukturen in Pascal Listenverarbeitung in Pascal 5.2 Abstrakte Datentypen und…
Share
Transcript
Kapitel 5: Von Datenstrukturen zu Abstrakten Datentypen 5.1 Zur Erinnerung: Datenstrukturen in Pascal Listenverarbeitung in Pascal 5.2 Abstrakte Datentypen und Objektorientierung Brüche als ADT Implementierung - objektorientiert Brüche als ADT Implementierung - funktional 5.3 Geordnete lineare Zusammenfassungen: Listen bzw. Folgen Cons-Zelle als Basisklasse Statisch-funktionale Listenimplementierung Listenimplementierung mit Objektmethoden 5.4 Stacks und Queues Zustandsorientierte Stack-Implementierung 5.5 Find and Merge 5.5.1 Implementierungen 5.5.2 Implementierung mit Bäumen 5.6 Priority Queues 1 Eigenschaften von Typ-Konstruktoren in Pascal: (nicht in Java) Array (Feld) Record (Verbund) Set (Menge) Vereinbarung S: Array [N .. S: Record S: Set of T N + k-1] of T F1: T1;... ; Fn: Tn end Selektor S[i] S.Fi Zugriff Index Feldname Enthalten-Test Kardinalität #(T) k #(T1) • ... • #(Tn) 2 #(T) 2 Für in der Tabelle aufgeführte Datentypen: jeweils ein fester Speicherbedarf. Rekursive Datenstrukturen: Speicherbedarf kann sich ändern! Muss dynamisch zugewiesen (und freigegeben werden). Rekursive Datenstrukturen in Pascal: realisiert durch Zeigertypen 3 Rekursive Datenstrukturen als Zeiger-Typen in Pascal: Typdefinition: type S = ^T (Zeiger auf Elemente vom Typ T) nil : ausgezeichneter Wert, steht für eine leere (terminierende) Belegung eines beliebigen Zeigertyps. Dereferenzierung: Ist z eine Zeigervariable, so ist z^ der Inhalt der durch die Variable repräsentierten Speicheradresse. Der aktuelle Wertebereich des Typs T ist die Menge aller bisherigen Adressen von T-Variablen ergänzt um nil. 4 Rekursive Datenstrukturen als Zeiger-Typen in Pascal: Variablendeklaration: var p: T Initialisierung einer T-Variablen: new(p) new(p) erzeugt eine neue (unbenannte) Variable vom Typ T und stellt den benötigten Speicher bereit. 5 Speicher-Allokation Beispiel 1: Stammbaum und Instantiierung: new(p); Grundelement: p^.Name := "Franz"; type Person = p^.Vater := nil; RECORD p^.Mutter := nil; Name: String; Vater, Mutter:^Person new(q); END; q^.Name := "Georg"; q^.Vater := nil; q^.Mutter := nil; Deklaration und (leere) p^.Vater := q; Initialisierung: new(q); var p,q: ^Person; q^.Name := "Maria"; q^.Vater := nil; p := nil; q := nil; q^.Mutter := nil; 6 p^.Mutter := q; Speicherfreigabe: • In Java: garbage collector. • In Pascal: kein garbage collector. Stattdessen: explizit mittels dispose, z.B.: dispose(p^.Vater); dispose(p^.Mutter); 7 Beispiel 2: Algebraische Ausdrücke Deklaration: Wieso nicht einfach ... type TermRef = ^Term; type ExprRef = ^Expr; type ExprRef = ^OpExpr; type Expr = RECORD type OpExpr = Op: Operator; RECORD Opd1, Opd2: ExprRef Op: Operator; END; Opd1, Opd2: TermRef END; type Term = RECORD case Atomic: Boolean of true: (Atom: Symbol); false: (SubExpr: ExprRef) 8 END; Beispiel 3: Listen-Verarbeitung in Pascal: program list1; type NString = String[20]; Pos = integer; List = ^El; El = Record Content: NString; Id: Pos; Succ: List end; 9 var L1,L2: List; LastPos: integer; Com: String; function isempty(L: List) : boolean; begin isempty := (L=nil) end; procedure newlist(var L: List); begin new(L); LastPos := 0; L := nil end; 10 procedure cons(var L: List; Name: NString); var X: List; begin new(X); X^.Content := Name; procedure lcons(var L: List; X^.Id := LastPos+1; Name: NString); X^.Succ := L; var X,Y: List; L := X; begin LastPos := LastPos+1; new(X); end; X^.Content := Name; X^.Id := LastPos+1; X^.Succ := nil; if isempty(L) then L := X else begin new(Y); Y := L; while NOT ( Y^.Succ = nil ) do Y := Y^.Succ; Y^.Succ := X end; LastPos := LastPos+1; end; 11 procedure delete(var L: List; Posit: Pos); var X,Y: List; begin Y := L; if isempty(Y) then (* empty *) else if isempty(Y^.Succ) AND (Y^.Id = Posit) then L := nil else begin while NOT ( ( Y^.Id = Posit ) OR ( Y^.Succ^.Succ = nil ) ) do Y := Y^.Succ; if Y^.Id = Posit then begin X:= Y^.Succ; Y^ := X^ end else if (Y^.Succ^.Succ = nil) then if Y^.Succ^.Id = Posit then begin X := Y^.Succ; Y^.Succ := nil; dispose(X) end else (* empty *) end end; 12 5.2 Abstrakte Datentypen und Objektorientierung Abstrakter Datentyp (ADT): Implementierungsunabhängige Spezifikation von Datenstrukturen. (analog zur implementierungsunabhängigen Beschreibung von Algorithmen) Zwei Methoden der ADT-Spezifikation: die algebraische und die axiomatische. Sie haben gemeinsam: die Angabe der Signatur. 13 Signatur legt fest: • Sorten (Objektmengen), • Operationen, inbesondere, was für Objekte Eingabe und Ausgabe der Operationen sind. Die Signatur definiert die Syntax und Typstruktur einer Datenstruktur. 14 Beispiel: Menge ganzer Zahlen (IntSet) Signatur: algebra (bzw. adt) IntSet sorts IntSet, int, boolean ops emptySet:  IntSet insertEl: int x IntSet  IntSet deleteEl: int x IntSet  IntSet member: int x IntSet  boolean isEmpty: IntSet  boolean 15 Operationale Semantik: Algebraische Spezifikation gibt als Semantik Algebren an, also Mengen (Semantik der Sorten) mit Funktionen (Semantik der Operationen). sets IntSet = {S | S Teilmenge von Z, S endlich} functions emptySet() := {} insertEl(x,S) := {x}  S deleteEl(x,S) := S \ {x} member(x,S) := true falls x in S, false sonst isEmpty(S) := ( S={} ) end IntSet. 16 Operationale Semantik: Axiomatische Methode spezifiziert die Semantik der Operationen über Axiome (als Postulate): axioms isEmpty(emptySet()) = true isEmpty(insertEl(x,S)) = false (für alle x, S) insertEl(x,insertEl(x,S)) = insertEl(x,S) (dito) member(x,insertEl(x,S)) = true (dito) member(x,deleteEl(x,S)) = false (dito) insertEl(x,deleteEl(x,S)) = insertEl(x,S) (dito) member(x,insertEl(y,S)) = true (für x <> y, alle S) ... 17 Axiomatische Methode Vorteile: • Man muss nur soviel festlegen, wie nötig (gibt Freiheit bei der Implementierung). Beachte: Zu einem axiomatisch spezifizierten Datentyp kann es mehrere verschiedene Algebren geben, die alle Axiome erfüllen (polymorpher Datentyp). • Präzise Sprache: ermöglicht evtl. formale Verifikation der Spezifikation. Nachteile • Bei größeren Anwendungen: sehr viele Axiome. • Spezifikation anhand von Axiomen oft schwer zu verstehen. • Charakterisierung einer gewünschten Datenstruktur durch Axiome oft schwer (Widerspruchsfreiheit und Vollständigkeit der Axiome). 18 Abbildung von ADT-Spezifikationen in Programmiersprachen: Kapselung: In einer ADT-Spezifikation werden zugleich Datentypen und Operationen spezifiziert Operationen sind damit an den Typ gebunden. Daher möglich: Überladung: ein und derselbe Operator kann je nach Typ unterschiedlich implementiert sein. Diese Aspekte finden sich unmittelbar in objektorientierten Programmiersprachen. 19 Beispiel: Brüche als abstrakte Datentypen Algebraische Spezifikation: algebra Fract sorts Fract, int ops initFract: int x (int \ {0})  Fract normFract: Fract  Fract addFract, multFract, ...: Fract x Fract  Fract sets Fract = {F=(z,n) | z aus Z, n aus Z \ {0}} functions initFract(x,y) := (x,y) normFract(F) := ... end Fract. 20 Implementierung von Brüchen in Java: Alternativen: • Statisch-funktional: z.B. public static FractionB add(FractionB f1, FractionB f2) {…} • Objektorientiert: z.B. public FractionA add(FractionA f2) {…} Der Bruch f1 wird hier implizit verwendet (explizit mittels this) 21 5.3 Geordnete lineare Zusammen- fassungen: Listen bzw. Folgen Listen: endliche Folgen. Unterschied zu Mengen: • Es gibt eine Reihenfolge der Elemente. • Ein Element kann auch mehrfach vorkommen. Nebenbei: es gibt auch noch Multisets. Bei ihnen gibt es keine Reihenfolge, aber ein Element kann mehrfach vorkommen. 22 Implementierung von Listen mittels: • statischer Speicherstrukturen: Array Vorteil: - Zugriff auf einzelne Elemente in Zeit O(1). Nachteile: - Listengröße durch Arraygröße beschränkt. - Speicherbedarf: bedingt durch Arraygröße, nicht die tatsächliche (meistens kleinere!) Größe der Liste • dynamischer Speicherstrukturen: Zeigerstrukturen. Vorteile: - Beliebig große Listen möglich, Größenänderung während des Programmablaufs kein Problem. - Speicherbedarf: nur der wirklich von der Liste benötigte Platz ((n)). Nachteil: - Zugriff auf einzelne Elemente im Schnitt in Zeit (n). 23 Aufwandsvergleich für Listen als Array bzw. einfach verkettete Zeigerstruktur: Operation Array Einfach verkettete Liste Vorn anfügen O(n) O(1) Hinten anfügen O(1) O(n) Konkatenation mit O(m) O(k) |Liste1|=k, |Liste2|=m Element-Suche O(n) O(n) • Im Array vorn anfügen kostet O(n). Grund: man muss alles verschieben! 24 Eine Signatur für Listen algebra List sorts List, El, boolean ops emptyList:  List first: List  El rest (bzw. butFirst): List  List cons (bzw. insertFirstEl): El x List  List null (bzw. isEmpty): List  Boolean Die folgenden Operationen kann auf die oben angegebenen Operationen zurückgeführt werden: member: El x List  boolean concat (bzw. appendList): List x List  List 25 Algebraische Spezifikation der Semantik: sets list = { (a1,…,an) | n  0, ai aus El} functions emptyList = nil first(a1…an) = a1, falls n  1, undefiniert, falls n=0 rest(a1…an) = (a2…an), falls n  1, undefiniert, falls n=0 cons(b, a1…an) = (b a1…an) null(a1…an) = (n=0) concat(a1…an, b1…bm) = (a1,…,an b1…bm) member(b, a1…an) = true, falls es ein i gibt mit ai=b, false sonst 26 Einfach verkettete Listen in Java: Zuerst: Definition der Klasse einer Cons-Zelle (bestehend aus einem Wert und einem Zeiger auf eine Cons-Zelle). class PCell { private Object elem; private PCell succ; // Konstruktor: PCell(Object c) { elem = c; succ = null; } // Selektor- und Modifikator-Methoden: public Object getEl() { return this.elem; } public void setEl(Object c) { this.elem = c; } public PCell getSucc() { return this.succ; } public void setSucc(PCell next) { this.succ = next; } 27 Implementation Dann: Implementation gemäß der Signatur. Das geht • statisch-funktional public static LiLiS insertFirstEl(Object El, LiLiS L) { PCell h = new PCell(El); if (! isEmpty(L) ) h.setSucc(L.head); return new LiLiS(h); } • objektorientiert public LiLiO insertFirstEl(Object El) { PCell h = new PCell(El); if (! this.isEmpty() ) h.setSucc(this.head); return new LiLiO(h); } 28 Doppelt verkettete Listen Zur effizienteren Implementierung von last und concat: doppelt verkettete Listen: 29 InsertFirstEL in DoLi public static DoLiS insertFirstEl(Object El, DoLiS L) { DoLiS R; DCell h,cf; h R = new DoLiS(L); h = new DCell(El); cf=a1 cf = R.head.getSucc(); R.head.setSucc(h); h.setPred(R.head); h.setSucc(cf); if (cf!=R) cf.setPred(h); R else R.head.setPred(h); return R; } 30 5.4 Stacks und Queues Stacks (Keller) und Queues (Warteschlangen): Datenstrukturen, die zur dynamischen, reihenfolgeabhängigen Verwaltung beliebiger Elemente dienen. Stacks: LIFO-Prinzip ("last in - first out") Queues: FIFO-Prinzip ("first in - first out") Beide: Spezialfälle von Listen 31 Stacks: LIFO Die Grundoperationen auf einem Stack entsprechen den bereits definierten Listenoperationen: • top  first • push  insertFirstEl • pop  butFirst 32 Stacks: axiomatische ADT-Spezifikation: adt Stack sorts Stack, El, boolean ops emptyStack:  Stack top: Stack  El pop: Stack  Stack push: El x Stack  Stack isEmpty: Stack  Boolean axioms isEmpty(emptyStack()) = true isEmpty(push(x,S)) = false pop(emptyStack())  error top(emptyStack())  error pop(push(x,S)) = S top(push(x,S)) = x not isEmpty(S) => push(top(S),pop(S)) = ???33 end Implementierung von Stacks: // Basis-Methoden: public Object top() { • Man kann return this.head.getEl(); } Implementierungen von public Object pop() { Listen verwenden. Object t = this.top(); this.head = this.head.getSucc(); • Meistens: return t; } objektorientiert (Objekte public void push(Object El) mit { PCell h1 = new PCell(El); h1.setSucc(this.head); Zustandsänderungen). this.head = h1; } Z.B. pop: ohne public boolean isEmpty() Rückgabe, vgl. Skript. { return (this == null || this.head==null); } 34 Anwendungen von Stacks Unterstützung von Kontrollstrukturen, z.B. • Auswertung algebraischer Ausdrücke, • Verwaltung geschachtelter Prozeduraufrufe, speziell bei rekursiven Prozeduren. 35 Queue (Warteschlange): FIFO Die Grundoperationen auf einer Queue: • front  first • enqueue  hänge ein Element hinten an • dequeue  butFirst 36 Queues: Axiomatische ADT-Spezifikation adt Queue sorts Queue, El, boolean ops emptyQueue:  Queue front: Queue  El dequeue: Queue  Queue enqueue: El x Queue  Queue isEmpty: Queue  Boolean axioms isEmpty(emptyQueue()) = true isEmpty(enqueue(x,Q)) = false isEmpty(Q) => front(enqueue(x,Q)) = x isEmpty(Q) => dequeue(enqueue(x,Q)) = Q not isEmpty(Q) => front(enqueue(x,Q)) = ??? not isEmpty(Q) => dequeue(enqueue(x,Q)) = ??? end 37
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks