Projet de cours personnel

Structures de données : templates C++ et travaux pratiques

Université de Shanghai · Structures de données (automne 2022)

Sept chapitres de cours organisés en 36 modules thématiques et deux projets intégrateurs : templates C++ pour listes, piles, files, arbres et graphes, couvrant KMP, Huffman, union-find, arbres couvrants minimaux, plus courts chemins, tri topologique et chemins critiques.

Contexte

Les structures de données sont un cours central du programme d’ingénierie de l’information à l’Université de Shanghai. Le programme va des listes, piles et files aux chaînes, tableaux et listes généralisées, puis aux arbres, tas, arbres de Huffman et union-find, et enfin aux parcours de graphes, arbres couvrants minimaux, plus courts chemins, tri topologique et chemins critiques.

Ce dépôt rassemble les TP, le projet final et les notes de cours selon trois axes : chapitres du cours, projets intégrateurs et supports d’apprentissage. Les chapitres 3 à 7 contiennent 36 modules thématiques et deux projets intégrateurs ; les structures centrales sont écrites avec des templates C++.

Organisation du dépôt

src/
├── chapter03_linear_list/           # liste séquentielle, listes chaînées, polynômes, ensembles
├── chapter04_stack_queue_recursion/ # piles, files, évaluation d'expressions, Hanoï, wagons
├── chapter05_string_array_generalized_list/  # force brute, KMP, matrices creuses, listes généralisées
├── chapter06_tree/                  # arbres binaires, arbres filés, tas min, Huffman, union-find
├── chapter07_graph/                 # DFS/BFS, Prim/Kruskal, Dijkstra/Bellman-Ford/Floyd
├── exercises_cpp_basics/            # exercices C++ des deux premières semaines
└── final_project_leaf_count/        # projet final : compter les feuilles d'un arbre binaire

Un module typique contient trois fichiers : Assistance.h pour les codes de retour, les exceptions et les fonctions de parcours ; un en-tête de structure comme SeqList.h ou BinaryTree.h pour l’implémentation template ; et Test*.cpp, une démonstration exécutable.

Points techniques

  • Templates : listes séquentielles, listes chaînées, piles, files, arbres binaires et graphes utilisent template <class ElemType>, donc une même implémentation peut contenir des int, des double, des string ou un type utilisateur.
  • Codes de retour plutôt qu’exceptions : insertion, suppression et accès renvoient SUCCESS, RANGE_ERROR, OVER_FLOW ou NOT_PRESENT, et l’appelant doit traiter l’échec explicitement. C’est le style du cours, et il rend les cas limites visibles.
  • Un spectre d’algorithmes complet : de l’accès séquentiel O(1) au KMP O(n+m), puis Prim / Kruskal / Dijkstra / Bellman-Ford / Floyd, tri topologique et chemins critiques.
  • Projet final : compter les feuilles d’un arbre binaire chaîné. Un enfant nul renvoie 0, un nœud sans enfant renvoie 1, sinon on additionne les deux sous-arbres ; temps O(n), espace O(h).

Vérification du code

Après réorganisation, j’ai passé g++ -fsyntax-only sur les 38 points d’entrée de démonstration : 35 / 38 passent. Les trois échecs proviennent du code original du cours et n’ont pas été modifiés :

  • chapter03_linear_list/seq_list/SeqList.h : getElem dans le constructeur de copie devrait être GetElem ;
  • chapter03_linear_list/set_intersection/SeqList.h : la même faute dans une copie indépendante ;
  • exercises_cpp_basics/Project1/main.cpp : le point d’entrée original a une incompatibilité de paramètres pointeur/référence et reste un brouillon inachevé.

Les conserver est volontaire : le dépôt est d’abord un témoignage de cours, ensuite un portfolio. Nettoyer le code original lui ferait perdre sa valeur d’apprentissage ; le README, en revanche, doit dire ce qui s’exécute et ce qui ne s’exécute pas.

Bilan

L’entraînement réel n’était pas de mémoriser des algorithmes, mais d’acquérir trois habitudes :

  • séparer la structure logique (linéaire, arbre, graphe) de la structure physique (séquentielle, chaînée) ;
  • comparer les implémentations par la complexité, pas par une impression de vitesse ;
  • faire en sorte que chaque module se compile, s’exécute et se vérifie seul.

Les notes de cours, les comptes rendus hebdomadaires, une partie des polycopiés et les captures d’exécution sont dans docs/.

Code et documentation : https://gitee.com/yicongl1/data-structures-cpp

Notes techniques

01 Structures de données en templates C++ : les frontières génériques des listes, piles et files template <class ElemType>, codes de retour, copies profondes et contrôles de capacité — et une faute de frappe dans le constructeur de copie qui n'apparaît qu'à l'instanciation. 02 De KMP aux chemins critiques : relier 36 TP de structures de données en un seul graphe Fonction d'échec, comptage récursif des feuilles, Dijkstra sur listes d'adjacence et chemins critiques ; une organisation en « en-tête + démonstration exécutable ».

Compétences associées

  • C++
  • Git