Structures de Données Avancées & Algorithmique en C

Implémentations de référence, gestion fine de la mémoire dynamique et analyse de complexité théorique et empirique — ISIMA (Clermont Auvergne INP).

Ce dépôt regroupe l'ensemble des modules d'algorithmique et de structures de données (SDD) développés en langage C. L'accent est mis sur la rigueur d'implémentation bas niveau (pointeurs, allocation dynamique sans fuite mémoire), le respect des invariants structurels et les garanties de complexité asymptotique ($O(1)$, $O(\log n)$, $O(n)$).

---

📊 Synthèse des Modules Implémentés

Module	Structure / Algorithme	Invariants Clés & Propriétés	Complexité Recherche
TP 1	Files d'attente (Queue FIFO)	Gestion dynamique des enfilages / défilages avec pointeurs de tête et queue	$O(1)$
TP 2	Tables de Hachage	Résolution des collisions par chaînage séparé, dimensionnement dynamique	$O(1)$ moyen
TP 3	Backtracking & Listes	Résolution du problème des $N$-Dames par exploration récursive avec élagage	$O(N!)$
TP 4	Arbres de Huffman	Compression sans perte de données par calcul de fréquences et codage préfixe	$O(n \log n)$
TP 5	Arbres AVL	Arbres binaires de recherche auto-équilibrés via rotations (LL, RR, LR, RL)	$O(\log n)$ pire cas
TP 6	Arbres Rouge-Noir (Red-Black)	Équilibrage binaire avec coloration des nœuds et maintien des 5 invariants RB	$O(\log n)$ pire cas
TP 7	B-Arbres (B-Trees)	Arbres de recherche équilibrés multi-branches pour accès disque et bases de données	$O(\log n)$
TP 8	Indexation & Enregistrements	Organisation de fichiers séquentiels indexés pour la recherche rapide	$O(\log n)$
TP 9	Listes Doublement Chaînées	Manipulation bidirectionnelle, insertion/suppression en tête, queue et milieu	$O(1)$ insertion

---

🛠️ Principes de Développement & Bonnes Pratiques

• Langage & Norme : C (norme C99/C11), typage fort avec stdint.h et stdbool.h.
• Gestion Mémoire : Allocation explicite (malloc / calloc), libération récursive intégrale (free) systématiquement vérifiée.
• Modularité : Séparation stricte de l'interface (.h) et de l'implémentation (.c), encapsulation des types par pointeurs opaques quand applicable.
• Automatisation : Chaque module dispose de son propre Makefile avec cibles de compilation et d'exécution des tests.

---

🚀 Compilation & Exécution des Tests

Chaque dossier dispose de règles de build autonomes :

# Exemple pour le module Arbres AVL (TP5) :
cd zz1-sdd-s2/tp5
make
./main

# Exemple pour les Arbres Rouge-Noir (TP6) :
cd zz1-sdd-s2/tp6
make
./main

Pour nettoyer les artefacts de compilation :

make clean