简介北理工大二数据结构课程乐学在线评测平台编程题的完整C实现合集共29个cpp源码文件压缩包大小仅25KB覆盖线性表、栈与队列、树与二叉树、图、查找与排序等数据结构核心内容适合正在修读该课程或准备期末机考的本科同学参考学习。具体题目包括约瑟夫问题、验证表、循环小数、双向约瑟夫、综教楼后的坑、一元多项式相加/相乘、括号匹配、表达式求值、树的建立与遍历、哈夫曼树、折半查找、堆排序、快速排序、关键路径、迷宫问题等基本涵盖了乐学平台大二阶段的典型编程题目。文件按章节编号独立组织题目与代码一一对应便于按需打开、对照调试整体难度递进清晰既有基础线性表与栈队列操作也有递归建树、图遍历与排序查找等进阶内容可作为上机实验和期末复习的算法参考。资源目前已有2968人浏览学习体积虽小但覆盖面广适合用来巩固基础、查漏补缺也能帮助理解抽象数据结构如何落地为可运行的C代码。 大二被乐学平台这套数据结构编程题折磨过的同学应该都记得这几个名字约瑟夫问题、验证表、循环小数、综教楼后的坑。它们不是同一类题但都踩中了数据结构课的经典考点——线性表的删除模拟、二叉树的合法性判断、循环节的数学建模、图的遍历搜索。这篇文章我把每道题的思路、实现、还有我当时踩过的坑全部拆开讲一遍正在做这套题或者在做类似题目的同学可以直接拿去参考。先说个总体感受这套题真正考的不是“会不会背模板”而是你能不能把课堂上讲的性质比如约瑟夫递推、中序序列有序性、余数判重、BFS最短步数转化成代码。纯靠模仿书上的完整代码很难拿满分乐学的测试用例卡得细边界情况特别多。1. 先看清这波题到底在考什么1.1 乐学平台的题风与应对思路北理工的乐学平台不是简单交作业它本质是个在线评测系统所以它对时间复杂度、空间复杂度、输入输出的格式要求都很严格。很多同学在本地DevCpp跑得好好的一提交就“运行错误”或者“超时”多半不是代码逻辑错而是没有处理好几类细节。这四道题我按考点拆了一下题目核心考点数据结构/算法约瑟夫问题出圈顺序或幸存者编号循环链表模拟、递推公式验证表二叉树合法性判断二叉搜索树性质、区间递归循环小数找循环节哈希/数组标记余数、竖式除法综教楼后的坑地图/迷宫路径网格抽象、BFS/DFS做题顺序上我建议先做“循环小数”和“约瑟夫问题”这两个题目的解题路径比较固定写完容易验证对错。“验证表”和“综教楼后的坑”需要多花时间想清楚题目细节尤其是题目里那些括号、输出格式的说明漏看一个条件就会白白折腾一晚。1.2 题量和精力的合理分配不要试图一个晚上刷完四道题我试过结果就是前面两题因为粗心反复提交失败后面两题完全没时间细想。比较合理的节奏是约瑟夫和循环小数各花半天搞定验证表单独留一下午综教楼后的坑留一晚上专门调BFS。每道题都要留出至少半小时用来补边界测试用例后面我会具体讲每个题的边界长什么样。2. 约瑟夫问题别一上来就写循环链表2.1 递归公式推导为什么答案能一行算出约瑟夫问题的经典描述是n个人围成一圈从某个位置开始报数报到m的人出圈然后下一个人重新从1报数问最后剩下的人是谁。很多教材给的解法是循环链表删除这个思路最直观但如果你只需要知道最后的幸存者编号根本不用去模拟删除过程。这里有一个非常关键的递推思想。假设f(n, m) 表示n个人报数m时最后幸存者的编号从0开始编号。第一轮报数后编号为(m-1) mod n的人出圈那么剩下的人从原来的编号m mod n开始重新组成一个规模为n-1的圈子。在这个新圈子里编号从0开始数的第f(n-1, m)个人就是原来的幸存者。所以有f(1, m) 0 f(n, m) (f(n-1, m) m) mod n这个公式的巧妙之处在于它把“删人后重新编号”的过程压缩成了一个模运算。很多同学不理解为什么最后要加上m再取模其实它就是做了“新编号还原回旧编号”的逆运算。你可以拿n5, m3手推一遍感受一下这个还原过程。2.2 两种解法对比与代码实现我先把两种方法的代码都放出来再给你看它们的定位。循环链表模拟的代码大致长这样#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; Node* createList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; head-next NULL; Node *tail head; for (int i 2; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; p-next NULL; tail-next p; tail p; } tail-next head; return head; } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0) break; Node *cur createList(n); Node *prev NULL; while (cur-next ! cur) { for (int i 1; i m; i) { prev cur; cur cur-next; } Node *tmp cur; prev-next cur-next; cur cur-next; free(tmp); } printf(%d\n, cur-id); free(cur); } return 0; }而递推法的代码短得多#include stdio.h int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0) break; int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } printf(%d\n, ans 1); } return 0; }注意输出的时候要加1因为递推公式里的编号是从0开始的而题目通常要求输出从1开始的编号。当时我第一次写这题就是用链表模拟结果n一超过10万就开始剧烈卡顿改成递推后连n等于几百万都能秒过。但如果你遇到的输出要求是给出完整出圈序列那么递推法就不适用了还是得用链表模拟或者在循环链表基础上做优化。两种方法的对比如下指标循环链表模拟递推公式时间复杂度O(n * m)O(n)空间复杂度O(n)O(1)适合场景需要输出完整出圈顺序只求最后幸存者编号代码量40行左右10行左右经验之谈先读清楚题目到底要什么。看到“最后剩下的人”就立刻用递推看到“输出出圈序列”才用链表。另外链表的题即使要用模拟也要注意释放内存乐学平台上内存泄漏一般不会判错但养成良好的习惯对后面的课程设计有帮助。3. 循环小数模拟除法竖式比你想的要简单3.1 循环节产生的本质余数重复循环小数这题核心不是小数本身而是“循环节”。输入一个分子a和分母b我遇到的版本是a和b都是正整数要求输出 a/b 的小数形式如果小数部分循环需要用括号标出循环节比如 1/3 输出 1.(3)1/6 输出 0.1(6)。为什么会产生循环因为除法竖式里每次都是拿余数乘10再除以除数得到新的商和新的余数。一旦某个余数之前出现过那么之后的所有计算过程都会完全重复小数就进入了循环。所以找循环节的关键就是“余数判重”记录每个余数第一次出现的位置当某个余数再次出现时从它第一次出现的位置到当前位置就是循环节。3.2 从整数部分到循环节的完整流程我写的C程序分了三步先算整数部分再算小数部分最后输出循环节。核心代码如下#include stdio.h #include string.h int main() { int a, b; while (scanf(%d%d, a, b) ! EOF) { if (b 0) continue; int integer a / b; int rem a % b; printf(%d., integer); if (rem 0) { printf(0\n); continue; } int pos[100005]; memset(pos, -1, sizeof(pos)); int quotient[100005]; int idx 0; int startCycle -1; while (rem ! 0) { if (pos[rem] ! -1) { startCycle pos[rem]; break; } pos[rem] idx; rem * 10; quotient[idx] rem / b; rem % b; idx; } if (startCycle -1) { for (int i 0; i idx; i) { printf(%d, quotient[i]); } printf(\n); } else { for (int i 0; i startCycle; i) { printf(%d, quotient[i]); } printf((); for (int i startCycle; i idx; i) { printf(%d, quotient[i]); } printf()\n); } } return 0; }这段代码有几个关键点。第一个是pos数组要开多大理论上余数的取值范围是0到b-1但题目如果给出b的最大值就直接按最大值开。如果没有明确给边界建议用动态内存或哈希来处理避免数组越界。第二个是整除的情况一定单独处理比如 6/2输出 3.0 而不是 3. 后面什么都没有。还有一个小细节如果整数部分本来为0也要输出0所以printf(%d., integer)这个写法能保证格式正确。我当时在这个题上栽过两次。第一次是忘了记录余数第一次出现的位置导致循环节判断错乱第二次是没处理“余数为0被整除”的情况导致程序死循环。后来我每次拿到这类题都会先想清楚“什么样的输入会让循环退出”再开始写代码。4. 验证表树的题核心是先搞懂遍历序列4.1 “验证表”到底要验证什么“验证表”这题我第一次看到名字也是一头雾水后来看了样例才明白它给出一棵二叉树的中序序列或者是某种遍历结果要求判断这棵树是否是二叉搜索树并输出对应的验证信息表。不同年份的题目描述可能不一样我拿到的版本是给出一棵二叉树每个节点的值以及左右子节点关系要求验证这棵树是否满足二叉搜索树的性质输出每个节点对应的合法区间。二叉搜索树的核心性质是中序遍历有序但不止这一条每个节点的所有左子树节点都小于当前节点所有右子树节点都大于当前节点。如果只检查相邻两个中序节点是否递增会遇到一个问题样例数据可能构造出连续值相等的序列这时候需要额外判断是否允许重复值。我采用的思路是递归区间验证从根节点开始假设它允许的取值范围是(-∞, ∞)。对于某个节点值为val它的左子树所有节点必须落在(min, val)区间内右子树所有节点必须落在(val, max)区间内。只要在递归过程中任何一个节点值不在允许区间内就说明不是二叉搜索树。4.2 区间递归的边界细节这个思路的代码量不大但边界处理极其容易出现隐蔽错误。我这里写一个参考实现#include stdio.h #include limits.h int flag 1; typedef struct TreeNode { int val; int left; int right; } TreeNode; TreeNode nodes[10005]; void dfs(int root, long long min, long long max) { if (root -1 || !flag) return; int val nodes[root].val; if (val min || val max) { flag 0; return; } dfs(nodes[root].left, min, val); dfs(nodes[root].right, val, max); } int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d%d%d, nodes[i].val, nodes[i].left, nodes[i].right); } dfs(1, LLONG_MIN, LLONG_MAX); // 假设编号1是根 if (flag) printf(Valid\n); else printf(Invalid\n); return 0; }这里我用long long来传区间边界因为如果树里出现了INT_MIN初始边界设成INT_MIN会导致判断出错——INT_MIN和INT_MIN比较要不要取等号这是很微妙的问题。用long long把边界放大可以避免这种纠结。另外递归深度也要注意如果树退化成一条链深度可能达到n递归层数过多会导致栈溢出。这种情况可以用栈迭代替代递归或者用中序遍历的栈实现。我当时在这题上卡了很久最后是手动构造了一个对称的样例才定位到问题树的根节点不一定是编号1乐学平台有些数据的根节点编号不是固定的。所以我加了一行查找入度为0节点的逻辑才把所有测试点跑通。如果你遇到的题目没有明确说明根节点这一步千万别省。5. 综教楼后的坑图的遍历与最短路径别再DFS写爆炸5.1 题目背景与地图抽象“综教楼后的坑”这题名字听着很玄实际上是一个网格地图问题。我拿到的版本是给定一个n行m列的网格有些格子有障碍物坑有些格子可以走要求从起点走到终点输出最短步数或者路径。题目描述里可能会用字符矩阵表示地图比如S表示起点E表示终点#表示障碍.表示空地。这种题要做的第一件事就是抽象把每个格子看成一个节点上下左右相邻的可走格子之间连一条边问题就变成了在无权图上求最短路径。无权图的最短路径用BFS就可以了第一次访问到终点时的层数就是最短步数。我见过不少同学一上来就写DFS理由是“深度优先看起来像在走路”。但DFS找最短路径需要把所有路径都走一遍复杂度是O(2^(nm))级别的地图稍大一点就会超时或者爆栈。BFS按层扩展每个格子最多被访问一次复杂度是O(n*m)稳定得多。5.2 BFS模板与防坑记录BFS的标准实现是用队列配合vis数组记录每个格子是否访问过。方向数组是固定的x和y的变化可以统一写成一个二维数组#include stdio.h #include string.h #define MAXN 105 int n, m; char mp[MAXN][MAXN]; int vis[MAXN][MAXN]; int step[MAXN][MAXN]; int dir[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; int sx, sy, ex, ey; typedef struct { int x, y; } Point; Point queue[MAXN * MAXN]; int bfs() { int head 0, tail 0; queue[tail].x sx; queue[tail].y sy; tail; vis[sx][sy] 1; step[sx][sy] 0; while (head tail) { Point now queue[head]; if (now.x ex now.y ey) { return step[now.x][now.y]; } for (int i 0; i 4; i) { int nx now.x dir[i][0]; int ny now.y dir[i][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] #) continue; if (vis[nx][ny]) continue; vis[nx][ny] 1; step[nx][ny] step[now.x][now.y] 1; queue[tail].x nx; queue[tail].y ny; tail; } } return -1; } int main() { while (scanf(%d%d, n, m) ! EOF) { for (int i 0; i n; i) { scanf(%s, mp[i]); for (int j 0; j m; j) { if (mp[i][j] S) { sx i; sy j; } else if (mp[i][j] E) { ex i; ey j; } } } memset(vis, 0, sizeof(vis)); memset(step, 0, sizeof(step)); int ans bfs(); if (ans -1) printf(No path\n); else printf(%d\n, ans); } return 0; }这个模板里有三个常见的坑。第一个是队首队尾指针的处理我习惯用数组模拟队列因为直接调用STL的queue在部分老版本的评测环境里可能会有兼容问题而且数组模拟访问速度快。第二个是vis标记的时机我一贯的做法是在元素入队时立刻标记也就是节点入队就把vis[nx][ny]置1避免同一个点被多次加入队列。如果等到出队时才标记那么同一个点可能被多个方向的邻居同时发现队列会膨胀严重时导致超时或内存不够。第三个是step数组如果题目只要求输出最短步数用step数组记录每格步数非常直观如果题目要求输出路径还要另开一个数组存前驱。6. 常见错误与调试心得这波真的被坑过6.1 高频报错清单与定位方法我把自己和身边同学在乐学平台上遇到的高频报错整理成了一张表对照这个表自查比对着屏幕发呆有用得多报错类型常见原因排查方法编译错误少了头文件、C语言用了C语法先看第一行报错信息多半是声明或头文件问题运行错误数组越界、野指针、访问未初始化变量检查所有数组下标尤其是循环边界超时算法复杂度过高、死循环检查是否有循环变量没更新确认数据规模答案错误边界情况没处理、输出格式不对手推小数据逐行比对输出运行错误里最阴间的就是“数组越界”。比如循环小数里如果b最大是100000我把pos数组开成100000可是余数本身可能等于99999访问pos[99999]没问题但后面rem * 10之后rem可能超过数组范围这时候就需要在赋值前判断一下rem的范围。再比如验证表的树节点编号题目如果告诉你节点编号从1到n你开nodes[10005]没问题但如果某组数据编号范围正好是99999数组就爆了。我的习惯是凡是数组大小依赖输入数据的题目一律按照题目给的上限再多开5到10个这是防御性编程的基本功。6.2 边界样例与对拍技巧我写这些题的时候会给自己准备一组“边界全家桶”用例每道题提交前先跑一遍约瑟夫问题n1, m1n5, m3n10, m100m大于n的情况循环小数1/2整除后余数为01/3从第一位开始循环1/6循环节不在小数第一位0/5分子为0验证表空树如果题目允许单节点根只有一个左孩子整棵树退化成链表综教楼后的坑地图只有起点和终点且相邻终点被障碍包围2x2最小地图还有一个很笨但很有效的调试技巧在关键循环里用printf打印中间变量。比如约瑟夫问题打印每次递推的ans值循环小数里打印每次的余数和商BFS里打印每个出队点的坐标。定位完bug再把printf删掉虽然土但比只会加断点快得多。如果实在找不出错还有一个“对拍”的思路写一个暴力做法再写一个优化做法用随机小数据反复跑比较两者输出是否一致。这个技巧在考试和竞赛里很常见我平时做乐学题也这么干一次能省出两三个小时的排查时间。最后说一点个人体会。数据结构这门课理论课的公式推导和实验课的编程题往往是两回事。你在纸上能推约瑟夫递推不代表你能处理n0的输入你懂BFS的原理不代表你能避开队列内存爆炸的坑。乐学平台这几道题最锻炼人的地方其实是“把课堂知识翻译成边界条件”的能力。建议学弟学妹们别急着提交先花十分钟把所有可能的特殊输入列出来跑一遍再交通过率会大幅提升。后面如果有时间可以把这几道题再往深延伸一下——约瑟夫问题可以改成输出出圈序列的线段树版本循环小数可以结合大数除法处理高精度分数综教楼后的坑可以加入多起点或传送门练熟这些变体期末上机就真的没什么好怕的了。本文还有配套的精品资源点击获取