C语言数据结构实验实战指南：从顺序表到二叉树的核心实现

简介华中科技大学计算机学院数据结构课程的四份实验代码为正在学习数据结构与算法、需要C语言实现参考的学生提供可直接对照的完整示例。资源以顺序表、单链表、二叉树和邻接表四种经典数据结构和无向图操作为核心帮助读者将理论课的抽象概念落实到具体编程中。压缩包内含4个C源文件整体大小仅17KB非常轻量适合快速下载后编译调试。每个文件对应一个实验覆盖了顺序表的创建插入删除与查找、单链表的节点创建与遍历、二叉树的前中后序遍历与搜索、以及基于邻接表的深度优先或广度优先遍历等内容代码可作为平时作业和实验报告的对照参考通过阅读可加深对顺序表与链表在插入删除时效率差异、二叉树递归遍历执行流程、邻接表存储空间优势等要点的理解。目前已有574人学习下载适合计算机专业本科生用于课程实验、考研复习或自学数据结构的编程实践。1. 这套数据结构实验资源值不值得下先看它能解决什么如果你正在准备华中科技大学计算机学院的数据结构实验最头疼的往往不是算法本身而是实验要求和你手上的资料对不上。网上下载的代码包要么是纯理论讲义要么代码风格混乱、注释缺失拿到手改半天还是编译不过。这套以C语言为基础的实验资源胜在把实验要求、代码骨架、测试用例都对齐到了课程实际考核点上从顺序表、链表到二叉树和图论每份代码都带清晰的标注照着输入数据能直接跑出结果。它适合两类人一类是刚学完指针和结构体、准备做第一次实验的新手另一类是实验报告需要补强、但不想从头搭框架的熟手。先说结论这不是一本教科书而是一套可以直接落地的参考实现。2. 配置实验环境从编译器选择到C99标准2.1 选对编译器DevC的坑与替换方案很多华科同学习惯用DevC写C语言但它在处理大型结构体数组时容易出现莫名其妙的“未响应”原因是老版本内置的编译器对C99标准支持不完整。我一般建议换成VS Code MinGW或者至少把DevC的内置编译器升级到TDM-GCC。这里给出一份可直接使用的编译命令gcc -stdc99 -Wall -Wextra -g main.c sqlist.c -o lab1.exe-stdc99明确启用C99标准这样声明变量时可以写在代码块开头不必全部堆到函数入口-Wall -Wextra会提示未初始化变量和隐式类型转换实验报告里出现这两个警告会被扣分-g生成调试信息配合gdb可以定位段错误。如果你使用的是VS Code把这段命令写进.vscode/tasks.json按CtrlShiftB即可一键编译。2.2 实验代码的目录结构别把所有文件堆在一起跨三个以上实验后我见过太多人把main.c、sqlist.c、search.c全部扔在一个文件夹最后分不清哪个文件对应哪次实验。建议每次实验独立目录内部按“头文件、实现、测试、报告”分四层lab3_binary_tree/ include/ btree.h src/ btree.c test/ test_btree.c report/ lab3_report.md编译时使用相对路径gcc -stdc99 -Iinclude src/btree.c test/test_btree.c -o bin/test_btree这样做的直接好处是实验验收时老师要求现场改参数你不会在十几个源文件里迷失。注意include路径用-I指定test文件单独编译避免把测试逻辑混进正式实现。3. 核心实验实战从顺序表到二叉树的关键选型3.1 顺序表的插入删除容量管理是隐藏考点第一次实验通常要求用顺序表实现学生信息管理。多数人卡在插入时的容量检查这里给出一个带有动态扩容的插入函数#include stdio.h #include stdlib.h typedef struct { int *data; // 指向堆区分配的数组 int length; // 当前元素个数 int capacity; // 实际容量 } SqList; int insertElem(SqList *L, int index, int elem) { if (index 1 || index L-length 1) return 0; // 位置从1开始 if (L-length L-capacity) { L-capacity L-capacity 0 ? 4 : L-capacity * 2; int *newData (int *)realloc(L-data, L-capacity * sizeof(int)); if (newData NULL) return -1; // 扩容失败 L-data newData; } for (int i L-length; i index; i--) { L-data[i] L-data[i - 1]; // 从后往前移动 } L-data[index - 1] elem; L-length; return 1; }这段代码的逻辑关键在realloc的使用原空间不足时先翻倍再转移避免每次都申请新内存导致频繁复制。参数index从1计数与考试题意一致但数组下标从0开始所以L-data[index - 1]是插入位置。别小看这次realloc它可能成功返回新地址而原指针失效所以必须先用中间变量接收返回值直接写L-data (int *)realloc(...)会导致原地址丢失时无法释放。3.2 链表实验头节点和空指针判断决定生死链表实验最常见的翻车点是遍历逻辑。很多人在删除节点时漏掉“删除第一个元素”的特殊分支导致头指针被错误移动。以下这段删除操作演示了标准写法int deleteNode(Node **head, int target) { Node *prev NULL; Node *cur *head; while (cur ! NULL cur-data ! target) { prev cur; cur cur-next; } if (cur NULL) return 0; // 没找到 if (prev NULL) { *head cur-next; // 删的是头节点 } else { prev-next cur-next; } free(cur); return 1; }这里最值得关注的是函数参数用了二级指针Node **head因为删除头节点时直接修改了外部的头指针。如果你只传一级指针函数内部对头指针的改动不会反映到外部这就是很多人从main里调用完发现链表“没变”的原因。另一个细节是free(cur)前已经让prev-next或*head指向了正确的后继节点不会悬空。3.3 二叉树遍历递归写法与栈模拟选哪个实验里二叉树的中序遍历可以用递归也可以用显式栈。递归代码几乎每本教材都有但老师喜欢追问“非递归怎么写”因为这是区分“背代码”和“真懂”的试金石。非递归版本核心在于用栈模拟系统调用栈#include stdbool.h void inorderTraversal(TreeNode *root) { TreeNode *stack[100]; int top -1; TreeNode *cur root; while (cur ! NULL || top ! -1) { while (cur ! NULL) { stack[top] cur; // 一路向左入栈 cur cur-left; } cur stack[top--]; // 弹栈访问 printf(%d , cur-val); cur cur-right; // 转向右子树 } }因为每个节点最多入栈一次、出栈一次时间复杂度是 O(n)栈空间在最坏情况下等于树高。这套代码在报告里分析自不必说面试或答辩时被追问也能讲清楚“为什么访问完左子树后要弹栈出当前节点”。4. 排序算法与查找实验两种成绩分水岭的实现路径4.1 快速排序partition 边界是扣分重灾区排序实验通常会要求对比至少两种排序算法。很多同学写了快排就以为稳了结果验收时被老师用极端数据一测就暴露问题。经典快排的 partition 函数最容易写错的是边界条件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; }这里两个内部while循环必须写成arr[high] pivot而不是否则遇到重复元素会死循环。low high的条件也要同时出现在内部和外部循环中不然指针会越界。基准值选择也有讲究实验数据若是基本有序的序列取第一个元素会让快排退化成 O(n²)此时可以考虑三数取中——取low、mid、high三者的中间值作为pivot能有效避免最坏情况。4.2 哈希表的设计除留余数法与冲突处理有些实验会要求实现哈希查找。很多人只写了线性探测法但老师更看重的其实是负载因子的设计和扩容策略。一个可用的查找函数片段如下int hashSearch(int table[], int tableSize, int key) { int idx key % tableSize; int probe 0; while (table[idx] ! 0 table[idx] ! key) { probe; idx (idx probe) % tableSize; // 平方探测指数次冲突 if (probe tableSize) return -1; } if (table[idx] key) return idx; return -1; }这里采用平方探测而不是线性探测是为了避免数据聚集。参数tableSize建议取质数比如 11、13、17除数越接近素数分布越均匀。实验报告中如果写了“负载因子不能超过0.7”并且用数据证明超过后冲突率上升那这一项的分数基本稳了。5. 实验避坑记录五个让C语言实验翻车的共性错误1. 段错误Segmentation fault现象程序编译通过运行时直接崩溃。原因访问了未分配的内存最常见的是链表遍历时指针已经为空还在取cur-next。解决先用gdb跑bt查看调用栈定位到出错函数再检查所有while (cur ! NULL)循环条件是否覆盖了空指针情况。我习惯在每次malloc后立刻判断是否为NULL。2. 内存泄漏被忽视现象小数据测试一切正常但循环一万次后内存持续增长最终卡死。原因malloc出来的节点删除时只改了指针关系没有free。解决写完删除函数后在函数末尾加一行printf(node freed: %p\n, cur)调试完再删掉确认每个分支都有free。常见的做法是写完代码后跑valgrind --leak-checkfull ./program看到definitely lost为0才算干净。3. 修改了头指针却传成一重指针现象在函数里删链表节点出来后打印链表发现头节点没变。原因C语言函数参数默认传值一重指针传入函数后修改它不会影响外部变量。解决凡是可能修改链表头位置的函数参数必须写Node **head并在函数里通过*head间接操作。4. 快排死循环在重复数据上现象有重复元素的数组排序时程序卡住不退出。原因内部while循环用了严格不等号和遇到相等元素时两个指针无法互相跨越。解决将比较改为和保证相同元素也能交换推进。实测数据用{2, 2, 2, 2}跑一遍最快暴露问题。5. 全局变量在二叉树的递归里互相污染现象用全局计数器统计节点数递归两次后结果叠加。原因全局变量不受递归深层级的影响但多次调用同一函数时没有重置。解决把计数器作为指针参数传入递归函数或者每次调用前手动清零。我在代码里常写成int count 0; countNodes(root, count);传址比全局变量安全得多。6. 进阶技巧从能跑通到会答辩的验证习惯做数据结构的实验不能以“跑出预期输出”作为终点。我建议每次写完一个模块都单独写一个test.c文件里面放三组边界测试空数据、单个元素、大量随机数据。空数据能验证函数是否对NULL或者size0有保护单个元素能验证循环边界大量随机数据能暴露性能问题。比如链表删除函数用head NULL调用一次再用只有一个节点的链表调用一次这两步能挡掉七成以上的段错误。另一个答辩前的必要动作是手动推导一遍自己的代码。老师经常指着arr数组的第i个元素问“这一步之后low和high分别指向哪里”如果你在代码注释里写下每轮循环结束后的状态比如“此时low3左边都比基准值小”这个习惯比临时背答案可靠得多。我自己的经验是把每个函数的参数和返回值整理成一页表格粘贴在实验报告开头答辩时被问“这个函数到底改了什么”直接看表格就能立刻回答。从那以后我每次做实验都强制自己先写test.c再写主程序逻辑把所有边界输入先想好再动手写main函数。虽然前期多花了十几分钟但调试时间缩短了一半。希望这份资源能让你的数据结构实验少走几趟弯路省下的时间拿去把排序算法多跑几组数据比什么都值。本文还有配套的精品资源点击获取