《数据结构》第七章查找.ppt》由会员分享，可在线阅读，更多相关《数据结构》第七章查找.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第7章章 查查 找找第第7章章 查查 找找学习目的要求学习目的要求:1.顺序表、有序表、索引顺序表的定义、查找顺序表、有序表、索引顺序表的定义、查找及算法。及算法。2.散列表的定义及构造法。散列表的定义及构造法。3.散列表冲突的处理方法。散列表冲突的处理方法。7.1 基本概念基本概念7.2 顺序查找顺序查找7.5 散列表及其查找散列表及其查找7.4 分块查找分块查找7.3 二分法查找二分法查找第第7章章 查查 找找7.1 基本概念基本概念查找表（查找表（Search Table）是由同一类型的数据元素是由同一类型的数据元素（或记录）构成的集合。（或记录）构成的集合。关键字（关键字（Key）是
2、数据元素（或记录）中某个数据项是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可以若此关键字可以惟一惟一地标识一个记录，则称此关键字地标识一个记录，则称此关键字为主关键字（为主关键字（Primary Key）。）。查找（搜索）：查找（搜索）：给定一个值，在查找表中确定是否存给定一个值，在查找表中确定是否存在一个数据元素（或记录），其关键字等于给定的值。在一个数据元素（或记录），其关键字等于给定的值。对查找表经常进行的操作对查找表经常进行的操作:1 1）查查询询(检检索索)某某个个“特特定定的的”数数据
3、据元元素是否在查找表中及各种属性；素是否在查找表中及各种属性；2 2）在查找表中）在查找表中插入插入一个数据元素；一个数据元素；3 3）从查找表中）从查找表中删去删去某个数据元素。某个数据元素。7.1 基本概念基本概念仅作仅作查询查询和和检索检索操作的查找表。操作的查找表。静态静态查找表查找表有时还需将有时还需将“查询查询”结果为结果为“不在查找表中不在查找表中”的的数据元素数据元素插入插入到表中；或者，从查找表中到表中；或者，从查找表中删除删除其其“查询查询”结果为结果为“在查找表中在查找表中”的数据元素。的数据元素。动态动态查找表查找表查找表可分为两类查找表可分为两类:7.1 基本概念基本
4、概念顺序查找顺序查找二分查找二分查找分块查找分块查找静态查找表静态查找表7.1 基本概念基本概念7.2 顺序查找顺序查找顺序查找（顺序查找（Sequential Search）也称为线性也称为线性查找。查找。基本思想：用给定的值与表中各个记录的关基本思想：用给定的值与表中各个记录的关键字值逐个进行比较，若找到相等的则查找成功，键字值逐个进行比较，若找到相等的则查找成功，否则查找不成功，给出找不到的提示信息。否则查找不成功，给出找不到的提示信息。这种查找方法对顺序存储和链式存储都是适这种查找方法对顺序存储和链式存储都是适用的。用的。A A顺序表的查找过程：顺序表的查找过程：顺序表的查找过程：顺序
5、表的查找过程：假设给定值假设给定值 e=64,e=64,要求要求 Ak=e,Ak=e,问问:k=?:k=?k kk k7.2 顺序查找顺序查找 顺序查找的查找过程为：顺序查找的查找过程为：从表中最后一个记从表中最后一个记录开始录开始，逐个地将记录的关键字值和给定值的比，逐个地将记录的关键字值和给定值的比较，若某个数据元素的关键字值和给定值相等，较，若某个数据元素的关键字值和给定值相等，则查找成功，找到所查记录；反之，若一直找到则查找成功，找到所查记录；反之，若一直找到第一个，其关键字值和给定值都不相等，则表明第一个，其关键字值和给定值都不相等，则表明数组中没有所查元素，查找不成功。数组中没有所
6、查元素，查找不成功。7.2 顺序查找顺序查找i 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找6464监视哨监视哨iiii比较次数：比较次数：查找第查找第n个元素：个元素：1 (最好情况最好情况)查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素：n(最坏情况最坏情况)查找第查找第i个元素：个元素：n+1-i查找失败查找失败：n+1本例比较本例比较次数：次数：5顺序查找的顺序查找的优点优点是：算法简单且适用面广，它对表的是：算法简单且适用面广，它对表的结构无任何要求。无论记录是否按关键字的大小有序，其结构无
7、任何要求。无论记录是否按关键字的大小有序，其算法均可应用，而且上述讨论对线性链表也同样适用。算法均可应用，而且上述讨论对线性链表也同样适用。成功查找的平均查找长度为成功查找的平均查找长度为（n+1）/2。显然不成功显然不成功查找次数为查找次数为n+1，其时间复杂度均为，其时间复杂度均为 O(n)。7.2 顺序查找顺序查找 顺序查找的顺序查找的缺点缺点是：查找效率低，当是：查找效率低，当 n 较大时，不宜较大时，不宜采用顺序查找。采用顺序查找。7.3 二分法查找二分法查找 在顺序存储的条件下在顺序存储的条件下，若各记录是按其关键字，若各记录是按其关键字值的大小依次存放的，则这个查找表称为值的大小
8、依次存放的，则这个查找表称为有序表有序表。在有序表中可采用在有序表中可采用二分法查找二分法查找（或称为折半查（或称为折半查找）的方法进行查找。找）的方法进行查找。假设表中元素为升序排列。假设表中元素为升序排列。基本思想：基本思想：取表的取表的中间记录的关键字值中间记录的关键字值与给定关与给定关键字的值相比较，如果键字的值相比较，如果给定值给定值比该记录的关键字值比该记录的关键字值大大，则要查找的记录一定在表的，则要查找的记录一定在表的后半部分后半部分;若若给定值给定值比该记录的关键字值比该记录的关键字值小小，则要查找的记录一定在表，则要查找的记录一定在表的的前半部分前半部分。依次反复进行，在最
9、坏的情况下，当表长缩小为依次反复进行，在最坏的情况下，当表长缩小为1 1时必然能找到时必然能找到;否则就表明找不到要查找的记录。否则就表明找不到要查找的记录。7.3 二分法查找二分法查找midlowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid查查找找的的数数据据在
10、在表表中中找到找到1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid 查查找找的的数数据据不不在在表表中中1 2 3 4 5 6
11、7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighlowhigh查找失败查找失败从二分法查找的执行情况分析，每做一次比较，查找的从二分法查找的执行情况分析，每做一次比较，查找的范围都缩小一半。因此二分法查找的平均查找长度为范围都缩小一半。因此二分法查找的平均查找长度为 ASL=log2(n+1)-1当当n足够大时，可近似表示为足够大时，可近似表示为 log2n。优点：二分法查找比顺序查找的速度要快得多。当然，优点：二分法查找比顺序查找的速度要快得多。当然，使用二分法查找必须是在顺序存储的条件下，且事先必须做使用二分法查找必须是在顺序存储的条件下，
12、且事先必须做到按关键字值排序才行。到按关键字值排序才行。7.3 二分法查找二分法查找练习练习1、若有一个由、若有一个由17个元素组成的有序表，利用二分个元素组成的有序表，利用二分法查找方法查找有序表的元素，问查找成功时，法查找方法查找有序表的元素，问查找成功时，最少比较几次？最多比较几次？最少比较几次？最多比较几次？【答案答案】查找成功时，最少比较查找成功时，最少比较1次，最多比较次，最多比较5次。次。2、已知如下、已知如下11个数据元素的有序表（个数据元素的有序表（6，14，19，21，36，57，63，76，81，89，93），请画出），请画出查找键值为查找键值为21和和85的查找过程。的
13、查找过程。7.4 分块查找分块查找分块查找分块查找又称索引顺序查找，它是顺序查找方法又称索引顺序查找，它是顺序查找方法的一种改进方法，是介于顺序查找和二分法查找之间的一种改进方法，是介于顺序查找和二分法查找之间的一种折中查找方法。的一种折中查找方法。基本思想是基本思想是把线性表分成若干把线性表分成若干块块，每块中，每块中最大的最大的关键字关键字存入存入索引表索引表。块内数据元素任意排放，索引表。块内数据元素任意排放，索引表内数据按从小到大的顺序排放。内数据按从小到大的顺序排放。块内进行顺序查找块内进行顺序查找，索引表中采用二分查找或顺序查找索引表中采用二分查找或顺序查找。查找步骤：查找步骤：首
14、先用给定值在索引表中查找，确定满足条首先用给定值在索引表中查找，确定满足条件的数据元素应存放在哪一块中。件的数据元素应存放在哪一块中。然后再到相应的块中进行顺序查找，便可以然后再到相应的块中进行顺序查找，便可以得到查找的结果。得到查找的结果。7.4 分块查找分块查找7.4 分块查找分块查找索引表索引表A的每个元素包含两个字段，一个是该块的最大关的每个元素包含两个字段，一个是该块的最大关键字值，另一个是指向子表的指针。键字值，另一个是指向子表的指针。例如，给定关键字序列如下：例如，给定关键字序列如下：22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86
15、,53,假假设设B=3，即即将将该该序序列列分分成成3个个子子表表（如如何何划划分分此此处处不不考考虑虑），每每个个子子表表有有6个个元元素素，则则得得到到的的主主表表和和索索引引表表如如图：图：22121389203342443824486058744986532248860612 分分块块查查找找的的过过程程是是先先确确定定待待查查记记录录所所在在的的块块，然然后后在在块块中中顺顺序序查查找找。假假设设给给定定k=38,则则先先在在索索引引表表中中按按顺顺序序（或或折折半半）比比较较，因因为为22k48，则则可可确确定定38应应该该在在第第二二块块中中，从从第第二二块块的第一个记录的第一个
16、记录 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）/
17、2+1 当当s=时，时，ASL取最小值，这时取最小值，这时ASL=+1。7.4 分块查找分块查找分块查找的速度比顺序查找要快得多，但又不如二分分块查找的速度比顺序查找要快得多，但又不如二分法查找。如果线性表元素个数很多，且被分成的块数法查找。如果线性表元素个数很多，且被分成的块数 b 很很大时，对索引表的查找可以采用二分法查找，还能进一步大时，对索引表的查找可以采用二分法查找，还能进一步提高速度。提高速度。优点：优点：在线性表中插入或删除一个元素时，只要找到在线性表中插入或删除一个元素时，只要找到元素应属于的块，然后在块内进行插入和删除运算。由于元素应属于的块，然后在块内进行插入和删除运算。由
18、于块内元素的存放是任意的，所以插入和删除比较容易，不块内元素的存放是任意的，所以插入和删除比较容易，不需要移动大量元素。需要移动大量元素。7.4 分块查找分块查找练习练习采用分块查找时，若线性表中共有采用分块查找时，若线性表中共有625个元素，查个元素，查找每个元素的概率相同，假设采用顺序查找来确找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为多少个结点最佳。定结点所在的块时，每块应分为多少个结点最佳。【答案答案】根据公式根据公式 s=n=625=25，每块应分为每块应分为25个结点最佳。个结点最佳。【三种查找方法比较三种查找方法比较】顺序查找顺序查找折半查找折半查找分块
19、查找分块查找平均查找平均查找长度长度最大最大等概率查等概率查找最小找最小次小次小表的表的结构结构 有序表、无有序表、无序表均可序表均可仅适用于仅适用于有序表有序表表中元素逐表中元素逐段有序段有序表的表的存储存储结构结构顺序、链式顺序、链式结构均可结构均可仅适用于仅适用于顺序存储顺序存储顺序、链式顺序、链式均可，索引均可，索引表顺序存储表顺序存储7.5 散列表及其查找散列表及其查找7.5.1 散列表的概念散列表的概念散列法亦称散列法亦称哈希（哈希（HASHHASH）法）法，是在记录的存储位置和它，是在记录的存储位置和它的关键字之间建立一个确定的对应关系的关键字之间建立一个确定的对应关系 H H，
20、使每个关键字与，使每个关键字与一个惟一的存储位置相对应。一个惟一的存储位置相对应。散列方法不同于顺序查找、二分查找。它不以关键字的散列方法不同于顺序查找、二分查找。它不以关键字的比较为基本操作，而采用比较为基本操作，而采用直接寻址技术直接寻址技术。在理想情况下，无。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为须任何比较就可以找到待查关键字，查找的期望时间为O(1)O(1)。7.5 散列表及其查找散列表及其查找基本思想基本思想:以记录中关键字的值为自变量，通过确定以记录中关键字的值为自变量，通过确定的函数的函数H（散列函数）进行计算，求出对应的函数值，（散列函数）进行计算，求
21、出对应的函数值，把这个函数值作为存储地址，将该记录（或把这个函数值作为存储地址，将该记录（或 记录的关键记录的关键字）存放在这个位置上，查找时仍按这个确定的函数字）存放在这个位置上，查找时仍按这个确定的函数H进行计算，获得的将是待查的关键字所在记录的存储地进行计算，获得的将是待查的关键字所在记录的存储地址。址。此表建好后，就可据此表查出任一关键字值的对应此表建好后，就可据此表查出任一关键字值的对应位置。位置。7.5 散列表及其查找散列表及其查找U（全集）：可能出现的关键字集合K：实际存储的关键字集合T：散列表散列表h：散列函数散列函数h(ki)：关键字为ki结点的存储地址，即散散列值列值（散列
22、地址）将结点按照其关键字的散列地址存储到散列表中的过程就是散列散列【例如例如】建立一张全国建立一张全国30个地区的各民族统计表个地区的各民族统计表H1：取键值中第一个字母在字母表中的序号作为散列：取键值中第一个字母在字母表中的序号作为散列函数。函数。H2：先求键值中首尾两个字母在字母表中的序号之和，：先求键值中首尾两个字母在字母表中的序号之和，如果这个和大于如果这个和大于30，则减去，则减去30。BEJINGSHANXISHANGHAISHANDONGHENANK北京北京山西山西上海上海山东山东河南河南H1(K)0219191908H2(K)09282826227.5 散列表及其查找散列表及其
23、查找7.5 散列表及其查找散列表及其查找由此可见由此可见:（1）散列函数是一个映象，因此散列函数的设定很灵活，）散列函数是一个映象，因此散列函数的设定很灵活，只要使得任何键值由此所得的散列函数值都落在表长允许只要使得任何键值由此所得的散列函数值都落在表长允许的范围之内即可的范围之内即可;（2）对于不同的键值可能得到相同的散列地址，）对于不同的键值可能得到相同的散列地址，即即K1K2，而，而H（K1）=H（K2），这种现象称为），这种现象称为散列冲突散列冲突。具有相同函数值的键值称该具有相同函数值的键值称该散列函数的同义词散列函数的同义词。在一般的情况下，冲突只能尽可能地减少，而不能完在一般的情
24、况下，冲突只能尽可能地减少，而不能完全避免。全避免。散列法查找归结为如下两个方面散列法查找归结为如下两个方面:（1）对给定的一组关键字构造一个计算简单且散列均）对给定的一组关键字构造一个计算简单且散列均匀的散列函数匀的散列函数;（2）拟订一个较好解决冲突的方法。）拟订一个较好解决冲突的方法。7.5 散列表及其查找散列表及其查找7.5.2 散列函数的构造方法散列函数的构造方法1.直接定址法直接定址法取关键字的某个线性函数值为散列地址，即取关键字的某个线性函数值为散列地址，即:H(key)=key 或或 H(key)=a key+b （a和和b为常数）为常数）由于直接定址法所得地址集合和关键字大小
25、相同，因由于直接定址法所得地址集合和关键字大小相同，因此，关键字不会产生冲突，但实际应用中能够使用这种散此，关键字不会产生冲突，但实际应用中能够使用这种散列函数的情况很少。列函数的情况很少。7.5 散列表及其查找散列表及其查找2.数字分析法数字分析法键值的位数比存储区域的地址码的位数多，在这种情况键值的位数比存储区域的地址码的位数多，在这种情况下可以对键值的各位进行分析，丢掉分布不均匀的位，留下下可以对键值的各位进行分析，丢掉分布不均匀的位，留下分布均匀的位作为地址。分布均匀的位作为地址。适用于适用于关键字集中的集合，且关键字是事先知道的。关键字集中的集合，且关键字是事先知道的。7.5 散列表
26、及其查找散列表及其查找若若以下标为以下标为000 999 的的顺序表顺序表表示之。表示之。【例如例如】为每年招收的为每年招收的 1000 名新生建立一张查找表，名新生建立一张查找表，其关键字为学号，其值的范围为其关键字为学号，其值的范围为 xx000 xx999(前两前两位为年份位为年份)。则查找过程可以简单进行：取给定值（学号）则查找过程可以简单进行：取给定值（学号）的后三位，的后三位，不需要经过比较不需要经过比较便可便可直接从顺序表中直接从顺序表中找到待查关键字。找到待查关键字。2.数字分析法数字分析法如如:关键字序列关键字序列 9 9 3 4 6 5 3 2 9 9 3 7 2 2 4
27、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（99
28、322817）2283.平方取中法平方取中法将关键字的值平方后，取其中若干位作为散列地址。将关键字的值平方后，取其中若干位作为散列地址。通常在选定散列函数时不一定能知道关键字的全部情况，通常在选定散列函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关。由此使随机分布的关键字得到的散列和数的每一位都相关。由此使随机分布的关键字得到的散列地址也是随机的。取的位数由表长决定。地址也是随机的。取的位数由表长决定。适合于适合于关键字位数比较少的情况。关键字位数比较少的情况。7.5 散列表及其查找散
29、列表及其查找如图：随机给出一些关键字，取平方后的第如图：随机给出一些关键字，取平方后的第2到到4位为位为函数地址。函数地址。3.平方取中法平方取中法4.折叠法折叠法如果键值的位数比地址码的位数多，而且各位分布不均如果键值的位数比地址码的位数多，而且各位分布不均匀，不适于用数字分析法丢掉某些位，那么可以考虑用折叠匀，不适于用数字分析法丢掉某些位，那么可以考虑用折叠法。法。u移位法（移位叠加）移位法（移位叠加）将关键字分割成位数相等的几段，然后将它们的叠加和将关键字分割成位数相等的几段，然后将它们的叠加和（舍去最高进位）作为散列地址（舍去最高进位）作为散列地址u折叠法（间界叠加）折叠法（间界叠加）
30、从一端向另一端沿分割界来回折迭，然后对齐相加。从一端向另一端沿分割界来回折迭，然后对齐相加。7.5 散列表及其查找散列表及其查找例例 关键字为关键字为：0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加4.折叠法折叠法H（k）=k%p （pm）k 关键字关键字m表长表长注意：注意：p应取小于表长应取小于表长m的最大的最大素数素数，才能达到使散列函，才能达到使散列函数值均匀分布的目的。数值均匀分布的目的。5.除留余数
31、法（求模取余法）除留余数法（求模取余法）7.5 散列表及其查找散列表及其查找例如例如:关键字集合关键字集合 19,1,24,14,55,16,39 设定哈希函数设定哈希函数 H(key)=key 7(表长表长=9)1912414551639 0 1 2 3 4 5 6 7 8 5.除留余数法除留余数法7.5.3 冲突处理冲突处理发生发生冲突冲突是指由关键字得到的散列地址的位置上已经是指由关键字得到的散列地址的位置上已经存有记录。而存有记录。而“处理冲突处理冲突”就是为该关键字的记录找到一就是为该关键字的记录找到一个个“空空”的散列地址。在找空的散列地址时，可能还会产的散列地址。在找空的散列地址
32、时，可能还会产生冲突，这就需要再找生冲突，这就需要再找“下一个下一个”空的散列地址，直到不空的散列地址，直到不产生冲突为止。产生冲突为止。7.5 散列表及其查找散列表及其查找1.开放地址法开放地址法所谓所谓“开放地址开放地址”，就是表中尚未被占用的地址。，就是表中尚未被占用的地址。解决冲突的方法是解决冲突的方法是:散列表中的散列表中的“空空”地址向处理冲突开地址向处理冲突开放。在散列表未满时，从发生冲突的那个单元开始，按照一定放。在散列表未满时，从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入
33、元素存入到该空闲单元中。的待插入元素存入到该空闲单元中。7.5 散列表及其查找散列表及其查找在开放地址法中，从发生冲突的散列地址为在开放地址法中，从发生冲突的散列地址为d的单元起的单元起进行查找空闲单元有多种方法，每一种都对应着一定的查进行查找空闲单元有多种方法，每一种都对应着一定的查找路径，都产生一个确定的探查序列。找路径，都产生一个确定的探查序列。从发生冲突的单元起查找空闲单元的主要方法有从发生冲突的单元起查找空闲单元的主要方法有:线性线性探查法探查法、平方探查法平方探查法和和双散列函数探查法双散列函数探查法等。等。7.5 散列表及其查找散列表及其查找它从发生冲突的它从发生冲突的d单元起，
34、依次探查下一个单元（当达单元起，依次探查下一个单元（当达到下标为到下标为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)19123 145568若采用线性探测再散列处理冲突若
35、采用线性探测再散列处理冲突11 8236112136 2 51ASL=（1+1+2+1+3+6+2+5+1）/9=22/9探查探查次数次数（1）线性探查法）线性探查法【线性探测法的线性探测法的缺点缺点】：(2)容易产生容易产生堆积堆积(又称又称聚集聚集现象现象)，即，即存入哈存入哈希表的记录在表中连成一片希表的记录在表中连成一片；但它是开放地址处理；但它是开放地址处理冲突最简单的一种探查方法。冲突最简单的一种探查方法。(1)按线性探测法建立起来的哈希表按线性探测法建立起来的哈希表不能直接不能直接进行删除操作进行删除操作，若进行删除则对该存储单元进行特若进行删除则对该存储单元进行特殊标记，否则会
36、造成线性探测序列的中断，从而无殊标记，否则会造成线性探测序列的中断，从而无法再查找后继同义词。法再查找后继同义词。（1）线性探查法）线性探查法（2）平方探查法平方探查法平方探查法的探查序列为平方探查法的探查序列为d，d+12，d+22，或表，或表示为（示为（d+i2）%m（0im-1）平方探查法是一种较好的处理冲突的方法，它平方探查法是一种较好的处理冲突的方法，它能够减少能够减少堆积现象的发生堆积现象的发生。它的缺点是。它的缺点是不能探查到散列表上的所有单不能探查到散列表上的所有单元元，但至少能探查到一半单元。不过在实际应用中，能探查，但至少能探查到一半单元。不过在实际应用中，能探查到一半单元
37、也就足够了，若探查到一半单元仍找不到一个空到一半单元也就足够了，若探查到一半单元仍找不到一个空闲单元，表明此散列表太满应该重新建立。闲单元，表明此散列表太满应该重新建立。7.5 散列表及其查找散列表及其查找这种方法使用两个散列函数这种方法使用两个散列函数H1和和H2，其中，其中H1和前面的和前面的 H（K）一样，是以关键字为自变量产生一个）一样，是以关键字为自变量产生一个0至至m-1之间的之间的数作为散列地址，数作为散列地址，H2也是以关键字为自变量，产生一个也是以关键字为自变量，产生一个1至至m-1之间并和之间并和m互素的数（即互素的数（即m 不能被该数整除）作为探查不能被该数整除）作为探查
38、序列的地址增量（即步长），双散列函数的探查序列为序列的地址增量（即步长），双散列函数的探查序列为d0=H1（K）di=（di-1+H2（K）%m （1im-1）7.5 散列表及其查找散列表及其查找（3）双散列函数探查法双散列函数探查法2.链接法链接法链接法（又叫链地址法）就是把发生冲突的同义词元素链接法（又叫链地址法）就是把发生冲突的同义词元素用单链表链接起来的方法。它需要在散列表的每个单元中增用单链表链接起来的方法。它需要在散列表的每个单元中增加一个指针域，用来存储由发生冲突的同义词元素所构成的加一个指针域，用来存储由发生冲突的同义词元素所构成的单链表的表头结点指针。单链表的表头结点指针。7
39、.5 散列表及其查找散列表及其查找单链表中的结点可以是静态结点也可以是动态结点，相单链表中的结点可以是静态结点也可以是动态结点，相应的链接法被称为应的链接法被称为静态链接法静态链接法和和动态链接法动态链接法。静态链接法：静态链接法：首先要把整个散列表分为基本区和溢出区首先要把整个散列表分为基本区和溢出区(即链接区即链接区)，按照元素的关键字计算出的散列地址按照元素的关键字计算出的散列地址d被存储在基本区上，被存储在基本区上，若发生冲突就从溢出区中取出一个空结点，把对应的元素存若发生冲突就从溢出区中取出一个空结点，把对应的元素存入该结点的值域，再把它链接到下标为入该结点的值域，再把它链接到下标为
40、d的单链表上。的单链表上。动态链接法（无基本区）：动态链接法（无基本区）：当冲突发生时，首先产生一个新结点，把待插入元素存当冲突发生时，首先产生一个新结点，把待插入元素存入该结点的值域，然后再把它链接到具有同义词结点的单链入该结点的值域，然后再把它链接到具有同义词结点的单链表中。表中。2.链接法链接法(将所有哈希地址将所有哈希地址相同的记录相同的记录都链接在同一链表中都链接在同一链表中)012345614136198223116855 ASL=(61+22+3)/9=13/9例如例如:关键字集合关键字集合 19,1,23,14,55,68,11,82,36 哈希函数为哈希函数为 H(key)=
41、key 7动态链接法动态链接法2.链接法链接法什么是装填因子？什么是装填因子？由于发生的冲突次数与表的填满程度直接有关，由于发生的冲突次数与表的填满程度直接有关，所以引进装填因子所以引进装填因子（1）:=表中已有的记录数表中已有的记录数/表的长度表的长度7.5 散列表及其查找散列表及其查找例：例：已知一组关键字为（已知一组关键字为（26，36，41，38，44，15，68，12，6，51，25），分别用线性探查法和链接法解决散），分别用线性探查法和链接法解决散列冲突。构造这组关键字的散列表，散列函数列冲突。构造这组关键字的散列表，散列函数H(K)=K%P。令装填因子令装填因子=0.75。则散列
42、表长。则散列表长m=n/=11/0.7514.6，取整，取整15，即散列表为，即散列表为HT0.14。H（K）=K%P中，中，P取接近取接近14的最大素数的最大素数 13，即散列，即散列函数为函数为H（K）=K%13。7.5 散列表及其查找散列表及其查找01234567891011121314264144363811111存入存入26、36、41、38、44后的散列表后的散列表（1）散列表用顺序表实现，线性探查法解决冲突。）散列表用顺序表实现，线性探查法解决冲突。0123456789101112131426411568446363812511122111123存入存入6、51后的散列表后的散列
43、表0123456789101112131426254115684463638125115122111123存入存入25后的散列表后的散列表01234567891011121314264115684436381211221112存入存入15、68、12后的散列表后的散列表7.5 散列表及其查找散列表及其查找（2）散列表用链表实现，用动态链接地址法解决散列冲突。）散列表用链表实现，用动态链接地址法解决散列冲突。练习练习设散列表的长度为设散列表的长度为13，散列函数为，散列函数为H(K)=K%13，给定的，给定的关键字序列为关键字序列为19，14，23，1，68，20，84，27，55，11，10，
44、79。试画出分别用线性探查法和链接法解决冲突时。试画出分别用线性探查法和链接法解决冲突时所构造的散列表，并求等概率下这两种方法查找成功的平均所构造的散列表，并求等概率下这两种方法查找成功的平均查找长度。查找长度。1.查找是数据处理中经常使用的一种重要运算。在许多软件系统中最耗查找是数据处理中经常使用的一种重要运算。在许多软件系统中最耗时间的部分是查找。因此，研究高效的查找方法是本章的重点。时间的部分是查找。因此，研究高效的查找方法是本章的重点。2.本章的基本内容是本章的基本内容是线性表线性表的查找（顺序查找、二分法查找和分块查找）的查找（顺序查找、二分法查找和分块查找），顺序查找比较慢，但适用
45、面广，顺序查找比较慢，但适用面广;二分法查找速度快，但必须是有序表二分法查找速度快，但必须是有序表;分分块查找是二者的折中方法。块查找是二者的折中方法。3.前面三种查找方法是基于比较的查找方法，而前面三种查找方法是基于比较的查找方法，而散列法散列法是希望不经过任是希望不经过任何比较，一次存取便能得到所查的记录，但由于何比较，一次存取便能得到所查的记录，但由于冲突冲突是不可避免的，解决是不可避免的，解决冲突将也是散列法的一个主要问题，可以通过冲突将也是散列法的一个主要问题，可以通过开放地址法开放地址法或或链接法链接法解决冲解决冲突，每种方法又有多种实现方案突，每种方法又有多种实现方案本章小结本章小结