《数据结构》实验指导书

1、实验指导书实验一 单链表的基本操作和简单程序一、实验目的 （1）深入理解线性表的基本概念和授课内容。 （2）深入理解单链表的基本概念和简单程序设计方法。 （3）提高实际动手进行程序设计的能力。二、实验设备高性能微机一台，安装VC+软件。三、实验内容 （1）阅读教材上单链表的程序，并自己键入这些程序。 （2）仿照例2-3和例2-4程序，编写一个使用单链表的应用程序，首先建立数值分别为1,2,3,10的单链表，然后删除数值4，最后输出该单链表。 （3）分析应用程序的运行情况。四、实验要求（1）理解头文件的用法，把单链表以头文件形式保存。 （2）单链表可设计成循环单链表。 （3）分析程序，理解模块化

2、程序设计方法。 （4）提交实验报告。实验二 折半查找算法设计一、实验目的 （1）深入理解递归的基本概念。 （2）深入理解递归程序的分析方法和程序设计方法。 （3）提高实际动手进行程序设计的能力。二、实验设备 高性能微机一台，安装VC+软件。三、实验内容 （1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。 （2）编写程序实现：在保存于数组的10000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中 （3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实

3、现。 （4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。四、实验要求 （1）10000个数据可以初始赋值时实现，也可以调用系统的随机函数，再设计一个排序函数实现。 （2）两种方法时间效率的分析对比可以有两种方法，一种是理论分析方法，一种是实际记录运行时间。 （3）提交实验报告。实验三 二叉树设计一、实验目的 （1）深入理解二叉树的基本概念和程序设计方法。 （2）深入理解二叉树的建立方法和遍历方法。 （3）提高实际动手进行程序设计的能力。二、实验设备 高性能微机一台，安装VC+软件。三、实验内容 （1）定义二叉链存储结构。 （2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、

4、左结点插入、右结点插入、中序遍历二叉树等）。 （3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。 （4）编写测试主函数并上机运行。打印出运行结果，并结合程序运行结果进行分析。四、实验要求 （1）为统一起见，可建立如图7-20的二叉树。 （2）遍历二叉树方法应包括前序、中序、后序和层序方法。 （3）遍历二叉树方法还可以包括一个求二叉树叶结点个数的函数。 （4）提交实验报告。实验四 图的设计一、实验目的 （1）深入理解图的基本概念和程序设计方法。 （2）深入理解图的建立方法和深度优先遍历、图的广度优先遍历方法。 （3）提高实际动手进行程序设计的能力。二、实验设备 高性能微机

5、一台，安装VC+软件。三、实验内容 （1）定义邻接矩阵存储结构或邻接表存储结构。 （2）按照建立一个带权有向图的操作需要，编写在邻接矩阵或邻接表存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个邻接结点、图的深度优先遍历、图的广度优先遍历等）。 （3）设计一个测试主函数，首先创建一个图（有n个结点和e条边），然后打印图的n个结点信息和e条边信息，最后分别打印出图的深度优先遍历和广度优先遍历的结点信息序列。四、实验要求 （1）为统一起见，可建立如图8-8的二叉树。 （2）图的广度优先遍历中使用的队列由教师提供头文件。 （3）提交实验报告。实验五 顺序队列下的基数排序算法设计一、实验目的 （1）深入理解排序的基本概念和程序设计方法。 （2）深入理解基数排序方法。 （3）深入理解顺序队列下的基数排序程序设计方法。 （4）提高实际动手进行程序设计的能力。二、实验设备 高性能微机一台，安装VC+软件。三、实验内容 （1）编写基于顺序队列的基数排序函数。 （2）设计一个测试主函数，实现对基于顺序队列结构的基数排序算法的测试。（3）分析程序的运行结果。 （4）讨论并分析比较链式队列结构的基数排序算法和顺序队列结构的基数排序算法的优缺点。四、实验要求 （1）为统