Datenstrukturen ermöglichen es Programmierern, Daten effizient zu speichern, zu organisieren und zu verwalten. Einfache Arrays oder sequentielle Speicherungen reichen für komplexe Aufgaben oft nicht aus, weshalb Strukturen wie Listen, Bäume und Hashtabellen verwendet werden.

In C bieten Strukturen (struct) eine flexible Möglichkeit, viele dieser Datenstrukturen zu implementieren.

Verkettete Listen

Eine verkettete Liste ist nützlich, wenn sich die Anzahl der Elemente dynamisch ändern kann. Jeder Knoten enthält Daten und einen Zeiger auf den nächsten Knoten.

Beispiel für eine Knotendefinition:

struct Node {
    int data;           // data in node
    struct Node* next;  // pointer to next node
};

Jeder Knoten enthält ein data-Feld und einen next-Zeiger. Dies ermöglicht das Hinzufügen oder Entfernen von Elementen an beliebiger Stelle in der Liste, ohne die gesamte Struktur wie bei Arrays neu organisieren zu müssen.

Hashtabelle

Hashtabellen ermöglichen das schnelle Abrufen von Daten mithilfe eines Schlüssels. Eine Hashfunktion wandelt den Schlüssel in einen Array-Index um, an dem der Wert gespeichert wird.

Beispiel für die Implementierung einer Hashtabelle:

struct Node {
    char* key;          // key
    int value;          // value
    struct Node* next;  // pointer to next node
};

struct HashTable {
    struct Node** table; // array of node pointers
    int size;            // table size
};

unsigned int hashFunction(char* key, int size) {
    unsigned int hash = 0;
    while (*key) {
        hash += *key++;
    }
    return hash % size;
}

Jedes Element in der Hashtabelle ist ein Knoten einer verketteten Liste, der einen Schlüssel und einen Wert enthält. Die Hashfunktion wandelt den Schlüssel in einen Array-Index um und ermöglicht so schnelle Suchvorgänge, selbst bei großen Datenmengen.

Bäume

Bäume eignen sich für hierarchische Daten, schnelles Suchen, Einfügen und Löschen.

Ein binärer Baum ist ein Baum, bei dem jeder Knoten höchstens zwei Kinder hat: links und rechts.

Ein Beispiel für die Implementierung eines binären Baums:

struct node
{
	int data;
	struct node* left; 
	struct node* right; 
};

Ein Knoten kann sowohl Elternteil seiner Kinder als auch Kind seines Elternteils sein. Binäre Bäume ermöglichen eine effiziente Datenorganisation und schnelles Suchen durch ihre logische "Links-Rechts"-Struktur.

Stack

Wird zur Modellierung von Netzwerken und Beziehungen verwendet.

Ein Stack ist eine Datenstruktur, bei der Elemente gemäß dem LIFO-Prinzip (Last In, First Out) hinzugefügt (push) und entfernt (pop) werden.

Beispiel für einen Stack mit einem Array:

// Stack structure
typedef struct {
    int data[MAX_SIZE]; 
    int top;
} Stack;

MAX_SIZE - the maximum number of elements a stack can contain.

// Push an element onto the stack
void push(Stack *stack, int value) {
    stack->data[++stack->top] = value;  // Increment top and add the element
    printf("Element %d pushed onto the stack\n", value);
}

// Pop an element from the stack
int pop(Stack *stack) {
    int value = stack->data[stack->top--];  // Retrieve the element and decrement top
    printf("Element %d popped from the stack\n", value);
    return value;
}

Das Element wird oben auf den Stack (top) gelegt. Stacks ermöglichen eine schnelle Hinzufügung und Entfernung von Elementen, wobei das zuletzt hinzugefügte Element als erstes entfernt wird.

Durch die Verwendung von Strukturen in C können flexible und leistungsfähige Datenstrukturen wie Arrays, verkettete Listen, Hashtabellen, Bäume und Stacks erstellt werden. Jede Struktur ist für bestimmte Aufgaben optimiert und macht Programme dadurch organisierter und effizienter.