buaa-ds-kit 是一个为北京航空航天大学的《数据结构与程序设计》课程考试定制的一套资料和模板集。目前，《数据结构与程序设计》课程考试允许携带电子版资料。本仓库包含了课件内容总结以及常用算法和数据结构的封装，希望能够帮助到您。
如果您认为本项目对您有帮助，可以在 GitHub 上点一个 Star。如果您发现本项目存在问题，请在 GitHub 上提出 issues。如果您希望给本项目做出贡献，请在 GitHub 上提出 PR。
本项目使用 GPLv3 协议开源。
请您仔细阅读本文档的所有内容。
该项目直接以源代码的形式分发，安装十分简单。
如果您熟悉 git 的基本用法，您可以直接克隆本仓库：
git clone https://github.com/ExplodingKonjac/buaa-ds-kit如果您不熟悉也没有关系，您可以在 GitHub 主页面处点击 Code → Download ZIP 来下载源代码的压缩包版本。然后自行解压缩。
如果您不熟悉下载和解压缩操作也没关系，请您开始学习计算机的基础操作，并且为可能的课程重修做准备。
除此之外，本项目所需要的系统环境依赖包括：
- 支持 C99 标准的 C 编译器。
- Python 3.10 或更高版本的运行环境。
本项目大体分为三个版块：文档、脚本、header-only 库。
下面假设所有命令运行的工作目录都是仓库根目录。
本项目的文档位于目录 docs/ 下。所有文档都使用 Markdown 格式，如果您不想直接阅读 Markdown 源代码，请自行准备能渲染 Markdown 的阅读器。其中
0_绪论.md,1_数据结构基础.md,2_线性表.md,3_栈与队.md,4_树与二叉树.md,5_图.md,6_查找.md,8_排序.md是课件内容的总结，包含了课件的关键知识点以及定义的算法描述。docs/dsx/下的文档是dsx库的 API 文档。我们将在后文介绍dsx库。
本项目的脚本位于目录 scripts/ 下。所有脚本都用 Python 语言编写，无第三方依赖。您需要自行准备好 Python 3.10 或更高版本的运行环境，然后使用命令 python3 script_file.py 来运行脚本。
demo/ 目录下的脚本是课件算法演示，其可以帮助您理解算法或者解决一些选择题。所有脚本及其功能如下表：
| 脚本目录 | 脚本功能 |
|---|---|
scripts/demo/b_tree.py |
B-树构造演示，支持指定阶数，输出逐步插入、结点分裂和最终树形层次。 |
scripts/demo/binary_insertion_sort.py |
折半插入排序演示，输出每轮排序结果和比较次数。 |
scripts/demo/bst.py |
二叉搜索树构造演示，可输出树形结构、比较次数，并支持逐步输出和重复元素。 |
scripts/demo/bubble_sort.py |
冒泡排序演示，输出每轮排序结果和比较次数。 |
scripts/demo/dijkstra.py |
Dijkstra 最短路径演示，支持有向图和无向图输入，输出从源点到各点的路径和长度。 |
scripts/demo/expression_tree.py |
表达式树构造演示，支持中缀、前缀和后缀表达式输入，输出表达式树及不同遍历形式。 |
scripts/demo/heap.py |
堆构造演示，支持大根堆和小根堆，可输出序列形式、树形结构和逐步构造过程。 |
scripts/demo/heap_sort.py |
堆排序演示，输出建堆、出堆过程和比较次数。 |
scripts/demo/huffman_tree.py |
Huffman 树构造演示，输出树形结构和带权路径长度。 |
scripts/demo/insertion_sort.py |
直接插入排序演示，输出每轮排序结果和比较次数。 |
scripts/demo/merge_sort.py |
归并排序演示，输出每轮归并结果和比较次数。 |
scripts/demo/mst.py |
最小生成树演示，基于 Kruskal 算法输出选中的边和总权值。 |
scripts/demo/quick_sort.py |
快速排序演示，输出每次划分后的序列和比较次数。 |
scripts/demo/selection_sort.py |
简单选择排序演示，输出每轮排序结果和比较次数。 |
scripts/demo/shell_sort.py |
希尔排序演示，输出每轮排序结果和比较次数。 |
这些脚本都从 stdin 读入信息，也接受一些命令行参数来控制行为。您可以使用 --help 参数来获取脚本的输入格式和参数格式：
python3 <script_path> --help比如
python3 scripts/demo/bst.py --help可以输出帮助文档；
usage: binary_search_tree.py [-h] [--steps] [--multi]
Demonstrate binary search tree construction
options:
-h, --help show this help message and exit
--steps Whether to print the tree structure step by step
--multi Whether to allow multiple nodes with same values in the tree
input format:
The script reads from stdin in the following format:
<a_1> <a_2> ... <a_n>
where `n` is the number of inserted elements and each element must be an integer.
为了方便开发我们并未准备中文版本的文档翻译。相信您具备阅读这些简单英语的能力。如果不能的话，可以在考试前提前借助机器翻译或者 LLM，预先熟悉好脚本功能，以免在考试期间浪费时间。
scripts/package.py 是用于将 dsx 库依赖和您的程序源代码打包到同一个 ZIP 压缩包的脚本。假设您要提交的源代码路径是 /path/to/your/source.c，那么您需要运行脚本：
python3 scripts/package.py /path/to/your/source.c就会自动打包生成一个 ZIP 文件 /path/to/your/source.zip。希冀平台支持提交 ZIP，您只需要提交这个 ZIP 文件至评测系统即可。
您也可以指定输出目录：
python3 scripts/package.py /path/to/your/source.c -o /path/to/the/output.zip这样输出的文件就会位于 /path/to/the/output.zip。
本项目提供了一个 header-only 的 C 库 dsx（stands for Data Structure eXam）。其中包含了常用算法和数据结构的封装，如下表：
| 头文件 | 简介 |
|---|---|
dsx/avl.h |
使用宏为指定元素类型生成 AVL 树，支持自动旋转维护平衡。 |
dsx/bst.h |
使用宏为指定元素类型生成二叉搜索树，支持动态结点分配和整树释放。 |
dsx/common.h |
定义 DSX 公共状态码和工具宏，如数组长度、变量交换和可选断言。 |
dsx/expr.h |
提供表达式树构造、遍历、整数求值和释放函数，支持中缀、前缀、后缀表达式。 |
dsx/graph.h |
使用宏生成邻接表图类型，支持添加顶点、添加边、DFS、BFS、Prim、Kruskal 和 Dijkstra。 |
dsx/hashmap.h |
使用宏生成动态 HashMap 和 HashSet，基于开放寻址实现。 |
dsx/huffman.h |
使用宏为指定权值类型生成 Huffman 树构建和带权路径长度计算函数。 |
dsx/list.h |
提供单向链表和双向链表，适合在已知结点附近频繁插入或删除元素。 |
dsx/pqueue.h |
使用宏为指定元素类型生成基于二叉堆的优先队列。 |
dsx/queue.h |
使用宏为指定元素类型生成自动扩容的循环数组队列。 |
dsx/sort.h |
使用宏为指定元素类型生成常见排序算法函数。 |
dsx/stack.h |
使用宏为指定元素类型生成动态数组栈。 |
dsx/strutils.h |
提供自动扩容字符串类型和字符串列表，封装常见 C 字符串操作。 |
dsx/trie.h |
使用宏为指定字符集生成动态分配的 Trie。 |
dsx/vector.h |
使用宏为指定元素类型生成自动扩容的动态数组。 |
由于篇幅有限，这里不会详细展开所有头文件的具体功能。但是 docs/dsx/ 目录下的文档有这些头文件的详细 API 参考以及示例，每个头文件都有一个对应的 Markdown 文档。
要使用这些头文件有两种方法：
-
如果您比较熟悉编译器的操作，那么可以在编译命令中加入
-I选项来设置头文件搜索目录。比如对于 GCC：gcc source.c -o source -I <repo_root>/include
其中
<repo_root>是您下载本仓库的位置。 -
如果您不熟悉编译器也没有关系。假设您的代码位于
<workspace>文件夹，那么您可以直接将include/目录下的内容拷贝到<workspace>（您应该得到<workspace>/dsx文件夹）。然后，所有直接放置在<workspace>下的源代码编译时都可以搜索到这些头文件。
完成上述操作之后，您可以直接 #include 这些头文件了：
#include "dsx/vector.h"注意这里需要使用双引号而不是尖括号。因为尖括号是为系统头文件使用的。
本项目是面向《数据结构与程序设计》课程复习和考试场景的辅助资料，不是课程组官方资料。课程内容、考试范围、考试规则和评测平台要求都可能发生变化，使用前请以任课教师、课程网站和评测平台的最新要求为准。
本文档和 docs/ 下的课程总结只保证尽量贴近课件内容，不保证覆盖所有知识点，也不保证表述与课程组标准答案完全一致。遇到定义、复杂度、算法细节存在差异时，请优先以课程课件和教师说明为准。
dsx 库和脚本已经经过基本测试，但它们仍然可能存在缺陷。请在考试或提交前自行编译、运行和验证自己的程序，不要在完全不了解代码行为的情况下直接套用。特别地，涉及动态内存分配的数据结构通常需要调用对应的释放函数，具体用法请查看 docs/dsx/ 下的 API 文档。
本项目使用 GPLv3 协议开源。如果您复制、修改或分发本项目代码，请遵守 LICENSE 中的许可证条款。是否允许在具体考试中携带、使用、修改或提交本项目中的内容，也请自行确认课程规则；本项目不为任何违反考试纪律或学术规范的行为背书。
如果您希望修正错误、补充文档、改进脚本或扩展 dsx 库，欢迎通过 issue 或 pull request 参与贡献。提交修改前，请尽量保持改动范围清晰，避免把无关格式化、重命名和功能修改混在同一个 PR 中。
本仓库的主要目录职责如下：
docs/：课程内容总结和dsxAPI 文档。include/dsx/：header-only C 库源码。scripts/：Python 脚本，包括算法演示脚本和打包脚本。tests/dsx/：dsx头文件的测试程序。ppt/：课程课件原文件。
修改 include/dsx/ 下的头文件时，请同步检查并更新对应的 docs/dsx/*.md 文档。如果新增头文件，也请同时补充测试、API 文档，并更新本文档中的 header-only 库表格。
修改或新增脚本时，请保持脚本无第三方依赖，并为命令行参数提供 --help 说明。算法演示脚本应尽量从 stdin 读取输入，输出格式要便于人工核对中间过程。
修改 dsx 库后，建议运行测试：
bash tests/run_dsx_tests.sh测试脚本会使用 GCC 以 C99 标准编译并运行 tests/dsx/ 下的测试程序。如果您新增了数据结构、算法或边界行为，请补充相应测试。
提交 PR 前建议至少确认以下事项：
- README 和相关 API 文档已经同步更新。
- 新增或修改的 C 代码能通过
tests/run_dsx_tests.sh。 - 没有提交临时文件、编译产物、压缩包或
__pycache__等缓存目录。 - 没有引入额外依赖，除非确实必要并已在文档中说明。
- 修改符合 GPLv3 协议要求，并且您有权贡献相关内容。