简介一份来自南京航空航天大学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 写的中文注释多半是 GB2312Windows 自带记事本另存为又会变成带 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 -stdc11文件名里有中文括号命令行里最好用引号包住整条文件名或者先把文件重命名成 t3_final.cpp 再编避免 shell 对中文括号处理不一致。加 -stdc11 是因为代码里很可能用到 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(nr))稳定O(nr)桶数量与 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 开始递减保证最后一趟 gap1 时退化成普通插入排序所以正确性不需要怀疑。内层 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::vectorint a) { int maxVal *std::max_element(a.begin(), a.end()); for (int exp 1; maxVal / exp 0; exp * 10) { std::vectorint 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(nr)这里的 r 是桶数int 数据一般取 10。说句实话这份代码处理不了负数遇到负数要么整体加偏移量排序完再减回去要么单独做正负两个桶课设数据能控制的话没必要写这么复杂。3.5 counttime 计时别用 time(NULL) 来测毫秒级差距排序对比题一定要做计时但 time(NULL) 只能测到秒排序跑完常常显示 0根本分不出快慢。正确的做法是用 chrono 库#include cstdio #include chrono #include vector #include algorithm int main() { std::vectorint 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::durationdouble, std::milli(end - start).count(); printf(sort time %.3f ms\n, ms); return 0; }chrono 的 now() 取的是系统高精度时钟durationdouble, 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::vectorEdge 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 的 sortstruct Edge { int u, v, w; }; bool cmp(const Edge a, const Edge b) { return a.w b.w; } std::vectorEdge 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; } }新节点的编号从 n1 开始只用到 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 -stdc11加了 -static 之后 exe 体积变大但换机器直接双击能跑课设演示最稳。如果还是不行检查是不是用了 C17 特有语法老版本 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; } }模板化之后调用处的数组类型由编译器推导自定义结构体只要重载了 运算符就能排。这个改造让我在复试机试里省了不少事遇到需要快速写排序的场景直接套模板就行。从那以后我每次拿到别人的课设代码包都先复制一份底稿归档再统一转编码、编译原始代码、跑通数据文件最后才动手改。这套步骤看着繁琐但每一步都在消除不确定因素真正做到了“拿到就能跑跑了能答问”。希望帮到你。本文还有配套的精品资源点击获取