Datastrukturer gör det möjligt för programmerare att lagra, organisera och hantera data på ett effektivt sätt. Enkla arrayer eller sekventiell lagring räcker ofta inte för mer avancerade 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 förä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 möjliggör 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.

Hash-tabell

Hash-tabeller 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, snabb sökning, 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 snabb sökning 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 - 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;
}

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.

Att använda strukturer i C gö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.