简介北邮《数据结构与算法》课程的实验与作业完整合集内含两版资料面向北邮在校生及自学数据结构的学习者可用于对照实验要求完成编码、撰写实验报告也可作为期末复习的参考素材。压缩包共43个文件以C源代码.cpp、实验报告.docx/.doc为主并包含Visual Studio工程文件.sln/.vcproj及少量可执行程序整体大小仅1.05MB。已有521人学习下载适合需要了解北邮实验风格或验证自身实现的人群。资料覆盖单链表通讯录、迷宫求解、Huffman编码、排序算法比较等典型实验每项均配有源码和实验报告作业部分还整理了三元组、单链表、二叉树等经典题目的实现。通过学习源码、对照报告能深入理解数组、链表、栈、队列、树、图及哈希表等核心结构的具体应用同时掌握时间复杂度和递归等算法分析思路为课程设计和后续编程打下扎实基础。1. 数据结构与算法实验为什么是考研和保研路上的硬骨头先把“最全”和“两版”想清楚“北邮数据结构与算法实验及作业最全内含两版”这类资源包几乎是每个计算机专业学生都搜过的关键词课程实验多、作业杂、考试还连着算法题手里的资料却永远是残缺的。所谓“最有价值”往往不在代码本身而在它替你趟过了哪些坑、你能否从中抄出正解并讲明白复杂度。“两版”通常意味着两个可对照的实现方向经典 C 风格与面向对象风格这正好用来理解同一种数据结构在不同思路下的差异。这篇笔记就按“先判断版本、再选方向、后落地调试、最后验收答辩”的顺序把整个实验与作业周期里最值得复用的经验拆给你。2. 先搞懂两版资源的差异再动手版本选型、环境约定与实验拆分2.1 两版相差的不只是代码风格数组实现 vs 指针/对象实现常见的“数据结构与算法实验及作业”打包里所谓“两版”最典型的是同一批实验分别用两套思路实现一套偏严蔚敏教材风格用 C 语言结构体指针操作注释少、代码密适合考研笔试和调试底层另一套偏 C/Java 的面向对象实现用类封装线性表、树、图配合泛型和 STL代码更易读、更贴近招聘笔试和工程习惯。选择哪一版应该由你的目标倒推而不是由资源里的目录顺序决定。我一般会建议面临考研的学生把“算法与数据结构”题单刷透优先以 C 语言版为蓝本重写一遍原因是考试手写代码时不能用 STL而指针操作和内存分配的细节只能在手写过程中暴露正在准备实习面试、目标 Java 岗位的同学则首选面向对象版因为面试手撕算法时你更熟练的是容器类 API实验里的类封装也能直接改写成 LeetCode 题解结构。当你把两个版本对照着看时才真正理解“数据结构是抽象逻辑实现是与语言的博弈”这件事。2.2 从课程大纲反推实验包内容别在下载后直接粘贴先做任务拆分绝大多数高校的“数据结构与算法”实验课无论是不是北邮的学期安排实验任务都逃不开如下几大类线性结构顺序表、链表、栈、队列、树与二叉树遍历、哈夫曼树、二叉排序树、图存储、DFS/BFS、最短路、最小生成树、查找二分、BST、散列、排序冒泡、快排、堆、归并以及串的模式匹配暴力枚举与 KMP。拿到资源包后第一件事不是解压看代码而是对照自己的实验课表画一张任务映射表。实验模块关键考点高频作业变体全包内常见两版差异线性表插入删除的边界条件多项式合并、约瑟夫环链式与顺序实现互换栈与队列栈顶指针语义表达式求值、双端队列数组模拟 vs 链式模拟二叉树递归遍历与层序哈夫曼编码、线索化指针版 vs 引用版图邻接矩阵/表选型最短路径、拓扑排序不同的存储结构封装查找与排序时间复杂度对比哈希表冲突处理、快排优化静态数组 vs 动态容器串匹配KMP next 数组暴力枚举对照实验手写 next vs 优化 next这张表的意思是要先把资源包里的文件按实验模块归类并判断两个版本分别对应哪些实验并把每个文件开头的大段注释题目描述、输入输出格式读透。很多学生粘贴代码后运行看结果相似就不管了结果实验验收时被问一句“你的存储结构为什么选这个”就哑火——这正是资源的注释部分能帮你挽回的分数。2.3 环境与输入输出约束评分系统不认“漂亮代码”只认约定多数学校的实验评测基于固定格式的判题脚本类似 Online Judge终端输入输出必须逐字节匹配。实验包若只有代码没有说明文档或者是两版混用你首先要补齐的就是 I/O 约定。我习惯在看任何源码前先建立一个最小工作环境确认编译器GCC/IDE 版本和标准C99 或 C14确认评测样例是否包含多组输入直到 EOF确认输出是否允许结尾多一个空格。下面是最常见的输入框架适用于排序、查找、图遍历这类命令行判题实验直接复制后按实验改#include stdio.h #include stdlib.h #include string.h #define MAXN 100005 int main() { int n; // 多数评测会连续给多组数据读到 EOF 必须能自己退出 while (scanf(%d, n) ! EOF) { if (n 0 || n MAXN) break; // 防非法输入 int *arr (int*)malloc(n * sizeof(int)); if (!arr) return 0; for (int i 0; i n; i) scanf(%d, arr[i]); // 此处替换为具体的实验逻辑例如快速排序 // 输出时用空格分隔最后一个数字后也允许跟空格 for (int i 0; i n; i) { if (i) putchar( ); printf(%d, arr[i]); } putchar(\n); free(arr); } return 0; }这段代码解决的是“在黑匣子里跑不通”的头号问题忘了处理多组输入。参数说明MAXN要根据题目给的数据上限调整别迷信大包里的 100000有的实验图规模到百万静态数组就变栈炸弹应该换成动态分配或开全局数组。while (scanf(...) ! EOF)是专业刷题环境的通用约定许多贪心算法、暴力枚举实验都是多组样例这一点两版资源包都应该保证。另一个经常翻车的是输出末尾换行与空格评测机通常对行末空格宽容但若题目明确“数字间一个空格”按上述if (i) putchar( );模式最稳既不会多打前导空格也不可能缺分隔符。3. 把高频实验做成“能答辩”的水平核心算法实现与参数调优3.1 线性表与双端队列为什么数组模拟栈是多数场景的最优解数据结构与算法的第一个高分实验通常是约瑟夫环或表达式求值资源包两版实现里最常出现的差异就是“静态数组模拟 vs 链表动态插入”。我的建议是除非实验明确要求验证指针/链表操作例如链表的就地逆置否则优先用数组模拟。原因很现实评测数据量大时链表频繁 malloc 会有时间损耗和碎片问题而数组模拟代码短、易调试、复杂度直观面试官也挑不出毛病。以“双端队列”实验为例作业要求通常是从输入流中反复在队首队尾插入删除。不熟悉的人会用std::dequeC一步到位但这类实验考察的恰恰是你能否手工实现循环队列和 deque 的边界控制。我推荐参考下面这版手工实现它在两版资源中属于“精简版”但结构足够清晰#include iostream using namespace std; class Deque { private: int *data; int head, tail, capacity, count; public: Deque(int cap) { capacity cap; data new int[capacity]; head 0; tail capacity - 1; // 让 tail 初始指向前端前一位 count 0; } bool push_front(int v) { if (count capacity) return false; head (head - 1 capacity) % capacity; data[head] v; count; return true; } bool push_back(int v) { if (count capacity) return false; tail (tail 1) % capacity; data[tail] v; count; return true; } int pop_front() { if (count 0) return -1; int v data[head]; head (head 1) % capacity; count--; return v; } int pop_back() { if (count 0) return -1; int v data[tail]; tail (tail - 1 capacity) % capacity; count--; return v; } ~Deque() { delete[] data; } }; int main() { Deque q(10); q.push_back(1); q.push_front(2); cout q.pop_front() q.pop_back() endl; // 2 1 return 0; }这段实现的关键在于两个指针的语义head指向队列第一个元素tail指向最后一个元素。入队时先移动指针再填值出队时先取值再移动指针取模操作用(index ± 1 capacity) % capacity保证循环。需要重点向验收老师解释的参数是capacity和countcapacity是分配的数组大小count是当前有效元素数二者共同决定了“队满/队空”的判断。这个解决方案最大的坑是tail的初始化方式——如果初始化为0而不是capacity - 1push_back第一次就会覆盖head位置的值这种边界问题是看两版资源差异时最值得反复推敲的地方。3.2 排序实验从冒泡到快排两版资源里你真正需要移植的只有快排排序是几乎所有数据结构与算法作业包的必选项实验要求一般是从冒泡、简单选择、直接插入、快排、堆排、归并里任选三种做对比记录比较次数和移动次数。大部分学生下载的“最全”包里都能找到全部六种的代码但真正需要你亲手改的其实只有快排和堆排因为冒泡和插入的教材实现几乎没有分歧而快排在“两版”里往往存在五个以上变体单边扫描、双边扫描、随机基准、三数取中、递归/非递归。我建议以三数取中快排为核心因为它兼顾了考试手写难度和效率。#include stdio.h void swap(int *a, int *b) { int t *a; *a *b; *b t; } // 三数取中选左端、中间、右端三个位置的中位数做基准 int median3(int arr[], int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) swap(arr[left], arr[mid]); if (arr[left] arr[right]) swap(arr[left], arr[right]); if (arr[mid] arr[right]) swap(arr[mid], arr[right]); swap(arr[mid], arr[right - 1]); // 把基准藏到 right-1 return arr[right - 1]; } void quickSort(int arr[], int left, int right) { if (right - left 1 3) { // 小区间用插入排序更稳 for (int i left 1; i right; i) { int tmp arr[i], j i - 1; while (j left arr[j] tmp) { arr[j 1] arr[j]; j--; } arr[j 1] tmp; } return; } int pivot median3(arr, left, right); int i left, j right - 1; while (i j) { while (arr[i] pivot) {} while (arr[--j] pivot) {} if (i j) swap(arr[i], arr[j]); } swap(arr[i], arr[right - 1]); // 把基准放回最终位置 quickSort(arr, left, i - 1); quickSort(arr, i 1, right); } int main() { int n 10; int a[] {5, 2, 9, 3, 7, 1, 6, 8, 4, 0}; quickSort(a, 0, n - 1); for (int i 0; i n; i) printf(%d , a[i]); return 0; }这个实现的参数取舍很微妙right - left 1 3时直接走插入排序是为了避免快排在小规模数据上递归开销反而大于简单排序median3把基准藏到right - 1是为了后续双指针扫描时不越界这也是资源包中“优化版”与“基础版”最大的区别。如果你的实验报告需要统计比较次数记得在上述比较前加计数器而不是在 swap 里计数——swap 次数不等于比较次数这个细节可以避免答辩时被追问得语塞。另外常见暴力枚举教材把快排写死成递归但当数据规模到百万量级时系统栈会翻车我在实验中会先测n 1000000再决定是否改成循环加自定义栈。这些内容是作业包里通常有的但你若不深读优化版快排很容易拿基础版去跑大数据从而被评测机判超时。3.3 串的模式匹配与 KMPnext 数组的两种求法决定实验能否拿高分“串模式匹配”实验在北邮这类课程里几乎是必做作业常见有两种提交版本朴素的暴力枚举和 KMP 算法。两版资源的差异通常就在 KMP 的 next 数组上——旧教材求的是 next最长相等前后缀长度新教材或考研资料里求的是 nextval避免失配后重复比较。实验报告如果能把两者都写出来并对比含金量会明显拉高。下面给出最稳妥的 KMP 骨架#include stdio.h #include string.h #define MAXLEN 1000005 char t[MAXLEN], p[MAXLEN]; int next[MAXLEN]; void getNext(char *s, int len) { int i 0, j -1; // j 表示已匹配的前缀长度 next[0] -1; while (i len) { if (j -1 || s[i] s[j]) { i; j; // next[i] 是失配后回退的位置理论上是 j但这里可以优化 if (i len s[i] ! s[j]) next[i] j; else next[i] next[j]; } else { j next[j]; } } } int kmpFind() { int n strlen(t), m strlen(p); if (m 0) return 0; getNext(p, m); int i 0, j 0; while (i n) { if (j -1 || t[i] p[j]) { i; j; } else { j next[j]; } if (j m) return i - m; // 返回匹配起点0-based } return -1; } int main() { scanf(%s%s, t, p); printf(%d\n, kmpFind()); return 0; }注意这段代码里我用了“带优化”的 next 数组即s[i] ! s[j]时才让next[i] j否则继续回溯用next[j]。这是 KMP 算法中最容易写错、也容易被实验判题区分度的部分如果用经典教材的 next 数组aaaab这类重复字符很多的模式串会多出螺旋回退的比较次数虽不影响正确性但实验报告中对比暴力枚举的效率提升就不明显了。参数层面的MAXLEN建议开到题目最大字符串长度加 5KMP 不涉及额外空间开销所以数组开大不心疼但字符串和 next 数组别共用 MAXLEN——如果模式串长度超过 next 数组生命周期内所需越界写入会污染栈上的其他变量这种问题用 gdb 排查时极其隐蔽。实验验收时被问“KMP 和暴力枚举在什么数据上差距最大”答案就是重复前缀极多的模式串比如在超长文本里匹配aaaaab这时暴力枚举的反复回溯会被放大成指数级比较而 KMP 依然线性。3.4 图的最短路与最小生成树邻接矩阵还是链式前向星图相关实验往往是整个数据结构实验的收官也是资源包内容差异最大的部分初版可能只有邻接矩阵实现而“最全”补充版多半会加入链式前向星或邻接表的 Dijkstra 堆优化。作业要求若是“实现 Dijkstra 并打印路径”用邻接矩阵写最短、最通俗但若实验附加了大数据量的时限要求就必须切换到链式前向星加优先队列。我不建议你直接把两版都抄一遍而是先用邻接矩阵把逻辑跑通再用堆优化版替换存储结构这样答辩时你能说清两种做法的复杂度差异。#include iostream #include vector #include queue #include climits using namespace std; const int N 10005; struct Edge { int to, w; }; vectorEdge graph[N]; int dist[N]; void dijkstra(int s) { // 小顶堆存 pair当前距离, 节点编号 priority_queuepairint, int, vectorpairint, int, greater pq; fill(dist, dist N, INT_MAX); dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期数据跳过 for (auto e : graph[u]) { int v e.to; if (dist[u] e.w dist[v]) { dist[v] dist[u] e.w; pq.push({dist[v], v}); } } } }这段代码有一个容易踩坑的参数细节if (d ! dist[u]) continue;必须写否则同一个节点会被重复入队多次有些资源包里的“优化版”图算法漏了这行导致大数据时正确性没毛病但耗时翻倍甚至被卡。另一个要提的是INT_MAX的加法风险——dist[u] e.w可能溢出变成负数进而错误更新最短路径。我在工程和作业里常用的解法是判断dist[u] INT_MAX - e.w再跳过或者直接用long long数组存距离。图实验的验收常常会问“邻接矩阵和邻接表在稀疏图/稠密图下的适用性”所以我的经验是先看数据规模点数 1000 以内邻接矩阵无脑够用点数上万就必须用链式前向星或邻接表这也是为什么“两版”资源的价值在于提供同一实验的不同解法对照而不是给你一份万能模板。4. 数据结构与算法实验最容易踩坑的 5 个地方现象、原因与补救4.1 评测机提示“运行时错误”本地却执行成功现象代码在 IDE 里跑官样数据完全正常提交到 OJ 就 Segmentation Fault。原因多半是数组越界或者递归过深。资源包里的模板有时默认开MAXN 1005但实验数据上限是100000你只改循环没改数组导致越界。解决方法是把所有数组定义改成题目上限再加 10或者干脆用vector/malloc动态扩容。另一个隐藏原因是递归层数快排和 DFS 在链式图上递归深度能到几十万层必须改成显式栈或非递归版本。我的习惯是任何一个数组下标都要检查来源数据范围并把MAXN写在明显位置。4.2 样例通过但总有几个点 Wrong Answer现象小数据样例全对一上大数据就错一两个。原因通常有两个多组输入没有处理干净上一次循环的脏数据留在全局数组里或者int溢出比如哈夫曼编码、最短路径中间累加和超过2^31。解决全局数组每次循环前memset重置距离和权重计算统一用long long输出前才转回要求格式。这里也有资源包“两版”的差异问题——如果你用的是面向对象版类成员变量默认构造不重置批量测试时上一次的对象状态会残留必须显式写 init 函数。4.3 快排和二分查找死循环不退出现象程序跑完不出结果CPU 占用 100%。原因快排双指针扫描时arr[i] pivot写成了导致相等的元素反复交换指针不推进。或者二分的mid (left right) / 2在left、right接近INT_MAX时溢出为负数。解决快排边界条件固定为左闭右闭区间while (i j)二分写成mid left (right - left) / 2到死循环时打印区间长度判断是否收敛。我排查这类问题有一个固定流程先用最大规模随机数据生成器再用printf在每轮循环头输出指针位置肉眼扫十行就能定位。所谓“血泪经验”就是不要把死循环问题误判成算法思想错误十有八九是边界条件多了一个等号。4.4 图实验内存爆炸或时间超限现象邻接矩阵开到5000×5000时直接卡死。原因二维int数组记忆体按 4 字节算5000×5000约 100MB比赛平台一般不给这么多。解决改用邻接表或者链式前向星如果是稠密图可以用vectorvectorpairint,int静态分配。时间超限则多半是遍历没有剪枝例如暴力枚举所有路径求最短路。解决用 Dijkstra 堆优化或 SPFA非负权图用 Dijkstra有负权才用 SPFA。参数上的重要设置是把存图的数组设计成vector而非定长二维数组能省就省避免没必要的空间申请。这类问题在两版资源里尤其明显基础版邻接矩阵适合教学演示补充版链式前向星适合交作业和跑大数据答辩前至少把两个版本都跑通一次才能回答“两个版本的区别”这种必问题。4.5 实验报告被要求“分析复杂度”时只会背结论现象老师问“你这个查找实验平均复杂度是多少”答了 O(log n)但继续追问“为什么二分查找是 O(log n)能用主定理推一遍吗”就哑火。原因只会抄结论没有亲自画递归树。解决把每份代码的核心函数单独拎出来手写递归式T(n) T(n/2) O(1)然后用主定理或递推展开算。比如归并排序T(n) 2T(n/2) O(n)堆排序建堆是O(n)而不是O(nlogn)——这是验收时最容易被揪的盲点。建议在资源包里每个实验文档开头补一段自己的复杂度推导不要指望现成答案因为老师爱看的是推导过程。5. 课程结束前做这几件事用数据说话把实验报告变成面试筹码收尾阶段我建议你把每个实验的代码集中到一个工程目录额外写一个stress_test.cpp来做压力测试生成随机数据、暴力解法和高效算法对拍。这个习惯能让你在验收前发现九成以上的隐蔽错误。对拍脚本不复杂但价值极高# stress.sh —— 对拍脚本假设 gen 生成输入brute 是暴力解sol 是提交版 for i in $(seq 1 10000); do ./gen input.txt ./brute input.txt out_brute.txt ./sol input.txt out_sol.txt if ! diff -q out_brute.txt out_sol.txt /dev/null; then echo Wrong Answer on test $i break fi done这段循环的意义在于把“示例过了”变成“随机数据全过”能覆盖到评测机不会给的边界样例。参数说明gen要能控制数据规模多测几组 n 在 1、2、100、上限这些临界值的brute不用考虑效率只要逻辑绝对正确。这套方法比任何资源包都管用因为它逼你自己把“作业”变成“工程”。再把每个实验的复杂度写成一页纸的对比表格连同两版实现的差异点放进个人技术博客或 GitHub 仓库——面试聊起项目时你能从“抄过作业”变成“独立做过、踩过坑、优化过”。我的习惯是每次实验结束都在 README 里留一段“已知缺陷”记录当时翻车的现象和根因这比漂亮的代码更能打动面试官。希望这些围绕“北邮数据结构与算法实验及作业最全内含两版”的实战复盘能帮你少走一段弯路祝你在期末验收和招聘笔试里都能从容作答。本文还有配套的精品资源点击获取