简介面向北邮数据结构与算法课程实验与作业合集含两版系统覆盖数组、链表、栈与队列、树、图、哈希表以及排序查找等核心知识模块适合正在学习该课程的本科生、备考复试的学生也适合需要夯实基础的在职开发者。压缩包共43个文件以C源码、实验报告docx/doc、工程与解决方案文件vcproj/sln及说明文档txt为主整体仅约1.05MB目录按实验与作业模块组织代码、报告、可执行文件对应放置便于对照学习。已有521人学习使用。内容涵盖迷宫求解、Huffman编码、顺序表多项式、单链表通讯录、排序算法比较等多个典型实验提供两版代码实现与配套实验报告既能看到不同写法和思路也能参考报告中的算法分析、复杂度讨论等规范表述从实验设计、编码实现到算法分析可完整还原北邮实验要求有效帮助提升编程实践能力、逻辑思维与报告撰写水平。1. 数据结构与算法实验为什么值得拿北邮这套当模板数据结构与算法是计算机专业的硬课但很多人的第一份实验代码是从网上东拼西凑来的跑通是一回事讲得清是另一回事。我拆完这份北邮的数据结构资料后确认了一件事它不只是代码包而是一整套可以照着对照的课设模板——链表通讯录、多项式合并、迷宫、Huffman编码、排序算法对比五个模块恰好覆盖了数据结构课最容易被拿来出实验题的核心知识点。无论你是还在赶实验报告的学生还是想快速复习一遍基础算法脉络的从业者这套资料的价值都在于有可运行的代码有成文的实验报告有不同期的版本可以对照。用这份资源你可以少走一半弯路。2. 链表实验通讯录和多项式其实是同一个套路北邮这门课的链表实验分成了两块一块是单链表通讯录另一块是多项式相加。很多同学误以为这是两个不相关的实验实际上它们都在练同一样东西结点怎么组织、指针怎么移动、插入删除时边界条件怎么处理。把这两份代码对照着看链表的功底基本就立住了。2.1 单链表通讯录为什么插入要传二级指针通讯录这个实验的核心是给每个联系人建一个结点结点里存姓名和电话再用 next 指针串成一条链。整个实验的考察点集中在头插法、尾插法和按名字排序插入这三件事上。其中最容易翻车的是头插法——如果你直接把原链表的头指针传进函数插入完发现调用方的 head 还是原来的值。#include cstring struct Node { char name[32]; char phone[16]; Node *next; }; // 头插法头指针会变必须传引用或二级指针 void insertAtHead(Node *head, const char *name, const char *phone) { Node *p new Node; strcpy(p-name, name); strcpy(p-phone, phone); p-next head; head p; }逻辑说明头插法把新结点挂在链表最前面所以新结点的 next 指向旧 head再把 head 更新为新结点。这里的关键是Node *head如果你写成Node *head函数内部确实把局部副本改了但外部的 head 纹丝不动。参数说明Node *head是二级引用的写法C 语言里没有引用通常用Node **head替代通讯录的插入操作如果要求按姓名排序则应该改成尾插加遍历比较不是在头部无脑插入。资料里的 a.cpp 同时演示了这两种插入方式实验报告里也专门讨论了“为什么插入要小心头指针”这一点这块内容建议直接抄进自己的报告。2.2 多项式实验链表的“系数-指数”结点怎么设计多项式相加的经典做法是每一项用一个结点存系数和指数整条链表按指数降序排列。两个多项式相加时从头开始遍历两条链指数相等的项合并系数指数不相等的项把指数大的先接到结果链上。这个逻辑用数组也能做但链表的好处是多项式项数动态变化时不需要预先分配固定大小。struct Term { double coef; // 系数 int exp; // 指数 Term *next; }; // 两个降序排列的多项式链表相加返回新链表头 Term* addPoly(Term *a, Term *b) { Term dummy; Term *tail dummy; while (a ! nullptr b ! nullptr) { if (a-exp b-exp) { double sum a-coef b-coef; if (sum ! 0.0) { // 系数和为 0 的结点直接丢弃 tail-next new Term{sum, a-exp, nullptr}; tail tail-next; } a a-next; b b-next; } else if (a-exp b-exp) { tail-next new Term{a-coef, a-exp, nullptr}; tail tail-next; a a-next; } else { tail-next new Term{b-coef, b-exp, nullptr}; tail tail-next; b b-next; } } // 处理剩余部分 while (a ! nullptr) { tail-next new Term{a-coef, a-exp, nullptr}; tail tail-next; a a-next; } while (b ! nullptr) { tail-next new Term{b-coef, b-exp, nullptr}; tail tail-next; b b-next; } return dummy.next; }逻辑说明dummy是一个栈上临时头结点作用是让尾指针永远有对象可指避免纠结“空链表时 head 要不要单独判断”。合并的核心规则就三句话指数相等就相加相加后系数为 0 就扔掉指数不相等就把指数大的先挂进去。参数说明这个算法的复杂度是 O(mn)因为每条链都只走了一遍。资料中的 LinkList.cpp 和实验1_多项式 目录下还有另一版实现用的是“静态数组游标”的方式那个写法不是链表是模拟链表遇到时要能分清。提示多项式实验一定要自己跑一遍“3x^2 5x^2 8x^2”和“4x - 4x 0”这两组数据前者验证正常合并后者验证系数归零删除。3. 迷宫实验栈、DFS 和路径回溯的三层关系实验2迷宫是这门课里“看起来最有趣、写起来最容易懵”的实验。地图是一个二维数组0 表示空地1 表示墙要求从起点走到终点并把路径打印出来。很多同学第一反应是用递归但北邮这份资料里的 Maze.cpp 用的是手写栈——这恰好点明了实验的考察意图栈不是抽象概念它就是用来实现深度优先搜索的载体。3.1 为什么说迷宫是栈的经典应用场景迷宫求解的本质是深度优先搜索。每一步往四个方向试探能走就压栈继续走走不通就弹栈退回去。这个过程天然符合栈“后进先出”的特性——最后压进去的格子最先被退出来。如果你用递归写 DFS系统调用栈在隐式地帮你做这件事但实验报告里看不清你懂不懂栈。手写栈版本把入栈、出栈、栈顶元素读取这些操作全部显式化了这才是老师要考察的东西。#include vector using namespace std; int maze[16][16]; // 0 可走1 墙 int vis[16][16]; // 1 表示已经访问过 int n, m; // 地图行数和列数 int sx, sy, ex, ey; // 起点和终点 vectorpairint, int path; // 方向数组右、下、左、上 int dirs[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; bool dfs(int x, int y) { if (x ex y ey) { path.push_back({x, y}); return true; } for (int i 0; i 4; i) { int nx x dirs[i][0]; int ny y dirs[i][1]; if (nx 0 || ny 0 || nx n || ny m) continue; // 越界跳过 if (maze[nx][ny] 1 || vis[nx][ny]) continue; // 墙或已访问 vis[nx][ny] 1; path.push_back({nx, ny}); if (dfs(nx, ny)) return true; path.pop_back(); // 回溯撤销当前点 vis[nx][ny] 0; // 关键恢复现场 } return false; }逻辑说明这个版本的 DFS 只要找到一条路径就提前返回所以递归返回true时路径容器里装的就是当前这条通路。path.pop_back()和vis[nx][ny] 0必须配对出现——弹出路径点的同时把访问标记清掉否则回溯之后这个点会被永久标记为已访问导致其它路线被错误剪掉。参数说明方向数组的顺序决定了优先试探的方向。这里先右后下意味着如果起点在左上角、终点在右下角找到的第一条路径会偏向“先向右再向下”路径形状和地方案都跟方向顺序直接相关。有的实验要求输出“所有路径”那个版本里vis不能在回溯时恢复只能在递归返回前保持标记状态控制的是找一条还是找全部。3.2 手写栈版本要处理的两个平凡细节资料里的 Maze 目录还包含一个手写栈的实现用数组模拟栈顶指针没有调用系统递归。这个版本里最容易被忽略的两个细节是起点要先入栈并标记访问否则第一次扩展时会把起点当作“还没到过的点”重新走一遍终点入栈后要立即停止扩展不要在终点之后继续向四周试探。这两个细节在递归版里不容易踩坑但手写栈里只要漏一步路径就会多出一个多余的格子。实验报告里写明了栈的每一步操作和迷宫地图状态的对应关系这是整个实验里最值钱的部分——因为老师看的不只是代码能不能跑更看重你能不能把“栈的状态变化”和“地图的搜索过程”一一对应起来。如果你要借鉴这份报告建议自己也画一张迷宫图标出栈的 push/pop 序列两相对照报告的说服力会强很多。4. Huffman 编码实验从字符统计到译码还原实验3哈夫曼编码是这几份实验里综合性最强的一个。它要完成四件事统计文本字符频率、用优先队列构建哈夫曼树、根据树生成每个字符的二进制编码、用编码表对原始内容做编码和译码。资料里提供了两份版本Huffman 目录下有实验报告和代码5.cpp 和 5.exe 是另一个时期的版本。两份代码可以互相校验。4.1 编码链路和结点结构设计哈夫曼树的结点结构比链表结点复杂一些因为它是二叉树结点同时还要记录字符和频率两个信息。struct HNode { char ch; // 叶子结点保存字符 int freq; // 字符出现频率 HNode *left; HNode *right; bool isLeaf; // 是否是叶子结点 HNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr), isLeaf(true) {} }; // 优先队列比较器最小堆 struct Cmp { bool operator()(const HNode *a, const HNode *b) const { return a-freq b-freq; } };逻辑说明先用一个长度为 256 的数组或mapchar, int统计每个字符出现次数再为每个出现过的字符创建一个叶子结点放入优先队列。之后每次从堆顶取两个频率最小的结点合并成一个新结点新结点的频率是两个子结点频率之和isLeaf 置为 false再放回队列。重复这个过程直到堆里只剩一个结点那就是哈夫曼树的根。参数说明isLeaf这个标记在编码阶段非常重要。递归遍历树时只有isLeaf true的结点才对应一个真实字符内部结点的 ch 是无意义的如果不加判断就会把空字符也输出到编码表里。Cmp 里用是为了让priority_queue变成最小堆——默认的 priority_queue 是最大堆这是新手最容易写反的地方。4.2 编码生成用递归译码还原用循环生成编码的方式是递归遍历哈夫曼树左子树路径记为 0右子树路径记为 1走到叶子时把路径字符串存入编码表。译码则是反过来从根开始读到一个 0 就走左子树读到 1 就走右子树走到叶子就输出该叶子对应的字符然后回到根继续读下一位。void buildCode(HNode *root, string cur, string codeTable[]) { if (root-isLeaf) { codeTable[(unsigned char)root-ch] cur; return; } cur.push_back(0); buildCode(root-left, cur, codeTable); cur.pop_back(); cur.push_back(1); buildCode(root-right, cur, codeTable); cur.pop_back(); }逻辑说明这一段代码的精髓是 cur 字符串的“push 得越深、pop 得越干净”。进入左子树前加 0退出左子树后立刻删掉这个 0这样进入右子树时 cur 仍然是父结点的编码不会把左子树路径混进来。参数说明这个实验里最值得深入理解的指标是 WPL即“带权路径长度”。计算方式是把每个叶子的频率乘以它在树中的深度再求和。实验报告里会要求你对比“等长编码”和“哈夫曼编码”的总位数差距推荐自己构一段英文文本数清楚两种方案的存储位差这是报告里最能出彩的数据。提示Huffman 编码的代码在 5.cpp 里有一个坑——它用了system(pause)和conio.h在非 Windows 环境下会编译失败。如果你在 Linux 或 macOS 上复现建议直接把这两个依赖删掉不影响核心逻辑。5. 全库踩坑记录这些坑我在别人的报告和代码里都见过5.1 现象链表插入后打印发现头结点没变原因插入函数形参是Node *head函数内部确实插入了新结点但实参和形参是两份拷贝函数结束时形参销毁实参指向的仍然是旧结点。解决把形参改成Node *headC 引用或者Node **headC 语言二级指针并在函数内部用*head p;更新。5.2 现象迷宫路径打印出来“多走”了一个格子原因把起点先标记成访问但起点没有被压入路径容器或者路径容器里同时装进了“正在试探但还没走通”的格子。解决在 DFS 入口处先把当前点压入 path返回 false 时才弹出去不要让四个方向的试探点都提前入栈只有确认dfs(nx, ny)返回 true 才保留这个点否则立即 pop。5.3 现象Huffman 译码结果乱码原因编码表生成时没有判断isLeaf把内部结点的空字符也写进去了或者译码时每读一位就重新从根开始找没有维护一个“当前结点指针”。解决编码时必须用 isLeaf 过滤非叶子结点译码时用循环而不是递归——每次只读一位移动当前指针指针到达叶子就输出字符并重置为根。5.4 现象排序比较实验里冒泡排序耗时永远为 0 毫秒原因测试数据量太小比如只有 1000 个数冒泡排序在这种规模下不足 1msclock()的精度不够显示为 0。解决把数据量撑到 10 万以上每次排序前重新生成随机数据并复制到临时数组避免前一个排序函数把数组排好后后面的排序函数拿到的已经是有序数据导致耗时虚低。重复执行 5 次取中位数比单次计时可靠得多。5.5 现象实验报告里的截图和实际跑出来的结果对不上原因资料里可能同时存在“实验3_Huffman编码”和“5.cpp/5.exe”两版代码exe 是老版本编译产物而报告截图是后来更新的代码输出。解决拿到任何实验包第一件事不是看代码而是重新编译所有 .cpp 文件把运行结果和报告里的每张截图逐一核对。如果对不上说明截图对应的是旧版本要以重新编译后的输出为准并在报告里说明版本差异。6. 把别人的实验变成自己的验证脚本与报告写作拆完这份北邮资料后我发现最实用的其实是“排序算法比较”那个实验。它不只是让你验证几种排序的时间复杂度还天然适合做成一个可复用的测试框架。我的习惯是用一个随机数组生成器打底每次排序前重新拷贝一份数据保证每一次排序都面对同一组输入。#include chrono #include cstdlib #include iostream using namespace std; // 对同一个随机数组分别调用不同排序函数统计毫秒耗时 void runSort(void (*sortFunc)(int[], int), int arr[], int n, const char *name) { int *tmp new int[n]; for (int i 0; i n; i) tmp[i] arr[i]; auto start chrono::steady_clock::now(); sortFunc(tmp, n); auto end chrono::steady_clock::now(); double cost chrono::durationdouble, milli(end - start).count(); cout name : cost ms endl; delete[] tmp; }逻辑说明runSort 接收一个函数指针、原始数组和数据规模每次进去先复制一份新数组保证排序函数操作的是一份独立数据。这样做的好处是排列顺序完全一致对比出的时间差异只来自算法本身而不是数据分布的偶然偏差。参数说明数据规模从 1 万、5 万、10 万、20 万分档能直观看到 O(n²) 的冒泡排序在 20 万规模下几乎跑不动而 O(n log n) 的快速排序依然在几十毫秒级别——这比在报告里干写复杂度分析有说服力得多。我的习惯是跑完把四档规模的结果做成表格附上复杂度推导再把“为什么冒泡到 20 万就失去理智”写成一两段讨论这几乎是稳拿分的写法。从那以后我每次拿到别人的实验包都强制自己先走一遍重新编译、核对输出、跑自测脚本这三步确认代码真的能跑才敢改。希望帮到你。本文还有配套的精品资源点击获取