# data-structures-cpp **Repository Path**: yicongl1/data-structures-cpp ## Basic Information - **Project Name**: data-structures-cpp - **Description**: C++ 数据结构与算法:36 个实验模块、周作业与二叉树叶子结点计数大作业 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: https://yicongl1.github.io/projects/data-structures/ - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-11-13 - **Last Updated**: 2026-11-13 ## Categories & Tags **Categories**: Uncategorized **Tags**: 数据结构, 算法, Cpp, 课程项目 ## README # 数据结构课程项目 · Projets de cours — Structures de données > 用 C++ 从零实现经典数据结构与算法:课程 7 章,第 3–7 章共 36 个专题实验模块、2 个综合项目。 > > *Implémentations classiques de structures de données et d'algorithmes en C++ : 7 chapitres de cours, 36 modules de TP (chapitres 3 à 7) et 2 projets intégrateurs.* ![C++](https://img.shields.io/badge/C%2B%2B-11-00599C?logo=cplusplus&logoColor=white) ![Visual Studio](https://img.shields.io/badge/Visual%20Studio-2022-5C2D91?logo=visualstudio&logoColor=white) ![Usage](https://img.shields.io/badge/usage-educational-2E8B57) --- ## 项目简介 / Présentation 本仓库整理了我本科阶段《数据结构》课程的实验代码、课程大作业与学习笔记。内容覆盖线性表、栈与队列、递归、串与模式匹配、数组与广义表、树与二叉树、堆、哈夫曼树、并查集,以及图论中的遍历、最小生成树、最短路径、拓扑排序和关键路径等经典内容。 全部核心数据结构使用 **C++ 模板** 编写,既包含对教材示例的整理与调试,也包含我独立完成的周作业和期末大作业。仓库按「课程章节 / 综合项目 / 学习资料」三条主线组织,适合作为数据结构与算法的学习参考,也可用于展示 C++ 工程能力。 *Ce dépôt rassemble les travaux pratiques, le projet final et les notes de mon cours de **Structures de données**. Il couvre les listes linéaires, les piles et les files, la récursivité, les chaînes et la recherche de motifs, les tableaux et les listes généralisées, les arbres binaires, les tas, les arbres de Huffman, les ensembles union-find, ainsi que les parcours de graphes, les arbres couvrants minimaux, les plus courts chemins, le tri topologique et le chemin critique.* *Le code est écrit en C++ avec des **templates**. Le dépôt est organisé selon trois axes : **chapitres du cours**, **projets intégrateurs** et **supports d'apprentissage**. Il peut servir de référence pour l'étude des structures de données et illustrer une pratique du C++.* --- ## 项目亮点 / Points forts - **36 个专题实验模块**:按章节组织,每个模块都有独立的头文件与演示入口。 - **模板化实现**:顺序表、链表、栈、队列、二叉树、图等均以 `template ` 实现,支持泛型数据类型。 - **完整的算法谱系**:从 O(1) 的顺序表访问,到 O(n+m) 的 KMP,再到 Prim / Kruskal / Dijkstra / Floyd 等图算法。 - **独立完成的大作业**:以二叉链表为存储结构,递归统计二叉树叶子结点个数,并附带可直接运行的 Visual Studio 工程与实验报告。 - **中法双语文档**:代码注释保留课程原貌,README 与学习笔记提供中文 + 法文说明,便于国际化展示。 *Points forts : 36 modules de TP organisés par chapitre ; implémentations génériques par templates ; panorama complet des algorithmes classiques ; projet final complet avec rapport et captures d'écran ; documentation bilingue chinois-français.* --- ## 仓库结构 / Structure du dépôt ```text . ├── README.md # 项目总览 / Présentation du dépôt ├── .gitignore # 忽略构建产物 / Artefacts de build │ ├── docs/ # 学习资料 / Supports de cours │ ├── README.md # 学习内容与零星代码 / Notes et exercices │ ├── notes/ │ │ ├── data_structures_notes.pdf # 课程笔记 / Notes de cours │ │ ├── data_structures_notes.docx │ │ └── weekly/ # 每周上机笔记 / Journal hebdomadaire │ ├── slides/ │ │ └── handouts/ # 部分章节讲义 PDF / Polycopiés │ └── assets/ # 运行截图 / Captures d'écran │ ├── src/ # 源代码 / Code source │ ├── chapter03_linear_list/ # 线性表 / Listes linéaires │ ├── chapter04_stack_queue_recursion/ │ ├── chapter05_string_array_generalized_list/ │ ├── chapter06_tree/ # 树与二叉树 / Arbres │ ├── chapter07_graph/ # 图 / Graphes │ ├── exercises_cpp_basics/ # 周作业 / Exercices C++ │ └── final_project_leaf_count/ # 期末大作业 / Projet final │ └── archive/ # 归档(不删除)/ Archives ├── drafts/ # 早期草稿 / Brouillons ├── duplicates/ # 重复副本 / Copies en double ├── build_artifacts/ # VS 构建产物 / Artefacts de compilation ├── macos_metadata/ # macOS 元数据 / Métadonnées macOS ├── submission_packages/ # 提交压缩包 / Archives de soumission ├── course_admin/ # 课程提交说明 / Consignes administratives ├── unrelated/ # 非本课程资料 / Documents hors sujet └── corrupted/ # 损坏文件 / Fichiers corrompus ``` --- ## 课程实验 / Travaux pratiques | 章节 / Chapitre | 主题 / Thème | 目录 / Dossier | 代表内容 / Contenu représentatif | |---|---|---|---| | 第 3 章 | 线性表
Listes linéaires | `src/chapter03_linear_list/` | 顺序表、单链表、双向链表、一元多项式、集合交集
*Liste séquentielle, liste chaînée, liste doublement chaînée, polynômes, intersection d'ensembles* | | 第 4 章 | 栈、队列与递归
Piles, files et récursivité | `src/chapter04_stack_queue_recursion/` | 顺序栈、链栈、循环队列、链队列、表达式求值、汉诺塔、车厢调度
*Piles, files circulaires, évaluation d'expressions, Tours de Hanoï, réorganisation de wagons* | | 第 5 章 | 串、数组与广义表
Chaînes, tableaux et listes généralisées | `src/chapter05_string_array_generalized_list/` | Brute-Force、KMP、稀疏矩阵(三元组 / 十字链表)、广义表、姓名反转
*Recherche naïve, KMP, matrices creuses, listes généralisées* | | 第 6 章 | 树与森林
Arbres et forêts | `src/chapter06_tree/` | 二叉链表、顺序二叉树、线索二叉树、最小堆、哈夫曼树、并查集
*Arbre binaire, arbre séquentiel, arbre filé, tas min, Huffman, union-find* | | 第 7 章 | 图
Graphes | `src/chapter07_graph/` | 邻接矩阵 / 邻接表、DFS / BFS、Prim / Kruskal、Dijkstra / Bellman-Ford / Floyd、拓扑排序、关键路径
*Matrice / liste d'adjacence, DFS / BFS, Prim / Kruskal, plus courts chemins, tri topologique, chemin critique* | 每个模块通常包含: - `Assistance.h`:状态码、异常类、遍历辅助函数; - 数据结构头文件(如 `SeqList.h`、`BinaryTree.h`); - `Test*.cpp`:可直接编译运行的演示程序。 *Chaque module contient généralement un fichier d'assistance, l'implémentation de la structure et un programme de démonstration `Test*.cpp`.* --- ## 重点项目 / Projets phares ### 1. 二叉树叶子结点计数 / Comptage des nœuds feuilles 课程期末上机大作业:以二叉链表为存储结构,编写程序统计二叉树中叶子结点的个数。 *Projet final du cours : compter les nœuds feuilles d'un arbre binaire stocké sous forme de liste chaînée binaire.* - **算法 / Algorithme**:递归遍历。若结点左右孩子均为空则返回 1,否则递归累加左右子树。 - **复杂度 / Complexité**:时间 `O(n)`,空间 `O(h)`(递归栈,`h` 为树高)。 - **入口 / Point d'entrée**:[`src/final_project_leaf_count/LeafNodeCount.sln`](src/final_project_leaf_count/LeafNodeCount.sln) - **说明 / Détails**:[`src/final_project_leaf_count/README.md`](src/final_project_leaf_count/README.md) ![叶子结点计数运行结果](docs/assets/leaf_count_output_2.png) ### 2. C++ 基础周作业 / Exercices C++ 第 1–2 周的三个小练习,用于熟悉 C++ 的值传递、指针传递、引用传递、运算符重载和双向链表。 *Trois exercices des semaines 1–2 : passage par valeur / pointeur / référence, surcharge d'opérateurs et liste doublement chaînée.* - `w1q2`:三种参数传递方式对比; - `w1q3`:复数类 `Complex`,重载 `+ - * /` 与 `>> <<`; - `w2q2`:有序双向链表,支持插入、删除、区间删除与两表合并。 入口 / Point d'entrée:[`src/exercises_cpp_basics/README.md`](src/exercises_cpp_basics/README.md) --- ## 技术栈 / Stack technique - **语言 / Langage**:C++11(模板、运算符重载、递归、动态内存) - **IDE**:Visual Studio 2022(工程工具集 `v143`,原工程由 VS2012 升级) - **构建 / Compilation**:MSVC / MSBuild;实验代码同样可用 `g++ -std=c++11` 编译 - **文档 / Documentation**:Markdown、PDF、PowerPoint --- ## 如何运行 / Compilation et exécution ### 方式一:Visual Studio 1. 打开 `src/final_project_leaf_count/LeafNodeCount.sln`; 2. 选择 `Debug | Win32`; 3. 按 `F5` 编译并运行。 *Ouvrez `src/final_project_leaf_count/LeafNodeCount.sln`, sélectionnez `Debug | Win32`, puis appuyez sur `F5`.* > `src/exercises_cpp_basics/Project1.sln` 收录第 1–2 周练习,其中入口 `main.cpp` 是课程原始草稿,存在已知的参数不匹配问题(见「代码校验」)。三个练习文件本身可通过语法检查。 > > *La solution `Project1.sln` contient les exercices des semaines 1–2 ; son entrée `main.cpp` est un brouillon original avec une incompatibilité de paramètres connue. Les trois fichiers d'exercices passent eux-mêmes la vérification syntaxique.* ### 方式二:命令行(g++) 章节实验没有单独的工程文件,直接编译对应的 `Test*.cpp` 即可: ```bash g++ -std=c++11 "src/chapter04_stack_queue_recursion/seq_stack/TestSeqStack.cpp" -o demo ./demo ``` 期末大作业: ```bash g++ -std=c++11 "src/final_project_leaf_count/LeafNodeCount/TestBinaryTree.cpp" -o leaf_count ./leaf_count ``` > 提示 / Astuce:在 Windows 上使用 g++ 编译第 5 章代码时,不要额外添加 `-I <模块目录>`。Windows 文件系统不区分大小写,本地的 `String.h` 会与系统头文件 `` 冲突;直接传入源文件路径即可正常编译。 > > *Sous Windows, n'ajoutez pas `-I ` pour le chapitre 5 : le système de fichiers étant insensible à la casse, le fichier local `String.h` masque l'en-tête système ``.* --- ## 代码校验 / Vérification 仓库整理完成后,使用 `g++ 16.2` 对所有 38 个演示入口执行了 `-fsyntax-only` 语法检查: - **35 / 38 通过**; - 3 个未通过的入口均为课程原始代码中保留的问题,未做改写: - `src/chapter03_linear_list/seq_list/SeqList.h`:复制构造函数中的 `getElem` 应为 `GetElem`; - `src/chapter03_linear_list/set_intersection/SeqList.h`:同上(该目录为独立副本); - `src/exercises_cpp_basics/Project1/main.cpp`:原始演示入口存在指针 / 引用参数不匹配,属于未完成草稿。 *Après réorganisation, les 38 points d'entrée de démonstration ont été vérifiés avec `g++ -fsyntax-only` : 35/38 passent. Les 3 échecs restants proviennent du code original du cours et ont été conservés tels quels.* --- ## 学习收获 / Bilan d'apprentissage - 理解**逻辑结构**与**存储结构**的区别,以及顺序存储 / 链式存储在时间、空间上的权衡; - 掌握线性表、栈、队列、树、图等结构的**抽象数据类型**设计与 C++ 模板实现; - 能够分析算法的最好、最坏与平均时间复杂度,并用 `O` 记号比较不同实现; - 理解递归与栈的关系,掌握递归转迭代、尾递归与单向递归的优化思路; - 熟悉 KMP、哈夫曼编码、最小生成树、最短路径、拓扑排序、关键路径等经典算法; - 具备使用 Visual Studio 组织多文件 C++ 工程、调试模板代码的实践经验。 *Ce travail m'a permis de consolider la distinction entre structure logique et structure physique, l'analyse de complexité, la conception d'ADT en C++ avec templates, la relation entre récursivité et piles, ainsi que les algorithmes classiques sur les chaînes, les arbres et les graphes.* --- ## 学习资料 / Supports d'apprentissage - 课程笔记:[`docs/notes/data_structures_notes.pdf`](docs/notes/data_structures_notes.pdf) - 每周上机记录:[`docs/notes/weekly/`](docs/notes/weekly/) - 部分章节讲义 PDF:[`docs/slides/handouts/`](docs/slides/handouts/) - 学习内容与零星代码详解:[`docs/README.md`](docs/README.md) --- ## 作者 / Auteur **李毅聪 / Li Yicong** > 欢迎交流数据结构与 C++ 学习经验。如果这个仓库对你有帮助,欢迎 Star。 > > *N'hésitez pas à me contacter pour échanger sur les structures de données et le C++. Si ce dépôt vous est utile, une étoile est la bienvenue.* --- ## 许可 / Licence 本仓库仅用于学习、教学与作品展示,不用于商业用途。 *Ce dépôt est destiné à l'apprentissage, à l'enseignement et à la présentation de portfolio. Il n'est pas destiné à un usage commercial.*