数据结构C++实验代码与报告：期末考研复习的完整复盘指南

简介：数据结构是计算机科学的核心课程，这份实验资料围绕一元多项式相乘、迷宫问题、霍夫曼编码和校园导游图导航四个经典课题，给出完整C++题目代码、可执行程序及实验报告，面向正在学习数据结构或备战课程设计的高校学生。资源包共53个文件，大小仅2.67MB，文件类型以cpp源代码、h头文件、exe可执行文件为主，同时包含obj编译中间产物、txt测试用例与编码结果、docx实验报告以及tlog等工程构建记录，结构清晰，便于直接运行和按需查阅。目前已有1523人学习，下载热度较高。各实验分别覆盖链表与多项式运算、栈和队列在图遍历中的应用、二叉树与优先队列实现霍夫曼编码、邻接矩阵/表与迪杰斯特拉最短路径求解等关键知识点；实验报告对设计思路、实现步骤、复杂度分析均有说明，完整代码可一键运行，适合用来巩固理论、学习算法落地和参考课程报告写法。

1. 数据结构实验课整理：这套 C++ 实验代码、题目和报告放进一个 zip 里意味着什么

数据结构课期末和考研复习，卡住的点往往不是概念背不下来，而是手边没有一套“能跑、能对得上报告、能解释原理”的实验代码。教学平台上抄下来的代码换台机器就报错，群里的报告截图和源码对不上号，题目文档又单独存在另一个压缩包里，复习时来回切换非常费劲。我拆这份 zip 的时候，最大的感受是它把数据结构与算法这门课最常布置的几个大方向——线性表、栈与队列、树、图、排序查找——按实验专题拆成了独立文件夹，每个文件夹里有题目说明、C++ 完整代码和对应的实验报告，三者放在一起，对照着看就能把理论和实现串起来。

它适合两类人。一类是准备数据结构期末复习、想快速过一遍各实验模块代码的人；另一类是准备考研数据结构、需要用具体实现反推概念细节的人。它不适合零基础学 C++ 语法，因为代码默认你已经有语言基础，更多精力放在数据结构逻辑上。后面我按“解压 → 编译 → 逐实验原理 → 踩坑 → 复习方法”的顺序讲清楚。

2. 解开 zip 之前先看目录：实验题目、完整代码和报告的对应关系

拿到 zip 先别急着全量解压跑代码，先看一次目录结构，能省下很多“找不到入口”的时间。

2.1 文件命名与归档规律

我解压之后看到的典型布局是：根目录有一个README.txt和一份题目汇总.pdf，然后是一串按序号排列的文件夹。每个文件夹的名字基本就是实验主题，比如01_顺序表与链表、02_栈和队列、03_二叉树遍历、04_图的最短路径、05_排序算法对比这样。拿其中一个实验文件夹举例，里面的文件对应关系是这样的：

这个结构比很多“单文件代码”要友好。你可以先打开题目说明，在cpp里搜对应的函数名，再回实验报告看设计说明。三步就能建立“题目 → 代码 → 结果”的闭环。文件名有前缀数字，目的是保证按顺序递进：前面用到“线性表”的实现，后面的“链表合并”“图的遍历”可以直接复用，方便你按课程进度做阶段性复习。

2.2 编译环境与 C++ 标准选择

这套资源全部用 C++ 写，不是纯 C。这个选型挺常见：学校数据结构实验课用 C++ 做载体，能直接用vector、stack、queue等容器封装底层结构，代码量比纯 C 少，重点更集中在“数据结构本身怎么设计”。比如栈的实验就可以直接用std::stack，链表实验则自己写class ListNode，两种风格同时出现，刚好覆盖教学要求里“既要用自定义类型、又要会用 STL”的习惯。

编译环境上，Dev-C++、Code::Blocks、Visual Studio 都可以。因为代码大量使用 C++11 的nullptr、auto、范围for，老旧的 VC6 可能会报错。命令行编译建议这样做：

