对各种查找算法进行计较

《对各种查找算法进行计较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、对各种查找算法进行计较一、实验目的：1、了解和掌握各种查找算法。2、学会计算各种查找算法的平均时间复杂度。3、了解各种算法的优势。二、实验内容：对各种查找算法进行比较三、实验要求：（1）任意输入1组有序数据；（2）对顺序查找、折半查找、分块查找的查找次数进行比较并输出比较结果。四、算法分析:顺序查找：由顺序表的后面往前遍历，一个一个元素与待查找的数比较，找到待查找的数的位置；折半查找：每一次都用表的中间元素与待查找的数进行比较，根据结果所要查找表的范围缩小一半，反复执行以上的操作，找到待查数为止；分块查找：把表分为n块，用一个顺序表记录每一块的最大值和起始位

2、置，待查找的元素先与顺序表比较，判断它所在的块，在快中利用折半查找找到其位置。顺序查找的平均查找长度为：ASL=(n+1)/2；折半查找的平均查找长度为：ASL=log2(n+1)-1；分块查找的平均查找长度为：ASL=(n/m+1)/2+log2(m+1)-1.五、程序代码：//#include"stdafx.h"#include"iostream"usingnamespacestd;typedefintKey;typedefstruct{Keykey;}Rec;typedefstruct{Keykey;inta;}R;intsrch(Recr[],int

3、n,Keyk){inti=n,j=0;r[0].key=k;while(r[i].key!=k){i--;j++;}cout<<"顺序查找比较次数为:"<

4、<"折半查找比较次数为:"<

5、找比较次数为:"<

6、ig=mid-1;elselow=mid+1;}cout<<"分块查找比较次数为:"<>n;int*we=newint[n+1];we[0]=0

7、;Rec*r=newRec[n+1];cout<<"输入有序顺序表的值:"<>we[i];r[i].key=we[i];}cout<<"输入分块查找块数："<>m;cout<<"输入查找的数:"<>d;R*a=newR[n/m+1];set(r,a,n,m);srch(r,n,d);bisrch(r,n,d);search(r,a,n,m,d);return0;}六、运行结果：