个人课程项目
上海大学 · 数据结构(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 等状态,调用方必须显式处理失败。这是课程代码的风格,也让边界条件变得可见。整理完成后,我用 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/。