实验三 查找 一、目的和要求

1. 掌握的静态查找表、动态查找表、Hash查找表的定义和存储结构的实现。

2. 分析各种查找表的查找性能，讨论它们的适用情况。

3. 根据实际问题的需要，选择相应的查找表解决实际问题。

二、实验环境

1. Windows操作系统；

2. DEV C++、Visual Studio语言环境等；

三、实验内容

（每个题目一个文件夹，包括源程序、编译好的可执行程序和所需测试数据；所有题目文件夹打包成一个压缩文件，文件名格式：学号姓名实验三.zip。抄袭0分。）

1．有序表查找的验证

编写一个程序对有序表的三种查找算法（顺序查找、折半查找和斐波那契查找）进行比较，在等概率查找的前提下，输出三个算法在同组数据集中的查找所有元素的查找次数总和及查找时间总和。

要求：数据集规模分别为4、4E1、4E2、4E3、4E4、4E5、4E6、4E7，其中E为以10为底的指数，可由程序自动生成整型数据有序表。

2．二叉排序树的验证

根据教材介绍的另外3种删除结点算法，实现二叉排序树的删除算法；并用相同的测试数据对1、2种算法和3、4种算法进行分析比较。

3．Hash表的实现验证

修改给出的Hash表查找，用二次探测处理冲突，进行测试验证；并用相同的测试数据对线性探测和二次探测两种方法进行分析比较。