《《数据结构》--第七章 查找》由会员分享，可在线阅读，更多相关《《数据结构》--第七章 查找（60页珍藏版）》请在金锄头文库上搜索。
1、第7章 查 找,第7章 查 找,学习目的要求:,顺序表、有序表、索引顺序表的定义、查找及算法。 散列表的定义及构造法。 散列表冲突的处理方法。,7.1 基本概念,7.2 顺序查找,7.5 散列表及其查找,7.4 分块查找,7.3 二分法查找,第7章 查 找,7.1 基本概念,查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。,关键字（Key）是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。 若此关键字可以惟一地标识一个记录，则称此关键字为主关键字（Primary Key）。,查找（搜索）：给定一个值，在查找表中确定是否存在一个数据元
2、素（或记录），其关键字等于给定的值。,对查找表经常进行的操作:,1）查询(检索)某个“特定的”数据元素是否在查找表中及各种属性； 2）在查找表中插入一个数据元素； 3）从查找表中删去某个数据元素。,7.1 基本概念,仅作查询和检索操作的查找表。,静态查找表,有时还需将“查询”结果为“不在查找表中”的数据元素插入到表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。,动态查找表,查找表可分为两类:,7.1 基本概念,顺序查找,二分查找,分块查找,静态查找表,7.1 基本概念,7.2 顺序查找,顺序查找（Sequential Search）也称为线性查找。 基本思想：用给定的值与表
3、中各个记录的关键字值逐个进行比较，若找到相等的则查找成功，否则查找不成功，给出找不到的提示信息。 这种查找方法对顺序存储和链式存储都是适用的。,A,顺序表的查找过程：,假设给定值 e=64, 要求 Ak = e, 问: k = ?,k,7.2 顺序查找,顺序查找的查找过程为：从表中最后一个记录开始，逐个地将记录的关键字值和给定值的比较，若某个数据元素的关键字值和给定值相等，则查找成功，找到所查记录；反之，若一直找到第一个，其关键字值和给定值都不相等，则表明数组中没有所查元素，查找不成功。,7.2 顺序查找,64,监视哨,比较次数： 查找第n个元素： 1 (最好情况) 查找第n-1个元素：2 .
4、 查找第1个元素： n (最坏情况) 查找第i个元素： n+1-i 查找失败： n+1,本例比较次数：5,顺序查找的优点是：算法简单且适用面广，它对表的结构无任何要求。无论记录是否按关键字的大小有序，其算法均可应用，而且上述讨论对线性链表也同样适用。,成功查找的平均查找长度为（n+1）/2。显然不成功查找次数为n+1，其时间复杂度均为 O(n)。,7.2 顺序查找,顺序查找的缺点是：查找效率低，当 n 较大时，不宜采用顺序查找。,7.3 二分法查找,在顺序存储的条件下，若各记录是按其关键字值的大小依次存放的，则这个查找表称为有序表。 在有序表中可采用二分法查找（或称为折半查找）的方法进行查找。
5、,假设表中元素为升序排列。,基本思想：取表的中间记录的关键字值与给定关键字的值相比较，如果给定值比该记录的关键字值大，则要查找的记录一定在表的后半部分;若给定值比该记录的关键字值小，则要查找的记录一定在表的前半部分。 依次反复进行，在最坏的情况下，当表长缩小为1时必然能找到;否则就表明找不到要查找的记录。,7.3 二分法查找,查找的数据在表中,找到,找70,查找的数据不在表中,lowhigh 查找失败,从二分法查找的执行情况分析，每做一次比较，查找的范围都缩小一半。因此二分法查找的平均查找长度为 ASL= log2(n+1) - 1 当n足够大时，可近似表示为 log2n。 优点：二分法查找比
6、顺序查找的速度要快得多。当然，使用二分法查找必须是在顺序存储的条件下，且事先必须做到按关键字值排序才行。,7.3 二分法查找,练习,1、若有一个由17个元素组成的有序表，利用二分法查找方法查找有序表的元素，问查找成功时，最少比较几次？最多比较几次？ 【答案】 查找成功时，最少比较1次，最多比较5次。 2、已知如下11个数据元素的有序表（6，14，19，21，36，57，63，76，81，89，93），请画出查找键值为21和85的查找过程。,7.4 分块查找,分块查找又称索引顺序查找，它是顺序查找方法的一种改进方法，是介于顺序查找和二分法查找之间的一种折中查找方法。,基本思想是把线性表分成若干块
7、，每块中最大的关键字存入索引表。块内数据元素任意排放，索引表内数据按从小到大的顺序排放。块内进行顺序查找，索引表中采用二分查找或顺序查找。,查找步骤： 首先用给定值在索引表中查找，确定满足条件的数据元素应存放在哪一块中。 然后再到相应的块中进行顺序查找，便可以得到查找的结果。,7.4 分块查找,7.4 分块查找,索引表A的每个元素包含两个字段，一个是该块的最大关键字值，另一个是指向子表的指针。,例如，给定关键字序列如下： 22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设B=3，即将该序列分成3个子表（如何划分此处不考虑），每个子表有6
8、个元素，则得到的主表和索引表如图：,分块查找的过程是先确定待查记录所在的块，然后在块中顺序查找。假设给定k=38, 则先在索引表中按顺序（或折半）比较，因为22k48，则可确定38应该在第二块中，从第二块的第一个记录 6 顺序查起.,分块查找的平均查找长度由两个部分组成: ASL= Eb +Ew Eb为确定某一块所需的平均查找长度，Ew为在块内的平均查找长度。假设线性表中共有n个数据元素，平均分成b块，每块s个数据元素，并假设查找各块概率相等，若在索引表内和块内查找均用顺序查找方法， 则Ew=（s+1）/2 ， Eb =（b+1）/2 ，所以 ASL=Eb+Ew=（b+s）/2+1=（n/s+
9、s）/2+1 当s= 时，ASL取最小值，这时ASL= +1。,7.4 分块查找,分块查找的速度比顺序查找要快得多，但又不如二分法查找。如果线性表元素个数很多，且被分成的块数 b 很大时，对索引表的查找可以采用二分法查找，还能进一步提高速度。 优点：在线性表中插入或删除一个元素时，只要找到元素应属于的块，然后在块内进行插入和删除运算。由于块内元素的存放是任意的，所以插入和删除比较容易，不需要移动大量元素。,7.4 分块查找,练习,采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为多少个结点最佳。 【答案】 根据公式 s =n =
10、 625 = 25， 每块应分为25个结点最佳。,【三种查找方法比较】,7.5 散列表及其查找,7.5.1 散列表的概念,散列法亦称哈希（HASH）法，是在记录的存储位置和它的关键字之间建立一个确定的对应关系 H，使每个关键字与一个惟一的存储位置相对应。 散列方法不同于顺序查找、二分查找。它不以关键字的比较为基本操作，而采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。,7.5 散列表及其查找,基本思想:以记录中关键字的值为自变量，通过确定的函数H（散列函数）进行计算，求出对应的函数值，把这个函数值作为存储地址，将该记录（或 记录的关键字）存放在这个位
11、置上，查找时仍按这个确定的函数H进行计算，获得的将是待查的关键字所在记录的存储地址。,此表建好后，就可据此表查出任一关键字值的对应位置。,7.5 散列表及其查找,U（全集）：可能出现的关键字集合,K：实际存储的关键字集合,T：散列表,h：散列函数 h(ki)：关键字为ki结点的存储地址，即散列值（散列地址）,将结点按照其关键字的散列地址存储到散列表中的过程就是散列,【例如】建立一张全国30个地区的各民族统计表 H1：取键值中第一个字母在字母表中的序号作为散列函数。 H2：先求键值中首尾两个字母在字母表中的序号之和，如果这个和大于30，则减去30。,7.5 散列表及其查找,7.5 散列表及其查找
12、,由此可见: （1）散列函数是一个映象，因此散列函数的设定很灵活，只要使得任何键值由此所得的散列函数值都落在表长允许的范围之内即可; （2）对于不同的键值可能得到相同的散列地址， 即K1K2，而H（K1）=H（K2），这种现象称为散列冲突。具有相同函数值的键值称该散列函数的同义词。,在一般的情况下，冲突只能尽可能地减少，而不能完全避免。,散列法查找归结为如下两个方面: （1）对给定的一组关键字构造一个计算简单且散列均匀的散列函数; （2）拟订一个较好解决冲突的方法。,7.5 散列表及其查找,7.5.2 散列函数的构造方法,1. 直接定址法,取关键字的某个线性函数值为散列地址，即: H(key)
13、 = key 或 H(key) = a key + b （a和b为常数）,由于直接定址法所得地址集合和关键字大小相同，因此，关键字不会产生冲突，但实际应用中能够使用这种散列函数的情况很少。,7.5 散列表及其查找,2. 数字分析法,键值的位数比存储区域的地址码的位数多，在这种情况下可以对键值的各位进行分析，丢掉分布不均匀的位，留下分布均匀的位作为地址。,适用于关键字集中的集合，且关键字是事先知道的。,7.5 散列表及其查找,若以下标为000 999 的顺序表表示之。,【例如】为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。,
14、则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,2. 数字分析法,如:关键字序列 9 9 3 4 6 5 3 2 9 9 3 7 2 2 4 2 9 9 3 8 7 4 3 3 9 9 3 0 1 3 6 7 9 9 3 2 2 8 1 7 9 9 3 3 8 9 6 7 9 9 3 6 8 5 3 7 9 9 3 6 8 5 3 2 ,分析:前3位相同，第8位只可取2、3、7，因此，这四位不可取。中间的四位的数字变化多些，可看成是随机的，若规定地址取3位，则哈希函数可取它的第4、5、6位。于是有： H（99346532）465 H（9937
15、2242）722 H（99387433）874 H（99301367）016 H（99322817 ）228,3. 平方取中法,将关键字的值平方后，取其中若干位作为散列地址。 通常在选定散列函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关。由此使随机分布的关键字得到的散列地址也是随机的。取的位数由表长决定。,适合于关键字位数比较少的情况。,7.5 散列表及其查找,如图：随机给出一些关键字，取平方后的第2到4位为函数地址。,3. 平方取中法,4. 折叠法,如果键值的位数比地址码的位数多，而且各位分布不均匀，不适于用数字分析法丢掉某些位，那
16、么可以考虑用折叠法。 移位法（移位叠加） 将关键字分割成位数相等的几段，然后将它们的叠加和（舍去最高进位）作为散列地址 折叠法（间界叠加） 从一端向另一端沿分割界来回折迭，然后对齐相加。,7.5 散列表及其查找,例 关键字为 ：0442205864，哈希地址位数为4,4. 折叠法,H（k）= k % p （pm） k 关键字 m表长 注意：p应取小于表长m的最大素数，才能达到使散列函数值均匀分布的目的。,5. 除留余数法（求模取余法）,7.5 散列表及其查找,例如: 关键字集合 19, 1, 24, 14, 55, 16, 39 ,设定哈希函数 H(key) = key 7 ( 表长=9 ),19,1,24,14,55,16,39,5. 除留余数法,7.5.3 冲突处理,发生冲突是指由关键字得到的散列地址的位置上已经存有记录。而“处理冲突”就是为该关键字的记录找到一个“空”的散列地址。在找空的散列地址时，可能还会产生冲突，这就需要再找“下一个” 空的散列地
