Articles

Abstrakte Datenstrukturen

by admin

Abstrakte Datentypen

In der Informatik ist ein abstrakter Datentyp (ADT) ein mathematisches Modell für Datentypen, bei dem ein Datentyp durch sein Verhalten (Semantik) aus der Sicht eines Benutzers des daten, insbesondere in Bezug auf mögliche Werte, mögliche Operationen an Daten dieses Typs und das Verhalten dieser Operationen. Dies steht im Gegensatz zu Datenstrukturen, die konkrete Darstellungen von Daten sind und die Sicht eines Implementierers und nicht eines Benutzers sind.Formal kann ein ADT als eine „Klasse von Objekten definiert werden, deren logisches Verhalten durch eine Menge von Werten und eine Menge von Operationen definiert wird“; Dies ist analog zu einer algebraischen Struktur in der Mathematik. Was mit „Verhalten“ gemeint ist, variiert je nach Autor, wobei die beiden Haupttypen formaler Spezifikationen für das Verhalten axiomatische (algebraische) Spezifikationen und ein abstraktes Modell sind; diese entsprechen der axiomatischen Semantik bzw. der Betriebssemantik einer abstrakten Maschine. Einige Autoren schließen auch die Rechenkomplexität („Kosten“) ein, sowohl in Bezug auf Zeit (für Rechenoperationen) als auch auf Raum (für die Darstellung von Werten).

Der Grund, warum wir abstrakte Strukturen verwenden, ist, dass sie den Speicher effizient nutzen, basierend auf dem Design der darin gespeicherten Daten. Bei sehr großen Datenmengen oder sehr häufig wechselnden Daten kann die Datenstruktur einen großen Unterschied in der Effizienz (Laufzeit) Ihres Computerprogramms ausmachen. In einer allgemeineren Sprache ist eine abstrakte Datenstruktur nur eine Anordnung von Daten, die wir in eine geordnete Anordnung eingebaut haben.

Ein sehr schöner Überblick

Einige Arten von abstrakten Datenstrukturen

Vom IB bewertet

  1. statische und dynamische Datenstruktur
  1. Arrays
  2. zweidimensionale Arrays
  3. Stapel
  4. Warteschlange
  5. verknüpfte Liste
  6. Baum
  7. Binärbaum
  8. Sammlungen
  9. Rekursion

NICHT vom IB bewertet, aber Sie sollten sie kennen

  1. Listen
  2. Wörterbücher
  3. sets
  4. Tupel

Grundlegende Operationen von Datenstrukturen

Ich habe diese hervorragende Folie von Simon Allardice gefunden.

Grundlegende Operationen von Arrays.png

Vergleich verschiedener Datenstrukturen

Datenstruktur Stärken Schwächen
Arrays Einfügen und Löschen von Elementen, Iterieren durch die Sammlung Sortieren und Suchen, Einfügen und Löschen – besonders wenn Sie am Anfang oder am Ende des Arrays einfügen und löschen
verknüpfte Liste direkte Indizierung, Einfach zu erstellen und zu verwenden direkter Zugriff, Suchen und Sortieren
Stapel und Warteschlange entwickelt für LIFO / FIFO direkter Zugriff, Suchen und Sortieren
Binärbaum Geschwindigkeit des Einfügens und Löschens, Geschwindigkeit des Zugriffs, Aufrechterhaltung der sortierten Reihenfolge etwas Overhead

  • Feste Strukturen sind schneller / kleiner
  • Wenn Sie überlegen, ob Sie eine abstrakte Datenstruktur verwenden sollten, sollten Sie sich fragen: Was enthält die meisten Daten und was enthält die am häufigsten geänderten Daten?

Vergleich von statischen und dynamischen Datenstrukturen

Dieser Vergleich wird aus unserem Informatik-Lehrbuch verwendet.

Statische Datenstruktur Dynamische Datenstruktur
Ineffizient, da Speicher zugewiesen wird, der möglicherweise nicht benötigt wird. Effizient, da die Speichermenge je nach Bedarf variiert.
Schneller Zugriff auf jedes Datenelement, da der Speicherort beim Schreiben des Programms festgelegt ist. Langsamerer Zugriff auf jedes Element, da der Speicherplatz zur Laufzeit zugewiesen wird.
Zugewiesene Speicheradressen sind zusammenhängend, sodass schneller darauf zugegriffen werden kann. Zugewiesene Speicheradressen können fragmentiert sein, so dass der Zugriff langsamer ist.
Strukturen haben eine feste Größe, wodurch die Arbeit vorhersehbarer wird. Sie können beispielsweise einen Header enthalten. Strukturen variieren in der Größe, daher muss ein Mechanismus vorhanden sein, um die Größe der aktuellen Struktur zu kennen.
Die Beziehung zwischen verschiedenen Datenelementen ändert sich nicht. Die Beziehung zwischen verschiedenen Datenelementen ändert sich, wenn das Programm ausgeführt wird.

Auswählen der zu verwendenden Datenstruktur

Diese Grafik wird mit großer Dankbarkeit von der Informatikabteilung der Dartford Grammar School verwendet.

Auswahl eines Datentyp-Flussdiagramms.png

Standards

  • Identifizieren Sie eine Situation, die die Verwendung von rekursivem Denken erfordert.
  • Identifizieren Sie rekursives Denken in einer bestimmten Problemlösung.
  • Verfolgt einen rekursiven Algorithmus, um eine Lösung für ein Problem auszudrücken.
  • Beschreiben die Eigenschaften eines zweidimensionalen Arrays.
  • Konstruieren Sie Algorithmen mit zweidimensionalen Arrays.
  • Beschreiben Sie die Eigenschaften und Anwendungen eines Stacks.
  • Konstruieren Sie Algorithmen mit den Zugriffsmethoden eines Stapels.
  • Beschreiben Sie die Eigenschaften und Anwendungen einer Warteschlange.
  • Konstruieren Sie Algorithmen mit den Zugriffsmethoden einer Warteschlange.
  • Erklären Sie die Verwendung von Arrays als statische Stapel und Warteschlangen.
  • Beschreiben Sie die Merkmale und Eigenschaften einer dynamischen Datenstruktur.
  • Beschreiben Sie, wie verknüpfte Listen logisch funktionieren.
  • Skizzieren Sie verknüpfte Listen (einfach, doppelt und kreisförmig).
  • Beschreiben Sie die Eigenschaften und Anwendungen einer Sammlung.
  • Konstruieren Sie Algorithmen mit den Zugriffsmethoden einer Sammlung.
  • Diskutieren Sie die Notwendigkeit von Unterprogrammen und Sammlungen innerhalb programmierter Lösungen.
  • Konstruieren Sie Algorithmen mit vordefinierten Unterprogrammen, eindimensionalen Arrays und / oder Sammlungen.
  • Beschreiben, wie Bäume logisch funktionieren (sowohl binär als auch nicht binär).
  • Definieren Sie die Begriffe: eltern, linkes Kind, rechtes Kind, Teilbaum, Wurzel und Blatt.
  • Gibt das Ergebnis von inorder, postorder und preorder tree Traversal an.
  • Binärbäume skizzieren.
  • Definieren Sie den Begriff dynamische Datenstruktur.
  • Vergleichen Sie die Verwendung statischer und dynamischer Datenstrukturen.
  • Schlagen Sie eine geeignete Struktur für eine bestimmte Situation vor.