Eigentlich eine simple Frage könnte man meinen, aber mich bringt sie immer noch zum nachdenken:
Was ist genau ein ADT und was eine dyn. Datenstruktur? Wo ist der Unterschied? Kann man sich überhaupt sauber trennen?
Meine Vermutung:
eine ADT ist eine Spezifikation einer dyn. Datenstruktur und ist daher implementationsunabhängig. Die ADT ist eine Zusammenfassung von Wertebereichen und Operationen uf diesen Wertebereichen.
Wie kann eine dyn. Datenstrukutr genau def. werden bzw. ist die obere Definion ohne Fehler?
Suchfunktion liefert 2 alte Topics zu 'ADT', vielleicht stehts da ja,
ich jedenfalls hab damals nie so wirklich den Unterschied erkannt ;)
also ich denke mal der unterschied ist, dass eine dynamische datenstruktur die implementation mit einbezieht.
bei z.b. einem adt menge kann man ja garnicht sagen oder der nun in einer einer statischen oder dynamischen datenstruktur implementiert wird. (S. I-28 ist ein adt set mit einer statischen datenstruktur und S. I-30 als dynamische datenstruktur)
Interessant ist auch der UNterschied zwischen Datentyp und abstraktem Datentyp.
[img]
http://www.fb18.de/gfx/google.gif[/img] ist your friend:
Als Abstrakte Datentypen bezeichnet man in der Informatik spezielle Datentypen, deren Operationen genau spezifiziert sind, die jedoch im Gegensatz zu den elementaren und zusammengesetzten Datentypen nicht an einen konkreten Wertebereich gebunden sind. Die Bindung an den Wertebereich findet erst durch die konkrete Ausprägung des abstrakten Datentypen statt.
Quelle:
http://www.computerbase.de/lexikon/Abstrakter_DatentypEin ADT besteht aus:
- einer Menge von Objekten, und
- einem Satz von Operationen auf dieser Menge, sowie
- einer genauen Beschreibung der Semantik der Operationen.
Das Konzept des ADT ist unabhängig von einer Programmiersprache, die Beschreibung kann in natürlicher Sprache abgefasst werden.
Der ADT beschreibt was die Operationen tun, aber nicht wie sie das tun. Getreu dem Prinzip der versteckten Information ist die Realisierung nicht Teil des ADT.
Quelle:
http://hal.iwr.uni-heidelberg.de/lehre/inf1-ws02/html/node67.htmlWer es formal mag findet hier 1-2 Screens nach unten was:
http://ivs.cs.uni-magdeburg.de/~dumke/EAD/Skript29.html
Ich würde mich einfach mal auf die Wortbestandteile beziehen:
Dynamische Datenstruktur klingt für mich sehr nach einer Struktur, die zur Laufzeit beliebige Ausprägungen im Speicher annehmen kann (etwa wie java.util.ArrayList, im Gegensatz zu structs in C).
Ein ADT ist ein durch Constraints definiertes Verhalten beschriebener Datentyp. Damit wäre nur das Verhalten beschrieben, die genaue Implementation steht an der Stelle noch aus.
Edit: Mist, da war wer schneller [img]
http://www.fb18.de/gfx/24.gif[/img]
@fred: [img]
http://www.fb18.de/gfx/google.gif[/img] unter "Mehr Smilies"
Was ist genau ein ADT und was eine dyn. Datenstruktur? Wo ist der Unterschied? Kann man sich überhaupt sauber trennen?
Ich frage mich eher, wo die Gemeinsamkeiten zwischen ADTs und dynamischen Datentrukturen sein sollen? [img]
http://www.fb18.de/gfx/28.gif[/img]
Sicherlich, bei der Realisierung einiger ADTs kann man dynamische Datenstrukturen benutzen. Aber viele ADTs kann man auch ohne sie implementieren und dynamische Datenstrukturen kann man für alles mögliche benutzen.
In der Gegenrichtung kann man noch feststellen, daß sich das Verhalten von dynamische Datenstrukturen als ADT beschreiben läßt. Aber man kann auch statische Datenstrukturen als ADT beschreiben.
gemeinsamkeit:
beide wurden in p3 erwähnt aber nie richtig geut definiert (also im script)
eine dynamische datenstruktur is doch zB das, was ein array *nicht* ist… nämlich zur laufzeit in ihrer größe veränderbar