ef:datenstrukturen [DokuWiki CSC]

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
~~NOTOC~~
<WRAP center 1200px>
====== I. Datenstrukturen ======

===== 1. Was sind Datenstrukturen? =====
Datenstrukturen sind spezielle Konzepte zur Organisation und Speicherung von Daten in einem Computerprogramm. 
Sie bestimmen, **wie Daten angeordnet und verwaltet werden**, um effiziente Zugriffe und Operationen zu ermöglichen.

**Zweck von Datenstrukturen:**
  * Effiziente Speicherung und Verwaltung von Daten
  * Schneller Zugriff und Bearbeitung
  * Grundlage für die Implementierung von Algorithmen

**Unterschied zu Datentypen:**
  * **Datentypen** beschreiben die Art einzelner Werte (z. B. Ganzzahl, Zeichenkette).
  * **Datenstrukturen** beschreiben die Anordnung und Beziehung mehrerer Werte (z. B. Liste, Baum).

===== 2. Datenstrukturen =====
Es gibt verschiedene Arten von Datenstrukturen, die je nach Anwendungsfall eingesetzt werden. 
Hier eine Übersicht der wichtigsten:

==== 2.1 Liste (Array) und Verkettete Liste ====
**Liste (Array):**
  * Geordnete Sammlung von Elementen, die über Indizes angesprochen werden.
  * Feste Größe (bei klassischen Arrays).
  * Direkter Zugriff auf Elemente.

Beispiel:
  [3, 7, 9, 12]

**Verkettete Liste:**
  * Besteht aus Knoten (Nodes), die jeweils Daten und einen Verweis auf den nächsten Knoten enthalten.
  * Dynamische Größe.
  * Kein direkter Zugriff per Index.

Visualisierung:
  [Head] → [3 | Next] → [7 | Next] → [9 | Next] → [12 | Next] →NULL

<WRAP nicebox green>
** Aufgabe 1 ** 
Welche Vorteile und Nachteile hat wohl eine Verkettete Liste verglichen mit einer einfachen Liste (Array)?
</WRAP>


==== 2.2 Stack (Stapel) und Queue (Warteschlange) ====
**Stack (Stapel):**
  * Prinzip: LIFO (Last In – First Out).
  * Letztes eingefügtes Element wird zuerst entfernt.
  * Operationen: `push` (einfügen), `pop` (entfernen).

Beispiel:
  Stapel von Tellern: Der zuletzt oben gelegte Teller wird zuerst genommen.

**Queue (Warteschlange):**
  * Prinzip: FIFO (First In – First Out).
  * Erstes eingefügtes Element wird zuerst entfernt.
  * Operationen: `enqueue` (einfügen), `dequeue` (entfernen).

Beispiel:
  Warteschlange im Supermarkt: Wer zuerst kommt, wird zuerst bedient.

==== 2.3 Bäume und Graphen ====

**Graphen:**
  * Sammlung von Knoten (Vertices) und Kanten (Edges), die die Knoten verbinden.
  * Kann gerichtet oder ungerichtet sein.
  * Kann Zyklen enthalten oder azyklisch sein.
  * Beispiel: Straßennetz, soziale Netzwerke.
  * Ein **Baum** ist ein **zusammenhängernder Graph ohne Zyklen**.

Visualisierung:
  (A) --- (B)
   |       |
  (C) --- (D)


**Bäume:**
  * Hierarchische Struktur mit Wurzel (Root) und Knoten (Nodes).
  * Jeder Knoten kann mehrere Kinder haben.
  * Für n Knoten hat ein Baum immer n-1 Kanten.
  * Es gibt einen eindeutigen Weg von zwischen zwei Knoten.
  * Beispiel: Binärbaum (max. 2 Kinder pro Knoten), Dateisystem

Visualisierung:
        Root
       /    \
    Node1   Node2


[[https://www.jamisbuck.org/presentations/rubyconf2011/index.html#title-page]]

[[ef:start|Zurück zur Übersicht]]
</WRAP>