软件技术基础第03章查找.ppt

思考问题思考问题数据存放在计算机中如何查找？数据存放在计算机中如何查找？查找方法有所不同吗？不同方法的查找查找方法有所不同吗？不同方法的查找效率有区别吗？效率有区别吗？基本的查找方式有几种？基本的查找方式有几种？1教学目标教学目标了解有关查找的了解有关查找的基本概念基本概念查找的主要算法查找的主要算法2教学要求教学要求通过本单元的学习，了解、掌握有通过本单元的学习，了解、掌握有关查找的：关查找的：基本概念基本概念查找、平均查找长度查找、平均查找长度主要查找算法主要查找算法顺序查找、折半查找、分块查找顺序查找、折半查找、分块查找哈希查找哈希查找3本单元涉及的内容本单元涉及的内容第第3 3章章3.1 3.1 基本的查找技术基本的查找技术 3.2 3.2 哈希表技术哈希表技术4一、基本概念一、基本概念查找查找查找表查找表静态查找静态查找动态查找动态查找平均查找长度平均查找长度5查找查找查查找找 就就是是在在给给定定的的DSDS中中找找出出满满足足某某种种条条件件的的结结点点；若若存存在在这这样样的的结结点点，查查找找成成功功；否否则则，查查找失败。找失败。查找表查找表 是一组待查数据元素的集合。是一组待查数据元素的集合。静静态态查查找找 是是仅仅仅仅进进行行查查询询和和检检索索操操作作，不不改改变变查找表中数据元素间的逻辑关系的查找。查找表中数据元素间的逻辑关系的查找。动动态态查查找找 是是除除了了进进行行查查询询和和检检索索操操作作外外，还还对对查查找找表表进进行行插插入入、删删除除操操作作的的查查找找，动动态态地地改改变查找表中数据元素之间的逻辑关系。变查找表中数据元素之间的逻辑关系。6平均查找长度平均查找长度 平均查找长度平均查找长度 （ASL-Average Search LengthASL-Average Search Length）在在查查找找过过程程中中，对对每每个个结结点点记记录录中中的的关关键键字字要要进进行行反反复复比比较较，以以确确定定其其位位置置。因因此此，与与关关键键字字进进行行比比较较的的平平均均次次数数，就成为就成为平均查找长度平均查找长度。它是用来评价一个算法好坏的一个依据。它是用来评价一个算法好坏的一个依据。对对含含有有n n个个数数据据元元素素的的查查找找表表，查查找找成成功功时时的的平平均均查查找找长长度度为：为：ASL=ASL=Pi*CiPi*Cin ni=1i=1 Pi=1Pi=1i=1i=1n n 其中：其中：Pi Pi 为查找表中第为查找表中第i i个数据元素的概率，且个数据元素的概率，且 CiCi为查找到第为查找到第i i个数据元素时需进行比较的次数。个数据元素时需进行比较的次数。显然，显然，CiCi随查找过程及随查找过程及DSDS的不同而各异。的不同而各异。7基本的查找技术基本的查找技术顺序查找顺序查找折半查找折半查找分块查找分块查找81.1.顺序查找顺序查找算法思想：算法思想：最最古古老老的的算算法法。从从第第1 1个个元元素素到到最最后后1 1个元素，逐个进行比较。个元素，逐个进行比较。查找表的存储结构查找表的存储结构既适用于顺序存储结构既适用于顺序存储结构也适用于链式存储结构也适用于链式存储结构 算法描述算法描述算法讨论算法讨论9算法描述算法描述查找操作步骤：查找操作步骤：step1step1 从第从第1 1个元素开始查找；个元素开始查找；step2step2 用用待待查查关关键键字字值值与与各各结结点点（记记录录）的的关关键键字字值值逐逐个个进进行行比比较较；若若找找到到相相等等的的结结点点，则则查查找找成成功功；否否则，查找失败。则，查找失败。10顺序查找算法顺序查找算法 seq_search(int*item,n,key)seq_search(int*item,n,key)int i=0;int i=0;while(i n&itemi!=key)while(i n&itemi!=key)i+;/*i+;/*查找查找keykey的循环的循环 */*/if(itemi=key)if(itemi=key)printf(“printf(“查找成功查找成功!n”);return(i);!n”);return(i);else else printf(“printf(“查找失败查找失败!n”);return(-1);!n”);return(-1);11顺序查找算法（改进算法）顺序查找算法（改进算法）seq_search_adv(int*item,n,key)seq_search_adv(int*item,n,key)int i=0;int i=0;itemn=key;/*itemn=key;/*设置哨兵设置哨兵 */*/while(itemi!=key)i+;/*while(itemi!=key)i+;/*查找查找keykey */*/if(i n)/*if(i0)if(loc 0)printf(“loc=%d,key=%dn”,loc,key);printf(“loc=%d,key=%dn”,loc,key);13算法讨论算法讨论平均查找长度平均查找长度ASLASL在等概率的情况下在等概率的情况下平均查找长度平均查找长度ASLASL在等概率的情况下在等概率的情况下优点优点:对结点的逻辑次序对结点的逻辑次序(不必有序不必有序)和存储结构和存储结构(顺序、链表顺序、链表均可）无要求；当序列中的记录均可）无要求；当序列中的记录“基本有序基本有序”或或N N值值较小时，是较好的算法；较小时，是较好的算法；缺点：缺点：ASLASL较长较长讨论：能否减少比较次数，以提高效率。讨论：能否减少比较次数，以提高效率。例如，例如，二分法等二分法等142.2.折半查找折半查找算法思想：算法思想：将将有有序序数数列列的的中中点点设设置置为为比比较较对对象象，如如果果要要找找的的元元素素值值小小于于该该中中点点元元素素，则则将将待待查查序列缩小为左半部分，否则为右半部分。序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。即通过一次比较，将查找区间缩小一半。二二分分查查找找的的先先决决条条件件是是查查找找表表中中的的数数据据元元素必须有序。素必须有序。15算法描述算法描述算法步骤：算法步骤：step1 step1 首先确定整个查找区间的中间位置，首先确定整个查找区间的中间位置，mid=mid=（left+right left+right）/2/2step2 step2 用用待待查查关关键键字字值值与与中中间间位位置置的的关关键键字字值值进进行行比较；比较；?若相等，则查找成功；若相等，则查找成功；?若大于，则在后半区域继续进行二分查找；若大于，则在后半区域继续进行二分查找；?若小于，则在前半区域继续进行二分查找。若小于，则在前半区域继续进行二分查找。对确定的缩小区域再按二分公式，重复上述步骤；对确定的缩小区域再按二分公式，重复上述步骤；最后，得到结果：最后，得到结果：?要么，查找成功，要么，查找成功，要么，查找失败。要么，查找失败。存储结构存储结构用一维数组存放。用一维数组存放。16折半查找算法举例折半查找算法举例l对给定数列（有序）对给定数列（有序）3 3，5 5，1111，1717，2121，2323，2828，3030，3232，5050，按折半，按折半查找算法，查找关键字值为查找算法，查找关键字值为3030的数据元素。的数据元素。leftrightmidleftrightmid第1次：3，5，11，17，21，23，28，30，32，50 第二次：23，28，30，32，50 mid1=（1+10）/2=5mid2=（6+10）/2=817折半查找算法折半查找算法 bin_search(item,n,key)bin_search(item,n,key)int*item,n,key;int*item,n,key;int left,right,mid;left=0;right=n-1;int left,right,mid;left=0;right=n-1;while(left while(left right)right)mid=(left+right)/2;/*mid=(left+right)/2;/*计算中点位置计算中点位置 */*/if(key itemmid)if(key itemmid)else if(key itemmid)left=mid+1;/*left=mid+1;/*待查区间在右部待查区间在右部 */*/else printf(“Successful searchn”);else printf(“Successful searchn”);return mid;/*return mid;/*查找成功查找成功 */*/printf(“Search failure n”);printf(“Search failure n”);return-1;/*return-1;/*查找失败查找失败 */*/18折半查找算法的主程序折半查找算法的主程序#define“stdio.h”#define“stdio.h”int num;int num;main()main()int res,key;int res,key;int int s10=1,3,5,7,9,11,13s10=1,3,5,7,9,11,13，1515，1717，1919，2121，23;23;res=b_search(s,12,7);res=b_search(s,12,7);if(res0)if(res0)printf(res=%d,num=%dn,res+1,num);printf(res=%d,num=%dn,res+1,num);else else printf(“search failuren”);printf(“search failuren”);19算法分析算法分析优点优点:ASL ASL log2n;log2n;即每经过一次比较即每经过一次比较,查找范围就缩小一查找范围就缩小一半。经半。经log2n log2n 次计较就可以完成查找过程。次计较就可以完成查找过程。缺点：缺点：因要求有序，所以对所有数据元素按大小排序是非常因要求有序，所以对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不大费时的操作。另外，顺序存储结构的插入、删除操作不大便利。便利。考虑：考虑：能否一次比较抛弃更多的部分（即一次比较，使查找范能否一次比较抛弃更多的部分（即一次比较，使查找范围缩得更小），以达到提高效率的目的；围缩得更小），以达到提高效率的目的；？把两种方法（顺序查找和二分查找）结把两种方法（顺序查找和二分查找）结合起来，即取顺序查找简单和二分查找合起来，即取顺序查找简单和二分查找高效之所长，来达到提高效率的目的？高效之所长，来达到提高效率的目的？203.3.分块查找分块查找l分分块块查查找找又又称称索索引引顺顺序序查查找找，这这是是顺顺序序查查找找的的一种改进方法。一种改进方法。l方法描述：方法描述：将将n n个数据元素个数据元素“按块有序按块有序”划分为划分为m m块（块（m m n n）。）。每每一一块块中中的的结结点点不不必必有有序序，但但块块与与块块之之间间必必须须“按按块块有有序序”；即即第第1 1块块中中任任一一元元素素的的关关键键字字都都必必须须小小于于第第2 2块块中中任任一一元元素素的的关关键键字字；而而第第2 2块块中中任任一一元元素素又又都都必必须须小小于于第第3 3块块中中的的任任一一元元素素，。每每个个块块中元素不一定是有序的。中元素不一定是有序的。21分块查找算法描述分块查找算法描述step1step1 先选取各块中的最大关键字构成先选取各块中的最大关键字构成一个索引表；一个索引表；step2step2 查找分两个部分：查找分两个部分：先对索引表进行二分查找或顺序查先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找。在已确定的块中用顺序法进行查找。22分块查找举例分块查找举例有数列如下：有数列如下：22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 按按“块有序块有序”分三块分三块:(22,12,13,9,8),(33,42,44,38,24),:(22,12,13,9,8),(33,42,44,38,24),(48,60,58,74,47)(48,60,58,74,47)。选取每块中最大的关键字组成索引表。选取每块中最大的关键字组成索引表22,44,74,22,44,74,查找关键字值为查找关键字值为6060的元素。的元素。用二分法，确定在索引表中的位置为用二分法，确定在索引表中的位置为 mid=2 mid=2，keykey值值6060与与a2a2比较，比较，60a2,60a2,取第取第3 3个块个块;在第在第3 3块中用顺序法查找块中用顺序法查找,比较两次比较两次,就可以找出就可以找出6060的元素来。的元素来。4422742212139833424438244860587447List1List1List2List2List3List323索引表结构定义索引表结构定义#include stdio.h#include stdio.htypedef structtypedef struct int key;/*int key;/*块最大值块最大值 */*/int link;/*int link;/*指向块入口地址指向块入口地址*/*/index;index;24index_seq_search.cindex_seq_search.c子函数子函数index_seq_search(index ls,int s,int m,int key,int l)index_seq_search(index ls,int s,int m,int key,int l)int i,j;int i,j;i=0;i=0;while(ilsi.key)while(ilsi.key)i+;/*i+;/*确定在哪块查找 */*/if(i=m)if(i=m)printf(“Searching failuren);printf(“Searching failuren);return(-1);return(-1);else/*else/*否则，查找成功处理否则，查找成功处理 */*/25分块查找子函数（续）分块查找子函数（续）j=lsi.link;/*j=lsi.link;/*块入口地址块入口地址 */*/while(key!=sj&(j-lsi.link)l)j+;while(key!=sj&(j-lsi.link)l)j+;if(key=sj&(j-lsi.link)l)/*if(key=sj&(j-lsi.link)l)/*查找成功查找成功*/*/printf(Successful searchn printf(Successful searchn LOC(s%2d)=%dn,j,sj);LOC(s%2d)=%dn,j,sj);return(j);return(j);else /*else /*查找失败查找失败 */*/printf(Searching failuren);printf(Searching failuren);return(-1);return(-1);/*/*结束结束 */*/26分块查找主函数分块查找主函数main()main()index ls5=14,0,34,5,66,10,85,15,100,20 ;index ls5=14,0,34,5,66,10,85,15,100,20 ;int a=8,4,3,2,14,34,20,17,28,29,58,61,59,66,48,int a=8,4,3,2,14,34,20,17,28,29,58,61,59,66,48,81,80,79,83,69,89,100,96,86,87;81,80,79,83,69,89,100,96,86,87;int i,j=0,key;int i,j=0,key;for(i=0;i25;i+)for(i=0;i25;i+)if(j=0)printf();if(j=0)printf();if(j=5)printf();j=0;printf();if(j=5)printf();j=0;printf();printf(%4d,ai);j+;printf(%4d,ai);j+;printf(n);printf(n);printf(Enter key:);printf(Enter key:);scanf(%d,&key);scanf(%d,&key);index_seq_search(ls,a,25,key,5);index_seq_search(ls,a,25,key,5);27算法讨论算法讨论设索引表使用二分法，则有：设索引表使用二分法，则有：ASL ASL log2 log2（n/S+1n/S+1）+S/2+S/2其中：其中：n n为表长，为表长，S S为块长（假设各块长度相等）。为块长（假设各块长度相等）。优点：优点：插入、删除操作方便；只要找到对应的块，插入、删除操作方便；只要找到对应的块，在块中任意位置操作均可。在块中任意位置操作均可。缺点：缺点：索引表增加了辅助存储空间。索引表增加了辅助存储空间。注：注：索引表在数据库系统中广泛使用。索引表在数据库系统中广泛使用。还有什么方法吗？还有什么方法吗？树表查找树表查找28二、哈希（二、哈希（hashhash）表技术）表技术哈哈希希查查找找也也称称为为散散列列查查找找。它它不不同同于于前前面面介介绍绍的的几几种种查查找找方方法法。上上述述方方法法都都是是把把查查找找建建立立在在比比较较的的基基础础上上，而而哈哈希希查查找找则则是是通过计算存储地址的方法进行查找的。通过计算存储地址的方法进行查找的。计计算算是是计计算算机机的的特特点点之之一一，因因此此，建建立立在在计计算算基基础础上上的的哈哈希希查查找找是是一一种种快快速速查查找找方方法。法。29哈希查找的基本概念哈希查找的基本概念哈哈希希表表 由由哈哈希希函函数数的的值值组组成成的的表表。哈哈希希查查找找是是建建立立在在哈哈希希表表的的基基础础上上，它它是是线线性性表表的的一一种种重重要要存存储储方方式式和和检检索索方方法法。在在哈哈希希表表中中可可以以实实现现对对数数据元素的快速检索。据元素的快速检索。哈哈希希函函数数 哈哈希希表表中中元元素素是是由由哈哈希希函函数数确确定定的的。将将数数据据元元素素的的关关键键字字K K作作为为自自变变量量，通通过过一一定定的的函函数数关关系系（称称为为哈哈希希函函数数），计计算算出出的的值值，即即为为该该元元素的存储地址。表示为：素的存储地址。表示为：AddrAddr=H=H（keykey）建立哈希函数的原则建立哈希函数的原则均匀性均匀性 H H（keykey）的值均匀分布在哈希表中；的值均匀分布在哈希表中；简单简单 以提高地址计算的速度。以提高地址计算的速度。30哈希函数常用的构造方法哈希函数常用的构造方法数字分析法数字分析法平方取中法平方取中法折叠法折叠法除留余数法（求模取余法）除留余数法（求模取余法）直接定址法直接定址法31数字分析法数字分析法当当关关键键字字的的位位数数比比存存储储区区地地址址码码位位数数多多时时，可可合理选择关键字的某几位组成的哈希地址。合理选择关键字的某几位组成的哈希地址。选取的原则：尽量避免计算出的地址有冲突。选取的原则：尽量避免计算出的地址有冲突。举举例例：学学校校的的电电话话号号码码是是7 7位位十十进进制制数数，学学校校的程控交换机是的程控交换机是30003000门。但经分析不难得出：门。但经分析不难得出：0XXX 0XXX 266 8XXX 266 8XXX 9XXX 9XXX 前前3 3位位是是相相同同的的，第第4 4位位分分别别为为“0 0、8 8、9”9”，这这样样一一来来，正正好好可可以以表表示示30003000个个不不同同的的电电话话号号码。码。H H（KEYKEY）=Right=Right（telnumtelnum，4 4）32平方取中法平方取中法l取取关关键键字字平平方方后后的的中中间间几几位位为为哈哈希希地地址址。这这是是一一种种较较常常用用的的构构造造哈哈希希函函数数的的方方法法。通通常常在在选选定定哈哈希希函函数数时时不不知知道道关关键键字字的的全全部部情情况况，取取其其中中的的哪哪几几位位也也不不一一定定合合适适，在在这这种种情情况况下下，取取一一个个数数平平方方后后的的中中间间几几位位数数作作哈哈希希地地址址。取取的的位数由表长决定。位数由表长决定。l例例如如，32883288，平平方方后后是是“10810944”“10810944”，取取后后4 4位为哈希地址，即位为哈希地址，即“0944”“0944”。33折叠法折叠法l将将关关键键字字分分割割成成位位数数相相同同的的几几部部分分（最最后后一一部部分分的的位位数数可可以以不不同同），然然后后取取这这几几部部分分的的叠叠加加和（舍去进位）作为哈希地址。和（舍去进位）作为哈希地址。l关关键键字字位位数数很很多多，且且每每一一位位上上数数字字分分布布大大致致均均匀时，可采用折叠法。匀时，可采用折叠法。l举举例例：某某资资料料室室藏藏书书近近万万册册。采采用用国国际际标标准准图图书书编编号号（ISBNISBN），每每个个编编号号1010位位十十进进制制数数字字。可用折叠法构造一个可用折叠法构造一个4 4位数的哈希函数。位数的哈希函数。例如：例如：书号为：书号为：0-4 4 2-2 0 5 8 6-4 0-4 4 2-2 0 5 8 6-4 5 8 6 4 5 8 6 4 4 2 2 0 H 4 2 2 0 H（keykey）=0088=0088 0 4 0 4+）1 0 0 8 81 0 0 8 834除留余数法（求模取余法）除留余数法（求模取余法）取取关关键键字字被被某某个个不不大大于于哈哈希希表表表表长长m m的的数数p p除除后后所得余数为哈希地址。所得余数为哈希地址。H H（keykey）=key MOD p=key MOD p 这这是是一一种种最最简简单单，也也是是最最常常用用的的构构造造哈哈希希函函数的方法。数的方法。举例，举例，32834872 32834872，哈希表长为，哈希表长为4 4位十进制数。位十进制数。P P值可取小于值可取小于99999999的数，例如，取的数，例如，取50005000；H H（KEYKEY）=32834872 MOD 5000=4872=32834872 MOD 5000=4872由由经经验验得得知知：通通常常选选p p为为小小于于哈哈希希表表长长的的最最大大素素数。数。35直接定址法直接定址法取取关关键键字字或或关关键键字字的的某某个个线线性性函函数数值值为为哈哈希希地地址址，即：即：H H（keykey）=key=key H H（keykey）=a*key+b=a*key+b（a a，b b为常数）为常数）例例如如：在在11001100岁岁的的人人口口统统计计表表中中，年年龄龄作作为为关关键字，哈希函数取关键字本身。键字，哈希函数取关键字本身。再再如如：解解放放后后出出生生人人口口统统计计表表中中，年年份份作作为为关关键字，哈希函数取为：键字，哈希函数取为：H H（keykey）=key+=key+（-1948-1948）地址地址年份年份人数人数 0101 0202 421949 19501990.4319913000 35002500 2300.36选择哈希函数的标准选择哈希函数的标准哈希函数计算所需要的时间哈希函数计算所需要的时间关键字的长度关键字的长度哈希表的长度哈希表的长度关键字的分布情况关键字的分布情况记录的查找频率记录的查找频率37冲突及冲突处理冲突及冲突处理在在哈哈希希元元素素（地地址址）求求解解过过程程中中，不不同同关关键键字字值值对对应应到到同同一一个个存存储储地地址址的的现现象象称称为为冲冲突突。即即关关键键字字K1 K1 K2K2，但但哈哈希希函函数数值值 H H（K1K1）=H H（K2K2）。）。均均匀匀的的哈哈希希函函数数可可以以减减少少冲冲突突，但但不不能能避避免免冲冲突突。发发生生冲冲突突后后，必必须须解解决决；也也即即必必须须寻寻找找下下一个可用地址。一个可用地址。处处理理冲冲突突是是建建立立哈哈希希表表过过程程中中不不可可缺缺少少的的一一部部分。分。处理冲突有两种方法：处理冲突有两种方法：开放地址法开放地址法链地址法链地址法38处理冲突处理冲突-开放地址法开放地址法当发生地址冲突后，求解下一个地址用当发生地址冲突后，求解下一个地址用 Hi=(HHi=(H（keykey）+didi）MOD m MOD m i=1,2,k(k i=1,2,k(k m-1)m-1)其其中中:H(key)H(key)为为哈哈希希函函数数,m,m为为哈哈希希表表长长度度,didi为为增增量量序序列列。增增量量序序列列的的不不同同取取法法，又构成不同的开放地址法。又构成不同的开放地址法。线性探测再散列线性探测再散列 didi=1,2,m-1=1,2,m-1二次探测再散列二次探测再散列 di=1di=12 2,-1,-12 2,2,22 2,-2,-22 2,+k,+k2 2,-k,-k2 2(k(k m/2)m/2)39处理冲突处理冲突-链地址法链地址法当当发发生生地地址址冲冲突突后后,将将所所有有函函数数值值相相同同的的记记录录连连成成一一个个单链表。单链表。40哈希查找操作步骤哈希查找操作步骤用给定的哈希函数构造哈希表用给定的哈希函数构造哈希表根根据据选选择择的的冲冲突突处处理理方方法法解解决决地地址冲突址冲突在哈希表的基础上执行哈希查找在哈希表的基础上执行哈希查找41建立哈希表建立哈希表建立哈希表操作步骤：建立哈希表操作步骤：step1step1 取取数数据据元元素素的的关关键键字字keykey，计计算算其其哈哈希希函函数数值值（地地址址）。若若该该地地址址对对应应的的存存储储空空间间还还没没有有被被占占用用，则则将将该该元元素素存存入；否则执行入；否则执行step2step2解决冲突。解决冲突。step2 step2 根根据据选选择择的的冲冲突突处处理理方方法法，计计算算关关键键字字keykey的的下下一一个个存存储储地地址址。若若下下一一个个存存储储地地址址仍仍被被占占用用，则则继继续续执执行行step2step2，直到找到能用的存储地址为止。，直到找到能用的存储地址为止。42举例举例对对给给定定数数列列 22,41,53,46,30,13,1,67 22,41,53,46,30,13,1,67,建建立立哈哈希希表表。表表长长取取9,9,即即0808。哈哈希希函函数数设设定定为为:H(key)H(key)=key key MOD MOD 8 8,用用线线性性探探测测解解决决冲冲突突 Hi=(H(key)+di)Hi=(H(key)+di)MOD MOD m m,di=1,2,m-1,di=1,2,m-1。取取2222，计算，计算H H（2222）=6=6，该地址空，可用；，该地址空，可用；0 1 2 3 4 5 6 7 82222 0 1 2 3 4 5 6 7 841比较次数：比较次数：1 1取取4141，计算，计算H H（4141）=1=1，该地址空，可用；，该地址空，可用；43举例（续一）举例（续一）取取5353，计算，计算 H H（5353）=5=5，该地址空，可用；，该地址空，可用；2241 0 1 2 3 4 5 6 7 853224153460 1 2 3 4 5 6 7 8 比较次数：比较次数：1 1 1 比较次数：比较次数：1 1 1 2取取4646，计算，计算 H H（4646）=6=6，该地址冲突，用线性探，该地址冲突，用线性探测法计算下一个可用地址测法计算下一个可用地址 Hi=Hi=（6+16+1）MOD 8=7MOD 8=7，该地址空，可用；，该地址空，可用；44举例（续二）举例（续二）取取3030，计算，计算 H H（3030）=6=6，该地址冲突，用线性探测法计，该地址冲突，用线性探测法计算下一个可用地址算下一个可用地址 Hi=Hi=（6+16+1）MOD 8=7MOD 8=7，该地址冲突，再用线性探测法计算下一个可用地址；该地址冲突，再用线性探测法计算下一个可用地址；Hi=0Hi=0，地址空，可用；，地址空，可用；22410 1 2 3 4 5 6 7 853224153460 1 2 3 4 5 6 7 8 比较次数：比较次数：3 1 1 1 2 比较次数：比较次数：3 1 6 1 1 246303013取取1313，计算，计算 H H（1313）=5=5，依法解决冲突，得出：，依法解决冲突，得出：45举例（续三）举例（续三）取取1 1，计算，计算 H H（1 1）=1=1，该地址冲突，解决冲突可得：，该地址冲突，解决冲突可得：22410 1 2 3 4 5 6 7 85322415346 46303013 比较次数：比较次数：3 1 6 3 1 1 2113167 比较次数：比较次数：3 1 6 3 2 1 1 20 1 2 3 4 5 6 7 8取取6767，计算，计算 H H（6767）=3=3，冲突，解决冲突，得出：，冲突，解决冲突，得出：46 哈希查找哈希查找 哈希查找的过程和建立哈希表的过程是一致的。哈希查找的过程和建立哈希表的过程是一致的。设设哈哈希希表表为为HST0M-1HST0M-1，哈哈希希函函数数取取H H（keykey），解决冲突的方法为解决冲突的方法为R R（x x），则哈希查找步骤为：），则哈希查找步骤为：Step1Step1 对对给给定定k k值值，计计算算哈哈希希地地址址 Di=HDi=H（k k）；若若HSTiHSTi为为空空，则则查查找找失失败败；若若HSTi=kHSTi=k，则查找成功；否则，执行则查找成功；否则，执行step2step2（处理冲突）。（处理冲突）。Step2Step2 重复计算处理冲突的下一个存储地址重复计算处理冲突的下一个存储地址 Dk=RDk=R（Dk-1Dk-1），直直 到到 HSTDkHSTDk为为 空空，或或HSTDk=kHSTDk=k为止。为止。若若HSTDk=KHSTDk=K，则查找成功，否则查找失败。，则查找成功，否则查找失败。47 查找举例查找举例 以上述哈希表为例。以上述哈希表为例。哈希函数为哈希函数为H(key)=key MOD 8,H(key)=key MOD 8,设设有有数数列列22,41,53,46,30,13,1,67,22,41,53,46,30,13,1,67,用用线线性性探测法解决冲突探测法解决冲突,建立的哈希的表为建立的哈希的表为:0 1 2 3 4 5 6 7 8比较次数比较次数：3 1 6 3 2 1 1 2 3 1 6 3 2 1 1 222415346301316781819平均查找长度平均查找长度ASL=(3+1+6+3+2+1+1+2)=ASL=(3+1+6+3+2+1+1+2)=查找查找key=67 key=67 比较两次找到比较两次找到,查找成功查找成功;查找查找key=21 key=21 比较比较8 8次找不到次找不到,查找失败。查找失败。48 链地址法处理冲突链地址法处理冲突以上述数列为例，产生的哈希表为：以上述数列为例，产生的哈希表为：123456741 1 46 13 30 225367H(22)=H(46)=H(30)=6H(22)=H(46)=H(30)=6H(53)=H(13)=5H(53)=H(13)=5H(67)=3H(67)=3H(41)=H(1)=1H(41)=H(1)=1平均查找长度平均查找长度ASL=(1+1+1+1+2+2+2+3)=8 181349思考题思考题1 1：长度为：长度为1212的按关键字有序的查找表采用顺的按关键字有序的查找表采用顺序组织方式，若采用二分查找法，则在等序组织方式，若采用二分查找法，则在等概的情况下，查找失败时的概的情况下，查找失败时的ASLASL值为？查找值为？查找成功时的成功时的ASLASL值？值？答案：成功时：答案：成功时：37/1237/12；失败时：；失败时：49/1349/132 2、哈希表平均、哈希表平均ASLASL的计算的计算50