各种查找算法性能分析.docx

细心整理
项 目 名 称：各种查找算法的性能测试
工程成员：
组编号：
完成时间：
书目
前言.......................................................................................................................13
前言
查找问题就是在给定的集合〔或者是多重集，它允许多个元素具有一样的值〕中找寻一个给定的值，我们称之为查找键。
对于查找问题来说，没有一种算法在任何状况下是都是最优的。有些算法速度比其他算法快，但是须要较多的存储空间；有些算法速度特殊快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题〔动态查找表〕。
在数据构造课程中，我们已经学过了几种查找算法，比拟有代表性的有依次查找〔蛮力查找〕，二分查找 〔接受分治技术〕，哈希查找〔理论上来讲是最好的查找方法〕。
细心整理
第一章：简介〔Introduction〕
：
依次查找从表中最终一个记录起先，逐个进展记录的关键字和给定值的比拟，假设某个记录的关键字和给定值比拟相等，那么查找成功，找到所查记录；反之，假设直至第一个记录，其关键字和给定值比拟都不等，那么说明表中没有所查记录，查找不成功。
：
〔1〕分析驾驭折半查找算法思想，在此根底上，设计出递归算法和循 环构造两种实现方法的折半查找函数。
〔2〕编写程序实现：在保存于数组a[i]有序数据元素中查找数据元素k是否存在。数元素k要包含两种状况：一种是数据元素k包含在数组中；另一种是数据元素k不包含在数组中
〔3〕数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。
〔4〕依据两种方法的实际运行时间，进展两种方法时间效率的分析比照。
其次章：算法定义〔Algorithm Specification〕

从表的一端向另一端逐个进展记录的关键字和给定值〔要查找的元素〕的比拟，假设某个记录的关键字和给定值比拟相等，那么查找成功，找到所查找记录；反之，假设直至第一个记录，其关键字和给定值比拟都不等，那么说明表中没有所查记录，查找不成功。
依次查找的算法如下：
int SeqSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合，n是数组中元素的个数〔即查找表的长度〕，k是要查找的元素
{
i=n;//从后往前把表中的元素及要查找的元素进展比拟
细心整理
while (i>0 && r[i]!=k)//当i>0并且数组元素中的值不等于要查找元素时，i减一接着执行while循环
{ i--;}
return i;//i的值为0那么没找到，为非0那么i为要查找元素的位置
}

二分查找又称折半查找，二分查找首先要求待查找的表是有序表，假如要查找的元素是表的中间的那个元素，那么找到要查找的元素，查找成功；假如要查找的元素比中间的那个元素小那么运用一样的策略只在左边的区间查找就可以；假如要查找的元素比中间的那个元素大，那么运用一样的策略在右边的区间进展查找；每次将待查找的元素的所在区间缩小一半。
〔1〕二分查找算法的递归算法
int binary_search_2(int a[],int n,int k)//递归的二分查找算法的伪代码：查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素
{
int Low,Mid,High;
Low=0,High=n-1;//选择查找的最大的范围
Mid=(Low+High)/2;
//quicksort(a,0,SIZE-1);
if (Low>=High) return -1;//数字-1表示没有结果
if (a[Mid]==k) return Mid; //找到要查找的元素
else if (a[Mid]>k)
return (binary_search_2(a,Mid-1,k));//须要在左边的更小的范围内查找
else return (binary_search_2(a+Mid+1,High-Mid,k));//在右边的更大的范围内查找
}
细心整理
〔2〕二分查找的非递归算法
int binary_search_1(int a[],int n,int k) //非递归的二分查找算法的伪代码：查找表放在数组a中，n是查找表中元素的个数，k是