Datenstrukturen I

Question 1

Datenstruktur

Answer 1

• Art, Daten im Computer zu speichern/verwalten
• statisch, dynamisch, abstrakt
• Beispiele:
  
  • Arrays
  • Listen
  • Kellerspeicher
  • Warteschlange
  • Bäume etc.

Question 2

Arrays - Eigenschaften

Answer 2

• statische Datenstruktur
• Zusammenhängender Speicherbereich (SB)
• Größe SB zur Laufzeit nicht veränderbar
• Direktzugriff über Speicheradresse

⇒ Problem, dass # der zu speichernden Objekte selten bekannt (→ dynamische DS)

Question 3

Dynamische Datenstrukturen

Answer 3

• werden mithilfe von statischen DS implementiert
• Knoten/nodes: zusätzliche Verwaltungsstruktur
• Referenz/pointers: Knoten aneinander gehängt

⇒ Nachteil: kein direkter Zugriff (Auswirkung Laufzeit)

• Soll (1-3 minimal, 4 + Konkatenation [Zusammenfügen von Listen] zusätzlich):
  
  1. schreiben
  2. löschen
  3. lesen
  4. suchen (Traversierung der DS → Ablaufen mittels Iterator = Hilfsobjekt zum seq. Ablaufen)

Question 4

Dynamische Datenstrukturen - Grundoperationen

Answer 4

• add (Object o)
• remove (Object o)
• boolean contains (Object o)

Question 5

Statisch vs. Dynamische Datentypen

Answer 5

Question 6

Abstrakter Datentyp (ADT)

Answer 6

• besteht aus
  
  • Menge M von Objekten
  • Menge O von Operationen auf M
  • Beschreibung der Semantik (“Bedeutung”) der Operationen

⇒ ADTen eignen sich gut, um DS zu beschreiben

Question 7

Auswahl der Datenstruktur

Answer 7

• stark von Anwendungsfall abhägig
  
  • erwartete Datenmenge
  • Häufigkeit/Wahrscheinlichkeit/Reihenfolge von Operationen
  • Semantik der Daten
  • Adressierung der Daten beim Lesen und Schreiben

⇒ geringere Komplexitätsklasse ≠ bessere Laufzeit, da u.U. zusätzlicher Mehraufwand für Verwaltungsstrukturen

Question 8

Aufbau

Answer 8

• Verwaltungselement: Organisation der Datenstruktur
• Datenelement: enthält zu speichernden Wert

Question 9

Wohlgeformte Klammerausdrücke - WKA

Answer 9

• (), {} und [] sind WKAs
• w₁, w₂ = WKA → w₁w₂ = WKA
• w₁ = WKA → (w₁), {w₁} und [w₁] = WKAs

Question 10

Aufbau Liste

Answer 10

aus zwei Sorten Verwaltungselementen:

• Knoten als Verwaltungselemente kennen jeweils ihren Nachfolger und ein Datenelement
• Ein Listen-Element kennt den ersten Knoten

Question 11

Methoden Liste

Answer 11

• get(int index) liefert Knoten zu index, Zugriff auf Inhalt dann mit getData
• add(int index, Objekt o) fügt an angegebener Stelle das Objekt o ein
• remove(Node n) löscht den Knoten
• remove(objekt o) löscht Knoten mit Inhalt o

Question 12

Verkettete Liste

Answer 12

• Nachteil bei Datensortierung (Traversierung)
• Vorteil bei Verwaltung nach Reihenfolge (LIFO - Keller / FIFO - Schlange)

Question 13

einfach/doppelt verkettete Liste

Answer 13

• doppelt: nodes haben Zeiger auf Vorgänger = prev.

⇒ Zeigeroperationen werden einfacher, da Reihenfolge auch rückwärts

• Vorteil einfach: weniger Speicherplatz
• Nachteil einfach: Laufzeitnachteile, da Finden Vorgänger muss Liste von vorne duchsucht werden

Question 14

Keller

Answer 14

≈ Tellerstapel

• LIFO-Prinzip
• kann WKAs erkennen
• Operationen
  
  • push(Object o): Anfügen an Ende
  • pop( ): Ansehen & Entfernen am gleichen Ende
  • peek( ): Ansehen ohne Entfernen
• Implementierung:
  
  • verkettete Liste
  • Array

Question 15

Schlange

Answer 15

≈ Supermarkt

• FIFO
• Operationen:
  
  • dequenue( ): Erstes Element wird entfernt
  • enquenue( ): Neues Element wird hinten angefügt
  • front( ): Liefert Anfangselement ohne Entfernen
• Implementierung:
  
  • verkettete Liste (Zeiger auf letztes Element)
  • zirkulärem Array