Komplex Datastruktur

Datastrukturer gör det möjligt för programmerare att lagra, organisera och hantera data effektivt. Enkla arrayer eller sekventiell lagring räcker ofta inte för komplexa uppgifter, vilket är anledningen till att strukturer som listor, träd och hashtabeller används.

I C erbjuder strukturer (struct) ett flexibelt sätt att implementera många av dessa datastrukturer.

Länkade listor

En länkad lista är användbar när antalet element kan ändras dynamiskt. Varje nod innehåller data och en pekare till nästa nod.

Exempel på nodstruktur:

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

Varje nod innehåller ett data-fält och en next-pekare. Detta gör det möjligt att lägga till eller ta bort element var som helst i listan utan att behöva omorganisera hela strukturen, till skillnad från arrayer.

Hashtabell

Hashtabeller möjliggör snabb hämtning av data med hjälp av en nyckel. En hashfunktion omvandlar nyckeln till ett arrayindex där värdet lagras.

Exempel på implementation 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;
}

Varje element i hashtabellen är en länkad lista-nod som innehåller en nyckel och ett värde. Hashfunktionen omvandlar nyckeln till ett arrayindex, vilket möjliggör snabba uppslag även med stora datamängder.

Träd

Träd är användbara för hierarkisk data, snabba sökningar, insättning och borttagning.

Ett binärt träd är ett träd där varje nod har högst två barn: vänster och höger.

Ett exempel på implementering av ett binärt träd:

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

En nod kan vara förälder till sina barn och samtidigt vara barn till sin förälder. Binära träd möjliggör effektiv dataorganisation och snabba sökningar tack vare deras logiska "vänster-höger"-struktur.

Stack

Används för att modellera nätverk och relationer.

En stack är en datastruktur där element läggs till (push) och tas bort (pop) enligt LIFO-principen - (Last In, First Out).

Exempel på stack med en array:

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

MAX_SIZE - det maximala antalet element som en stack kan innehålla.

// 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 läggs till överst i stacken (top). Stackar möjliggör snabb tilläggning och borttagning av element, där det senast tillagda elementet tas bort först.

Genom att använda strukturer i C är det möjligt att skapa flexibla och kraftfulla datastrukturer såsom arrayer, länkade listor, hashtabeller, träd och stackar. Varje struktur är optimerad för specifika uppgifter, vilket gör programmen mer organiserade och effektiva.