
简介面向高校数据结构课程与计蒜客实验场景的2021年USTB综合实验参考实现覆盖公司管理系统、文本编辑程序、文学作品分析、滤镜功能、排位系统、高速路网设计六个递进式任务适合计算机专业本科生对照学习C数据结构的综合运用与工程化组织。压缩包共82个文件以33个cpp源码、14个头文件和12个Makefile为主辅以png结果截图、txt输出样例、PDF说明文档及少量c文件代码与构建脚本分层存放便于按Work模块独立编译调试。资源整体约1.55MB已有3022人学习下载。内容不仅给出各实验的完整可运行方案还包含输入输出样例、关键算法实现如哈希表、堆排序、图像像素处理等和开发环境说明能够帮助读者理解从问题建模、模块划分到测试验证的完整流程适合期末复习或实验报告撰写前参考。 去年上半年我把大量的时间都泡在计蒜客上做北科大那套“2021-USTB-数据结构实验”的题目。第一次打开实验列表的时候我其实是有点懵的课程里讲链表、讲树、讲图到了实验平台上却变成一道道输入输出格式卡得死死的编程题交上去以后不是答案错误就是运行超时一度有点怀疑人生。但这套实验做完之后我有一个很明确的感受数据结构如果不落到代码上永远只是纸面上的概念反过来把这套题弄明白基本能把整个数据结构的主线串起来对后续算法课甚至考研408都有实打实的帮助。这篇文章不打算贴完整实验报告而是想把我在计蒜客平台上做这套实验时的整体思路、关键代码写法、以及反复踩过的坑整理出来。不管是正在做这套实验的学弟学妹还是想复习数据结构基础、准备机试的同学应该都能从中拿到一些可以直接用的东西。1. 实验整体印象它在考什么1.1 别把它当成普通OJ题计蒜客上的数据结构实验和平时刷题用的在线评测平台相比最大的区别是它不考竞赛里那种偏门技巧而是非常“教科书”。题目基本上按照线性表、栈和队列、二叉树、图、查找、排序这几个经典模块来出每一道题都在要求你把课本上的某个数据结构用代码实现出来再套一层特定的输入输出场景。举个例子课本里讲的“循环链表”可能就几行伪代码但实验题会让你读入一串数字按某种规则建立链表再在指定位置做插入删除最后输出若干轮操作后的结果。这时候你必须考虑用带头节点的链表还是不带头节点删除节点之后指针怎么改内存要不要手动释放这些细节恰恰是课堂上看不到的东西。所以我建议拿到题目之后先想清楚它对应课本哪一章的知识点再动手写效率会高很多。1.2 计蒜客平台到底好在哪刚开始我也会问为什么课程实验不放在普通的OJ上而是用计蒜客做过之后发现它有几点很适合教学场景。首先是评测环境统一谁也没法拿“在我电脑上能跑”来当借口编译器和版本都是平台定好的其次是提交记录都在助教可以看你的代码、运行结果和提交次数对实验报告的真实性帮助很大再者在线评测会强制你考虑边界条件因为平台准备的测试数据往往比你本地随手造的样例刁钻得多这比纯写纸质实验报告更有训练价值。不过也要提醒一点计蒜客的评测对输出格式要求非常严格多一个空格、少一个换行都可能导致答案错误。平台上的C/C环境对语言标准支持得比较传统虽然C11的常用特性没问题但别依赖太新的库函数。这些都是后话下面逐一展开。2. 重难点拆解这几个模块最容易翻车2.1 线性表指针不是万能的线性表题目看起来简单反而最容易出问题。常见题型有顺序表插入删除、单链表就地逆置、两个有序链表合并、循环链表判断等。很多同学一上来就定义struct Node { int data; Node* next; }然后各种new节点思路清晰代码也确实能过但稍不注意就会写出野指针。我在做这类题时有个习惯先画出节点的连接图标清楚每个指针在操作前后指向谁再写代码。比如单链表就地逆置核心就是“先保存后继再改指向”Node* reverse(Node* head) { Node* prev NULL; Node* cur head; while (cur) { Node* next cur-next; // 先保存后继 cur-next prev; // 反转当前节点 prev cur; // 移动prev cur next; // 移动cur } return prev; }这段逻辑看着简单但第一次写的人很容易把cur cur-next写在cur-next prev之后结果指针指飞了。另外如果平台禁止额外空间那就不能开数组去存节点再逆序输出必须用指针操作。真正写实验报告时我还会把节点释放的部分加上避免内存泄漏这也是报告的一个加分项。2.2 树和二叉树递归与非递归的平衡树这块是重头戏。实验里常见的是给出前序和中序序列要求重建二叉树或者要求按层次输出节点再进阶一点会要求求树高、统计叶子节点数。递归版本很好写但也有坑如果树的深度很大递归调用栈会溢出做层序遍历时如果忘了用队列或者把“空节点”也盲目入队输出就会错位。我见过很多同学在建树时这样写Node* build(char pre[], char in[], int l1, int r1, int l2, int r2) { if (l1 r1) return NULL; char rootVal pre[l1]; int pos l2; while (in[pos] ! rootVal) pos; Node* root new Node(rootVal); int leftLen pos - l2; root-left build(pre, in, l1 1, l1 leftLen, l2, pos - 1); root-right build(pre, in, l1 leftLen 1, r1, pos 1, r2); return root; }这段代码看起来清爽但问题在于递归边界l1 r1和l2 r2的判定。如果序列下标算错一位程序就会越界访问在计蒜客上稳拿Runtime Error。我的建议是树相关的题目不要凭感觉写下标先在草稿纸上拿一个小例子把每个区间的边界推一遍哪怕多花五分钟也比反复提交节省时间。2.3 图、排序与查找基础表达比“炫技”重要图这一块的实验题通常是给定邻接表或邻接矩阵要求做深度优先搜索、广度优先搜索或者判断连通分量个数。有些基础好的同学一看到图就想上并查集、Dijkstra、Kruskal但在数据结构实验里老师更想看到的是你对邻接表建图、DFS/BFS访问顺序这些基础内容的掌握而不是一上来就套算法模板。我的建议是把最基础的DFS递归版本和BFS队列版本写熟练再考虑优化。排序和查找题相对来说最容易AC但也最容易忽视细节。排序题常常会问你“在某一趟排序之后数组长什么样”这要求你对冒泡、选择、插入、快排、堆排的实际执行过程非常熟悉不能只会调sort()。查找题则集中在二分查找和二叉排序树的插入、删除、查找注意重复元素和边界下标的处理。3. 实操记录从搭建环境到AC3.1 输入输出与本地环境准备计蒜客这类平台的题目输入输出格式往往是第一个“拦路虎”。很多题目不是单组数据而是“输入包含多组测试用例每组以某个条件结束”所以最常用的结构就是int n; while (scanf(%d, n) ! EOF) { // 处理一组数据 }如果题目要求读到某个特定值结束比如输入0表示结束那就是while (scanf(%d, n) 1 n ! 0) { // ... }我本人在本地习惯用CLion来写调试方便但提交前会把所有调试输出注释掉尤其是printf在当前两组数据之间打的那些分隔行一旦忘了删平台全部判成格式错误。另外如果用cin / cout记得在main里加一行ios::sync_with_stdio(false)否则大数据量时可能被评测卡掉时间。3.2 一个完整例子二叉树层序遍历拿最常见的“二叉树层次遍历”实验题来说。题目会给你一种建树方式比如按完全二叉树的编号建树或者按前序序列输入#表示空节点然后要求你输出层序遍历结果。我用的是手写循环队列的方式因为部分学校实验要求不允许直接使用STL容器而且手写队列还能帮你加深“队头队尾指针”的理解。#include cstdio #define MAXN 1005 typedef struct Node { int val; struct Node *left, *right; } Node; Node* createNode(int v) { Node* p new Node(); p-val v; p-left p-right NULL; return p; } Node* buildTree() { // 按题目前序建树#表示空 char c; scanf( %c, c); if (c #) return NULL; Node* root createNode(c - 0); root-left buildTree(); root-right buildTree(); return root; } void levelOrder(Node* root) { if (root NULL) return; Node* queue[MAXN]; int head 0, tail 0; queue[tail] root; while (head tail) { Node* cur queue[head]; printf(%d , cur-val); if (cur-left) queue[tail] cur-left; if (cur-right) queue[tail] cur-right; } }这段代码里最需要注意的有两点。第一点队列中存的是节点指针不是节点值否则出队后根本没法继续访问它的孩子第二点入队前必须先判断孩子是不是空不能把空节点也塞进队列否则输出结果会多出奇怪的内容。头尾指针都从0开始出队时head入队时tail只要数组开得足够大这个队列在实验数据范围内不会溢出。从这个例子也可以看出所谓的“层序遍历”本质上就是BFS而BFS的核心就是队列。能把这一题想明白后面的图的广度优先搜索也等于学了一大半。3.3 提交与查错CE、WA、TLE、MLE分别怎么处理在计蒜客上提交常见的评测结果有几种我这里整理了一张速查表评测结果常见原因排查方向Compile Error语法错误、头文件缺失、编译器版本不兼容先看编译日志别盲目重新提交Wrong Answer算法逻辑错误、边界条件没处理、输出格式不对造边界样例逐步打印中间结果Time Limit Exceeded算法复杂度太高、死循环、输入读不进来检查循环是否有出口优化数据结构Memory Limit Exceeded数组开得过大、递归层数太深缩减存储空间改迭代写法Runtime Error数组越界、野指针、栈溢出检查下标、指针、递归深度遇到Wrong Answer时最忌讳的是盯着代码干看。我会先手算一个多组数据的小样例然后输出每一步的中间变量看看从哪一步开始和预期对不上。比如链表合并的题我会分别打印两个链表的当前指针和被合并节点的值马上就能定位是哪个分支写错了。4. 常见问题与避坑指南4.1 我在实验里踩过的几个坑第一个坑是数组开小。有一道图的实验题我图省事只开了node[105]结果测试数据里图的节点数上限是100但邻接边数能够到上千导致每次提交都是段错误。后来我养成了习惯像图这种“边数”和“点数”不是同一个量级的题目数组统一按两倍、甚至四倍去开宁可多一点不要少。第二个坑是多组数据之间的状态没清空。比如DFS里常用的visited数组上一轮搜索已经把标记改成1了下一组测试用例开头如果不把它重置为0整个连通分量计算结果就是错的。这个毛病特别隐蔽本地一组样例跑不出来因为本地数据太少根本不会触发多轮连续输入。第三个坑是字符串读入。计蒜客实验里有些题会涉及到字符型数据比如前序遍历序列里的#如果直接用scanf(%s, ...)读很容易把换行也带进去。稳妥做法是用scanf( %c, c)前面的空格用来吃掉空白字符这个细节虽然小但能省下很多无谓的WA。4.2 计蒜客平台的使用经验平台使用上也有几个值得注意的点。首先提交前一定要看清题目要求的语言有的题明确限制只能用C语言那就不要选C提交否则即使代码本身没问题也可能因为语言设置不对而编译失败。其次计蒜客的环境对“标准”的要求比较细致有些在本机正常运行的C17新特性和第三方库在平台上是编译不过的所以代码里尽量只使用最基础的C/C功能不要炫技。还有一个现象是同一道题可以反复提交平台会把多次记录都保留下来。这对我们来说既是好事也是坏事好在不用害怕一提交就完蛋可以不断调试坏在有些人会盲目“试交”无心思考。我的经验是每道题最多保留一次主动提交前的本地自测过程确保自己认为正确了再交。提交后如果报错先回到代码逻辑而不是立刻改两个字符再交一次。4.3 给后来人的方法建议说到方法论我最想强调的一点是数据结构实验不是比谁“想得快”而是比谁“写不犯错”。拿到题目以后先画图、再想清楚数据结构、最后才是写代码。这个过程听起来很慢但恰恰是最省时间的。每道题结束后不要马上做下一题。花十分钟把刚才的代码重新整理一遍加上注释写明每一步做了什么这件事对你的实验报告撰写帮助极大。到了写报告的时候你会发现很多过程可以直接复用甚至能总结出一个“链表操作常见模板”和“树遍历常见模板”后面复习也会顺手很多。如果遇到实在不会的题我建议先放下去翻严蔚敏的《数据结构C语言版》对应章节把课本例题的手动模拟过程推一遍再回来写代码。很多人觉得课本写得偏理论但实验题其实就是把课本例题换了一种输入输出格式本质并没有变。最后再分享一个小技巧做完这套实验以后可以把每个代码文件按“章节_题目名.cpp”的方式命名比如03_Tree_LevelOrder.cpp。这样期末复习时你可以快速找到对应模块的代码对照着回顾自己当时的思路和注释效率比重新翻报告高太多。数据结构这门课代码量就是底气动笔写永远比只看书重要。本文还有配套的精品资源点击获取