《【教学课件】第3章查找和排序.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第3章查找和排序.ppt（23页珍藏版）》请在三一办公上搜索。
1、1,第3章 查找和排序,3.1 什么是查找 3.2 顺序表查找3.3 树表查找3.4 哈希查找,2,3.1 查找的概念,查找 在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则查找失败。查找表 一组待查数据元素的集合。查找的方法与数据的组织形式有关。平均查找长度 ASL 在查找过程中,用来评价查找算法的时间复杂度。,3,3.2 顺序表的查找,-.顺序查找 1)从第1个元素开始查找；2)用给定值与各结点的关键字值逐个比较；若找到相等的结点，则查找成功;否则，继续查找,直到第n个记录都不相等,查找失败。,4,3.2 顺序表的查找-折半查找,二.折半查找(二分查找)查找效率高前提
2、:查找表中的数据元素必须有序。算法:1)确定区间的中间位置 mid=(left+right)/2 2)用给定值与中间位置的关键字值比较；若相等，则查找成功；若给定值大,新查找区为后半区；若给定值小,新查找区为前半区。3)对缩小的区域重复上述步骤；,5,折半算法举例,有序数列3,5,11,17,21,23,28,30,32,50,按折半查找法，查找关键字值为30的元素 第1次:3,5,11,17,21,23,28,30,32,50 mid1=（1+10）/2=5 第2次：23，28，30，32，50 mid2=（6+10）/2=8 查找成功优点:比较次数少,查找速度快缺点：要求事先排序,left
3、,6,3.2 顺序表的查找-分块查找,三.分块查找 顺序查找的改进1.分块 1)n个数据元素分为m块(mn)2)块内可以无序 3)块间必须有序 4)选各块中的最大关键字构成一个索引表,7,分块查找算法描述,2.查找1)对索引表用二分或顺序查找，确定待查记录在哪一块中；2)在已确定的块中用顺序法进行查找。3.优点：块中插入、删除方便 缺点：索引表增加了存储空间。,8,分块查找举例,数列 22,12,13,9,8,33,42,44,38,24,48,60,58,75,471)按“块有序”分三块:见下图 2)每块中最大关键字组成索引表22,44,74,3)查找关键字值为60的元素。用二分法，60在4
4、474之间，取第3块;在第3块中用顺序法查找,44,22,74,22,12,13,9,8,33,42,44,38,24,48,60,58,74,47,List1,List2,List3,9,3.3 二叉排序树查找,将数据元素组织成二叉树形式，达到与二分法相同的查找效率，又具有链表的插入、删除操作的灵活性。,10,二叉排序树查找算法,1)建立二叉排序树。2)将待查关键字值与根结点进行比较，若相等，查找成功；3)否则根据比较结果确定查找路径：若小于根结点的关键字值，则与左子树的根结点的关键字值进行比较；若大于根结点的关键字值，则与右子树的根结点的关键字值进行比较。4)重复上述步骤，直到要么找到，查
5、找成功；要么找不到，查找失败。,11,举例:对数列10，18，3，4，9，13，25，生成二叉排序树如下:,1)查找关键字值为25:25与根结点值10比较，走右路，再与18比较，走右路，最后与25比较，查找成功,比较3次。2)若查找35 与10、18、25分别比较后仍没找到相等元素，查找失败，比较了三次。,10,3,9,4,18,13,25,12,3.4 哈希查找,一.概念哈希函数 将元素的关键字K作自变量，通过一定的函数关系(哈希函数),计算出该元素的存储地址:Addr=H（K）哈希表 由哈希函数的值组成的表。建立哈希函数的原则:使地址值均匀分布在哈希表中哈希查找:通过运算确定存储位置,实现
6、快速检索对比其它查找方法:通过比较确定元素位置,13,二.建立哈希表,构造哈希函数常用的方法数字分析法平方取中法折叠法除留余数法（求模取余法）直接定址法,14,三.冲突及冲突处理,1.冲突:在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象,即 K1K2，但 H（K1）=H（K2）2.均匀的哈希函数可以减少冲突，不能避免冲突。3.处理冲突开放地址法链地址法再哈希法公共溢出区法,15,处理冲突 开放地址法,发生冲突后，求解下一个地址 Hi=(H(key)+di)MOD m i=1,2,k(k m-1)m:哈希表长度,di:增量序列增量序列的不同取法，构成不同的开放地址法。1)线
7、性探测再散列 di=1,2,m-1 2)二次探测再散列 di=12,-12,22,-22,+k2,-k2(k m/2),16,处理冲突 链地址法,发生冲突后,将所有函数值相同的记录连成单链表：H(41)=H(1)=1 H(67)=3 H(530=H(13)=5 H(22)=H(46)=H(30)=6,1234567,41,1 NULL,46,13 NULL,30 NULL,22,NULL,53,NULL,NULL,NULL,67,17,四.建立哈希表举例,数列22,41,53,46,30,13,1,67,表长9哈希函数:H(key)=key MOD 8,用线性探测解决冲突 Hi=(H(key)
8、+di)MOD m1)计算H(22）=6，该地址空，可用；2)计算H(41）=1，该地址空，可用；,0 1 2 3 4 5 6 7 8,22,22,0 1 2 3 4 5 6 7 8,41,比较次数：1 1,18,举例（续一）,3)H(53）=5，该地址空，可用；4)H(46）=6，该地址冲突 下一个可用地址 Hi=(6+1）MOD 8=7，该地址空，可用；,22,41,0 1 2 3 4 5 6 7 8,53,22,41,53,46,0 1 2 3 4 5 6 7 8,比较次数：1 1 1,比较次数：1 1 1 2,19,举例（续二）,5)H(30）=6，冲突 下一个地址Hi=(6+1)MO
9、D 8=7，冲突 再下一个可用地址；Hi=0，可用；6)H(13）=5，依法解决冲突，得出：,22,41,0 1 2 3 4 5 6 7 8,53,22,41,53,46,0 1 2 3 4 5 6 7 8,比较次数：3 1 1 1 2,比较次数：3 1 6 1 1 2,46,30,30,13,20,举例（续三）,7)H(1）=1，该地址冲突，解决冲突可得；8)H(67）=3，冲突，解决冲突，得出：,22,41,0 1 2 3 4 5 6 7 8,53,22,41,53,46,46,30,30,13,比较次数：3 1 6 3 1 1 2,1,13,1,67,比较次数：3 1 6 3 2 1 1
10、 2,0 1 2 3 4 5 6 7 8,21,五.哈希查找,设哈希表为HSTM，解决冲突的方法为R（x）哈希查找步骤(对给定k值)：1.计算哈希地址 Di=H（k）；若HSTi为空，则查找失败；若HSTi=k，则查找成功；否则，执行下一步处理冲突。2 重复计算下一个存储地址 Dk=R(Dk-1)，直到HSTDk为空，或HSTDk=k为止。,22,查找举例,设有数列22,41,53,46,30,13,1,67,哈希函数为H(key)=key MOD 8,用线性探测法解决冲突,建立的哈希的表为:平均查找长度ASL=(3+1+6+3+2+1+1+2)/8=19/8 查找key=67 比较两次找到,查找成功;查找key=21 比较8次找不到,查找失败,0 1 2 3 4 5 6 7 8,比较次数：3 1 6 3 2 1 1 2,22,41,53,46,30,13,1,67,23,作业、思考题,1、第3章思考:第2、3、57、11题作业：第13题,
