Monimutkainen Tietorakenne

Tietorakenteet mahdollistavat ohjelmoijille tiedon tallentamisen, järjestämisen ja hallinnan tehokkaasti. Yksinkertaiset taulukot tai peräkkäistallennus eivät usein riitä monimutkaisiin tehtäviin, minkä vuoksi käytetään rakenteita kuten listoja, puita ja hajautustauluja.

C-kielessä rakenteet (struct) tarjoavat joustavan tavan toteuttaa monia näistä tietorakenteista.

Linkitetyt listat

Linkitetty lista on hyödyllinen, kun alkioiden määrä voi muuttua dynaamisesti. Jokainen solmu sisältää tietoa ja osoittimen seuraavaan solmuun.

Esimerkkisolmun rakenne:

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

Jokainen solmu sisältää data-kentän ja next-osoittimen. Tämän ansiosta voit lisätä tai poistaa alkioita missä tahansa kohtaa listaa ilman, että koko rakennetta tarvitsee järjestellä uudelleen, toisin kuin taulukoissa.

Hajautustaulu

Hajautustaulujen avulla tietoja voidaan hakea nopeasti avaimen avulla. Hajautusfunktio muuntaa avaimen taulukon indeksiksi, johon arvo tallennetaan.

Esimerkki hajautustaulun toteutuksesta:

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

Jokainen hajautustaulun alkio on linkitetyn listan solmu, joka sisältää avaimen ja arvon. Hajautusfunktio muuntaa avaimen taulukon indeksiksi, mikä mahdollistaa nopeat haut myös suurilla tietomäärillä.

Puut

Puut soveltuvat hierarkkiseen tietoon sekä nopeaan hakuun, lisäykseen ja poistoon.

Binääripuu on puu, jossa jokaisella solmulla on enintään kaksi lasta: vasen ja oikea.

An example implementation of a binary tree:

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

Solmu voi olla vanhempi omille lapsilleen ja samalla olla lapsi omalle vanhemmalleen. Binääripuut mahdollistavat tehokkaan tietojen järjestämisen ja nopean haun niiden loogisen "vasen-oikea"-rakenteen ansiosta.

Pino

Käytetään verkkojen ja suhteiden mallintamiseen.

Pino on tietorakenne, johon alkioita lisätään (push) ja poistetaan (pop) LIFO-periaatteen mukaisesti - (Last In, First Out, viimeksi sisään, ensimmäisenä ulos).

Esimerkki pinosta taulukon avulla:

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

MAX_SIZE - pinon sisältämien alkioiden enimmäismäärä.

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

Alkio lisätään pinon ylimmäiseksi (top). Pinot mahdollistavat nopean alkioiden lisäämisen ja poistamisen, ja viimeksi lisätty alkio poistetaan ensimmäisenä.

C:n rakenteiden avulla voidaan luoda joustavia ja tehokkaita tietorakenteita, kuten taulukoita, linkitettyjä listoja, hajautustauluja, puita ja pinoja. Jokainen rakenne on optimoitu tiettyihin tehtäviin, mikä tekee ohjelmista järjestelmällisempiä ja tehokkaampia.