Komplexe Datenstruktur

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 Knotendatenstruktur:

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. Dadurch können Elemente an beliebiger Stelle in der Liste hinzugefügt oder entfernt werden, ohne die gesamte Struktur wie bei Arrays neu anzuordnen.

Hashtabelle

Hashtabellen ermöglichen eine schnelle Datenabfrage 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, schnelle Suche, Einfügen und Löschen.

Ein Binärbaum 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

Verwendung zur Modellierung von Netzwerken und Beziehungen.

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 – die maximale Anzahl von Elementen, die ein Stack enthalten kann.

// 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) hinzugefügt. 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 sorgt für eine bessere Organisation und Effizienz von Programmen.