简介：一份来自南京航空航天大学2019-2020年秋季学期数据结构课程设计的完整代码与报告资源，主要面向正在修读数据结构、需要完成课程设计任务的高校学生。资源共76个文件，以36个C++源文件为核心，包含多个课程设计题目实现，如Kruskal最小生成树、Huffman编码、多种排序算法及邻接表等经典数据结构应用；另有31个TXT文件提供测试数据与运行输出，6个EXE可直接运行验证，1个DOCX为课程设计报告，整体压缩包约6.2MB。代码全部为个人原创，报告与代码互相配合，重点展示设计思路与关键实现细节。已有2788人学习下载，适合在课程设计过程中需要参考完整方案、快速搭建代码框架或核对算法逻辑的学习者。
1. 一份能直接跑的南航课设代码包：它到底帮你省了什么
期末考试周拿到数据结构课程设计的题，最难受的不是不会写，而是不知道代码写到什么程度才算做完。我拆这份南京航空航天大学的数据结构课程设计代码加报告时，第一反应是：条件齐全，可以照着跑。排序、图、树、哈夫曼编码这些经典点都有，每个题目独立成一个 cpp，配套 data 数据文件、可执行程序和课程设计报告。它解决的问题很具体——数据结构算法的落地边界：邻接表怎么存、kruskal 的并查集怎么敲、多个排序怎么统一计时。适合正在赶课设、准备复试，或者想快速把手写 C++ 算法跑通的人。
2. 拆包之前：T编号、data数据文件与“完成版”命名背后的设计意图
压缩包解开后第一眼会很乱：十几二十个 cpp、一份 docx 报告，还有成片的 data 和 txt 文件。别急着开 IDE，先把命名规律读出来，能省一晚上。
2.1 从文件名读出题目组织方式
没有说明文档，但文件名本身把组织方式交代得很清楚。T 前缀是题目编号，T3、T5、T12 各对应一题；后面跟“(完成)”的是可交付版本，不带的多数是当时写到一半的中途稿。比如 T5(用bit输出未完成).cpp，看名字就知道是用位运算写了一半没跑通，而 T5（完成）.cpp 才是最终代码。包里还有 T4（完成）、T6(1)、T6(2) 这样的双版本，说明同一题反复改过不止一次。
data 开头的文本文件是各题目的测试输入，data7.txt、data14.txt、data21.txt 对应不同数据规模。cs 开头的 cpp 基本是临时测试程序，csgb.cpp 就是国标排序的验证代码，cs5.cpp、cs6.cpp 是当时调试用的辅助文件。排序模块单独放着 AllSort.cpp、random.cpp 和几个 exe，一看就是专门做了“排序算法对比”这个课设题。包里还有 .DS_Store，说明这份资料是从 macOS 上打包拷贝出来的，Windows 上可以直接删掉。
把文件名分个类才能对上号，我整理了一张对照表：
| 命名格式 | 含义 | 使用方式 |
|---|---|---|
| T编号（完成）.cpp | 第编号题的最终版 | 直接打开编译运行 |
| T编号.cpp | 第编号题的中途版 | 保留备用，一般不交 |
| data数字.txt | 对应题目测试数据 | 放到可执行文件同目录 |
| AllSort.cpp / 各排序.exe | 排序模块总集与成品 | 跑算法对比用 |
| random.cpp / counttime.cpp | 随机数据与计时工具 | 生成输入、测耗时 |
| 课程设计报告.docx | 课设正文 | 和代码配套读 |
2.2 把源文件放进 IDE 跑通的三个固定动作
每个人都有自己惯用的编译环境，我一般 Dev-C++ 和 VS Code 换来换去。这套代码大概率是在同一台机器上写出来的，换环境后最容易翻车的不是算法逻辑，而是编码和路径。我拿到手后固定做三个动作。
第一步，统一文件编码。老电脑上 Dev-C++ 写的中文注释多半是 GB2312，Windows 自带记事本另存为又会变成带 BOM 的 UTF-8。我习惯先把全部源码备份，再用 VS Code 批量把 cpp 和 txt 转成 UTF-8 无 BOM，这样在 MinGW 下编译不会出现“常量中有换行符”“stray ‘\327’ in program”这类报错。
第二步，把数据文件放到编译产物的当前目录。很多程序写的是相对路径，直接 ifstream 打开 data7.txt，如果 debug 目录和工作目录不一致就会读不到。最省事的方式是把要跑的 data 文件复制到 exe 同一个文件夹，Windows 下用命令行一次性完成：
mkdir build copy data*.txt build\先创建 build 目录，再把所有以 data 开头的文本文件复制进去。注意 copy 不会自动建目录，所以 mkdir 要放前面。如果还要带上家谱.txt、Huffman.txt，就改成 copy *.txt build\。
第三步，单独编译单个题目，而不是一上来就编译整个工程。因为每个 cpp 都有 main，多个 cpp 同时进工程会报 multiple definition。我一般按题目逐个编译：
g++ T3（完成）.cpp -o T3.exe -std=c++11文件名里有中文括号，命令行里最好用引号包住整条文件名，或者先把文件重命名成 t3_final.cpp 再编，避免 shell 对中文括号处理不一致。加 -std=c++11 是因为代码里很可能用到 vector、unordered_map 等新特性，老标准编译会报错。
如果想快速知道这个包里哪些文件可以独立运行，直接搜主函数：
grep -l "int main" *.cpp把带 main 的 cpp 列出来，其余没有 main 的基本是辅助文件或测试片段。这个命令在 Windows 的 Git Bash 或 Mac 终端下都能用，比一个个打开文件快得多。
2.3 多个题目共用一个工程的主分发器写法
有些老师要求把所有题目汇总成一个菜单程序，这时多个 main 就得合并。处理办法是保留一个 main，把其余 main 改名成 SolveT3()、SolveT5() 这样的函数，再加一个分发器：
#include <cstdio> void SolveT3(); // 题目3，排序 void SolveT5(); // 题目5，查找 void SolveT12(); // 题目12，图论 int main() { int choose = 0; printf("1. T3 排序 2. T5 查找 3. T12 图论\n"); scanf("%d", &choose); if (choose == 1) SolveT3(); else if (choose == 2) SolveT5(); else if (choose == 3) SolveT12(); else printf("No such choice.\n"); return 0; }这里的函数对外统一成 void SolveTxx()，main 只负责读选项然后分发。改动的成本很低：把旧代码里的 int main() 这一行改成 void SolveTxx()，其余逻辑原样保留。数据文件依然走相对路径，菜单程序不用关心具体数据是哪一份。要注意函数名不能和变量名冲突，旧的 main 如果被注释了就别再恢复，否则链接阶段照样报 multiple definition。
这样拆完包，每个题目的代码位置、数据文件、编译方式都清楚了。接下来才是真正动手改代码的阶段。
3. 排序算法板子：希尔、归并、基数、快排的参数与计时边界
包里的 AllSort.cpp、希尔排序.exe、归并排序.exe、基数排序.cpp、random.cpp 和 counttime.cpp 组成了一套完整的排序算法对比实验。这类题在南航数据结构课设里很常见，做法也最标准：同一组随机数据，用不同算法分别跑一遍，记录耗时和比较次数，写进报告。
3.1 四类排序在课设报告里的选型逻辑
做排序对比前，先想清楚要突出什么。希尔排序可以讲 gap 序列的影响，归并排序可以讲分治思想，基数排序可以讲空间换时间，快速排序则要强调最坏情况退化的风险。我在课设报告里常用这样一张表：
| 算法 | 平均时间复杂度 | 稳定性 | 额外空间 | 报告里适合分析的指标 |
|---|---|---|---|---|
| 希尔排序 | 约 O(n^1.3) | 不稳定 | O(1) | gap 序列选择 |
| 归并排序 | O(n log n) | 稳定 | O(n) | 分治和临时数组开销 |
| 基数排序 | O(d(n+r)) | 稳定 | O(n+r) | 桶数量与 d 的关系 |
| 快速排序 | 平均 O(n log n) | 不稳定 | O(log n) | 基准值选择与退化 |
希尔排序在小规模数据上经常比归并快，因为归并的递归调用和临时数组拷贝开销不小；数据量过了十万之后，归并和快排的优势才体现出来。基数排序对非负整数最稳，但一旦遇到负数，桶的设计就要重做。这些结论不是背出来的，是在 counttime.cpp 跑几轮之后自然得出来的。
3.2 希尔排序：gap 怎么定才不玄学
希尔排序的核心是分组插入排序。课设里最常见的写法是 gap 从 n/2 开始每次折半，直到 1。代码很短，但边界条件容易写错：
void shellSort(int a[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = a[i], j = i; while (j >= gap && a[j - gap] > temp) { a[j] = a[j - gap]; j -= gap; } a[j] = temp; } } }gap 从 n/2 开始递减，保证最后一趟 gap=1 时退化成普通插入排序，所以正确性不需要怀疑。内层 while 不是交换，而是把较大的元素往后移，等价于插入排序里的移位。注意 j >= gap 这个判断，如果写成 j >= 0 而 a[j-gap] 会访问负下标，读到的就是野指针。外层循环条件写 gap > 0 而不是 gap >= 1，因为整数除法最终会从 1 变成 0，写成等于 1 会出现死循环。
3.3 归并排序：临时数组到底开多大
归并排序最容易翻车的地方不是递归逻辑，而是临时数组。正确做法是一次性开好 n 个 int，在递归里复用，而不是每次合并都 new 一块内存：
void merge(int a[], int left, int mid, int right, int temp[]) { int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; while (j <= right) temp[k++] = a[j++]; for (int t = 0; t < k; t++) a[left + t] = temp[t]; } void mergeSort(int a[], int left, int right, int temp[]) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(a, left, mid, temp); mergeSort(a, mid + 1, right, temp); merge(a, left, mid, right, temp); }mid 用 left + (right - left) / 2，能避免 (left + right) 溢出，数据量接近 2^31 时这个写法才是安全的。合并时用 <= 保证相等元素不交换，这就是稳定性的来源。两个 while 把剩余元素兜进临时数组，少一个就丢数据。最后必须把 temp 拷回原数组，漏掉这一步，下一轮递归拿到的就是半成品数据。
快排在 AllSort.cpp 里一般也会出现，写法大同小异：取中位数为基准，双指针往中间扫，左右递归。做课设时要注意递归深度，数据本来有序的情况下如果基准取端点，快排会退化到 O(n²)，所以别用最朴素的端点基准写法。
3.4 基数排序：桶的大小和负数处理
基数排序按个位、十位、百位依次装桶。课设里数据文件通常是正整数，桶数取 10 就够了：
void radixSort(std::vector<int>& a) { int maxVal = *std::max_element(a.begin(), a.end()); for (int exp = 1; maxVal / exp > 0; exp *= 10) { std::vector<int> bucket[10]; for (int x : a) { int digit = (x / exp) % 10; bucket[digit].push_back(x); } int idx = 0; for (int d = 0; d < 10; d++) for (int v : bucket[d]) a[idx++] = v; } }exp 是当前位的权重，从 1 开始，每次乘 10，直到最大值的最高位被处理完。bucket 用 vector 数组省去手写链表的麻烦。空间复杂度是 O(n+r)，这里的 r 是桶数，int 数据一般取 10。说句实话，这份代码处理不了负数，遇到负数要么整体加偏移量排序完再减回去，要么单独做正负两个桶，课设数据能控制的话没必要写这么复杂。
3.5 counttime 计时：别用 time(NULL) 来测毫秒级差距
排序对比题一定要做计时，但 time(NULL) 只能测到秒，排序跑完常常显示 0，根本分不出快慢。正确的做法是用 chrono 库：
#include <cstdio> #include <chrono> #include <vector> #include <algorithm> int main() { std::vector<int> a(100000); // 这里用 random.cpp 生成的随机数填充 a auto start = std::chrono::high_resolution_clock::now(); std::sort(a.begin(), a.end()); auto end = std::chrono::high_resolution_clock::now(); double ms = std::chrono::duration<double, std::milli>(end - start).count(); printf("sort time = %.3f ms\n", ms); return 0; }chrono 的 now() 取的是系统高精度时钟，duration<double, std::milli> 把开始结束的差值换算成毫秒并保留三位小数。注意这里排的是同一个数组副本，如果直接对原数组排序，测第二个算法时数据已经部分有序，结果会虚低。正确做法是每轮开始前复制一份原始数组。计时结果可以存进 log.txt，报告里的曲线直接用它画。
说到这想起来，random.cpp 生成随机数据时最好用 std::mt19937 而不是 rand()，rand() 在多平台下的质量参差不齐，有可能会生成重复度很高的序列，导致排序对比的结论不稳定。
4. 图与树：kruskal、邻接表、家谱和哈夫曼的实现细节
图论部分有邻接表.cpp、kruskal.cpp，以及 T12、T8 等题目；树结构部分对应家谱.txt 和 Huffman.txt。这几个题目的实现都不算复杂，难的是把数据文件的结构和代码的数据结构对上。
4.1 邻接表：先想清楚顶点编号从 0 还是 1 开始
邻接表本身不难，难在一致性。数据文件里顶点编号是 0 开头还是 1 开头，决定数组下标要不要减一。我习惯用结构体加 vector 模拟链式存储：
struct Edge { int to, weight; }; std::vector<Edge> graph[1005]; void addEdge(int u, int v, int w) { graph[u].push_back({v, w}); graph[v].push_back({u, w}); // 无向图要加反向边 }这里的节点数组开 1005，是为了防止顶点编号从 1 开始时下标越界。addEdge 里第二行是无向图的反向边，题目如果明确是单向边就去掉；是无向图但漏了反向边，DFS 会漏掉一半路径，最小生成树也会算错。weight 在最短路径相关的题里必须有，纯连通性检测可以不要。
遍历的时候配合布尔数组标记已访问节点：
void dfs(int u, bool vis[]) { vis[u] = true; for (auto e : graph[u]) { if (!vis[e.to]) dfs(e.to, vis); } }递归的 DFS 在节点数很大的时候有栈溢出风险。如果数据文件里顶点数超过一万，建议改成栈模拟或者 BFS。课堂上讲的递归写法最多支撑几千个节点。
4.2 Kruskal 最小生成树：并查集的压缩和边排序
Kruskal 算法分三步：把边按权值排序，逐条取最小边，用并查集判断是否会成环。并查集是这里最容易写错的部分：
int fa[1005]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void unionSet(int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) fa[ra] = rb; }find 里的路径压缩是核心，递归时把当前节点直接挂到根节点下面，能把链式集合的查询从 O(n) 降到近似 O(1)。unionSet 这里只做了简单合并，没有按秩合并，1000 个节点以内影响不大；如果课设数据给到十万级，最好加一个 rank 数组优化。
配合并查集的边排序，直接用 STL 的 sort：
struct Edge { int u, v, w; }; bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; } std::vector<Edge> edges; std::sort(edges.begin(), edges.end(), cmp);cmp 里一定要用小于号，写成大于号就把最大生成树了。选边的循环里检查两个顶点是否已在同一集合，不在才合并并输出这条边，生成树的边数达到 n-1 就可以提前结束。
4.3 家谱和哈夫曼：树形结构的两套实现
家谱.txt 涉及的是家族关系，通常用树结构存孩子节点。如果用左孩子右兄弟的表示法，可以处理任意多孩子的家谱树；如果题目只是输出某人的所有后裔，孩子链表就够了。哈夫曼编码是另一类树题，核心在建树和生成编码表：
struct Node { int weight; char ch; int left, right, parent; }; void buildHuffman(Node nodes[], int n) { for (int i = n + 1; i <= 2 * n - 1; i++) { // 找两个当前最小权值节点 int m1 = 0, m2 = 0; for (int j = 1; j < i; j++) { if (nodes[j].parent == 0) { if (m1 == 0 || nodes[j].weight < nodes[m1].weight) { m2 = m1; m1 = j; } else if (m2 == 0 || nodes[j].weight < nodes[m2].weight) { m2 = j; } } } nodes[m1].parent = i; nodes[m2].parent = i; nodes[i].left = m1; nodes[i].right = m2; nodes[i].weight = nodes[m1].weight + nodes[m2].weight; } }新节点的编号从 n+1 开始，只用到 2n-1，所以数组容量至少要开 2n。m1、m2 维护的是两个最小权值节点，这段双 if 判断第一次写容易漏掉第二小的更新；更保险的写法是扫两遍，第一遍找最小值，第二遍找次小值，逻辑直白不容易错。哈夫曼编码表的生成本质是 DFS 二叉树：左子树记 0，右子树记 1，从叶子顺着 parent 回溯到根，把路径反转就是字符的码字。
4.4 图数据文件的读取和自检
读取图数据文件这一步，最容易出现格式不对导致读入全 0。典型写法是：
int n, m; FILE* fin = fopen("data14.txt", "r"); fscanf(fin, "%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v, w; fscanf(fin, "%d %d %d", &u, &v, &w); addEdge(u, v, w); } fclose(fin);fscanf 的读取格式必须和数据文件里的列数一致：三列就是三个 %d，两列就不能读 w。读完之后自己用几个 printf 验证 n、m 和前几条边，这一步能省下后面大把排错时间。我见过不少翻车现场，最后发现是 data 文件里混入了空行或者全角逗号，fscanf 直接读失败。
5. 避坑记录：这套课设包里最容易翻车的六个点
拆这份包的这半个月，我踩了不少坑，有些是文件版本问题，有些是开发环境问题，记录下来比较有通用性。
5.1 中文注释乱码导致编译报错
现象：Dev-C++ 里打开源码是正常的，换到 VS Code 或者 MinGW 命令行编译，啪啦啦报一堆 stray ‘\377’ in program、stray ‘\327’。
原因：源码文件用的是 GBK 编码，编译器按 UTF-8 解读中文字符，把注释里的多字节字符当成了分隔符和非法 token。
解决：先备份，再用 VS Code 打开乱码的 cpp，右下角编码菜单选择“通过编码重新打开”，切到 GBK，然后另存为 UTF-8。批量转码可以用命令：
iconv -f GBK -t UTF-8 -o T3_fixed.cpp "T3（完成）.cpp"-f 是源编码，-t 是目标编码，-o 输出到新文件。注意转码后中文字符串在内存里的字节数变了，如果代码里手工按 strlen 截取中文，输出就会错位。
5.2 同名数据文件多份，程序读错输入
现象：同一个题目跑两次，结果差很多，排除随机因素后发现数据文件对不上号。
原因：data7.txt、data7(1).txt、data7(2).txt 同时存在，代码里写死打开 data7.txt，但那份文件的内容是另一道题的输入。
解决：运行前先 grep 代码里 fopen、ifstream 引用的文件名，再检查当前目录那份文件的行数是否和数据规模一致。用文本编辑器打开对比一下，比在代码里打断点快得多。
5.3 未完成版和完成版混用，交上去跑出半成品
现象：打包交作业时选中了 T5(用bit输出未完成).cpp，题目分数直接腰斩。
原因：文件名后缀“(完成)”没看清，或者整理目录时把同名文件搞混了。
解决：我现在的习惯是交之前用脚本把带“（完成）”的文件单独复制到一个 deliver 目录：
mkdir deliver cp *（完成）*.cpp deliver\复制完进去人工核对一遍每个文件的最后一次修改时间。整个操作顺序固定下来之后，再没交错过文件。
5.4 换电脑后 exe 跑不了
现象：在宿舍电脑上编译好的 exe，拿到教室电脑双击没反应，提示缺少 MSVCP140.dll 之类的运行库。
原因：MinGW 或 MSVC 编译产物默认动态链接运行库，目标机器没装对应运行环境。
解决：编译时加 -static 把运行库打进去：
g++ "T3（完成）.cpp" -o T3.exe -static -std=c++11加了 -static 之后 exe 体积变大，但换机器直接双击能跑，课设演示最稳。如果还是不行，检查是不是用了 C++17 特有语法，老版本 GCC 对某些新特性支持不完整。
5.5 相对路径读取失败，数据文件明明在文件夹里
现象：程序启动正常，fopen 一直返回 NULL，数据文件就在旁边。
原因：工作目录不等于 exe 所在目录。IDE 里跑时工作目录是工程目录，命令行直接跑则是系统盘的当前路径。
解决：最简单的方式是 cd 到 exe 所在目录再运行：
cd build T3.exe或者代码里用绝对路径拼接。我一般图方便，直接要求所有 data 文件和 exe 放同一目录，用相对路径打开。
5.6 固定数组开小导致越界
现象：家谱人数超过 1000 程序崩溃，哈夫曼节点开到 2n 还是越界。
原因：数组定成 1000 或者 2n，题目上限再加一就爆了。
解决：数组容量直接用约束上限加 5 的余量：
const int MAXN = 10005; int fa[MAXN];哈夫曼要开 2 * MAXN，留出余量之后这类问题基本绝迹。经验是固定数组的容量绝不写“刚刚好”，宁可多开也不要让程序在边界线上蹦迪。
6. 把“课设代码”变成“自己的代码”：验证、答辩与改造
能跑通别人的代码只是第一步，课设答辩老师问几个问题就能知道你是真懂还是背答案。我的应对方法是把整包代码按下面这套流程处理一遍。
6.1 用随机数据验证正确性，给报告攒图表
排序类的题，用 random.cpp 生成几组不同规模的数据，分别跑 AllSort 里的各个算法，把时间记录成表格。这样报告里有了自己的实验数据，代码也验证过正确性。图论类的题，可以写一个暴力求解器，比如把 Kruskal 的结果和全排列枚举的结果对比，验证并查集写对了。
6.2 从报告反推代码逻辑，练“答辩讲述”
课程设计报告里通常写了每个题目的设计思路、核心代码和测试结果。答辩前我会打开报告，对着每个模块的流程图，从 main 函数开始把代码从头走一遍，边讲边问自己“这一步在报告里对应哪一段”。练个两三遍，老师问“你这个算法为什么选这个结构”，你能指着报告里的分析段落回答出来，比临时背代码靠谱得多。
6.3 模板化改造，让排序函数支持更多类型
既然代码都是手写的，顺手做个泛型化改造，复试或考研数据结构、算法题复习时都能复用。把排序函数的 int 改成模板参数，就能同时支持 int、double 和自定义结构体：
template <typename T> void insertSort(T a[], int n) { for (int i = 1; i < n; i++) { T temp = a[i]; int j = i - 1; while (j >= 0 && a[j] > temp) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; } }模板化之后，调用处的数组类型由编译器推导，自定义结构体只要重载了 > 运算符就能排。这个改造让我在复试机试里省了不少事，遇到需要快速写排序的场景，直接套模板就行。
从那以后我每次拿到别人的课设代码包，都先复制一份底稿归档，再统一转编码、编译原始代码、跑通数据文件，最后才动手改。这套步骤看着繁琐，但每一步都在消除不确定因素，真正做到了“拿到就能跑，跑了能答问”。希望帮到你。
本文还有配套的精品资源，点击获取
