《《数据结构》第七章查找.ppt》由会员分享，可在线阅读，更多相关《《数据结构》第七章查找.ppt（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.查找第1个元素：n(最坏情况)查找第i
4、个元素：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+EwEb为确定某一块所需的平均查找长度，Ew为在块内的平均查找长度。假设线性表中共有n个数据元素，平均分成b块，每块s个数据元素，并假设查找各块概率相等，若在索引表内和块内查找均用顺序查找方法，则Ew=（s+1）/2，Eb=（b+1）/2，所以ASL=Eb+Ew=（b+s）/2+1=（n/s+s）/2+1 当s=时，ASL取最小值，这时ASL=+1。,7.4 分块查找,分块查找的速度比顺序查找
9、要快得多，但又不如二分法查找。如果线性表元素个数很多，且被分成的块数 b 很大时，对索引表的查找可以采用二分法查找，还能进一步提高速度。优点：在线性表中插入或删除一个元素时，只要找到元素应属于的块，然后在块内进行插入和删除运算。由于块内元素的存放是任意的，所以插入和删除比较容易，不需要移动大量元素。,7.4 分块查找,练习,采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为多少个结点最佳。【答案】根据公式 s=n=625=25，每块应分为25个结点最佳。,【三种查找方法比较】,7.5 散列表及其查找,7.5.1 散列表的概念,散
10、列法亦称哈希（HASH）法，是在记录的存储位置和它的关键字之间建立一个确定的对应关系 H，使每个关键字与一个惟一的存储位置相对应。散列方法不同于顺序查找、二分查找。它不以关键字的比较为基本操作，而采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。,7.5 散列表及其查找,基本思想:以记录中关键字的值为自变量，通过确定的函数H（散列函数）进行计算，求出对应的函数值，把这个函数值作为存储地址，将该记录（或 记录的关键字）存放在这个位置上，查找时仍按这个确定的函数H进行计算，获得的将是待查的关键字所在记录的存储地址。,此表建好后，就可据此表查出任一关键字值的
11、对应位置。,7.5 散列表及其查找,U（全集）：可能出现的关键字集合,K：实际存储的关键字集合,T：散列表,h：散列函数h(ki)：关键字为ki结点的存储地址，即散列值（散列地址）,将结点按照其关键字的散列地址存储到散列表中的过程就是散列,【例如】建立一张全国30个地区的各民族统计表H1：取键值中第一个字母在字母表中的序号作为散列函数。H2：先求键值中首尾两个字母在字母表中的序号之和，如果这个和大于30，则减去30。,7.5 散列表及其查找,7.5 散列表及其查找,由此可见:（1）散列函数是一个映象，因此散列函数的设定很灵活，只要使得任何键值由此所得的散列函数值都落在表长允许的范围之内即可;（
12、2）对于不同的键值可能得到相同的散列地址，即K1K2，而H（K1）=H（K2），这种现象称为散列冲突。具有相同函数值的键值称该散列函数的同义词。,在一般的情况下，冲突只能尽可能地减少，而不能完全避免。,散列法查找归结为如下两个方面:（1）对给定的一组关键字构造一个计算简单且散列均匀的散列函数;（2）拟订一个较好解决冲突的方法。,7.5 散列表及其查找,7.5.2 散列函数的构造方法,1.直接定址法,取关键字的某个线性函数值为散列地址，即:H(key)=key 或 H(key)=a key+b（a和b为常数）,由于直接定址法所得地址集合和关键字大小相同，因此，关键字不会产生冲突，但实际应用中能够
13、使用这种散列函数的情况很少。,7.5 散列表及其查找,2.数字分析法,键值的位数比存储区域的地址码的位数多，在这种情况下可以对键值的各位进行分析，丢掉分布不均匀的位，留下分布均匀的位作为地址。,适用于关键字集中的集合，且关键字是事先知道的。,7.5 散列表及其查找,若以下标为000 999 的顺序表表示之。,【例如】为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999(前两位为年份)。,则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,2.数字分析法,如:关键字序列 9 9 3 4 6 5 3 2
14、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）465H（99372242）722H（99387433）874H（99301367）016H（99322817）228,3.平方取中法,将关键字的值平方后，取其中若干位作为散列地址。通常在选
15、定散列函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关。由此使随机分布的关键字得到的散列地址也是随机的。取的位数由表长决定。,适合于关键字位数比较少的情况。,7.5 散列表及其查找,如图：随机给出一些关键字，取平方后的第2到4位为函数地址。,3.平方取中法,4.折叠法,如果键值的位数比地址码的位数多，而且各位分布不均匀，不适于用数字分析法丢掉某些位，那么可以考虑用折叠法。移位法（移位叠加）将关键字分割成位数相等的几段，然后将它们的叠加和（舍去最高进位）作为散列地址折叠法（间界叠加）从一端向另一端沿分割界来回折迭，然后对齐相加。,7.5
16、散列表及其查找,例 关键字为：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 冲突处理,发生冲突是指由关键字得到的散列地址的位置上已经存有记录。而“处理冲突”就是为该关键字的记录找到一个“空”的散列地址。在找空的散列地址时，可能还会产生冲突，这就需要再
17、找“下一个”空的散列地址，直到不产生冲突为止。,7.5 散列表及其查找,1.开放地址法,所谓“开放地址”，就是表中尚未被占用的地址。解决冲突的方法是:散列表中的“空”地址向处理冲突开放。在散列表未满时，从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该空闲单元中。,7.5 散列表及其查找,在开放地址法中，从发生冲突的散列地址为d的单元起进行查找空闲单元有多种方法，每一种都对应着一定的查找路径，都产生一个确定的探查序列。,从发生冲突的单元起查找空闲单元的主要方法有:线性探查法、平方探查法和双散列函数探查法等。,7.5 散列表及其查找,它从
18、发生冲突的d单元起，依次探查下一个单元（当达到下标为m-1的表尾时，下一个探查单元是下标为0的表首单元），直到碰到一个空闲单元为止。这种方法的探查序列为d，d+1，d+2，或表示为（d+i）%m（0im-1）,（1）线性探查法,7.5 散列表及其查找,例如:关键字集合 19,1,23,14,55,68,11,82,36,设定哈希函数 H(key)=key 11(表长=11),19,1,23,14,55,68,若采用线性探测再散列处理冲突,11,82,36,1,1,2,1,3,6,2,5,1,ASL=,（1+1+2+1+3+6+2+5+1）/9=22/9,探查次数,（1）线性探查法,【线性探测法
19、的缺点】：,(2)容易产生堆积(又称聚集现象)，即存入哈希表的记录在表中连成一片；但它是开放地址处理冲突最简单的一种探查方法。,(1)按线性探测法建立起来的哈希表不能直接进行删除操作，若进行删除则对该存储单元进行特殊标记，否则会造成线性探测序列的中断，从而无法再查找后继同义词。,（1）线性探查法,（2）平方探查法,平方探查法的探查序列为d，d+12，d+22，或表示为（d+i2）%m（0im-1）平方探查法是一种较好的处理冲突的方法，它能够减少堆积现象的发生。它的缺点是不能探查到散列表上的所有单元，但至少能探查到一半单元。不过在实际应用中，能探查到一半单元也就足够了，若探查到一半单元仍找不到一
20、个空闲单元，表明此散列表太满应该重新建立。,7.5 散列表及其查找,19,1,23,14,68,若采用二次探测再散列处理冲突,55,11,82,36,1,1,2,1,4,3,2,1,1,例如:关键字集合 19,1,23,14,55,68,11,82,36,设定哈希函数 H(key)=key 11(表长=11),ASL=,（1+1+2+1+2+1+4+1+3）/9=16/9,探查次数,（2）平方探查法,这种方法使用两个散列函数H1和H2，其中H1和前面的 H（K）一样，是以关键字为自变量产生一个0至m-1之间的数作为散列地址，H2也是以关键字为自变量，产生一个1至m-1之间并和m互素的数（即m
21、不能被该数整除）作为探查序列的地址增量（即步长），双散列函数的探查序列为d0=H1（K）di=（di-1+H2（K）%m（1im-1）,7.5 散列表及其查找,（3）双散列函数探查法,2.链接法,链接法（又叫链地址法）就是把发生冲突的同义词元素用单链表链接起来的方法。它需要在散列表的每个单元中增加一个指针域，用来存储由发生冲突的同义词元素所构成的单链表的表头结点指针。,7.5 散列表及其查找,单链表中的结点可以是静态结点也可以是动态结点，相应的链接法被称为静态链接法和动态链接法。,静态链接法：首先要把整个散列表分为基本区和溢出区(即链接区)，按照元素的关键字计算出的散列地址d被存储在基本区上，
22、若发生冲突就从溢出区中取出一个空结点，把对应的元素存入该结点的值域，再把它链接到下标为d的单链表上。,动态链接法（无基本区）：当冲突发生时，首先产生一个新结点，把待插入元素存入该结点的值域，然后再把它链接到具有同义词结点的单链表中。,2.链接法,(将所有哈希地址相同的记录都链接在同一链表中),ASL=(61+22+3)/9=13/9,例如:关键字集合 19,1,23,14,55,68,11,82,36 哈希函数为 H(key)=key 7,动态链接法,2.链接法,什么是装填因子？,由于发生的冲突次数与表的填满程度直接有关，所以引进装填因子（1）:=表中已有的记录数/表的长度,7.5 散列表及其
23、查找,例：已知一组关键字为（26，36，41，38，44，15，68，12，6，51，25），分别用线性探查法和链接法解决散列冲突。构造这组关键字的散列表，散列函数H(K)=K%P。,令装填因子=0.75。则散列表长m=n/=11/0.7514.6，取整15，即散列表为HT0.14。H（K）=K%P中，P取接近14的最大素数 13，即散列函数为H（K）=K%13。,7.5 散列表及其查找,（1）散列表用顺序表实现，线性探查法解决冲突。,7.5 散列表及其查找,（2）散列表用链表实现，用动态链接地址法解决散列冲突。,练习,设散列表的长度为13，散列函数为H(K)=K%13，给定的关键字序列为19
24、，14，23，1，68，20，84，27，55，11，10，79。试画出分别用线性探查法和链接法解决冲突时所构造的散列表，并求等概率下这两种方法查找成功的平均查找长度。,查找是数据处理中经常使用的一种重要运算。在许多软件系统中最耗时间的部分是查找。因此，研究高效的查找方法是本章的重点。本章的基本内容是线性表的查找（顺序查找、二分法查找和分块查找），顺序查找比较慢，但适用面广;二分法查找速度快，但必须是有序表;分块查找是二者的折中方法。前面三种查找方法是基于比较的查找方法，而散列法是希望不经过任何比较，一次存取便能得到所查的记录，但由于冲突是不可避免的，解决冲突将也是散列法的一个主要问题，可以通过开放地址法或链接法解决冲突，每种方法又有多种实现方案,本章小结,
