简介：北理工2020年《数据结构》课程资料包，面向正在学习C++与数据结构的学生，覆盖从基础概念到算法实现的全流程。压缩包共65个文件，包含29个cpp源代码、9个ppt课件、16个doc和5个docx文档，另有5个pdf试卷及1个pptx讲义，整体55.42MB，适合离线整理学习。课件部分围绕数组、链表、栈、队列、树、图、哈希及排序等核心结构展开，并配有乐学平台编程题代码，如约瑟夫问题、表达式求值、二叉树遍历、图的关键路径等，能直观对照理论动手调试。复习PPT与知识点归总提炼了复杂度分析、各类排序与查找算法等要点，便于考前快速回顾；历年试题和练习题则可用于自测，检验掌握程度。目前已有685人下载学习，对于想借助完整课程资料系统梳理数据结构并提升C++编码能力的学习者来说，是值得收藏的参考包。
1. 从课件到实验代码再到十年真题：这份C++数据结构资源怎么用最值
数据结构这门课，最尴尬的事不是听不懂，而是听懂了课件、看懂了书，一到自己写代码就卡在链表指针和递归出口上。期末更难受，复习资料一大摞，不知道按什么顺序看，也不知道哪些是考点。这份“北理工-2020《数据结构》”资源，把课件、乐学平台实验代码、复习归总和十年期末题打包在一起，正好补上“理论到代码、代码到考试”中间那段空白。它适合两类人：正在学数据结构的C++新手，以及期末前需要快速把知识体系收拢一遍的备考者。接下来我按自己实际拆包使用的顺序，逐个模块讲清楚用法和坑。
2. 九份课件怎么读：按树、哈希、排序、图的顺序建立知识主线
2.1 先看课件的文件顺序，它本身就是一条完整的学习路径
解压后课件目录里有九份PPT，编号和内容分别是：01.intro、02.algorithm、03.lists stacks and queues、04.trees、05.hashing、06.priority queues(heaps)、07.sorting、08.the disjoint set ADT、09.graph algorithms。这个顺序不是随便排的，它基本就是北理工这门课的教学推进顺序：先讲抽象概念和算法分析基础，再讲线性结构，然后进入树、哈希、堆、排序、不相交集，最后落到图算法。
我一般会建议第一次学的人不要按上课顺序看，而是按“结构→算法”分成两轮。第一轮看01到04，把链表、栈、队列、树这些“容器”搞清楚，重点理解它们各自的插入、删除、查找代价。第二轮把05、06、07、09连起来看，因为哈希、堆、排序、图算法都是“在某种结构上做操作”的典型场景，放到一起对比效率才明显。08不相交集单独看，它在课件里篇幅不大，但在迷宫、连通分支这类题里非常实用。
2.2 04.trees和09.graph_algorithms是全套课件的核心章节
04.trees篇幅最大，二叉树遍历、二叉搜索树、AVL树的旋转是重点。课件里对前序、中序、后序的递归和非递归实现都有演示，这部分直接对应乐学代码里的4-2、4-3、5-2、5-3。看这一章时要特别注意两个点：一是中序序列和其他任一序列组合才能唯一确定一棵二叉树，这对应代码题4-3“遍历序列还原”；二是AVL树的四种旋转（LL、RR、LR、RL）的判断条件，课件里画了很清楚的示意图，理解旋转比死记代码重要得多。
09.graph_algorithms值得单独花一晚上。这一章的BFS、DFS、拓扑排序、最短路径、关键路径方法，直接对应第3章代码里的8-1、8-2、8-3。看这一章时我建议手推一遍关键路径的ve、vl两个数组的计算过程，因为只看PPT会觉得很简单，真到自己写代码时就容易把“vl取最小值还是最大值”搞混。这个问题在第3章代码部分会再展开。
2.3 课件和乐学代码怎么对照使用
课件目录和代码目录并不是一一对应的，这是这份资源里需要先适应的一个点。比如05.hashing在课件里单独成章，但乐学代码里并没有单独的哈希实验题；而06.priority_queues(heaps)对应对应7-2堆排序和6-2哈夫曼树权值。所以只看课件找代码是找不全的。
我的用法是：每看完一章课件，就去代码目录里找这一章对应的实验题，做完再回头翻PPT。比如看完04.trees，就做4-1、4-2、4-3、5-2、5-3；看完09.graph，就做8-1到8-4。这样课件是“骨架”，代码是“验证”，复习时再通过真题把两者串起来，比单纯刷课件或单纯抄代码都高效。
3. 30个乐学编程题拆成八组：栈、树、图的核心代码与编译参数
3.1 先把30个CPP按编号分组，才知道从哪里下手
“乐学编程代码”文件夹里有30个.cpp文件，编号规则是“章号-题号.题目名.cpp”。按章号分组非常清晰：
| 分组 | 题号范围 | 涉及知识点 | 推荐优先级 |
|---|---|---|---|
| 1 基础 | 1-1到1-3 | 约瑟夫问题、循环小数、表 | 必做 |
| 2 线性表 | 2-1到2-5 | 双向约瑟夫、多项式相加/相乘、栈应用 | 必做 |
| 3 栈与队列 | 3-1到3-4 | 括号匹配、出栈序列、表达式求值、中缀转后缀 | 必做 |
| 4 树 | 4-1到4-3 | 树的建立、二叉树建立、遍历还原 | 必做 |
| 5 二叉树与查找 | 5-1到5-3 | 二叉哥的二叉树、排序二叉树、平衡二叉树 | 选做/重点 |
| 6 树应用 | 6-1到6-3 | 前缀码、哈夫曼树、博弈树 | 选做 |
| 7 查找与排序 | 7-1到7-3 | 折半查找、堆排序、快速排序 | 必做 |
| 8 图 | 8-1到8-4 | 广度优先遍历、关键路径、迷宫、连通分支 | 必做 |
优先级是我自己定的标准：必做意味着这些题覆盖了课程80%的考点，且代码量适中，适合手敲；选做是思路有难度但期末考试出现频率略低。第一次拿到这个文件夹的人，先按这个表把必做12题做完，再回头补选做，比从1-1顺序撸到最后要稳妥。
3.2 栈专题四连：括号匹配、出栈序列、表达式求值、中缀转后缀
3-1括号匹配是栈最入门的应用，但很多人翻车在“栈空时出现右括号”这个边界条件。3-2出栈序列是这类题里最值得写的一题，它本质是模拟：按1到n的顺序入栈，随时可以选择出栈，判断给定的序列是否合法。核心逻辑如下：
bool is_valid_pop_sequence(const vector<int>& pop_seq, int n) { stack<int> s; int push_val = 1; // 当前待入栈的数字 for (int x : pop_seq) { // 遍历出栈序列 while (push_val <= n && (s.empty() || s.top() != x)) { s.push(push_val); push_val++; // 压入下一个数 } if (!s.empty() && s.top() == x) { s.pop(); // 栈顶匹配，弹出 } else { return false; // 无法匹配，序列非法 } } return true; }这段代码的关键参数是push_val和pop_seq。push_val控制“还能入栈哪些数”，pop_seq是给定待验证序列。循环里while条件写的“栈空或栈顶不等于x”意味着“一直入栈直到栈顶能匹配或数字用尽”，如果数字用尽了栈顶还不匹配就返回false。这个写法避免了常见的“先全部入栈再匹配”的错误思路，也是3-4中缀转后缀的基础。
3-3表达式求值和3-4中缀转后缀是同一个问题的两个方向。中缀转后缀只需要一个运算符栈，遇到数字直接输出，遇到运算符则把栈顶所有优先级不低于当前运算符的弹出去。表达式求值则要维护两个栈：操作数栈和运算符栈。一个容易忽略的坑是：减法和除法不满足交换律，弹出两个操作数时要注意先后顺序——先弹出的是右操作数，后弹出的是左操作数。这个坑我见很多同学踩过，代码跑出负数结果后对着屏幕发呆。
3.3 树专题：遍历序列还原和哈夫曼树的优先队列实现
4-3二叉树的遍历序列还原是个经典题：已知中序序列和前序（或后序）序列，重建二叉树。思路本身不难——前序第一个元素是根，在中序里找到根的位置，左边是左子树，右边是右子树，递归处理。但递归参数非常容易写错，核心在区间边界：
TreeNode* build(vector<char>& pre, int pre_l, int pre_r, vector<char>& in, int in_l, int in_r) { if (pre_l > pre_r || in_l > in_r) return nullptr; char root_val = pre[pre_l]; // 前序区间第一个是根 int root_pos = in_l; while (in[root_pos] != root_val) root_pos++; // 在中序里找根 int left_len = root_pos - in_l; // 左子树长度 TreeNode* root = new TreeNode(root_val); root->left = build(pre, pre_l + 1, pre_l + left_len, in, in_l, root_pos - 1); root->right = build(pre, pre_l + left_len + 1, pre_r, in, root_pos + 1, in_r); return root; }这里最容易错的是pre的区间。很多版本把左子树前序右边界写成pre_l + root_pos，这个写法只在某些巧合下对，正确做法是用left_len推：左子树的前序区间是[pre_l+1, pre_l+left_len]，右子树是[pre_l+left_len+1, pre_r]。参数含义要记清楚：pre_l、pre_r是前序序列的左右端点，in_l、in_r是中序序列的左右端点，root_pos是中序中根的位置。调试时打印每个递归层次的四个边界值，比盯着代码空想要快得多。
6-2哈夫曼树权值用到优先队列（堆），这是priority_queues那章课件的直接应用。常见做法是定义一个小顶堆，每次pop两个最小权值合并后push回去：
priority_queue<int, vector<int>, greater<int>> pq; for (int w : weights) pq.push(w); // 所有叶子权值入堆 int total = 0; while (pq.size() > 1) { // 只剩一个根时结束 int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); total += a + b; // 累加合并代价 pq.push(a + b); // 新结点入堆 }注意priority_queue默认是大顶堆，要使用greater 变成小顶堆。这段代码的total就是哈夫曼树的带权路径长度，也就是WPL。如果你在考试里遇到“求哈夫曼树权值”这类题，用这个循环手算或上机，比每次都重新画树要快。依次执行时观察pq.size()的变化——每轮减少一个，最终停在1，这是循环终止的正确条件。
3.4 图专题：BFS、连通分支、关键路径和迷宫
8-1图的广度优先遍历和8-4无向图的各连通分支可以合并看。BFS的框架是队列加visited数组：
void bfs(int start, vector<vector<int>>& adj, vector<int>& visited) { queue<int> q; q.push(start); visited[start] = 1; while (!q.empty()) { int u = q.front(); q.pop(); // 处理当前结点u，例如输出或统计 for (int v : adj[u]) { if (!visited[v]) { visited[v] = 1; q.push(v); } } } }用这个框架求连通分支只需要在外层再套一个循环：遍历所有结点，只要没被访问过就调用一次bfs，调用次数就是无向图的连通分支个数。visited数组要在bfs内及时置位，而不是等到出队时才置位，否则同一结点可能被重复入队，造成死循环。这是图遍历最常见的bug来源。
8-2计算工程完成的关键路径是整套资源里最复杂的代码题。它需要先做拓扑排序得到结点顺序，再按顺序计算事件最早发生时间ve，然后逆序计算最迟发生时间vl，找ve等于vl的路径。
// 结束点n-1，ve[n-1]即工程最短完成时间 // 求vl时从汇点逆推: vl[i] = min(vl[j] - w(i,j)) bool topo_order(vector<vector<Edge>>& graph, vector<int>& order) { int n = graph.size(); vector<int> indegree(n, 0); for (int u = 0; u < n; u++) for (Edge& e : graph[u]) indegree[e.v]++; queue<int> q; for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (Edge& e : graph[u]) if (--indegree[e.v] == 0) q.push(e.v); } return order.size() == n; // 等于n说明无环 }关键路径的边界条件有两个：一是图必须无环，所以要先跑拓扑排序并检查返回的order长度是否等于结点数；二是vl逆推时初始化——通常把汇点的vl设为ve，而不是0。很多同学把vl数组初始化为一个大数INF，结果推出来全是INF，找不到关键路径。
8-3迷宫问题可以用BFS求最短路径，也可以用手动模拟的DFS回溯。如果用递归DFS，要特别注意“四个方向的探索顺序”和“撤销标记”这两件事。撤销标记就是回溯时将当前位置重新置为可走，否则递归返回后其他路径无法通过这个格子，导致漏解。
3.5 编译环境与参数：建议直接用命令行工具链
这些CPP是典型的“乐学平台风格”代码：以stdio.h的scanf/printf为主，部分旧代码用的是C++98标准。在Windows上最常见的编译方式有两种：Visual Studio新建控制台应用，或者MinGW-g++命令行编译。我推荐后者，因为更接近OJ环境，也少受IDE配置干扰：
g++ -std=c++11 -Wall -o 3-2 3-2.出栈序列.cpp ./3-2参数说明：-std=c++11指定C++标准，部分代码用到了C++11特性（如auto、范围for），但主体是C++98风格，所以这个标准完全够用；-Wall打开警告，能提示未初始化变量等隐蔽问题；-o指定输出文件名。如果你的代码里有中文字符串且控制台出现乱码，多半是源文件编码和终端编码不一致，把源文件另存为UTF-8或GBK试一次即可。用VS的用户需要在项目属性里把“C++语言标准”设为C++14，否则个别代码的括号初始化列表可能报错。
4. 期末冲刺的组合拳：知识点归总、复习PPT与十年真题的配合顺序
4.1 复习材料有八件，按“先归总、再真题、后查漏”排序
“复习”文件夹里文件虽多，但用途层次分明。数据结构知识点归总.pdf是最精炼的提纲，适合考前两周每天过一遍；复习review.pdf和数据结构复习ppt.ppt是知识点的展开版，适合针对薄弱章节细读；数据结构练习题.pdf是平时作业级题量，用作检验；数据结构试卷.pdf、18级数据结构考试题型.docx、北京理工大学数据结构十年期末试题及答案.pdf则是真正的考试材料。
我的冲刺顺序是：第一天先看数据结构知识点归总.pdf，把目录里每一章的标题变成“我会不会”的问题，比如看到“散列表”就问自己“链地址法装填因子怎么算”，如果答不上来就标记为盲区。然后直接用十年期末题做限时训练，限定两小时内做完一张，做完对照答案。十年前的历史题偶尔会有答案缺失的情况，上一份文件里有答案标注为十年期末试题及答案，实际使用中我建议把它当成“题目来源”，而不是“标准答案库”。
4.2 排序和查找的复杂度表，是复习效率最高的知识点
数据结构知识点归总.pdf里对排序算法的归纳非常集中。复习时自己默写一张复杂度表，比反复翻PPT更有用：
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn)~O(n) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 折半查找 | O(1) | O(logn) | O(logn) | O(1) | 不适用 |
注意快速排序最坏情况发生在序列基本有序时，解决办法是随机选择基准或三数取中，这是7-3快速排序实验题的进阶考点。堆排序和7-2代码里建堆过程能对上，复习时手推一遍从无序数组建堆的过程，比单纯背复杂度表更有把握。稳定性的记忆方法可以这样：快选堆希（快速、选择、堆、希尔）都不稳定，其他基于相邻交换的基本稳定。
4.3 18级题型docx告诉你考试怎么出题，别到最后才发现
18级数据结构考试题型.docx是这份资源里最容易被忽略的文件。它直接给出了期末考试的题目分布结构，比如选择、填空、简答、算法设计各占多少分。很多人复习到最后才发现，原来考试有大量概念性简答题，代码题只占一小部分。
我的经验是：看完这个docx之后，再回去看知识点归总.pdf里那些用一句话能说清的概念，比如“栈和队列的异同”“散列表的冲突解决方法”。十年题库里的简答题就是真题的近似复现，很容易在这类题上拿分。而算法设计题通常是从课件例题或乐学实验题变形来的，所以哪些必做实验题的代码一定要自己写过，而不是只看懂。
4.4 练习题和试卷pdf怎么用：错题标记法
数据结构练习题.pdf和数据结构试卷.pdf这两份可以配合起来做“错题标记法”：第一遍做完后，把错题对应的知识点编号记在归总PDF的目录页上，全部做完后检查哪个编号出现次数最多，那就是你的薄弱点。比如错题集中在图算法，就回到09.graph_algorithms.pptx和8-x代码里重新过一遍。
整套复习材料只需要占用每天两个小时，坚持两周就能覆盖。不要试图把每份PDF从头看到尾，在数据结构这门课上，读十遍不如亲手解一遍题。
5. 避坑：5个让新手翻车的资源使用现场
5.1 双击PPT没反应或排版错乱
现象：直接双击课件中的.ppt文件，Office提示文件格式不兼容，或者打开后公式和图片整体偏移。
原因：课件命名带.ppt后缀，实际可能是旧版PowerPoint 97-2003格式，新版Office默认设置下兼容性展示会有问题；另外部分PPT内容用了较老的公式编辑器，新版本打不开内嵌公式。
解决：别双击，先打开PowerPoint或WPS，再用“打开”命令选文件。如果公式还是乱码，用LibreOffice导入再导出为.pptx。我在自己机器上测试过一次，LibreOffice对老公式的兼容性比Office还好，只是导出后个别版式需要微调。
5.2 在VS里编译报错：C4996和C++标准不匹配
现象：把3-3表达式求值.cpp丢进Visual Studio直接编译，报一堆“scanf is unsafe”或“use of undeclared identifier”错误。
原因：VS的默认SDL检查会拦截传统的scanf/printf族函数，且新版VS默认语言标准较高，旧代码里的某些写法需要适配。
解决：在源文件第一行加
#define _CRT_SECURE_NO_WARNINGS或者在项目属性→C/C++→预处理器定义里加_CRT_SECURE_NO_WARNINGS，再把“C++语言标准”改为C++14。用g++的读者不需要处理这步，但要注意代码里可能用到了非标准头文件，如果报找不到头文件就改用MinGW环境。
5.3 实验代码和课件知识点对不上
现象：6-3博弈树题，在课件06.priority_queues(heaps).ppt里完全找不到“博弈树”相关内容；8-2关键路径在08.the_disjoint_set_adt.ppt里也没有。
原因：乐学平台的实验题范围大于课堂课件覆盖范围，部分题目是对知识点的延伸应用，课件里只讲了基础原理。
解决：遇到这种情况就不要试图按课件顺序找解释。正确做法是先把代码读懂跑通，再按“这个题用了什么结构”去归总PDF里找对应章节。比如博弈树本质是树形结构的递归搜索，那就回04.trees看树的遍历方式。我在处理8-2时就吃了这个亏，后来先理解了拓扑排序再回来看关键路径，才豁然开朗。
5.4 十年试题没有答案解析
现象：北京理工大学数据结构十年期末试题及答案.pdf里题目完整，但对照答案时发现部分年份只有题目没有详细解答，或者答案过于简略。
原因：这是老试卷的常规情况，学校放出的试卷往往只有参考答案而无评分细则。
解决：我的做法是先用知识点归总.pdf和复习ppt来自我核对简答题；对于算法设计题，用乐学代码去对照答案的算法思路，如果代码和答案结论一致，基本可以放心。另一个办法是找同学一起做同一张卷然后互评，这比一个人干瞪眼有效得多。
5.5 review.pdf和复习PPT的内容顺序不一致
现象：数据结构复习ppt.ppt按章节推进，review.pdf却是按“知识点清单+例题”模式组织的，两者顺序对不上，交叉查阅耗时。
原因：两份材料来自不同整理者，组织方式不同，内容有重叠但不完全一致。
解决：不要试图同时看。以知识点归总.pdf为骨架，需要细读时选其中一份展开即可。我习惯用复习PPT配课件看原理，用review.pdf考前快速过一遍，两份分开用，效率最高。
6. 进阶用法：把这包代码变成你自己的数据结构刷题集
资源里的30个CPP文件，每道题都代表一类问题。进阶用法是把它们改造成“个人刷题集”：给每个代码文件头部加两行注释，一行写考点标签，一行写复杂度记法。比如在3-2出栈序列.cpp顶部加“考点：栈模拟 | 复杂度O(n) | 常见变形：判断两个序列是否互为合法出入栈序列”。这个习惯能让你复习时不用打开代码就知道每题的定位，还能按标签快速组成专题卷。
第二个技巧是用STL重写一遍核心题。比如7-3快速排序实验题里要求手写partition，那你就再写一版用std::sort实现的对照程序，用随机数组比较结果。
#include <iostream> #include <vector> #include <algorithm> #include <random> using namespace std; int main() { vector<int> a(100000); random_device rd; mt19937 gen(rd()); uniform_int_distribution<int> dist(0, 1000000); for (int& x : a) x = dist(gen); vector<int> manual = a, stl = a; quick_sort(manual, 0, manual.size() - 1); // 手写版本 sort(stl.begin(), stl.end()); // STL版本 cout << (manual == stl ? "OK" : "MISMATCH") << endl; }这段代码用随机数生成器产生十万个整数，同时跑手写快排和std::sort，用结果相等性验证正确性。random_device和mt19937是C++11标准库的随机数工具，uniform_int_distribution 把数据范围限制在0到1000000之间。这个对照方法能立刻暴露手写排序的边界错误，比如分区时越界、相等元素处理不当等。
第三个技巧是给每个难度较高的题写一个“测试用例清单”。比如8-3迷宫问题，至少准备三组数据：无解迷宫、单一通道迷宫、带环迷宫，每组数据都要明确预期路径长度。我用这个办法检查自己写的DFS，一次就抓出了“没有撤销访问标记”的bug。从那以后我每次拿到新代码，都会强制先写测试用例再跑主函数，无论是这份资源里的实验题还是工作后遇到的问题，都少走了很多弯路。这些代码题的价值不止于期末，C++的数据结构实现功底是靠一遍遍手写、改错、复盘堆出来的。希望这套拆解后的用法能帮到你，把这30道题变成你自己的题库，而不是硬盘里的一个压缩包。
本文还有配套的精品资源，点击获取
