简介：华南农业大学《数据结构》上机实验指导书（附答案）是面向高校计算机专业学生的实验教学文档，适合正在学习数据结构课程、准备上机考核或复习备考的读者使用。文档覆盖线性表、堆栈、队列、模式匹配、二叉树等核心知识点，每个实验按“实验目的—实验内容—实验报告”结构展开，既给出题目要求，也提供可核对的参考答案。资源包内共1个doc文件，大小约639KB，内容紧凑集中，可直接打开阅读或打印。目前已有293人学习下载，是广受同类课程学习者认可的实用资料。通过完成这些实验，读者可掌握线性表、栈、队列的数组与链表实现方式，理解模式匹配中暴力算法与KMP算法的区别，并进一步熟悉二叉树的遍历与基本操作，从而为后续算法设计与数据结构进阶奠定扎实基础。
1. 数据结构实验指导书：这份八件套文件到底能帮你拿到什么
这份华南农业大学的数据结构上机实验指导书（附答案），不是普通课件，而是一份从实验一到实验八全部覆盖、附带完整可运行代码和模拟试卷的“数据结构上机全流程包”。很多人以为它是给学生交作业用的模板，实际上它最大的价值在于：每道题都给出了可运行的 C 代码、测试样例和输出格式，相当于把教材里“算法 2.3、2.4、2.5”的抽象描述直接变成了能跑通的东西。如果你正在准备数据结构实验报告、考研复试上机，或者想把手写伪代码变成真正的 C 语言程序，这份文档能省下大量查错时间。下面我从一个实际拆过这份文档、照着跑过代码的角度，把它怎么用、坑在哪、哪些地方需要自己补全说清楚。
2. 线性表顺序存储：把“补全代码”变成真正能跑的初始化、插入、删除
2.1 顺序表结构定义和 InitList_Sq：malloc 不是交了就行
文档里的存储结构定义是经典的《数据结构（C 语言版）》风格，SqList里三个字段：elem是存储空间基址，length是当前长度，listsize是当前分配容量。题目 1 的框架代码里留了三个空让你补：InitList_Sq、Load_Sq、ListInsert_Sq和ListDelete_Sq。文档后面给了完整代码，但如果你直接抄，可能会漏掉一个关键细节——InitList_Sq里 malloc 完之后没有判断返回值。
int InitList_Sq(SqList &L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem){ printf("Memory allocation failed!\n"); return ERROR; } L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }这段代码的逻辑是：先按LIST_INIT_SIZE（100）个ElemType大小分配内存，L.length置 0，L.listsize记录当前容量。参数&L是 C++ 引用语法，在纯 C 环境下要改成指针SqList *L并做一次解引用。补全时最容易漏的是 malloc 之后没判空，后面ListInsert_Sq扩容时如果 realloc 失败，L.elem会变成野指针，程序直接段错误。我一般会在这里加一层保护，宁可多写两行也不让空指针裸奔。
2.2 ListInsert_Sq 和 ListDelete_Sq：位置合法性判断和移位方向
插入操作是顺序表里最需要小心的函数，文档特意把“i 的合法值为 1≤i≤L.length+1”写在注释里。完整代码里有两个容易写反的地方：一是容量不足时用 realloc 扩容LISTINCREMENT（10）个元素，二是从表尾往表头方向循环移位。
int ListInsert_Sq(SqList &L,int i,int e){ if(i<1||i>L.length+1) return ERROR; ElemType *newbase,*q,*p; if(L.length>=L.listsize){ newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) return ERROR; L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); // q 指向插入位置 for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; // 从最后一个元素开始后移 *q=e; ++L.length; return OK; }注意这里循环是从L.length-1开始往前移到q的位置，p>=q这个条件保证了插入位置及其后面的元素都后移一位。如果写成从q开始往后移，会把后面的元素覆盖掉，这是顺序表插入最常见的翻车点。删除操作则相反，从删除位置的后一个元素开始往前覆盖，循环条件for(++p;p<=q;p++) *(p-1)=*p;，p初始指向删除位置i-1，q指向最后一个元素。补全代码时先判断i<1||i>L.length再操作，否则越界访问会读到未初始化内存。
2.3 题目 2 的 MergeList 和题目 3 的逆置：不提供代码时怎么独立完成
题目 2 要求把两个非递减有序顺序表 A、B 合并成非递减的 C，文档只给了测试样例不给代码。完整代码在算法思路上用的是双指针归并：i和j分别指向 A、B 当前元素，k记录 C 的长度。GetElem(La,i,ai)取出 A 的第 i 个元素，GetElem(Lb,j,bj)取出 B 的第 j 个元素，谁小谁先进 C，然后移动对应指针。
while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai<=bj){ ListInsert_Sq(Lc,++k,ai); i++; }else{ ListInsert_Sq(Lc,++k,bj); j++; } } while(i<=La_len){ GetElem(La,i++,ai); ListInsert_Sq(Lc,++k,ai); } while(j<=Lb_len){ GetElem(Lb,j++,bj); ListInsert_Sq(Lc,++k,bj); }归并结束后两个while循环负责把剩余元素追加进去。这里有个细节：++k先自增再作为插入位置，因为 C 表从第 1 个位置开始插入，每插一个 k 加 1。题目 3 的逆置要求“仍占用原顺序表的空间”，意思是不能申请新表，而是原地交换：for(i=0;i<L.length/2;i++)交换L.elem[i]和L.elem[L.length-1-i]。我建议逆置函数独立写，不要嵌到 main 里，这样题目 2 的合并和题目 3 的逆置可以复用Load_Sq输出。
3. 链式存储、堆栈与队列：链表定义和栈队列实现的对照理解
3.1 单链表 LNode 定义：头结点到底要不要？next 初始化是生死线
第二章进入链式存储，文档给出的定义是经典的单链表结点：
typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList;新建链表时最常犯的错是只 malloc 头结点却忘了把next置成 NULL，导致后续遍历判断p!=NULL时访问到野指针。我习惯建表时统一走一个InitList_L函数，头结点next显式置空，后面插入删除都以“带回一个头结点的链表”为前提。文档的题目里要求补全插入、删除、遍历，和顺序表的结构几乎一一对应，区别只在于链表的插入不需要移动元素，而是修改指针。头插法和尾插法的差异也要注意：头插法每次都在头结点后面插入，插入顺序和输入顺序相反；尾插法需要维护一个尾指针r，每插一个更新一次。
3.2 堆栈和队列的结构差异：后进先出和先进先出不是换个名字
文档实验二、实验三分别要求实现堆栈和队列。堆栈的数组实现需要top指针，入栈push先判满再top++后赋值，出栈pop先判空再取元素后top--。队列的数组实现则要两个指针front和rear，入队rear++，出队front++，循环队列还要(rear+1)%MAXSIZE判满。很多同学做完实验二直接照抄堆栈逻辑写队列，结果队尾队首分不清。这里有一个判断技巧：堆栈只需要一个top就能控制两端，队列必须两个指针；堆栈判满条件是top==MAXSIZE-1，循环队列判满条件是(rear+1)%MAXSIZE==front。文档提到“同学们可扩展考虑循环链表与双链表”，实际上队列用循环数组表示时，取余运算里那个“牺牲一个存储单元”的设计，就是最容易写错的细节。
4. 模式匹配：暴力算法和 KMP 的 next 数组到底怎么推
4.1 暴力匹配：两层循环里的两个指针各自什么时候回退
实验四的模式匹配，文档明确要求同时实现暴力算法和 KMP 算法。暴力匹配的思路是：主串 S 从第 i 个位置起与模式串 T 逐个字符比较，失败则 i 回退到 i-j+1，j 回退到 0。下面这段是完整的暴力匹配实现：
int Index_BF(char S[], char T[], int pos){ int i=pos-1, j=0; while(S[i]!='\0' && T[j]!='\0'){ if(S[i]==T[j]){ i++; j++; }else{ i=i-j+1; // 主串回退到本轮起始的下一个位置 j=0; // 模式串从头开始 } } if(T[j]=='\0') return i-j; // 匹配成功，返回起始下标 else return -1; }如果匹配失败，i=i-j+1的意思是：本轮从 i 开始匹配了 j 个字符后失败，主串回到本轮最开始的位置加 1。这个式子网上一搜一堆，但真正写的时候很多人把i-j+1算成i-j或i-j+2，导致漏匹配。暴力算法的时间复杂度是 O(n*m)，主串长 n、模式串长 m，最坏情况下每个位置都要比到模式串最后一个字符才失败。
4.2 KMP 的 next 数组：理解“最长相等前后缀”比背代码更省事
KMP 的核心是 next 数组，文档里只给了题目要求，没给推导步骤。next[j] 的含义是：当模式串第 j 个字符失配时，j 应该回退到的位置。对于模式串 "abaabc"，手动推一遍：
j: 0 1 2 3 4 5 T[j]: a b a a b c next: -1 0 0 1 1 2next[0]=-1 是特殊约定的哨兵。next[1]=0，因为前缀 "a" 没有相等前后缀。next[2]=0，因为 "ab" 的前缀 a 和后缀 b 不相等。next[3]=1，因为 "aba" 的最长相等前后缀是 "a"，长度为 1。next[4]=1，因为 "abaa" 的最长相等前后缀仍是 "a"。next[5]=2，因为 "abaab" 的最长相等前后缀是 "ab"。求 next 的代码里最关键的是k=next[k]这一行：
void get_next(char T[], int next[]){ int i=0, k=-1; next[0]=-1; while(T[i]!='\0'){ if(k==-1 || T[i]==T[k]){ i++; k++; next[i]=k; }else{ k=next[k]; } } }k=next[k]是在当前字符不相等时，把 k 回退到更短的相等前缀位置继续尝试。这一行是 KMP 里最像玄学的地方，很多人抄代码时漏了它，结果 next 数组全是错的。我建议在纸上先把模式串的每个子串的前后缀列出来，再对照代码理解，比空看代码高效得多。KMP 的时间复杂度是 O(n+m)，因为主串指针 i 从不回退，只回退模式串的 j。
5. 数据结构实验避坑清单：五个最容易翻车的代码细节
5.1 realloc 失败导致原指针丢失
现象：程序跑着跑着插入元素时突然崩溃，或者Load_Sq输出乱码。原因：realloc失败时返回 NULL，如果直接写L.elem=newbase，原指针就被覆盖了，后续free会崩溃。解决：先用临时变量接收 realloc 返回值，判空后再赋给L.elem。文档题目 1 的完整代码里没有判空，自己补全时建议加上。
5.2 插入和删除的移位方向写反
现象：插入后部分元素丢失，或者删除后最后一个元素重复出现。原因：插入应该从表尾往前移，删除应该从删除位置往后往前覆盖。写反了就把还没移位的元素覆盖掉了。解决：插入用for(p=&(L.elem[L.length-1]);p>=q;--p)，删除用for(++p;p<=q;p++)，先把循环边界条件和指针初始值写在注释里再编码。
5.3 scanf 读入位置不合法时，输出未初始化的 e
现象：删除操作输入的位置超出范围时，程序输出“The Element 被删除”但数字是一串随机值。原因：case 2里先scanf("%d",&i)，如果ListDelete_Sq返回 ERROR，e根本没有被赋值，但 printf 仍然打印了它。解决：先判断函数返回值，成功才打印 e 的值。这是文档测试样例格式说明里没写清楚的边界情况。
5.4 合并测试样例中 B 表的输入循环复制粘贴忘了改上限
现象：题目 2 输入 B 表数据时，只读了一半就跳到输出。原因：文档完整代码里有一处经典错误，B 表输入循环写的是for(i=1;i<=an;i++)，复制 A 表的循环忘改bn。如果 A 表 5 个元素、B 表 4 个元素，B 表只读 4 个就到上面了。解决：凡是复制粘贴循环，先看变量名和循环上限是否对应。这一步也能帮你判断是否真的理解了线性表结构。
5.5 单链表头结点 next 没有初始化为 NULL
现象：遍历链表时死循环或者段错误。原因：malloc 出来的头结点内存是随机的，next没有置空，遍历时p=p->next走到随机地址。解决：建表后立刻L->next=NULL;。这道题在文档里没有现成代码，却是链表所有操作的前提。
6. 二叉树、查找与排序：用附录试卷做一轮复习闭环
二叉树的实验五、查找的实验六、内部排序的实验七，正好是数据结构考试的三座大山。文档 133 页之后有“数据结构课程设计安排”“图算法实验题目”和“团队题目（各种排序算法效率分析）”，再往后是两套模拟试卷。我的建议是：别把模拟试卷留到考前一周才看，而是每做完一次实验就做一遍对应部分的题。比如做完二叉树，就只看试卷里二叉树相关的选择题和算法题，做完排序，再对照“团队题目：各种排序算法效率分析”自己写一遍比较函数。
排序实验的核心是“理解稳定性分别是什么决定的”——冒泡排序相等元素不交换所以稳定，简单选择排序每次选最小的放到前面，相等元素可能被交换所以不稳定；快排的 partition 从两端交替扫描，时间复杂度平均 O(n log n) 最坏 O(n²)；归并排序稳定但需要 O(n) 辅助空间。文档要求对这些排序做效率分析，我一般会写一个统一的测试框架：随机生成 10000 个整数，分别跑冒泡、选择、插入、快排、归并，记录比较次数和移动次数，这个实验做完对“什么场景选什么排序”的理解会非常深。二叉树部分，递归先序、中序、后序遍历代码只有几行，但“非递归中序遍历用栈模拟”才是上机常考的点。查找实验里，折半查找的前提是有序表，二叉排序树的插入和删除则是考研必考的大题。
附录 1 的“实验报告与习题”是这份文档被很多人低估的地方。每份实验报告模板里都有“实验结果与分析”栏，把测试样例的输出贴进去，再写两行“本次实验遇到的问题及解决方法”，整份实验报告的质量立刻上一个台阶。附录 2 的“数据结构课程设计完成情况登记表”可以用来做课程设计的进度规划，附录 3 的“图的应用”补上了图实验的缺口——Dijkstra 和 Floyd 算法在那两套模拟试卷里都有对应的填空题。
从那以后我每次拿到这种实验指导书，都会先通读一遍附录里的试卷和报告模板，再回头做实验题——这样能清楚知道哪些知识点是老师真正要考的。做实验五二叉树时，我会先写递归遍历验证逻辑，再写非递归版本对照输出；做实验七排序时，我会把所有排序算法写进同一个文件里，用宏定义开关切换，这样调一个 bug 不用重新编译整个程序。这份指导书的完整代码里有几处隐藏错误（比如 B 表输入循环的上限），你按“发现问题 - 定位原因 - 修正测试”的顺序走一遍，收获比直接抄答案大得多。希望帮到你。
本文还有配套的精品资源，点击获取