g++ -std=c++11 -Wall -O2 -o SeqList_demo.exe SeqList.cpp

参数含义：-std=c++11让编译器按 C++11 标准解析代码；-Wall输出所有警告，实验代码里常见的“变量未使用”“比较有符号无符号”都会提示；-O2开优化，跑大数据量测试时快一些。我一般会再加一个-g，配合 gdb 看段错误，对于后续踩坑定位关键步骤非常有用。

2.3 批量编译脚本：一次把全部实验编译出来

文件夹多的时候一个个敲命令不方便。可以在 zip 解压后的根目录放一个批量编译脚本，比如 Windows 下的build_all.bat：

@echo off for %%f in (*.cpp) do ( echo compiling %%f ... g++ -std=c++11 -Wall -O2 -o %%~nf.exe %%f )

并不是所有的.cpp都能直接编译成 exe，有的文件只是类实现，没有main函数。我实际会先用g++ -c只编译不链接，把语法错误先消灭掉，再单独编译带main的主程序文件。如果某个文件报告“undefined reference tomain”，说明它只是一个模块，不属于独立可执行文件。批量脚本的意义是快速建立“这份代码能不能跑”的初步印象，而不是替代逐个实验的验证。

2.4 与《数据结构（C 语言版）》教材的对位

很多学校用的教材还是严蔚敏老师的《数据结构（C 语言版）》，但这套实验用 C++ 实现同样的逻辑。你在复习时不必纠结语言差异，把重点放在“逻辑结构 + 存储结构 + 基本操作”上。比如教材里的顺序表用struct和malloc实现，实验代码则用class和new，但是插入、删除、查找的操作逻辑完全一样。换语言只是换了表达方式，数据结构本身的边界条件和复杂度分析才是实验考察的核心。这份 zip 的代码刚好可以作为那种“把伪代码变成真实可查的执行过程”的参考，配合王道考研复习书上对同一知识点的讲解，收获会更大。

3. 线性表、栈与队列的实验代码：边界条件是满分和及格的分水岭

线性表和栈队列是数据结构实验里最基础也最容易丢分的模块。题目本身不难，但判分点往往隐蔽在边界条件里。

3.1 顺序表插入删除：位置判断要写成双重保险

顺序表本质是数组，插入操作最经典的问题是“数组下标越界”和“位置判断错误”。常见写法是允许pos从 0 到length，其中pos == length表示尾部追加。代码里常见的正确实现：

bool SeqList::insert(int pos, int e) { if (length >= MAX_SIZE) { cerr << "list full" << endl; return false; } if (pos < 0 || pos > length) { cerr << "position out of range" << endl; return false; } for (int i = length; i > pos; --i) { data[i] = data[i - 1]; // 从后往前搬，先腾出 pos 位置 } data[pos] = e; ++length; return true; }

这个代码里的关键点是for (int i = length; i > pos; --i)。循环从最后一个元素开始，把它挪到后一个位置，一直挪到pos位置腾出来为止。如果写成i = length - 1; i >= pos; --i，就会出现数组数据覆盖，且i可能变负导致死循环。我还见过一种错误是把判断写成pos >= length，这样尾部插入直接被拒绝，测试样例通过率会明显降低。实验报告里如果要体现完整，建议把“头插、中间插、尾插、越界插”四种情况各跑一遍，并截图存证。

3.2 单链表反转与有序合并：带头结点和不带头结点的差异

链表实验出现频率最高的就是反转和合并。反转最容易写乱的是指针丢失，下面这个迭代版本是公认不容易出错的写法：

ListNode* reverseList(ListNode* head) { ListNode *pre = nullptr, *cur = head; while (cur != nullptr) { ListNode* next = cur->next; // 先保存后继，防止断链 cur->next = pre; // 翻转当前节点的指向 pre = cur; // pre 前移 cur = next; // cur 前移 } return pre; }

这里的核心习惯：在改cur->next之前，必须先保存cur->next到临时变量。我第一次写的时候就吃过亏，cur->next被改写后，cur->next原来的值就丢失了，循环根本没走出两个节点。如果有不带头结点的链表，反转后pre就是新头；如果带头结点，更稳妥的做法是保留一个头结点，只反转头结点后面的数据节点，这样外部接口不变，调用方不需要重新接受返回值。

两个有序链表合并的代码也很典型，用哨兵节点可以省去单独判断头节点：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; }

哨兵节点避免了“第一个节点比较前需要判断tail是否为空”的麻烦，这也是实验报告里值得写的“设计亮点”。题目如果只要合并结果而不允许申请新节点，这份代码正好满足：它只是把节点的next指针改来改去，没有new新节点。

3.3 栈的应用：括号匹配和表达式求值

栈的经典实验题是括号匹配。用 STL 的std::stack写起来非常直观：

bool isBalanced(const string& s) { stack<char> st; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty()) return false; char top = st.top(); if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) return false; st.pop(); } } return st.empty(); }

