Complexe Datastructuur

Gegevensstructuren stellen programmeurs in staat om data efficiënt op te slaan, te organiseren en te beheren. Eenvoudige arrays of sequentiële opslag zijn vaak niet voldoende voor complexe taken, daarom worden structuren zoals lijsten, bomen en hashtabellen gebruikt.

In C bieden structuren (struct) een flexibele manier om veel van deze gegevensstructuren te implementeren.

Gelinkte lijsten

Een gelinkte lijst is handig wanneer het aantal elementen dynamisch kan veranderen. Elke node bevat data en een pointer naar de volgende node.

Voorbeeld van een knoopstructuur:

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

Elke knoop bevat een data-veld en een next-pointer. Hierdoor kun je elementen overal in de lijst toevoegen of verwijderen zonder de gehele structuur te herorganiseren, in tegenstelling tot arrays.

Hash-tabel

Hash-tabellen maken het mogelijk om snel gegevens op te halen met behulp van een sleutel. Een hashfunctie zet de sleutel om in een array-index, waar de waarde wordt opgeslagen.

Voorbeeldimplementatie van een hash-tabel:

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;
}

Elk element in de hashtabel is een gekoppelde lijstnode met een sleutel en een waarde. De hashfunctie zet de sleutel om in een array-index, wat snelle opzoekingen mogelijk maakt, zelfs bij grote datasets.

Bomen

Bomen zijn nuttig voor hiërarchische gegevens, snelle zoekopdrachten, invoegingen en verwijderingen.

Een binaire boom is een boom waarbij elke node maximaal twee kinderen heeft: links en rechts.

Een voorbeeldimplementatie van een binaire boom:

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

Een knooppunt kan zowel ouder zijn van zijn kinderen als kind van zijn ouder. Binaire bomen bieden efficiënte gegevensorganisatie en snelle zoekmogelijkheden dankzij hun logische "links-rechts" structuur.

Stack

Gebruikt voor het modelleren van netwerken en relaties.

Een stack is een datastructuur waarin elementen worden toegevoegd (push) en verwijderd (pop) volgens het LIFO-principe - (Last In, First Out).

Voorbeeld van een stack met behulp van een array:

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

MAX_SIZE - het maximale aantal elementen dat een stack kan bevatten.

// 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;
}

Het element wordt toegevoegd aan de bovenkant van de stack (top). Stacks maken snelle toevoeging en verwijdering van elementen mogelijk, waarbij het laatst toegevoegde element als eerste wordt verwijderd.

Door het gebruik van structuren in C kunnen flexibele en krachtige datastructuren worden gemaakt, zoals arrays, gekoppelde lijsten, hashtabellen, bomen en stacks. Elke structuur is geoptimaliseerd voor specifieke taken, waardoor programma's overzichtelijker en efficiënter worden.