Kompleks Datastruktur

Datastrukturer gjør det mulig for programmerere å lagre, organisere og håndtere data effektivt. Enkle arrayer eller sekvensiell lagring er ofte ikke tilstrekkelig for komplekse oppgaver, og derfor brukes strukturer som lister, trær og hashtabeller.

I C gir strukturer (struct) en fleksibel måte å implementere mange av disse datastrukturene på.

Lenket liste

En lenket liste er nyttig når antall elementer kan endres dynamisk. Hver node inneholder data og en peker til neste node.

Eksempel på nodestuktur:

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

Hver node inneholder et data-felt og en next-peker. Dette gjør det mulig å legge til eller fjerne elementer hvor som helst i listen uten å måtte omorganisere hele strukturen, i motsetning til med arrayer.

Hashtabell

Hashtabeller gjør det mulig å hente data raskt ved hjelp av en nøkkel. En hash-funksjon konverterer nøkkelen til en indeks i et array, hvor verdien lagres.

Eksempel på implementering av hashtabell:

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

Hvert element i hashtabellen er en lenket liste-node som inneholder en nøkkel og en verdi. Hashfunksjonen konverterer nøkkelen til en indeks i arrayet, noe som gir raske oppslag selv med store datasett.

Trær

Trær er nyttige for hierarkiske data, raske søk, innsetting og sletting.

Et binært tre er et tre der hver node har maksimalt to barn: venstre og høyre.

Et eksempel på implementering av et binært tre:

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

En node kan være forelder til sine barn samtidig som den er barn av sin forelder. Binære trær gir effektiv dataorganisering og raskt søk på grunn av deres logiske "venstre-høyre"-struktur.

Stakk

Brukes til å modellere nettverk og relasjoner.

En stakk er en datastruktur der elementer legges til (push) og fjernes (pop) etter LIFO-prinsippet – (Last In, First Out).

Eksempel på stakk ved bruk av en tabell:

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

MAX_SIZE – det maksimale antallet elementer en stack kan inneholde.

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

Elementet legges til øverst i stacken (top). Stacks gir rask innsetting og fjerning av elementer, hvor det siste elementet som legges til er det første som fjernes.

Bruk av strukturer i C gjør det mulig å lage fleksible og kraftige datastrukturer som arrayer, lenkede lister, hash-tabeller, trær og stacker. Hver struktur er optimalisert for spesifikke oppgaver, noe som gjør programmene mer organiserte og effektive.