注意循环结束后必须检查st.empty()，否则可能出现 “输入((()但函数返回 true” 的误判。这个细节在实验报告的测试截图里尤其容易遗漏。进阶题里有时会要求同时处理“圆括号、方括号、花括号”三层嵌套，这个代码天然支持。如果题目改成了“双端队列”的判定，比如判断一组数据能否通过双端队列实现特定输出，那就是把栈顶、队头、队尾的操作混在一起，思路类似但要注意接口差异。

3.4 为什么报告里要写“核心代码片段”而不是贴全部代码

实验报告评分通常在“是否自己实现、边界是否处理、测试是否充分”这三项上扣分。贴全部代码会显得没有重点，我建议选一段最容易被边界条件打败的函数，比如顺序表插入或链表反转，配上两到三行文字解释哪里容易写错。具体写法是：先说明“这里我采用了从后往前移动元素的方式”，再贴代码，最后补一句“如果从前往后移动，后一个元素会覆盖前一个”。这样排版出来的报告，老师一眼就能看到你真正理解了结构和边界。这份 zip 里的报告模板大多是这种结构，可以直接参考它的排版节奏。

4. 树与图的实验代码：遍历、最短路径和测试用例怎么搭

树和图是考研数据结构里的重头戏。代码实现和概念理解之间的落差，往往比线性表更大。

4.1 二叉树遍历：递归好写，非递归才是考点

二叉树先序、中序、后序的递归版本很容易写，但实验题经常要求“写出非递归实现”，目的是考察你对递归栈的理解。以中序遍历为例：

void inorderIterative(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { while (cur != nullptr) { st.push(cur); cur = cur->left; // 一直向左走到头 } cur = st.top(); st.pop(); cout << cur->val << " "; // 出栈时访问 cur = cur->right; // 再转向右子树 } }

这段代码的边界条件是循环结束的判定：cur != nullptr || !st.empty()。有人会漏掉!st.empty()，导致访问到最后一个节点后提前退出。我习惯把“指针走到空栈”和“栈里还有待返回节点”分开理解，这样写出来的循环不会少条件。层次遍历则用queue，每访问一个节点就把左孩子右孩子入队，顺序上和后序非递归有很大差异，实验报告里最好把两个遍历的测试输出分开截图，防止混在一起。

4.2 图的邻接表与 Dijkstra 最短路径：优先队列的排序问题

图实验里 Dijkstra 是最常见的“压轴题”。用邻接表加优先队列实现，代码短、效率高，但有一个坑：priority_queue默认是大顶堆，需要对比较规则额外指定。正确写法是这样：

#include <queue> #include <vector> #include <limits.h> using namespace std; vector<vector<pair<int, int>>> adj; // 邻接表：pair<目标节点, 边权> vector<int> dist; void dijkstra(int source) { dist.assign(adj.size(), INT_MAX); // 注意：priority_queue 默认第一个元素最大的，所以要指定 greater priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; dist[source] = 0; pq.push({0, source}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d != dist[u]) continue; // 过期的旧记录，跳过 for (auto edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }

这里的关键参数有两个。第一个是greater<pair<int,int>>，让优先队列按pair第一个元素（距离）升序输出，距离最小的先出队。如果不写，Dijkstra 会优先处理距离最大的节点，算法全乱。第二个是if (d != dist[u]) continue;，因为同一个节点可能被多次压入优先队列，弹出的可能是一份旧的距离值，不跳过旧记录会污染后续计算。pair 的比较规则是先比第一个元素，再比第二个，所以写{dist[v], v}会让同距离节点按节点编号排序，行为可预测，调试更容易。

4.3 测试用例设计：如何证明你的代码真的符合实验要求

很多实验报告得分低，不是因为代码没写对，而是测试用例太单薄。比如图遍历只测一个“教科书里最常见”的连通图，从不测不连通图；Dijkstra 只测正权图，从不测两个节点之间有多条路径时最短路径的更新过程。我通常会这样设计测试输入：

5 7 0 1 2 0 3 6 1 2 3 1 3 8 1 4 5 2 4 7 3 4 9

第一行是节点数和边数，后面每一行是“起点、终点、边权”。这个用例包含重边、长路径覆盖、不同最短路径的对比，能同时验证邻接表建图正确、松弛条件正确、优先队列弹出顺序正确。把这份输入和程序输出贴在报告里，再写一句“期望最短路径是 0-1-2-4，距离 2+3+7=12”，比贴十行代码更有说服力。对树遍历也有类似技巧：测试空树、只有左子树的树、只有右子树的树，这三种情况能把递归和非递归实现里最容易漏的“空指针访问”问题暴露出来。

5. 避坑专题：数据结构实验代码最常见的五个翻车现场

这部分是我自己编译和运行这套资源时真实踩过的坑，每条都按“现象 → 原因 → 解决”写清楚。

5.1 顺序表尾部插入失败，测试用例总是少一项

现象：插入函数在尾部追加元素时，程序返回失败，控制台打印position out of range，但题目明确要求支持尾部追加。

原因：插入位置判断被写成了if (pos < 0 || pos >= length)，把pos == length这种合法尾部插入挡在了外面。逻辑上这是写代码时把“数组下标 <= length-1”的习惯带到了位置语义里，没有区分“下标”和“元素序号”。

解决：把判断改成if (pos < 0 || pos > length)。顺序表合法插入位置是从 0 到length的闭区间，其中length专门给尾部追加留的。改完后再跑一次“空表插第一个元素、最后一个位置插入、尾部追加”三个用例，就可以覆盖全部边界。

5.2cin和getline混用，导致读入数据为空

现象：程序先执行cin >> n;读一个整数，再执行getline(cin, line);，结果line读到的总是空字符串，后面的遍历直接少一条数据。

原因：cin >> n只读取数字，会遗留一个换行符在输入缓冲区；getline读取到的是这个残留换行，直接结束。这是输入流混用最经典的坑。

解决：在读getline之前先把缓冲区里的换行吞掉。常见做法是：

cin >> n; cin.ignore(numeric_limits<streamsize>::max(), '\n'); // 丢弃换行符 getline(cin, str);

参数numeric_limits<streamsize>::max()表示一次性忽略足够多的字符，直到遇到换行。有的同学会用fflush(stdin)，这在 C++ 标准里行为未定义，不建议写在实验代码里。

5.3 中文输出在 Windows 命令行变成乱码

现象：代码是正常的cout << "请输入节点数："，但运行后控制台显示一堆乱码，英文输出正常。

原因：源文件保存为 UTF-8 编码，但 Windows 控制台默认代码页是 GBK，两者不匹配。程序内部存储的是 UTF-8 字节序列，控制台试着按 GBK 解析，自然显示成乱码。

解决：我一般在main开头加上：

#ifdef _WIN32 system("chcp 65001"); // 切换控制台代码页到 UTF-8 #endif

还有个更底层的方式是SetConsoleOutputCP(CP_UTF8)，需引入<windows.h>，实验报告里通常不会深究这些，能显示中文就行。注意修改后控制台字体也许需要调整，否则部分中文仍显示为方框，这属于字体问题，不是程序问题。

5.4 快排或递归遍历数据量一大就“栈溢出”崩溃

现象：排序实验里用递归快排跑一万条数据没问题，换成二十万条随机数据后，程序直接在递归调用处崩溃，报错stack overflow。

原因：快排递归深度在最坏情况下接近元素数量，系统给线程栈的默认空间有限，递归太深撑爆了调用栈。

解决：有两个可行方案。一是把递归改成显式栈的迭代实现，代码多但不依赖系统栈大小；二是调大链接器的栈空间。用 g++ 编译时加参数：

g++ -std=c++11 -Wl,--stack,16777216 -o quickSort.exe quickSort.cpp

--stack,16777216表示把栈空间设为 16MB。如果是 Visual Studio，可以用#pragma comment(linker, "/STACK:16777216")。实验报告的“算法分析”里值得提一句“本实现针对大数据量使用了手动栈避免递归溢出”，这能体现你理解了问题本质。

5.5 链表销毁时 double free，程序退出前崩掉

现象：用循环遍历链表并delete每个节点，代码在退出时崩溃，报错double free or corruption。

原因：释放当前节点后，立刻访问它的next来获取下一个节点，但next所在内存已被释放，访问到的内容可能是垃圾，重复delete同一块地址。根本原因是释放节点之前没有先保存下一个节点指针。

解决：销毁链表的正确写法是：

ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; // 先保存下一个节点地址 delete cur; cur = next; }

这个思路和链表反转里的“先存 next 再改 cur->next”是一样的，是链表操作最通用的保命习惯。我后来写任何链表代码，涉及delete或next指针重关联前，都会在注释里标注“保存 next 之后再操作”。

6. 期末和考研复习：用这套资源做代码反推理论的复盘

最后一部分不讲编译，讲怎么用这份 zip 把理论复习得更扎实。

6.1 从代码反推“为什么”，把抽象概念变成可执行行为

复习时不要只看代码能不能跑，要试着回答“这段代码对应教材哪一句话”。比如看到平衡二叉树实验代码里的rotateLeft和rotateRight，就回头翻王道复习书里 AVL 树的调整策略，用代码验证：插入导致不平衡时，旋转后的中序遍历序列有没有恢复有序？这样每跑通一个实验，就相当于把一个抽象知识点变成一条可验证的事实。数据结构与算法里那些“为什么快排平均复杂度是 O(n log n)”的结论，也必须结合代码看：每次 partition 把数组分成两半，递归层数就是 log n。这份 zip 里的实验代码正好提供了最直接的观察对象。

6.2 排序比较实验：别背复杂度表，跑一次数据看增长趋势

很多实验设计会要求“比较插入排序、冒泡排序、快排在大数据量下的时间”。你可以用 zip 里的排序实验程序试一组数据量：

实验报告里贴这种对比表格，比空写“快速排序效率更高”要有说服力得多。实际运行时会发现冒泡排序在百万级数据下需要好几分钟，这就让你直观理解了为什么排序算法要设计那么多不同策略。

我自己的习惯是：拿到任何一份实验代码，先假装自己是老师，把代码里每个if的边界条件都试着改成错误版本，看运行结果会不会变坏。这样能快速定位“哪些代码是老师特意留下的考点”，比单纯把代码抄一遍有价值得多。从这份 zip 里我得到的最大启发不是代码本身，而是“边界条件才是数据结构的灵魂”这句话的含义。从那以后我每次写顺序表插入、链表删除、二叉树遍历，都强制自己走一遍边界输入测试，再打开报告写上结论。这份资源里的题目、代码和报告三件套，恰好就是做这种沉浸式复盘的最佳入口，希望帮到你。

本文还有配套的精品资源，点击获取