kap8a.pps - Lehrstuhl 11 Algorithm Engineering

 Documents

 37 views
of 20
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
Wintersemester 2006/07 Einführung in die Informatik für Naturwissenschaftler und Ingenieure (alias Einführung in die Programmierung) (Vorlesung) Prof. Dr.…
Share
Transcript
Wintersemester 2006/07 Einführung in die Informatik für Naturwissenschaftler und Ingenieure (alias Einführung in die Programmierung) (Vorlesung) Prof. Dr. Günter Rudolph Fachbereich Informatik Lehrstuhl für Algorithm Engineering Kapitel 8: Abstrakte Datentypen Inhalt ● Definition ● ADT Keller mittendrin: Exkurs ● ADT Schlange „Dynamischer Speicher“ ● ADT Liste ● ADT Binärbaum ● … Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 2 Kapitel 8: Abstrakte Datentypen Definition: Abstrakter Datentyp (ADT) ist ein Tripel (T, F, A), wobei ● T eine nicht leere Menge von Datenobjekten ● F eine Menge von Operationen, ● A eine nicht leere Menge von Axiomen, die die Bedeutung der Operationen erklären. ■ Abstrakt? ● Datenobjekte brauchen keine konkrete Darstellung (Verallgemeinerung). ● Die Wirkung der Operationen wird beschrieben, nicht deren algorithmische Ausprägung. → „WAS, nicht WIE!“ Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 3 Kapitel 8: Abstrakte Datentypen Beispiel: ADT bool F: Operationen true : → bool false : → bool Festlegung, welche not : bool → bool Funktionen es gibt and : bool x bool → bool or : bool x bool → bool A: Axiome not(false) = true not(true) = false and(false, false) = false Festlegung, was die and(false, true) = false Funktionen bewirken and(true, false) = false and(true, true) = true or(x, y) = not(and(not(x), not(y))) Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 4 Kapitel 8: Abstrakte Datentypen Eigenschaften ● Wenn man ADT kennt, dann kann man ihn überall verwenden. ● Implementierung der Funktionen für Benutzer nicht von Bedeutung. ● Trennung von Spezifikation und Implementierung. ● Ermöglicht späteren Austausch der Implementierung, ohne dass sich der Ablauf anderer Programme, die ihn benutzen, ändert! Nur Operationen geben Zugriff auf Daten! → Stichwort: Information Hiding! Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 5 Kapitel 8: Abstrakte Datentypen Lineare Datenstrukturen: Keller bzw. Stapel (engl. stack) create : → Keller Aufräumen: push : Keller x T → Keller Kiste in Keller, pop : Keller → Keller oben auf Haufen. top : Keller →T Etwas aus Keller holen: empty : Keller → bool Zuerst Kiste, weil oben auf Haufen. empty(create) = true Stapel empty(push(k, x)) = false Teller pop(push(k, x)) = k top(push(k, x)) =x LIFO: Last in, first out. Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 6 Kapitel 8: Abstrakte Datentypen Implementierung: (Version 1) const int maxSize = 100; struct Keller { T data[maxSize]; // data array int sp; // stack pointer }; void create(Keller &k) { T top(Keller k) { k.sp = -1; return k.data[k.sp]; } } bool empty(Keller k) { void push(Keller &k, T x){ return k.sp == -1; k.data[++k.sp] = x; } } void pop(Keller &k) { k.sp--; Probleme: } Arraygrenzen! Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 7 Kapitel 8: Abstrakte Datentypen Wann können Probleme auftreten? Bei pop, falls Keller leer ist: → Stackpointer wird -2, anschließendes push versucht auf data[-1] zu schreiben Bei top, falls Keller leer ist: → es wird undefinierter Wert von data[-1] zurückgegeben Bei push, falls Keller voll ist: → es wird versucht auf data[maxsize] zu schreiben ) diese Fälle müssen abgefangen werden! Fehlermeldung! void error(char *info) { gibt Fehlermeldung info aus und bricht cerr << info << endl; das Programm durch exit(1) sofort ab exit(1); und liefert den Wert des Arguments (hier: 1) } an das Betriebssystem zurück Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 8 Kapitel 8: Abstrakte Datentypen Implementierung: (Version 2, nur Änderungen und Zusätze bei Funktionen) const int maxSize = 100; struct Keller { T data[maxSize]; // data array unverändert int sp; // stack pointer }; T top(Keller k) { void push(Keller &k, T x){ if (!empty(k)) if (!full(k)) return k.data[k.sp]; k.data[++k.sp] = x; else error(“leer“); else error(“voll“); } } void pop(Keller &k) { bool full(Keller k) { if (!empty(k)) k.sp--; return k.sp == maxSize-1; else error(“leer“); } } Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 9 Kapitel 8: Abstrakte Datentypen Lineare Datenstrukturen: Schlange (engl. queue) FIFO: First in, first out. create : → Schlange Schlange an der enq : Schlange x T → Schlange Supermarktkasse: deq : Schlange → Schlange front : Schlange →T Wenn Einkauf fertig, empty : Schlange → bool dann hinten anstellen. Der nächste Kunde an der Kasse steht ganz vorne in der Schlange. empty(create) = true empty(enq(s, x)) = false Eingehende Aufträge deq(enq(s, x)) = empty(s) ? s : enq(deq(s), x) werden „geparkt“, und front(enq(s, x)) = empty(s) ? x : front(s) dann nach und nach in der Reihenfolge des Eingangs abgearbeitet. Rudolph: EINI (WS 2006/07) ● Kap. 8: Abstrakte Datentypen 10 Kapitel 8: Abstrakte Datentypen Implementierung: (Version 1) const int maxSize = 100; struct Schlange { T data[maxSize]; // data array int ep; // end pointer }; void create(Schlange &s){ void enq(Schlange &s, T x) { s.ep = -1; s.data[++s.ep] = x; } } bool empty(Schlange s) { void deq(Schlange &s) { return s.ep == -1; for (int i=0; i
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