Les structures de données permettent aux programmeurs de stocker, organiser et gérer les données de manière efficace. Les tableaux simples ou le stockage séquentiel ne suffisent souvent pas pour des tâches complexes, c'est pourquoi des structures telles que les listes, les arbres et les tables de hachage sont utilisées.

En C, les structures (struct) offrent un moyen flexible d'implémenter bon nombre de ces structures de données.

Listes chaînées

Une liste chaînée est utile lorsque le nombre d'éléments peut changer dynamiquement. Chaque nœud contient des données et un pointeur vers le nœud suivant.

Exemple de structure de nœud :

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

Chaque nœud contient un champ data et un pointeur next. Cette structure permet d’ajouter ou de supprimer des éléments n’importe où dans la liste sans réorganiser l’ensemble de la structure, contrairement aux tableaux.

Table de hachage

Les tables de hachage permettent de récupérer rapidement des données à l’aide d’une clé. Une fonction de hachage convertit la clé en un indice de tableau, où la valeur est stockée.

Exemple d’implémentation d’une table de hachage :

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

Chaque élément de la table de hachage est un nœud de liste chaînée contenant une clé et une valeur. La fonction de hachage convertit la clé en un indice de tableau, permettant des recherches rapides, même avec de grands ensembles de données.

Arbres

Les arbres sont utiles pour les données hiérarchiques, la recherche rapide, l'insertion et la suppression.

Un arbre binaire est un arbre où chaque nœud possède au maximum deux enfants : gauche et droite.

Un exemple d'implémentation d'un arbre binaire :

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

Un nœud peut être parent de ses enfants tout en étant lui-même enfant de son parent. Les arbres binaires offrent une organisation efficace des données et une recherche rapide grâce à leur structure logique « gauche-droite ».

Pile

Utilisée pour modéliser des réseaux et des relations.

Une pile est une structure de données dans laquelle les éléments sont ajoutés (push) et retirés (pop) selon le principe LIFO - (Last In, First Out).

Exemple de pile utilisant un tableau :

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

L'élément est ajouté en haut de la pile (top). Les piles permettent une addition et une suppression rapides des éléments, le dernier élément ajouté étant le premier à être retiré.

L'utilisation des structures en C permet de créer des structures de données flexibles et puissantes telles que les tableaux, les listes chaînées, les tables de hachage, les arbres et les piles. Chaque structure est optimisée pour des tâches spécifiques, rendant les programmes plus organisés et efficaces.