个人课程项目

数据结构:C++ 模板实现与课程实验

上海大学 · 数据结构(2022 秋)

把课程 7 章内容整理成 36 个专题实验模块与 2 个综合项目:C++ 模板实现顺序表、链表、栈、队列、树与图,覆盖 KMP、Huffman、并查集、最小生成树、最短路径、拓扑排序与关键路径。

项目背景

数据结构是上海大学信息工程专业的核心课。课程内容跨度很大:从线性表、栈、队列,到串、数组、广义表,再到树、堆、哈夫曼树、并查集,最后是图的遍历、最小生成树、最短路径、拓扑排序和关键路径。

这个仓库把课程实验、期末大作业和学习笔记整理在一起,按“课程章节 / 综合项目 / 学习资料”三条线组织。第 3–7 章共 36 个专题实验模块,另有 2 个综合项目;所有核心结构都用 C++ 模板编写。

仓库结构

src/
├── chapter03_linear_list/           # 顺序表、单链表、双向链表、多项式、集合
├── chapter04_stack_queue_recursion/ # 栈、队列、表达式求值、汉诺塔、车厢调度
├── chapter05_string_array_generalized_list/  # Brute-Force、KMP、稀疏矩阵、广义表
├── chapter06_tree/                  # 二叉树、线索树、最小堆、哈夫曼树、并查集
├── chapter07_graph/                 # DFS/BFS、Prim/Kruskal、Dijkstra/Bellman-Ford/Floyd
├── exercises_cpp_basics/            # 前两周的 C++ 基础练习
└── final_project_leaf_count/        # 期末大作业:统计二叉树叶子结点

每个模块通常包含三个文件:Assistance.h 放状态码、异常类和遍历辅助函数;数据结构头文件(如 SeqList.h、BinaryTree.h)放模板实现;Test*.cpp 是可直接编译运行的演示入口。

技术要点

  • 模板化:顺序表、链表、栈、队列、二叉树、图等均以 template <class ElemType> 实现,同一份代码可以存放 int、double、string 或自定义类型。
  • 状态码而不是异常:插入、删除、取元素返回 SUCCESS、RANGE_ERROR、OVER_FLOW、NOT_PRESENT 等状态,调用方必须显式处理失败。这是课程代码的风格,也让边界条件变得可见。
  • 算法谱系完整:从 O(1) 的顺序表访问,到 O(n+m) 的 KMP,再到 Prim / Kruskal / Dijkstra / Bellman-Ford / Floyd、拓扑排序和关键路径。
  • 期末大作业:以二叉链表为存储结构,递归统计叶子结点个数。空结点返回 0,左右孩子都为空返回 1,否则递归累加左右子树;时间 O(n),空间 O(h)。

代码校验

整理完成后,我用 g++ -fsyntax-only 对全部 38 个演示入口做了语法检查:35 / 38 通过。剩下三个失败都来自课程原始代码,我没有改写:

  • chapter03_linear_list/seq_list/SeqList.h:复制构造函数里的 getElem 应为 GetElem;
  • chapter03_linear_list/set_intersection/SeqList.h:同一处笔误的独立副本;
  • exercises_cpp_basics/Project1/main.cpp:原始演示入口存在指针 / 引用参数不匹配,属于未完成草稿。

保留它们是有意的:仓库首先是课程记录,其次才是作品集。把原始代码改“干净”会失去它作为学习材料的价值;但 README 里必须写清楚哪些能跑、哪些不能。

收获

这个仓库真正训练的不是“背算法”,而是三件事:

  • 把逻辑结构(线性、树、图)和存储结构(顺序、链式)分开想;
  • 用复杂度而不是“跑得快不快”来比较实现;
  • 让每个模块都能独立编译、独立运行、独立验证。

课程笔记、每周上机记录、部分章节讲义和运行截图也一并放在 docs/。

源码与文档:https://gitee.com/yicongl1/data-structures-cpp

技术文章

01 C++ 模板数据结构:顺序表、链表、栈与队列的泛型边界 template <class ElemType>、状态码、深拷贝与容量检查;以及一个只在实例化时才暴露的复制构造函数笔误。 02 从 KMP 到关键路径:把 36 个数据结构实验串成一张图 失效函数、递归数叶子、邻接表上的 Dijkstra 与关键路径;一套“头文件 + 演示入口”的实验组织方式。

相关技能

  • C++
  • Git