Lernzettel: Structures de Données et Types Abstraits

1. 📌 L'essentiel

• Types abstraits : définis par domaine,, axiomes, indépendants de l'implémentation.
• Allocation dynamique : malloc (type size_t, void*), free — gestion mémoire en C.
• Structures fondamentales : listesitératives/récursives), piles, files, arbres, tas, hachage.
• Parcours d'arbres : DFS (préfixe, infixe, postfixe), BFS, hauteur, équilibrage.
• Structures arborescentes : nœuds, filiation, arbres binaires (complet, parfait, recherche).
• Tri par tas (heap sort), codage Huffman (compression optimale, préfixe).
• Structures associatives : dictionnaires (hachage), ensembles (bit, liste, hachage).
• Concepts clés : formalisation AD, organisation hiérarchique, optimisation mémoire et accès.
• Relations structure-fonction : flux, hiérarchie, hiérarchies spatiales.
• Pièges fréquents : confusion entre listes chaînées et tableaux, erreurs de parcours, collisions en hachage.

2. 🧩 Structures & Composants clés

• Type abstrait (AD) — interface définissant domaine, opérations, axiomes.
• Liste — collection linéaire, itérative ou récursive, avec gestion mémoire.
• Pile (LIFO) — structure d’empilement, tableau ou chaînée.
• File (FIFO) — structure de file d’attente, tableau ou chaînée.
• Arbre — hiérarchie de nœuds, parcours DFS (profondeur), BFS (largeur).
• Arbre binaire — complet, parfait, recherche (ABR).
• Tas (heap) — propriété d’ordre, opérations d’insertion, extraction.
• Hachage — fonction de hachage, gestion des collisions (chaînage, sondage).
• Ensembles — représentations diverses, opérations d’union, intersection.
• Codage Huffman — arbre de codage, compression sans perte, préfixe.

3. 🔬 Fonctions, Mécanismes & Relations

• Organisation hiérarchique : arbres, tas, structures arborescentes.
• Flux d’opérations :
  • Listes : ajout, suppression, parcours.
  • Arbres : insertion, recherche, parcours (préfixe, infixe, postfixe).
  • Tas : heapify (organisation), tri par tas.
  • Hachage : calcul, résolution collisions.
• Relations structure-fonction :
  • Parcours DFS/BFS → exploration hiérarchique.
  • Tas → gestion priorité.
  • Hachage → accès rapide.
• Organisation hiérarchique :

  Structures
   ├─ Listes
   ├─ Piles
   ├─ Files
   ├─ Arbres
   │   ├─ Binaires
   │   └─ Recherche
   ├─ Tas
   ├─ Ensembles
   └─ Dictionnaires
  

4. Tableau de Synthèse

Élément	Caractéristiques clés	Notes / Différences
Types abstraits	Domaine, opérations, axiomes	Interface indépendante de l’implémentation
Allocation mémoire	malloc, free	Gestion dynamique en C
Listes	Itératives (indices), récursives (tête, reste)	Structures fondamentales
Listes Python	append, coût amorti, réallocation	Facilité d’usage, coût en temps
Listes chaînées	malloc, libération, circulaire	Flexibilité mémoire
Piles	LIFO, tableau ou chaînée	Utilisées en algos (recursion, undo)
Files	FIFO, tableau ou chaînée	Gestion tâches, parcours
Arbres	hiérarchie, DFS, BFS, hauteur	Recherche, hiérarchisation
Arbres binaires	complet, parfait, recherche (ABR)	Recherche efficace, équilibrage
Tas (heap)	propriété, heapify, tri par tas	Tri, gestion priorité
Hachage	fonctions, collisions, résolutions	Accès rapide, dictionnaires
Ensembles	bit, liste, hachage	Opérations d’union, intersection
Huffman	arbre optimal, préfixe, compression	Compression sans perte

5. 🗂️ Diagramme Hiérarchique (ASCII)

Structures de Données
 ├─ Listes
 │    ├─ Itératives
 │    └─ Récursives
 ├─ Piles
 │    ├─ Tableau
 │    └─ Chaînée
 ├─ Files
 │    ├─ Tableau
 │    └─ Chaînée
 ├─ Arbres
 │    ├─ Binaires
 │    │    ├─ Complet
 │    │    └─ Parfait
 │    └─ Recherche (ABR)
 │        ├─ Insertion
 │        └─ Recherche
 ├─ Tas (heap)
 ├─ Ensembles
 │    ├─ Bit
 │    ├─ Liste
 │    └─ Hachage
 ├─ Dictionnaires
 └─ Codage Huffman

6. ⚠️ Pièges & Confusions fréquentes

• Confondre liste chaînée et tableau (gestion mémoire, accès).
• Mal interpréter la différence entre arbre complet et parfait.
• Confondre parcours DFS (préfixe, infixe, postfixe) avec BFS.
• Confondre collision en hachage (chaînage vs sondage).
• Surévaluer la complexité en cas de mauvaise gestion mémoire.
• Confondre opérations sur tas (heapify) et tri par tas.
• Confusion entre structure d’un arbre binaire de recherche et un arbre binaire complet.
• Termes similaires : liste vs tableau, arbre binaire vs arbre n-aire.

7. ✅ Checklist Examen Final

• Définir un type abstrait, ses opérations et axiomes.
• Expliquer la gestion mémoire en C (malloc, free).
• Différencier listes, piles, files, arbres, tas, hachage.
• Décrire les parcours d’un arbre (DFS, BFS).
• Expliquer le principe du tri par tas et du codage Huffman.
• Connaître les représentations d’ensembles (bit, liste, hachage).
• Savoir gérer collisions en hachage.
• Comprendre la hiérarchie des structures (arbre, tas, dictionnaire).
• Identifier la complexité moyenne des opérations.
• Savoir formaliser une structure en termes d’opérations et axiomes.
• Reconnaître les pièges courants en implémentation.
• Maîtriser les opérations principales : insertion, recherche, suppression.
• Connaître les propriétés d’un arbre binaire de recherche.
• Expliquer le fonctionnement d’un arbre de Huffman.
• Savoir faire un parcours en profondeur et en largeur.
• Comprendre l’intérêt de l’organisation hiérarchique pour l’optimisation.

Ce résumé synthétise l’essentiel pour une préparation efficace aux examens.