简介华中科技大学数据结构实验代码与解析面向计算机专业学生及C语言数据结构学习者也可用于期末复习或实验课自学。压缩包共四个C语言源文件对应顺序表、单链表、二叉树、邻接表无向图四个经典实验整体仅17KB每个源文件对应一个实验命名清晰代码精简且注释到位适合逐行研读。已有574人学习下载内容完整覆盖线性表、树和图的核心操作顺序表实现创建、插入、删除与查找单链表包含头节点构建、节点插入删除与遍历二叉树支持前序、中序、后序遍历以及增删查操作邻接表实现无向图的创建、深度与广度优先遍历。通过对照代码可深入理解不同存储结构的特性与时间复杂度同时掌握递归设计与图遍历算法既可作为实验报告的参考框架也能帮助理清数据结构知识体系为算法设计打下扎实基础。1. 华中科技大学数据结构实验到底在考什么从“能跑通”到“能答辩”的距离华中科技大学数据结构实验是计算机专业一块绕不过去的硬骨头。它不要求你发明新算法也不考你背了多少定义验收时干的事情很直接现场编译、现场跑测试数据、现场回答“这里为什么会段错误”。很多同学把严蔚敏版《数据结构C语言版》看了两遍代码也抄懂了结果一到台上就被一个野指针问住。这门实验的真正考点是C语言里结构体、指针、动态内存这三样东西的组合使用——也就是“代码到底在内存里怎么动”。适合正在上这门课、或者准备课程设计和考研的人把它当成一份可复现的上机训练来读。2. 实验环境与代码骨架先在本机把C的调试链跑通再谈算法华科的数据结构实验课堂验收用的机器从机房到个人笔记本都有。常见组合是 Windows Dev-C也有人用 VS Code 配 gccLinux 下无非就是 gcc 加一个 Makefile。环境不重要重要的是你得在同一个工程里同时看到头文件、实现文件和测试代码并且能一条命令完成编译。我的习惯是每个实验建一个独立文件夹比如 lab2_list、lab3_stack里面只放当前实验要的东西省得几个实验的文件互相引用最后变成一堆不知道该不该删的 .c 文件。2.1 为什么这个实验的主战场是C语言数据结构实验用 C 语言不是老师守旧。链表操作里Java 和 Python 把 next 指针封装得干干净净你是看不见一块内存是怎么被串起来的C 语言里结构体 Node 的 next 就是一个实实在在的指针变量改它的值就是改地址。华科的教材是严蔚敏那本《数据结构C语言版》实验代码长期沿用 C 的写法接口里的 ElemType、Status 也都是这本书里的习惯。想抄王道 408 书上的代码可以但王道的代码偏考研应试函数签名和实验指导书不一定对得上你最终还是要自己把类型和返回值改过来。另一个现实原因是C 语言的报错信息很直白。Segmentation fault 出现的时候你至少知道有指针出事了Java 的 NullPointerException 也很直白但 Java 里没有野指针这个概念你体会不到“地址失效”的刺激而这些正是实验报告里老师最爱追问的点。所以哪怕你 C 更熟我也会建议实验原样用 C 提交不要混用 cin/cout 和 new免得验收时答不上“malloc 和 new 有什么区别”这种衍生问题。实验是课程设计的前置把 C 的这套内存操作练熟后面做课程设计时才不会一边写界面一边补指针的课。2.2 三文件拆分头文件、实现文件、测试文件各管一件事大多数实验代码其实只有三部分结构体与函数声明、函数实现、main 里的测试。我一般按下面这个结构建工程以链表实验为例文件职责必须出现的内容list.h对外接口结构体定义、函数声明、宏定义list.c实现每个函数的完整定义包含 malloc/freemain.c测试创建链表、调用操作、打印结果、释放内存list.h 里只放声明不放实现。这样 main.c 包含头文件之后就能调用 list.c 里的函数而不用关心实现细节。下面是一个最小可编译的头文件// list.h链表实验的对外接口 #ifndef LIST_H #define LIST_H #include stdio.h #include stdlib.h typedef int ElemType; // 实验一般用整数测数据ElemType 便于以后换类型 typedef struct Node { ElemType data; struct Node *next; } Node, *LinkList; // LinkList 就是 Node*严蔚敏教材里最常见的写法 LinkList createList(int arr[], int n); // 用数组建表 void printList(LinkList L); // 打印全部节点 void freeList(LinkList L); // 逐个释放避免内存泄漏 #endif这段代码里有几个值得注意的参数和写法。ElemType是严蔚敏教材里的经典抽象实验要求用 int 时直接typedef int ElemType就够了后面如果想测字符只需改这一行。LinkList本质上是指向 Node 的指针但它和Node*在函数参数里是有语义区别的LinkList L表示“指向第一个节点的指针”Node* p表示“指向某个节点的指针”写函数前先想清楚用的是哪一个能减少一半的命名混乱。#ifndef防止重复包含多文件工程里必须写否则两个 .c 都包含 list.h 时会看到一堆 redefinition 报错。对应的测试文件 main.c 长这样// main.c链表实验的测试入口 #include list.h int main() { int arr[] {3, 1, 4, 1, 5}; LinkList L createList(arr, 5); printList(L); freeList(L); return 0; }main.c 只做三件事准备数据、调用接口、释放内存。这样写的好处是实验指导书换一组测试数据时你只需要改 arr 那一行而不动链表实现。万一输出不对也能确认问题出在 createList 还是 printList。freeList(L)这一行最容易漏。实验数据量小漏了也能跑但 valgrind 一检查全是 still reachable 记录报告里写“程序没有内存泄漏”就站不住脚。编译命令我一般这么写gcc -Wall -g -o lab2 main.c list.c-Wall打开所有常见警告-g生成调试信息让 gdb 能定位到具体行号。没有-g的时候段错误只告诉你一个地址你根本不知道是哪一行加上-g之后gdb 能直接指向出问题的源码行。这个习惯值得在第一次实验就养成后面所有实验都用得上。提示实验课检查时老师可能不看你的 Makefile只看你能不能当场编译运行。如果不熟 gcc 参数记住-g -Wall这两个已经能覆盖 80% 的现场情况。真正到验收的时候老师关心的不是你的代码风格多优雅而是“现在把 n 改成 100000再跑一次”。这就意味着测试数据必须好改不能把数组长度写死在函数里。上面 createList 接收 n 作为参数就是为了应对这种现场改数据的操作。有的同学图省事在函数内部写死int n 5换数据就得改函数体这种代码在验收时非常被动。文件命名也建议统一list.c 就叫 list.c不要叫 createListV2final.c实验做到第 5 个的时候你会感谢自己当初的克制。3. 线性表与栈队列实验顺序表插入、链表反转和括号匹配的必会写法线性表和栈队列是华科实验里最早交的两份报告也是最容易让新手第一次在电脑前懵掉的实验。这轮实验的函数都很短但每个接口都涉及“改一个变量还是改一个指针指向的内存”的区分。很多人在这轮养成了两个坏习惯一是把所有代码塞进 main.c二是用注释临时屏蔽代码而不是删掉。下面这三个题目基本涵盖了这两次实验的高频考点。3.1 顺序表插入循环从后往前覆盖边界条件一个不能少顺序表插入的考点是“移动元素的方向”。把元素插入到 pos 位置必须先移动最后一个元素再往前逐个移动从前往后移动后面的数据会被前面覆盖结果是数组尾巴上多出一个不该有的值。下面是一个可直接测试的插入函数// 顺序表插入把 val 插到 pos 位置n 是当前元素个数cap 是容量 int insertSeq(int arr[], int *n, int cap, int pos, int val) { if (pos 0 || pos *n) return 0; // 位置越界 if (*n cap) return 0; // 容量不足 for (int i *n; i pos; i--) { // 从最后一个元素开始后移 arr[i] arr[i - 1]; } arr[pos] val; (*n); return 1; }pos *n这个边界里pos *n是合法的表示插到末尾pos 0则直接拒绝。很多同学只写了pos maxsize忘了 n 和 cap 是两个量结果插入位置在 n 和 cap 之间时数组中间出现空洞。函数返回 0 表示失败可以让 main 里立刻知道参数有问题而不是靠 printf 在插入函数里报错——实验报告里“函数应返回状态而不是直接打印”这条评分点就是冲这个来的。为什么用int *n而不是int n因为插入操作要修改元素总数C 语言里函数参数是值传递不用指针带不回来。这一点也是实验报告里常被追问的地方。顺带一提顺序表删除操作的循环方向正好相反从 pos 位置开始把后面的元素一个一个往前挪最后(*n)--。把插入和删除作为一组写在一个文件里对比着看比单独背代码记得牢。3.2 链表反转三指针原地改不新建任何节点链表实验常有一道“反转单链表”的必考题。递归写法只有三行但链表几万节点时递归深度也会上万实验机上栈可能不够用直接爆栈。迭代写法是标准答案用三个指针往前走// 反转单链表pre 永远指向已反转部分的头 LinkList reverseList(LinkList head) { Node *pre NULL, *cur head, *next; while (cur ! NULL) { next cur-next; // 先保存下一跳否则改完 cur-next 就找不到了 cur-next pre; // 把当前节点指向已经反转好的部分 pre cur; // 反转好的部分向后延伸 cur next; // 当前节点移动到原链表的下一个 } return pre; // 结束时 pre 指向新链表的头 }这个函数最反直觉的地方是next cur-next为什么要放在最前面。如果先执行cur-next pre当前节点后面的链表就断了cur 再想往后走已经没有路。实验里十次段错误有七八次来自这里。另一个容易错的是返回值循环结束时 cur 是 NULLpre 才是新的头返回 pre 而不是 cur。实验报告里如果画三张图分别标出 pre、cur、next 在第一次循环前后的指向老师一看就懂。这也是“链表反转”在答辩里最常被要求现场画图讲解的原因。画图时注意一个细节三个指针的初始位置pre 在 head 左边cur 在 head 上next 在 cur-next 上不是三个指针都在开头。3.3 括号匹配用数组模拟栈理解栈顶指针的变化栈实验最经典的题目是括号匹配。用 C 写栈最简单的是数组模拟不需要完整的链表栈也能体现“后进先出”的验证逻辑#include string.h // 检查括号是否匹配只处理 ()[]{} 三种 int isBalanced(const char *s) { char stack[100]; // 实验数据一般不超过 100 个字符 int top -1; // top -1 表示空栈 for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { stack[top] s[i]; } else if (s[i] ) || s[i] ] || s[i] }) { if (top -1) return 0; // 右括号来了但栈是空的 char left stack[top--]; // 弹出栈顶左括号 if ((left ( s[i] ! )) || (left [ s[i] ! ]) || (left { s[i] ! })) { return 0; } } } return top -1; // 结束时栈里还有没配对的左括号就是失败 }top -1而不是 0是因为入栈时要先 top 再存数据栈顶永远指着最后一个元素如果初值是 0第一个元素会存在 stack[1]浪费一个位置而且空栈判断变成 top 0语义容易乱。判断不匹配时把“右括号多余”“左括号剩余”“括号类型不对”三种情况分开处理写成三个 if比写一个复杂条件好排查得多。为什么不直接用一个计数器那只能处理一种括号。三种括号同时出现时([)]这种字符串计数器是平衡的但括号类型根本不配对必须用栈记录最近一个未配对的左括号。这个实验的测试技巧是准备一组边界用例空字符串、单个括号、((()))、([)]、(]、)(。把字符串当成测试数据放进数组验证完打印 PASS/FAIL验收时直接能看到比现场敲键盘可靠。4. 树与图实验递归建树、非递归遍历和 Dijkstra 的一次性写对思路树和图是两个独立实验很多人从这一轮开始从“会写”变成“看不懂”。递归能建树但不知道怎么打印图的 BFS 写熟了但不会求最短路径。这一章把两个实验的硬骨头分开啃。树实验的输入方式、指针传递、递归边界各是一个坎图实验的最大坎是把算法描述翻译成数组下标操作。4.1 二叉树递归建树先序输入配合 # 占位严蔚敏教材里二叉树的输入约定是按先序顺序输入遇到空节点用#代替。比如AB##C##表示的是一棵只有三个节点的树。递归建树的函数必须用二级指针因为要在函数里给节点指针分配内存#include stdio.h #include stdlib.h typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 按先序读入并建树遇到 # 表示空子树 void createBiTree(BiTree *T) { char ch; scanf( %c, ch); // 前面的空格跳过换行符 if (ch #) { *T NULL; } else { *T (BiTree)malloc(sizeof(BiTNode)); (*T)-data ch; createBiTree(((*T)-lchild)); // 递归建左子树 createBiTree(((*T)-rchild)); // 递归建右子树 } }为什么要BiTree *T而不是BiTree T如果只传指针本身函数内部T malloc(...)改的是形参调用方的 T 还是 NULL。scanf( %c, ch)里格式串前面加一个空格是为了吃掉上一次输入残留的换行符不加这个空格第一次输入 A 后按回车第二次递归读到的就是\n而不是真实节点。这是二叉树实验里最常见的玄学问题之一现象是建出来的树总是多出一些奇怪的节点。建完树之后要做三件套验证先序、中序、后序各打印一遍。如果输入是AB##C##中序输出应该是BAC。这一步能在一秒钟内确认建树是否正确比盯着代码看十分钟有效。注意释放树也要递归先释放左右子树再 free 根节点顺序反了会造成悬垂指针。4.2 非递归中序遍历递归改循环就两句话栈里存什么要想清楚非递归遍历本身就是一个小栈实验。中序非递归的思路是沿着左子树一直往下走走过的节点全部入栈走到 NULL 时弹出栈顶并访问然后转到右子树继续。代码// 非递归中序遍历栈用数组模拟容量按节点数上限开 void inorder(BiTree T) { BiTree stack[100]; int top -1; BiTree p T; while (p ! NULL || top ! -1) { while (p ! NULL) { // 先把左链全部压栈 stack[top] p; p p-lchild; } if (top ! -1) { p stack[top--]; // 弹出一个节点 printf(%c , p-data); // 访问 p p-rchild; // 转向右子树下一次循环继续 } } }外层循环条件p ! NULL || top ! -1很容易写反成p ! NULL top ! -1。用的话一旦某次 p 变成 NULL循环立刻结束右子树还没遍历完。递归改循环的通用套路就是显式用栈保存递归过程中的临时变量这里每一层递归只需要保存一个“当前节点”所以栈里存节点指针就够了。先序非递归和中序的区别只在访问时机先序是在压栈前访问中序是在弹栈后访问。后序最麻烦需要额外记录右子树是否访问过实验里一般不要求但如果指导书提了可以加一个 visited 标记。应付验收时能把中序非递归讲清楚已经足够证明“你理解递归的本质是栈”。4.3 Dijkstra 最短路径邻接矩阵实现别一上来就堆优化图实验里最短路径比遍历难因为即使你理解算法写出来的代码也可能逻辑正确但结果不对。实验规模通常在 20 个节点以内邻接矩阵足够不建议直接上优先队列优化堆的代码更长验收时追问“为什么这里要 down 一下”很容易答不上来。先用邻接矩阵把算法写对再去谈优化。#define INF 0x3f3f3f3f // 表示不可达加法不会溢出 // n 是节点数G 是邻接矩阵start 是源点dist 输出到各点的最短距离 void dijkstra(int n, int G[][20], int start, int dist[]) { int visited[20] {0}; for (int i 0; i n; i) dist[i] G[start][i]; // 初始化一步可达 dist[start] 0; visited[start] 1; for (int round 0; round n - 1; round) { int u -1, min INF; for (int i 0; i n; i) { // 找当前距离最小的未访问点 if (!visited[i] dist[i] min) { min dist[i]; u i; } } if (u -1) break; // 剩下的点都不可达 visited[u] 1; for (int v 0; v n; v) { // 用 u 松弛邻居 if (!visited[v] G[u][v] INF dist[u] G[u][v] dist[v]) { dist[v] dist[u] G[u][v]; } } } }INF选0x3f3f3f3f而不是 999999是因为 0x3f3f3f3f 接近 2^30两个 INF 相加不会溢出 int而 999999 相加后有可能变成负数松弛条件永远不成立。初始化 dist 时直接复制邻接矩阵是从 start 一步到达的代价dist[start]要再置 0因为 G[start][start] 不一定为 0有些数据会填 0但有些模板会填 INF统一置 0 最稳。这段代码在实验报告里配一张手画的图标出每一步选中的 u基本就是满分结构。图实验输入数据的下标陷阱值得单独说。如果实验指导书里的节点编号从 1 开始而 C 数组下标从 0 开始读入边时要写成G[u-1][v-1] w。这个问题我踩过现象是所有结果比标准答案错一位排查了很久才发现是下标没转。我的习惯是读入后立刻打印一遍邻接矩阵的前三行肉眼确认数据落位正确再进入算法主流程。5. 排序查找实验排查手记从数组越界到测试文件读空的三个真实案例排序和查找实验往往放在最后但它的分值不低也是老师唯一可能现场改动测试数据来验收的实验。前面链表、树那几轮代码写对了基本就过了排序这里测试数据一变程序可能立刻翻车。快排本身好写但边界条件和文件读取是扣分重灾区。5.1 快速排序和折半查找先守住边界再谈优化排序实验至少要求实现一种 O(nlogn) 排序。快速排序的写法很多考场上最稳的是严蔚敏教材的挖坑法代码少、边界清楚// 一趟划分把区间 [low, high] 以 pivot 为基准分成两部分 int partition(int arr[], int low, int high) { int pivot arr[low]; // 先挖一个坑 while (low high) { while (low high arr[high] pivot) high--; arr[low] arr[high]; // 右边找到小的填到左边坑 while (low high arr[low] pivot) low; arr[high] arr[low]; // 左边找到大的填到右边坑 } arr[low] pivot; // 最后把基准放回坑里 return low; } void quickSort(int arr[], int low, int high) { if (low high) { int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } }挖坑法的关键是两个内层 while 都带了low high条件。漏掉这个条件当 high 指针一直往左走直到和 low 重合时还会再执行一次比较数组可能被越界访问。另一个常见问题是和写反写成和也可以排序但相等的元素会来回交换数据全是相同数时性能退化实验报告里如果对比了时间看起来会特别奇怪。折半查找的代码短但中点的写法有讲究// 折半查找返回下标找不到返回 -1 int binarySearch(int arr[], int n, int target) { int low 0, high n - 1; while (low high) { // 注意是 不是 int mid low (high - low) / 2; // 避免 (lowhigh)/2 溢出 if (arr[mid] target) return mid; else if (arr[mid] target) low mid 1; else high mid - 1; } return -1; }mid low (high - low) / 2是王道和考研教材都强调的写法。(lowhigh)/2在 low 和 high 都接近 int 最大值时可能溢出成负数实验数据量不大倒是遇不到但这是一个能写进实验报告“算法分析”部分的加分点。循环条件用是因为当 low high 时当前元素还没比较过用会漏掉最后一次比较。5.2 实例一数组越界让快排结果神秘出错现象数组只有 6 个元素排序结果里出现一个不知道从哪来的大数有时是垃圾值有时是 0。原因partition 里两个内层 while 少写了low high条件。high 指针一路滑过 low访问了 arr[-1] 或者 arr[n]写进了不属于数组的内存。更隐蔽的是这种越界不一定会段错误而是把栈上别的变量改了所以表现是“数据错乱”而不是“程序崩溃”。解决内层 while 加上low high同时在 partition 开头加一句断言assert(low high)跑测试时能直接定位。我自己的习惯是排序函数入口统一加断言数据规模小性能损失可以忽略。5.3 实例二fscanf 读取测试文件读到一半就停现象从 data.txt 读 100 个数字程序只读进去 80 个剩下的没处理。原因文件里混了空行或者末尾多了一个换行符fscanf遇到空白字符会跳过但如果格式串是%d而文件里有非数字字符比如中文逗号、全角空格读取就失败了。另一个常见原因是判空写成了while (!feof(fp))。feof 只有在读操作尝试越过文件末尾之后才会置位所以循环体往往多执行一次最后一次读到的可能是上次残留的值。解决用while (fscanf(fp, %d, x) 1)判断读取成功的个数而不是用 feof。这个写法每次读一个整数成功就继续遇到非数字立刻停止。实验报告里“文件读取”这个点老师最喜欢问的就是“你为什么不用 feof”。5.4 实例三报告里贴了代码却没贴测试用例被扣到及格线现象代码能跑报告也写了但分数不高。验收时老师问“测试数据是什么”“覆盖了哪几种情况”答不上来。原因实验报告评分点往往包含“测试数据设计”和“运行结果分析”。有的同学只贴了输出截图没说明测试数据覆盖了哪几种边界情况。排序实验里至少要有随机乱序、完全升序、完全降序、全部相等这四组数据。解决报告里放一张四组测试的对比表每组写输入规模、数据特点、比较次数或耗时、结果是否有序。如果实验要求输出排序过程把每趟划分后的序列也贴出来这样答辩时老师问“这个序列为什么这样变”你可以指着 partition 的返回值讲比现场打印靠谱得多。血的教训是报告里的每一个输出都要能说出由哪段代码产生贴代码不问出处是扣分重灾区。6. 用 assert 和日志宏给数据结构实验上一道保险调试技巧不贪多一个日志宏加一个断言就能覆盖数据结构实验 90% 的排错场景。日志宏的核心是把“中间状态打出来”变成一件随手可做的事#include stdio.h #ifdef DEBUG #define LOG(fmt, ...) printf([%s:%d] fmt, __FILE__, __LINE__, ##__VA_ARGS__) #else #define LOG(fmt, ...) #endif__FILE__和__LINE__是编译器预定义宏能告诉你日志来自哪个文件的哪一行。调试时用gcc -DDEBUG编译日志全部输出交作业时去掉-DDEBUG日志代码一个字符都不用删。对比一下没有日志时的手段临时加 printf提交前再删掉删的时候漏掉一行编译报错或者输出留在了报告里这种翻车我经历过不止一次。assert 适合表达“这里一定成立”的假设。排序函数入口写assert(arr ! NULL)链表删除后写assert(p-next ! NULL || p head)文件读取后写assert(n 0)。这些断言在数据量小时几乎不花时间却能在你还在怀疑算法时把问题精确地引向第一处假设被打破的地方往往那就是 bug 所在。我自己的教训是从第一个实验起就在 main.c 里放一个 TEST 宏把每个函数的测试用例组织成输入、期望输出、实际输出、PASS/FAIL。后面做树和图实验时回归测试直接复用新增一个函数就补一行用例。数据结构实验的程序规模都不大但越到最后越是改一处、崩三处有断言和日志兜底你才敢在验收前最后一晚动代码。希望帮到你。本文还有配套的精品资源点击获取
