简介华中科技大学数据结构课程配套实验代码面向计算机专业学生、考研复习者及需要巩固数据结构与C语言实现的初学者能够直接用于实验课参考或算法理解。压缩包内共四个c文件整体仅十七KB分别对应顺序表、单链表、二叉树和邻接表无向图四个经典实验覆盖线性表、树形结构与图结构的基本操作代码体量精简便于逐行阅读。代码实现包含顺序表的创建与插入删除、单链表的节点插入与遍历、二叉树的递归遍历及查找、邻接表的图构建与深度优先搜索等核心功能能够帮助读者对照教材理解抽象概念与具体编码的对应关系掌握不同数据结构的适用场景与操作细节。已有五百七十四人学习下载适合作为实验课参考、期末复习或自学练手的轻量资料。1. 数据结构实验到底在考什么不是把代码跑通就完事数据结构实验在很多学校是本科阶段第一道硬门槛某高校的上机验收通常由“代码演示 随机提问 实验报告”三部分组成。很多同学把实验当成普通作业写完能跑就提交结果验收现场被一个“如果链表只有一个节点你的删除函数还正确吗”问住。数据结构实验真正衡量的不是“能不能编译”而是三件事能否把抽象结构落成可维护的代码、能否扛住边界条件和异常输入、能否讲清楚时间与空间复杂度。本文按某高校常见实验大纲展开覆盖线性表、链表、二叉树、排序与图并专门整理验收时经常翻车的问题。适合正在做实验或准备机试的读者也适合想把自己写的数据结构代码从“能跑”提升到“经得起追问”的人。2. 实验环境与工程骨架从编译器选型到 Makefile 组织数据结构实验的代码量虽然不大但工程组织的差别直接影响调试效率。很多第一次做实验的同学习惯把所有函数堆在一个 main.cpp 里头文件、实现、测试混在一起改一个 bug 要滚动半天。一个干净的工程骨架能让你在验收时快速定位问题也给后续实验复用代码打下基础。2.1 语言标准与编译器为什么推荐 C17多数在线评测系统和高校上机环境支持 C实验通常允许自由选择 C 或 C。我的习惯是用 C17原因是它提供了更安全的内存管理工具。链表、二叉树这类结构涉及大量动态内存手动 new/delete 很容易在边界条件下泄漏或重复释放。用智能指针能减少这类问题但要注意部分 OJ 环境对 C17 支持不完整编译前先确认版本。g -stdc17 -Wall -Wextra -g -fsanitizeaddress,undefined -o lab main.cpp list.cpp-Wall -Wextra打开所有常规警告未初始化变量、符号不匹配都会提示。-g生成调试信息配合 gdb 才能看到行号。-fsanitizeaddress,undefined是内存检查利器数组越界、野指针、整数溢出会在运行时报出具体位置。本地调试时加上交到 OJ 前去掉。如果题目明确要求只能提交单个源文件也要在本地用多文件组织最后再合并。合并时最容易出问题的是头文件重复包含和全局变量冲突所以从一开始就养成写头文件守卫的习惯。2.2 目录结构头文件、实现与测试分离我一般给每次实验建独立目录按“头文件 实现 测试 数据”四部分组织。这样做的目的是让测试代码和算法代码分离验收演示时只展示算法实现测试部分放在另一个文件里避免被提问时手忙脚乱。lab2/ ├── include/ │ ├── list.h │ └── tree.h ├── src/ │ ├── list.cpp │ └── tree.cpp ├── test/ │ ├── test_list.cpp │ └── test_tree.cpp └── Makefileinclude目录放公开接口src放实现test放测试入口。测试文件可以直接编译成可执行程序配合断言做自动化验证。数据文件如input.txt、output.txt单独放一个目录避免和源码混在一起被误提交。头文件里只暴露必要的接口内部辅助函数用static或匿名命名空间限制在源文件内。这样在验收时讲代码结构会更清晰评审老师问“这个函数在哪定义的”你能直接指向具体文件而不是在一堆代码里翻找。2.3 最小 Makefile一条命令完成编译和测试多文件工程手动敲 g 命令容易漏文件而且警告参数每次都要重复输入。一个最小 Makefile 能解决这个问题还能自动处理头文件依赖。CXX g CXXFLAGS -stdc17 -Wall -Wextra -g LDFLAGS -fsanitizeaddress,undefined TEST_TARGETS test_list test_tree all: $(TEST_TARGETS) test_list: test/test_list.cpp src/list.cpp include/list.h $(CXX) $(CXXFLAGS) $(LDFLAGS) -Iinclude -o $ test/test_list.cpp src/list.cpp test_tree: test/test_tree.cpp src/tree.cpp include/tree.h $(CXX) $(CXXFLAGS) $(LDFLAGS) -Iinclude -o $ test/test_tree.cpp src/tree.cpp clean: rm -f test_list test_tree .PHONY: all clean-Iinclude让编译器在 include 目录找头文件。$是目标文件名这样每个编译目标只用写一次。clean目标用于清理中间产物。注意-fsanitize既要在编译期加也要在链接期加所以放到LDFLAGS里。写完这个 Makefile后续每次实验只需改文件名和依赖关系不用再重复记编译参数。这也是数据结构实验里最值得先投资的部分——后面几个实验都能复用这份模板。3. 线性表和链表实验顺序存储与链式存储的边界条件线性表是最早做的实验也是后续所有结构的基础。这块的考核点集中在插入删除的正确性和边界处理上。很多同学顺序表部分顺利通过一到单链表就翻车主要原因是没有建立“指针是指向节点的变量”这一直觉。3.1 顺序表和链表两类实现的考核点对比顺序表用数组实现逻辑简单但插入删除要移动元素。链表用节点指针串联插入删除只需修改指针但细节更多。两者都要掌握的判断点是插入位置合法性、空表操作、删除最后一个元素。操作顺序表单链表按位查找O(1)O(n)按值查找O(n)O(n)插入O(n) 需移动元素O(1) 前提是要找到前驱删除O(n) 需移动元素O(1) 前提是要找到前驱考核时最常见的提问是“为什么带头结点比不带头结点好用”。带头结点统一了空表和非空表的处理逻辑插入删除头节点时不需要单独判断表是否为空代码分支更少。不带头结点的写法在一些教材里出现但上机实现时容易漏掉头节点更新所以实验用带头结点更稳。3.2 带头结点单链表的插入与删除实现插入操作的核心是“先连后断”。如果先断开原链再接入新节点链会断掉。很多同学写成prev-next node; node-next current;结果后面的节点全部丢失原因就是先把前驱指向新节点原链关系被破坏。bool insertNode(LinkList L, int pos, int val) { if (pos 0) return false; LNode* prev L; int idx 0; while (prev idx pos) { // 找到第 pos 个位置的前驱 prev prev-next; idx; } if (!prev) return false; // 位置超出链表长度 LNode* node new LNode(val); node-next prev-next; // 先连后继 prev-next node; // 再改前驱 return true; }prev定位到插入位置的前驱节点。node-next prev-next这一步先把新节点和后继连上prev-next node再把前驱指向新节点。顺序不能反这是链表操作的铁律。参数pos从 0 开始计数0 表示插到头节点之后这样就统一了头插和尾插的逻辑。删除操作的原理类似定位到前驱后用临时变量保存待删节点修改指针最后释放内存。释放内存时注意先用next del-next保存后续链表再delete del否则会丢链。3.3 链表反转迭代与递归的对比链表反转是实验验收和笔试都喜欢问的题。迭代写法用三个指针遍历递归写法代码更短但理解难度更高而且递归深度受链表长度限制。// 迭代反转 LNode* reverseList(LNode* head) { LNode* prev nullptr; LNode* cur head; while (cur) { LNode* next cur-next; // 保存后继防止断链 cur-next prev; // 当前节点指向前驱 prev cur; // 前驱后移 cur next; // 当前节点后移 } return prev; } // 递归反转 LNode* reverseListRecursive(LNode* head) { if (!head || !head-next) return head; LNode* newHead reverseListRecursive(head-next); head-next-next head; // 后继节点指回当前节点 head-next nullptr; // 当前节点置空 return newHead; }迭代版本的关键是next必须在修改cur-next之前保存否则后续节点全部丢失。递归版本结束条件是链表为空或只剩一个节点每次递归返回的是新链表的头节点。递归写法在链表长度超过几千时可能栈溢出实验数据规模一般不大但如果你在 OJ 上遇到十万级链表反转优先用迭代版。链表部分还有一个常见考核点判断链表是否有环。快慢指针是最经典的做法慢指针每次走一步快指针每次走两步如果存在环两个指针必然相遇。这个题目不需要额外空间但要注意快指针每次移动两步时需要判断是否为 NULL。4. 树与二叉树实验从递归遍历到非递归实现二叉树实验是数据结构课程的分水岭。递归遍历写法简单但“递归转非递归”几乎每次实验都会被问到。很多同学能写出递归版却讲不清递归调用栈的变化导致非递归实现无从下手。这一章从递归框架讲起逐步过渡到显式栈和队列实现。4.1 三种递归遍历先序、中序、后序递归遍历的代码量很小核心是访问根节点的时机不同。先序在递归左子树前访问根中序在左子树递归完后访问后序在左右子树都访问完后。void preorder(TreeNode* root) { if (!root) return; cout root-val ; // 先访问根 preorder(root-left); preorder(root-right); } void inorder(TreeNode* root) { if (!root) return; inorder(root-left); cout root-val ; // 左子树完毕后访问根 inorder(root-right); }递归实现的关键理解是“访问根节点的时机”。画一棵三层二叉树手动模拟三个版本的输出顺序比背代码有用得多。验收老师常问“如果中序和前序结果已知能否唯一确定一棵二叉树”答案是可以前提是节点值不重复。这个问题在实验报告里也经常出现。递归转非递归的本质是用显式栈模拟系统调用栈。写非递归中序时思想是沿着左子树一直入栈直到没有左孩子出栈访问节点再转向右子树。4.2 非递归中序遍历显式栈模拟调用过程中序非递归是最常考的实现之一它比先序非递归多一个“回溯”步骤也更考验对栈的理解。void inorderIterative(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); // 左子树一路入栈 cur cur-left; } cur st.top(); st.pop(); cout cur-val ; // 出栈访问节点 cur cur-right; // 转向右子树 } }外层循环条件cur || !st.empty()判断当前节点和栈是否为空。内层循环把当前节点的所有左子树节点入栈直到 NULL。出栈后访问节点再转向右子树。整个过程中每个节点入栈一次出栈一次时间复杂度 O(n)空间复杂度 O(h)h 是树高。写这个实现时最常出的错是忘记cur cur-right。如果漏掉这一行节点会反复入栈出栈形成死循环。另一个常见错误是内层循环写成while (cur-left)没有把当前节点本身入栈导致访问顺序错乱。4.3 层次遍历与完全二叉树判定层次遍历用队列实现是从根开始逐层扫描。完全二叉树判定是综合题里比较有区分度的部分它考察的是对“完全二叉树定义”的理解除了最后一层其余层必须填满最后一层节点靠左排列。bool isCompleteTree(TreeNode* root) { if (!root) return true; queueTreeNode* q; q.push(root); bool mustBeLeaf false; while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (mustBeLeaf (node-left || node-right)) return false; if (node-left) { q.push(node-left); } else if (node-right) { return false; // 左空右非空必然不是完全二叉树 } if (node-right) { q.push(node-right); } else { mustBeLeaf true; // 右孩子为空后续节点都必须是叶子 } } return true; }判定思路层次遍历时如果遇到某个节点缺少右孩子则后续所有节点都不能有孩子。更严格地说只要出现一个节点没有左孩子但有右孩子直接判定不是完全二叉树。当节点右孩子为空时设置mustBeLeaf标记后续所有出队节点必须左右孩子都为空否则返回 false。这个实现时间复杂度 O(n)空间复杂度 O(n)在验收时可以顺手讲出来这是加分项。二叉树实验的关键就是要能把这个结构的问题用代码表达清楚再配合图来解释原理。5. 避坑数据结构实验常见的 5 个雷区与排查顺序这一节整理的是实验过程中最容易踩的坑每个都按“现象、原因、解决”三步来写。你在实验里遇到的八成问题翻到对应条就能找到答案。5.1 现象本地跑通交上去就段错误这是最玄学的问题之一。程序在自己机器上输出正确换到 OJ 或验收环境就段错误。通常原因不是编译器差异而是代码里存在未定义行为数组越界、空指针解引用、函数返回局部变量地址。本地没崩只是运气好内存布局恰好没触发。解决方法是开 AddressSanitizer 重新编译运行它能精确定位到越界的行号。另一个常见原因是没有判空比如对空链表调用cur-next。写代码时对每一个-操作都要问自己当前节点是否可能为 NULL。我的习惯是凡是可能为空的节点统一加判空逻辑。5.2 现象链表插入删除在头尾节点上翻车边界节点是最容易出错的。现象是中间插入删除都正常一操作头节点就丢数据或者删除尾巴节点后遍历死循环。原因往往是没带头结点或头插时忘记更新链表头指针。解决方法是写代码前先用纸画出链表的逻辑图分别走一遍空链表、单节点链表、双节点链表的插入删除路径。画图这一步不能省很多看似复杂的指针操作在图上就是一目了然的事情。代码里统一用带头结点写法把空表情况和非空表情况合并处理。5.3 现象递归深度过大导致栈溢出二叉树退化成长链表时递归深度等于节点数。如果实验数据构造了一棵一万层的树递归先序会直接爆栈。现象是程序在递归入口崩溃或报 “stack overflow” 错误。解决方法是把递归改成显式栈的迭代版。对于遍历类操作非递归实现和递归实现的时间复杂度相同只是空间从系统栈挪到了堆内存。如果题目要求必须递归比如求树的高度可以考虑增大调用栈大小但这不是通用解法。我更建议在实验开始前就写迭代版本省得后期改。5.4 现象OJ 显示超时但本地测试秒出超时通常不是常数慢而是复杂度不达标。比如在链表查找中每次都用扫描从头开始或者在排序题里用了冒泡去处理十万级数据。本地数据规模小感受不出来OJ 数据量大差距立刻体现。另一个隐蔽原因是死循环常见于链表反转时指针方向没改对。解决方法是先用题目给的最大数据规模构造测试数据本地跑一遍看耗时如果操作数量级在千万级就要检查算法是否优化。养成写完代码先算一遍时间复杂度的习惯当你的算法是 O(n²) 而输入规模是 10⁵ 时无论如何优化常数都救不了必须换思路。5.5 现象内存泄漏检测工具报错检查了 delete 还是不够delete 明明写了内存泄漏还是存在这一般是浅拷贝导致的。自定义链表类时如果没写拷贝构造函数和赋值操作符默认的浅拷贝会让两个对象指向同一块内存析构时重复释放程序崩溃。另一种情况是删除节点时只改指针没释放节点或释放顺序错误导致节点丢失。解决方法是遵循“拷贝三件套”规则定义析构函数时必须同时定义拷贝构造函数和拷贝赋值操作符。排查泄漏时用编译器的 AddressSanitizer它会在程序退出时报告泄漏内存的大小和分配位置。数据结构的实验代码应尽量避免手写 new/delete能用unique_ptr就用智能指针。6. 实验报告之外的验证技巧用对拍和断言给自己挑毛病最后一章聊一个很多同学到实验结束都没掌握的技巧用测试脚本验证代码正确性而不是靠肉眼盯几组样例就交付。数据结构实验的测试量不大但边界条件多一个简单的对拍脚本能发现大量隐蔽错误。对拍的基本流程是写一个暴力解法作为参考答案再写一个优化解法作为被测对象用随机数据生成器构造输入比较两个程序输出是否一致。在数据结构实验里暴力解法一般是简单直观的写法比如排序用冒泡去验证快排查找用线性扫描去验证二叉搜索树。随机测试跑一千组数据正确性基本能得到保障。断言也是一种低成本验证方式。在链表操作后断言头节点不为空、长度符合预期在树操作后断言中序遍历结果有序。这些断言在发布代码前可以保留在 OJ 提交时可以选择性删除。我自己的经验是写完一个函数先写三到五条断言往往能在一分钟内发现隐藏问题。另一个值得做的验证是构造极端数据。链表实验用单节点和空链表测试二叉树实验用只有左子树的退化链测试排序实验用完全逆序和完全有序的数据测试。这些极端情况比老师随机问的边界问题覆盖更全面。验收前还可以把所有测试用例整理成一个脚本一条命令跑全部测试。把 printf 的输出重定向到文件再用 diff 对比标准答案文件这样避免了一条条肉眼比对。这个习惯并不复杂但能显著减少验收现场改 bug 的时间。回想起我自己做实验时最深刻的教训有一回二叉树层次遍历在空树上没判空本地测试没测这个输入验收时老师第一句话就是“空树怎么办”当场改代码改到满头汗。从那以后我对自己写结构代码都会多问一句“如果是空结构我的代码能直接运行吗”。这个习惯一直保留到现在写队列、写图邻接表时都先处理空容器。希望帮到你。本文还有配套的精品资源点击获取