《数据结构与算法》实验指导书
实验6 图
一、实验目的
（1）熟练掌握图的基本概念、构造及其存储结构。
（2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。
二、实验要求
（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；
（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。
三、实验设备、环境
奔腾以上计算机，装有Turbo C 2.0或Visual C++软件
四、实验步骤及内容
实验步骤：
1．根据题目，编写程序。 2．上机调试通过。
3．按照实验报告格式，撰写各实验报告。 实验内容：
1．构造一个无向图，要求用邻接矩阵表示存储结构。
2．对上面构造的无向图，进行深度优先遍历和广度优先遍历，分别输出遍历序列。 3．构造一个连通网络，分别用PRIM算法和KRUSKAL算法构造该网络的最小生成树。
五、讨论、思考题
1、图是如何存储的？
2、如何从一个无向图的邻接矩阵（或邻接表）中，判断图中有多少条边？任意两个顶点i和j是否有边相连？任意一个顶点的度是多少？ 3、图有哪些遍历算法，这些算法之间有何区别？
158
《数据结构与算法》实验指导书
实验7 排序
一、实验目的
（1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。 （3）区分以上不同排序的优、缺点。
二、实验要求
（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；
（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。
三、实验设备、环境
奔腾以上计算机，装有Turbo C 2.0或Visual C++软件
四、实验步骤及内容
实验步骤：
1．根据题目，编写程序。 2．上机调试通过。
3．按照实验报告格式，撰写各实验报告。 实验内容：
用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。
五、讨论、思考题
1、排序方法有哪些？各有哪些特点？
2、什么是排序方法的稳定性？哪些排序方法是稳定的，哪些又是不稳定的？
159
《数据结构与算法》实验指导书
实验8 查找
一、实验目的
（1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。 （2）掌握哈希表设计。
二、实验要求
（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；
（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。
三、实验设备、环境
奔腾以上计算机，装有Turbo C 2.0或Visual C++软件
四、实验步骤及内容
实验步骤：
1．根据题目，编写程序。 2．上机调试通过。
3．按照实验报告格式，撰写各实验报告。 实验内容：
（1）在一个递增有序的线性表中利用二分查找法查找数据元素X。
（2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。
五、讨论、思考题
1、二分查找的前提是什么？ 2、如何合理设计哈希函数？
160