简介这是一份面向北理工大二数据结构乐学编程训练整理的完整代码合集涵盖线性表、栈与队列、树与二叉树、图与查找排序等核心知识点与常见算法题型。全包共29个cpp源文件压缩后大小约25KB全部为C实现代码结构简洁可直接查阅或编译运行。题目覆盖约瑟夫问题、循环小数、表达式求值、括号匹配、哈夫曼树权值与关键路径等典型编程题每个文件对应一道乐学题目便于按题目编号顺序对照练习。目前已有2968人学习下载适合正在学习数据结构课程、准备乐学编程作业或复习考研基础算法的同学。资源目录结构清晰拿到手后既能快速查看某一知识点的经典写法也能依据源码排查自己的调试思路用于考前冲刺或实验报告参考都很有价值。 在北理工读到大二你必然绕不开两样东西一是乐学平台上每周准时出现的编程题二是数据结构课上那些“看着眼熟、写起来翻车”的经典问题。我第一次点开“约瑟夫问题、验证表、循环小数、综教楼后的坑”这个题组时内心是有点不服气的——这不都是网上一搜一大把的题吗真自己动手写才发现每道题都在疯狂拷打我对基础知识的理解。这篇就把我的做题思路、翻过的车、最后怎么改到通过的过程完整写下来给正在被乐学折磨、或者准备期末的学弟学妹做个参考。1. 约瑟夫问题一道题里藏了三种层次的解法1.1 为什么乐学第一题总是它乐学平台开放作业时第一个让人睡不着的综合题往往就是约瑟夫问题。题目背景是老套的“n个人围成一圈第一个人从1开始报数报到m的人出圈后面的人再从1开始报数问最后剩下的人的编号”。别笑这题从大一C语言课就见过但到了数据结构课它已经不是简单的模拟题了而是想让你回答一个问题针对同一件事数组、链表、数学推导你到底会选哪种为什么我第一次写的时候觉得这不就是“报数标记删除”吗直接开一个数组存所有人状态循环扫描到第m个未出圈的人就标记为出圈。代码十分钟写完一提交超时。平台判题的数据规模比想象中大很多O(n*m)的复杂度在n和m都到十万以上时跑得简直让人怀疑人生。1.2 循环链表练的就是指针细节课上老师会推荐用循环链表来模拟约瑟夫环。思路很直观把节点串成一个环从某个点开始走每到第m个节点就删除然后从下一个节点继续。循环链表实现的时候坑非常密集我第一次写直接段错误。核心删除操作的代码长这样Node* p head; // p始终指向被删节点的前驱 while (p-next ! p) { for (int i 1; i m - 1; i) { p p-next; } Node* q p-next; // q就是要出圈的人 p-next q-next; free(q); p p-next; // 从下一人继续报数 } printf(%d\n, p-data);这段代码有几个必须想清楚的点循环链表删节点必须知道前驱所以我让p在报数前就停在被删节点的前一个位置当链表只剩一个节点时p-next p循环结束这个节点就是答案每次删除后要把p移动到下一人的位置否则会漏数。我自己的经验是动手前先在纸上画一个三节点的环把每次删除后指针的走向画出来比直接敲代码稳得多。1.3 数学递推n和m都很大时的唯一活路如果需要高效解决约瑟夫问题数学递推法才是正道。假设f(i)表示长度为i的约瑟夫环中最后剩下那个人的编号编号从0开始。第一个出圈的人编号是(m-1)%i把这个人删掉后问题变成了从下一个位置开始、长度为i-1的环所以f(1) 0f(i) (f(i-1) m) % i实现起来简单到不像话int last 0; for (int i 2; i n; i) { last (last m) % i; } printf(%d\n, last 1);为什么输出时要1因为推导时编号从0开始题目要求从1开始。这个解法是O(n)的而且对m没有限制。我第一次看到这个递推时很不理解为什么一个模拟问题能被化简成这样后来想明白了删除一个人之后环的规模变小但“最后剩谁”这个问题本质是一样的这就是子问题重叠只是它不需要我们真的去模拟每一轮的报数过程。理解这个递推的过程比记住公式本身重要得多期末如果考到“大数约瑟夫”这几乎是唯一的优选方案。2. 验证表题目很枯燥但它偷偷在教你怎么做测试2.1 先弄明白到底要验证什么乐学平台上的“验证表”每个版本的描述细节可能不太一样但核心都差不多你需要用一个线性表维护一个数据集合然后依次执行插入、删除、查找、清空等操作判断每个操作是否合法合法就执行并输出当前表的状态非法就输出错误提示。我一开始没把这道题当回事觉得就是顺序表的基础操作。真写起来才发现这题的难点根本不是“实现功能”而是“怎么把规则理解对”。比如删除操作如果表是空的算非法还是什么都不做查找一个不存在的元素是报错还是返回一个约定值这些细节题目里往往会写但不仔细读很容易漏。2.2 顺序表还是链表动手前先想清楚验证表用什么结构实现直接决定了代码的复杂程度。如果操作里经常要按下标访问顺序表更自然如果插入和删除很频繁链表更合适。我当时选的顺序表因为输出当前状态特别方便直接遍历数组就行。顺序表实现时的核心就是“移动元素”// 在第pos个位置插入元素val if (len MAXSIZE) { printf(error\n); return; } if (pos 1 || pos len 1) { printf(error\n); return; } for (int i len; i pos; i--) { data[i] data[i - 1]; } data[pos - 1] val; len;插入的时候要从后往前移删除的时候要从前往后移这个方向千万别搞反不然元素会被覆盖。我第一次就是这里出问题插入前没有判断表满导致数组越界平台判的是运行错误不是答案错误找了很久才想到是越界。2.3 这题真正的考点是“测试用例设计”做验证表这道题我最大的收获不是复习了一遍线性表而是意识到了测试用例的重要性。乐学的判题会有一堆边界输入空表删除、连续删除、插入到头部和尾部、查找不存在的值。你会发现代码的核心逻辑可能只有几十行但为了应付这些边界情况要加一堆判断。我的建议是提交之前自己先构造几组测试输入空表操作、单个元素操作、大量元素操作。我习惯在每个输出结果后面手动画一遍“我期望的答案”再对比程序输出。这样能抓出很多逻辑漏洞。这题过了之后我做很多其他题都养成了先写边界用例的习惯收益比想象中大得多。3. 循环小数一道看起来很数学实际上考哈希表的题3.1 题目到底让你干什么循环小数这道题题目描述通常是给定分子a和分母b输出a/b的小数形式循环节用括号括起来。比如1/3输出0.(3)1/6输出0.1(6)2/5输出0.4。看到这题的时候很多人第一反应是“这不就是高精度小数除法吗”但实际上它考的是数据结构里的哈希表。你只需要做一件事模拟长除法用一个哈希表记录每个余数第一次出现的位置一旦某个余数重复出现就说明小数部分开始循环了。3.2 余数才是判断循环的唯一标准长除法的操作是这样的先计算整数部分然后拿余数乘以10再去除得到下一位小数再得到新的余数。关键规律是在除法过程中如果某个余数之前已经出现过那么接下来产生的商和余数序列必然会重复小数就从上一次该余数出现的位置开始循环。我用一个数组或哈希表记录余数在结果字符串中的下标。每次得到新余数先检查它是否出现过key n / d; // 整数部分 n n % d; // 余数 if (n 0) return decimal; // 能除尽没有循环 // 哈希表记录每个余数第一次出现的位置 // key: 余数, value: 结果字符串中的下标 while (n ! 0 !visited[n]) { visited[n] result.length(); n * 10; result.push_back((n / d) 0); n n % d; }如果循环退出时n为0说明是有限小数如果n不为0说明命中了某个已经出现过的余数那么从visited[n]这个位置开始加左括号在字符串末尾加右括号就得到最终结果。每次余数*10后可能出现整数部分进位乱掉的问题吗不会长除法的特殊性在于n每次都会先对d取余所以n永远小于d乘10之后也不会超过10d除法得到的一定是一位商。这也是为什么这个算法代码量很小但非常优雅。3.3 边界情况能埋一堆雷这题的边界情况比主体逻辑更磨人。第一分子为0时直接输出0第二结果为负时负号要放在所有括号外面不能在循环节内部出现第三如果整数部分和小数部分都有内容输出格式不能漏掉小数点。我翻车翻得最狠的是“负数取模”。C语言里负数取余的符号和数学上不一样如果分子分母可能为负要先把符号单独提取出来把两个数都转成无符号的绝对值再计算。否则你拿-1和3做长除法余数序列可能完全乱掉。这一题通过之后我对“模拟过程中数据的符号一致性”有了条件反射般的警觉。4. 综教楼后的坑BFS最短路径与一道题目名字背后的故事4.1 题目背景和题意理解“综教楼后的坑”这题名字一看就不是正经算法题倒像是出题老师在综教楼后面踩了坑气不过出了道题报复社会。题目大概意思是给你一张二维地图0表示可以走的地方1表示坑或者障碍物给定起点和终点问从起点走到终点的最少步数走不到就输出-1。这类题在大二数据结构里非常典型本质是图的最短路径问题但不用Dijkstra因为每步边权都相等用BFS就够了。4.2 BFS为什么是最短路径的最优选择BFS按层扩展先把起点入队然后取出队首把它四周能走且没访问过的格子入队。第一圈扩展的是距离1的格子第二圈是距离2的格子以此类推。因为每一层都对应一个“步数层级”所以第一次到达终点时走的步数一定是最少的。这也解释了为什么DFS不适合求最短路径DFS会一条路走到黑找到一条路径就返回但这条路未必最短。想用DFS求最短路径只能遍历所有可能路径后取最小值指数级复杂度地图稍微大一点就扛不住。4.3 方向数组、visited和队列三个最容易翻车的细节BFS代码框架大家都熟但细节处理不好照样AC不了。方向数组我习惯写成这样int dx[4] {0, 0, -1, 1}; int dy[4] {-1, 1, 0, 0};然后是visited数组。一定是在入队的时候标记访问而不是出队的时候标记。如果出队才标记同一个格子会被多个方向重复入队队列膨胀不说步数统计也会乱。这是BFS最常见的性能杀手。队列方面C语言手写循环队列时要留好空间最坏情况所有格子都可能入队用STL的queue会省心很多。我自己踩过的一个坑是每次跑新测试用例之前忘记清空队列导致上一轮的数据残留答案直接错乱。后来我干脆在每个用例开头重新初始化队列从根上杜绝这个问题。边界检查也不能忘新坐标越界、遇到障碍物、已经访问过这三个条件只要有一个不满足就直接跳过。把这些条件组织好BFS的正确性就有了九成保障。5. 从四道乐学题看期末数据结构复习重点5.1 把题目映射到考点做完这四道题再回头看数据结构课的章节会发现乐学真的把重点都藏在题里了。我把它们整理成一张表期末复习时可以对着自查题目核心数据结构隐藏考点约瑟夫问题循环链表指针操作、数学递推、模拟优化验证表线性表插入删除的边界处理、测试用例设计循环小数哈希表余数状态记录、长除法模拟综教楼后的坑图BFS最短路径、队列与visited数组表格里的每一行都对应着期末考试很爱出的题型。约瑟夫问题的变体通常会改成“每次删除第k个人后从下一个开始”验证表可能改成“判断栈的出入序列是否合法”循环小数可以改成“求分数的小数部分第n位”综教楼后的坑可以改成“地图上有多个入口求最近出口”。考点没变变的是壳。5.2 给备考同学的三点实操建议第一链表类题目不要在脑子里模拟指针变化必须画图。约瑟夫问题我之所以一开始段错误不断就是因为懒得画图觉得逻辑简单。后来每画一次图写的代码准确性就提升一大截。数据结构考试可以带草稿纸平时养成画图的习惯考场上就会自然很多。第二BFS和DFS的模板要熟到不用想就能写。方向数组、visited标记、队列操作这些不是“背下来”就行而是要做到肌肉记忆。考场上时间紧张如果你还要现场想队列怎么实现基本就做不完后面的大题了。第三乐学的错题记录一定要留好。很多题目第一次提交失败的原因就是期末复习最好的素材。我习惯把每次报错类型记下来编译错误、运行错误、答案错误、超时。期末翻一遍你会发现自己的“坑位”非常集中重点补那一两处就够。最后一句话是我个人很深的体会数据结构这课光看书记不住光刷题也记不牢最有效的方法是每做完一道题都问问自己“这题到底考的是什么结构、什么思想”把题和知识点之间的映射关系想清楚。乐学平台这些题看着零散其实就是想逼你建立这种映射。把这几道经典的吃透期末复习的底气会足很多。本文还有配套的精品资源点击获取