《数据结构》实验指导书
计算机专业实验中心 编
2017年10月24日
目 录
《数据结构》上机实验内容和要求 .................................................................................................. 3 实验一、顺序表的实现及应用 .......................................................................................................... 5 实验二、链表的实现及应用 .............................................................................................................. 8 实验三、栈的实现及应用 ................................................................................................................ 13 实验四、队列的实现及应用 ............................................................................................................ 14 实验五、二叉树操作及应用 ............................................................................................................ 15 实验六、图的遍历操作及应用 ........................................................................................................ 20 实验七、查找算法的实现 ................................................................................................................ 27 实验八、排序算法的实现 ................................................................................................................ 29
2
《数据结构》上机实验内容和要求
通过上机实验加深对课程内容的理解，增加感性认识，提高程序设计、开发及调试能力。 本实验指导书适用于16学时《数据结构》实验课，实验项目具体内容如下：
序号 1 内 容 每组 实验 提 要 人数 时数 掌握顺序表结构，实现其插入、删除等算法。利用顺序表的实现及应用 1 2 顺序表将两个有序线性表合并为一个有序表。 掌握单链表结构，实现其插入、删除、查找等算法。链表的实现及应用 1 2 利用单链表将两个有序链表合并为一个有序链表。 掌握栈的结构，将栈应用栈的实现及应用 1 2 于表达式计算问题 掌握队列的结构，将队列队列的实现及应用 应用于模拟服务台前的排1 2 队现象问题 掌握二叉树的存储，实现三种遍历的递归算法、实二叉树操作及应用 1 2 现前序或中序的非递归遍历算法 实现图的存储、深度遍历图的遍历操作及应用 1 2 和广度遍历算法 实现顺序表的二分查找算查找算法的实现 1 2 法 实现直接插入排序、快速排序算法的实现 1 2 排序等算法 实 验 名 称 实验 实验 分值（总要求 类别 100分） 必做 设计 10分 2 必做 设计 10分 3 4 必做 设计 15分 必做 设计 15分 5 必做 设计 15分 6 7 8 必做 设计 10分 必做 设计 10分 必做 设计 15分
实验报告要求
请按照实验教师要求，按时提交实验报告电子版文件。 实验报告格式可个性化定义，内容包括但不限于以下内容： 1、题目、姓名、学号、班级（首页）
2、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定： （1）输入的形式和输出值的范围； （2）输出的形式； （3）程序所能达到的功能；
（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。
3、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。 4、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
3