Projet de cours personnel
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.
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++.
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.
template <class ElemType>, donc une même implémentation peut contenir des int, des double, des string ou un type utilisateur.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.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.
L’entraînement réel n’était pas de mémoriser des algorithmes, mais d’acquérir trois habitudes :
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