数据结构上机实验避坑指南：线性表、栈、队列与二叉树C语言实现

简介这份华南农业大学数据结构上机实验指导书面向计算机专业学生及数据结构初学者以实验驱动的方式帮助读者掌握线性表、堆栈、队列、模式匹配、二叉树等核心结构。资源包内含1个doc文档约639KB按实验目的、实验内容、实验报告三部分组织每个实验均给出基本概念、数组与链表等实现方式以及时间空间复杂度分析要求并附有参考答案便于对照自查。目录覆盖实验一至实验五从线性表的插入删除查找遍历到堆栈的压入弹出、队列的入队出队、暴力与KMP模式匹配再到二叉树相关操作知识点层层递进。目前已有293人学习下载适合需要完成课程上机任务、准备考试或希望系统梳理数据结构基础的学习者可借助其清晰的实验框架与答案参考快速定位薄弱环节并巩固实现思路。1. 从一份 .doc 实验指导书说起数据结构上机到底在练什么很多人第一次拿到《华南农业大学数据结构上机实验指导书附答案).doc》这类文档第一反应是把它当复习资料背。但真正做过上机的人都知道这份文档的价值不在“答案”而在它逼着你把线性表、堆栈、队列、二叉树这些抽象结构用 C 语言一行行敲出来、调通、跑对。它对应的不是期末背概念而是“手能写出来”的能力。这份指导书通常覆盖的顺序是线性表顺序表和链表、栈与队列、二叉树及其遍历、查找与排序。每个实验都要求你提交可编译运行的源码和实验报告。适合两类人一是正在上数据结构课、被上机卡住的学生二是想用 C 语言把基础结构重新夯实一遍的自学者。下面我不复述文档内容而是按这类指导书最常见的实验路径把每个结构的实现要点、参数设置和翻车点讲清楚让你拿到任何一份同类指导书都能照着做出来。2. 线性表顺序表和链表到底该先写哪个2.1 顺序表的插入删除为什么总在边界翻车顺序表的核心是一个数组加一个长度变量。看起来简单但上机时最常翻车的地方全在边界上。我一般会先定义结构体把数据域和长度绑在一起#include stdio.h #include stdlib.h #define MAXSIZE 100 #define OK 1 #define ERROR 0 typedef int ElemType; typedef int Status; typedef struct { ElemType data[MAXSIZE]; // 静态分配实验课常用 int length; // 当前元素个数不是下标 } SqList; // 插入在第 i 个位置前插入 ei 从 1 开始 Status ListInsert(SqList *L, int i, ElemType e) { if (i 1 || i L-length 1) return ERROR; // 位置合法性 if (L-length MAXSIZE) return ERROR; // 表满 for (int j L-length; j i; j--) { // 从后往前挪 L-data[j] L-data[j - 1]; } L-data[i - 1] e; L-length; return OK; }这段代码里有两个参数最容易设错。第一是i的范围插入允许插到length1也就是表尾之后但删除只能到length。第二是循环方向插入必须从后往前挪否则前面的元素会被覆盖。删除则相反从前往后挪。很多同学两个操作都写成同一个方向编译能过运行结果却少一个元素这就是典型的“玄学 bug”。顺序表的时间复杂度插入和删除平均要移动一半元素是 O(n)按位查找是 O(1)。所以实验报告里如果问“什么时候用顺序表”答案就是“查得多、改得少”。2.2 单链表的头结点到底要不要加链表实验里第一个分歧就是带不带头结点。我的建议是统一带头结点。头结点不存有效数据它的next指向第一个真实节点。好处是插入和删除第一个位置时不用单独判断代码能统一。typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; // 尾插法建表返回头指针 LinkList CreateListTail(int n) { LinkList head (LNode *)malloc(sizeof(LNode)); head-next NULL; LNode *tail head; // tail 始终指向最后一个节点 for (int i 0; i n; i) { LNode *p (LNode *)malloc(sizeof(LNode)); scanf(%d, p-data); p-next NULL; tail-next p; // 挂到尾部 tail p; // 更新尾指针 } return head; }参数说明n是节点个数tail是尾指针初始指向头结点。如果不设尾指针每次插入都要从头遍历到尾建表复杂度从 O(n) 退化到 O(n²)。这是链表实验里最容易被忽略的性能点。链表删除操作要特别注意释放内存和断链顺序Status ListDelete(LinkList L, int i, ElemType *e) { LNode *p L; int j 0; while (p-next j i - 1) { // 找到第 i-1 个节点 p p-next; j; } if (!p-next || j i - 1) return ERROR; LNode *q p-next; // q 是要删的节点 *e q-data; p-next q-next; // 先断链 free(q); // 再释放 return OK; }顺序不能反。如果先free(q)再访问q-next就是访问已释放内存轻则结果错重则程序崩溃。这个坑在实验报告里经常被扣分。3. 栈与队列迷宫求解和循环队列的实现细节3.1 用栈做迷宫求解路径为什么走不通“ds堆栈-迷宫求解”是数据结构实验里的经典题。思路是从入口出发按某个方向顺序试探能走就入栈走不通就出栈回退。核心是用栈保存当前路径。#define MAXSIZE 100 typedef struct { int x, y; // 当前坐标 int dir; // 下一步尝试的方向 0-3 } Box; typedef struct { Box data[MAXSIZE]; int top; } Stack; int MazePath(int maze[][10], int startX, int startY, int endX, int endY) { Stack s; s.top -1; Box cur {startX, startY, -1}; s.data[s.top] cur; maze[startX][startY] -1; // 标记已走过 int dx[] {0, 1, 0, -1}; // 右、下、左、上 int dy[] {1, 0, -1, 0}; while (s.top 0) { Box *top s.data[s.top]; if (top-x endX top-y endY) return 1; // 到达终点 int found 0; for (int d top-dir 1; d 4; d) { int nx top-x dx[d]; int ny top-y dy[d]; if (maze[nx][ny] 0) { // 0 表示可走 top-dir d; // 记录当前方向 Box next {nx, ny, -1}; s.data[s.top] next; maze[nx][ny] -1; // 入栈即标记 found 1; break; } } if (!found) { // 四个方向都不通出栈 maze[top-x][top-y] -2; // 标记死路可选 s.top--; } } return 0; }参数说明maze是二维数组0 表示通路1 表示墙dx/dy是方向增量dir记录当前节点已经试到哪个方向避免重复试探。最容易翻车的地方是标记时机必须在入栈时就标记maze[nx][ny] -1如果等出栈再标记同一个格子会被反复入栈程序陷入死循环。另一个坑是方向数组的顺序不同顺序会得到不同路径但都能走通实验报告里要说明你用的顺序。3.2 循环队列的队空队满判断为什么必须牺牲一个空间队列实验通常要求实现循环队列。如果用数组加front和rear两个指针队空是front rear队满也是front rear无法区分。常见做法是牺牲一个存储单元(rear 1) % MAXSIZE front表示队满。#define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int front; // 队头下标 int rear; // 队尾下标指向下一个空位 } SqQueue; // 入队 Status EnQueue(SqQueue *Q, ElemType e) { if ((Q-rear 1) % MAXSIZE Q-front) return ERROR; // 队满 Q-data[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return OK; } // 出队 Status DeQueue(SqQueue *Q, ElemType *e) { if (Q-front Q-rear) return ERROR; // 队空 *e Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return OK; }参数说明front指向队头元素rear指向队尾的下一个空位。队列实际最多存MAXSIZE-1个元素。如果实验要求不浪费空间可以用一个tag变量或size计数来区分空和满但代码会多一个分支。我一般先用牺牲空间法因为逻辑最清晰调试时不容易出错。链式队列则是另一套写法入队在尾部插入出队在头部删除需要同时维护front和rear指针。链式队列不会满但要注意出队后释放节点以及空队列时rear指针的处理。4. 二叉树遍历、建树和运行时错误排查4.1 二叉树的三种遍历为什么递归最好写二叉树实验的核心是遍历。先序、中序、后序的递归写法几乎一样只是访问根节点的位置不同typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 先序遍历 void PreOrder(BiTree T) { if (T NULL) return; printf(%d , T-data); // 访问根 PreOrder(T-lchild); // 左 PreOrder(T-rchild); // 右 } // 中序遍历 void InOrder(BiTree T) { if (T NULL) return; InOrder(T-lchild); printf(%d , T-data); InOrder(T-rchild); }参数说明T是当前子树根节点递归终止条件是T NULL。很多同学写遍历时忘记判空导致空指针访问程序直接崩溃。这就是“写二叉树程序时为什么总是报运行时错误”的最常见原因。如果要非递归实现就要用栈模拟递归。先序非递归根入栈出栈访问右孩子入栈左孩子入栈。中序非递归一路向左入栈直到空出栈访问再转向右孩子。后序非递归最难需要记录上一个访问的节点。4.2 由遍历序列建树先序加中序为什么能唯一确定实验里常要求根据先序和中序序列建树。原理是先序的第一个是根在中序里找到根的位置左边是左子树右边是右子树然后递归。BiTree BuildTree(int *pre, int *in, int preL, int preR, int inL, int inR) { if (preL preR) return NULL; BiTree root (BiTNode *)malloc(sizeof(BiTNode)); root-data pre[preL]; int k; for (k inL; k inR; k) { if (in[k] pre[preL]) break; // 在中序里找根 } int leftLen k - inL; // 左子树节点数 root-lchild BuildTree(pre, in, preL 1, preL leftLen, inL, k - 1); root-rchild BuildTree(pre, in, preL leftLen 1, preR, k 1, inR); return root; }参数说明preL/preR是先序序列的左右边界inL/inR是中序序列的左右边界。leftLen是左子树节点个数用来划分先序序列。这里最容易错的是边界计算左子树先序范围是preL1到preLleftLen右子树是preLleftLen1到preR。差一个下标建出来的树就完全错了。后序加中序也能唯一建树但先序加后序不行因为无法区分只有一个孩子的情况。这个结论实验报告里经常考。5. 避坑与排查上机实验里最常见的五个翻车现场5.1 段错误指针没初始化就使用现象程序编译通过运行到某一行突然崩溃提示 Segmentation fault。原因定义指针后没有分配内存就直接访问p-data或者链表操作中p-next已经是 NULL 还继续p p-next。解决每次用指针前先判空动态节点必须malloc后检查返回值。调试时可以在可疑行前加printf定位。5.2 死循环循环队列或迷宫方向判断写反现象程序一直运行不结束CPU 占用高。原因循环队列的front或rear更新时忘记取模或者迷宫求解中标记时机不对导致重复入栈。解决在循环体内加计数器超过一定次数就打印当前状态退出。检查所有% MAXSIZE是否漏写。5.3 结果错位顺序表插入方向写反现象插入一个元素后后面的元素全部变成同一个值。原因插入时从前往后挪覆盖了后面的数据。解决插入从length往i倒着挪删除从i往length正着挪。记住“插后删前”这个口诀。5.4 内存泄漏链表删除只断链不释放现象程序运行时间长了内存占用越来越高或者实验报告被扣分。原因删除节点时只改了指针没有free。解决删除操作固定三步——保存待删节点、断链、释放。顺序不能反。5.5 遍历结果不对建树时边界算错现象先序和中序建树后遍历输出少一个节点或顺序混乱。原因递归划分左右子树时下标差一。解决先用小例子手算比如三个节点的树把preL/preR/inL/inR四个值写在纸上确认左子树长度等于k - inL再写代码。6. 把实验代码变成可复用的调试习惯上机实验做完不是终点。我自己的习惯是每写完一个结构就写一个最小的测试main函数把边界情况全跑一遍空表插入、表满插入、删除第一个、删除最后一个、只有一个节点的树、完全退化成链的树。这些情况跑通了实验报告里的测试用例才有说服力。另一个技巧是给每个操作加返回值。C 语言没有异常返回OK/ERROR是最简单的错误传递方式。调用方必须检查返回值不要假设一定成功。比如malloc之后要判断是否为NULL入栈前要判断栈满出队前要判断队空。这些检查在实验课上可能觉得多余但到了实际项目里就是这些检查决定了程序是偶尔崩还是一直稳。如果你正在用这份指导书做实验我的建议是不要先看答案。先把结构定义和操作函数自己写一遍编译报错就查报错行运行不对就用printf打印中间状态。卡住了再对照答案重点看它的边界处理和你哪里不一样。这样一轮下来线性表、栈、队列、二叉树这些结构才真正长在你手上。希望帮到你。本文还有配套的精品资源点击获取