二叉树-查找-遍历课件.ppt

《二叉树-查找-遍历课件.ppt》由会员分享，可在线阅读，更多相关《二叉树-查找-遍历课件.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 查找(Search)7.1 7.1 查找基本概念查找基本概念7.2 7.2 基于线性表基于线性表静态查找静态查找7.3 7.3 基于基于树表动态查找树表动态查找7.4 7.4 哈希查找哈希查找1/11/20231第7章 查找Introduction查找查找是非数值处理中一种最基本、最重要的操作是非数值处理中一种最基本、最重要的操作。查找查找，也称检索，是一种运算，是软件设计中经常，也称检索，是一种运算，是软件设计中经常遇到的一种运算。数据结构不同，查找方法也会不遇到的一种运算。数据结构不同，查找方法也会不同。查找方法的好坏直接影响着计算机的使用效率。同。查找方法的好坏直接影响着计算机的

2、使用效率。查找概述查找概述1/11/20232第7章 查找7.1、查找基本概念1 1）查找）查找 Search Search：又称又称检索检索，是指在大量的数据中，是指在大量的数据中寻找关键寻找关键字等于给定值字等于给定值的记录。若存在这样一个记录，则称查找的记录。若存在这样一个记录，则称查找成功，否则称查找不成功。成功，否则称查找不成功。分为分为:静态查找静态查找;动态查找动态查找;2 2）关键字）关键字(Keyword)(Keyword)：就是数据元素中可以唯一标识一个就是数据元素中可以唯一标识一个数据元素的数据项。数据元素的数据项。例如：学生管理登记卡中的学号。例如：学生管理登记卡中的学

3、号。3 3）平均查找长度）平均查找长度(Average Search Length)(ASL)(Average Search Length)(ASL)算法评价算法评价:评价时考虑：（评价时考虑：（1 1）速度；速度；（2 2）占用存储空间；占用存储空间；（3 3）复杂程度。复杂程度。1/11/20233第7章 查找 引入平均查找长度，作为查找算法评价的依据。引入平均查找长度，作为查找算法评价的依据。平均查找长度：为确定记录在表中的位置所进行的平均查找长度：为确定记录在表中的位置所进行的和关键字比较的次数的期望值，简写为和关键字比较的次数的期望值，简写为ASL.ASL.含有含有n n个元素的表中

4、找一个元素成功的个元素的表中找一个元素成功的ASLASL为：为：P Pi i为查找第为查找第i i个元素的概率；个元素的概率；C Ci i为为 查到第查到第i i个元素所需的比较次数。个元素所需的比较次数。ASL=Pi Cii=1i=1n n1/11/20234第7章 查找结构体数组 typedef structtypedef struct char name10;char name10;KeyType key;KeyType key;DataType;DataType;DataType rMaxnum;DataType rMaxnum;name0name9keyr0r1rMaxnumname

5、0name9key设表中记录以顺序存储结构组织。设表中记录以顺序存储结构组织。每个记录包括：关键字，其他数据项等。每个记录包括：关键字，其他数据项等。其类型说明用其类型说明用C C语言描述如下：语言描述如下：4)4)类型说明：类型说明：1/11/20235第7章 查找 5 5）查找方法）查找方法:顺序表静态查找，顺序表静态查找，树表动态查找，哈希查找树表动态查找，哈希查找7.27.2、基于线性表的静态查找、基于线性表的静态查找 顺序表上的查找主要有三种方法顺序表上的查找主要有三种方法:顺序查找法顺序查找法:针对顺序表存储结构针对顺序表存储结构 折半查找法折半查找法:针对有序顺序表存储结构针对有

6、序顺序表存储结构 分块查找分块查找:针对索引顺序表存储结构针对索引顺序表存储结构 1/11/20236第7章 查找i=01826322137566475i=1i=5i=4i=3i=2基本思想：从第一个元素开始，将给定值与表基本思想：从第一个元素开始，将给定值与表中逐个元素的关键字比较，直至检索成功或直中逐个元素的关键字比较，直至检索成功或直至最后一个元素检索失败为止。至最后一个元素检索失败为止。1.1.顺序查找：顺序查找：1/11/20237第7章 查找int Seqsearch(DataType r ,int key,int n)int i=0;while (r i.key!=key&i n

7、)i+;if (r i.key=key)return i ;else return -1 ;顺序查找算法：顺序查找算法：i=01826322137566475i=1i=5i=4i=3i=2演示：查找演示：查找key=56key=561/11/20238第7章 查找算法分析：算法分析：ASL=Pi Ci =1/n (1+2+.+n)*2 =n+1i=1n表从表从r r1-rMax,r01-rMax,r0存放存放keykey。改进算法：改进算法：希望尽量减少比较次数。希望尽量减少比较次数。1/11/20239第7章 查找32int seqsearch(DataType r,int key,int

8、n)int i;r0.key=key;i=n;while(ri.key!=key)i-;return i;i=81826322137566475i=7i=6i=5i=4i=30 1 2 3 4 5 6 7 8演示：查找演示：查找 key=32key=321/11/202310第7章 查找算法分析算法分析算法简单，效率较低算法简单，效率较低算法特点算法特点ASL=Pi Ci =(1/n)(1+2+.+n)=(n+1)/2i=1n1/11/202311第7章 查找2.折半查找法（对半或二分查找）折半查找法（对半或二分查找）针对有序表使用的查找方法，是简单有效的方法。针对有序表使用的查找方法，是简单

9、有效的方法。有序表：有序表：记录的关键字以记录的关键字以递增（或递减）递增（或递减）顺序排列的表。顺序排列的表。基本思想：基本思想：给定值给定值keykey与中间位置的记录的关键字比与中间位置的记录的关键字比 较，若相等则查找成功；若给定值大于中间较，若相等则查找成功；若给定值大于中间 位置记录的关键字值，则在表的后半部分继位置记录的关键字值，则在表的后半部分继 续折半查找；否则在表的前半部分进行折半续折半查找；否则在表的前半部分进行折半 查找，直至查找成功或不成功。查找，直至查找成功或不成功。1/11/202312第7章 查找步骤：步骤：（1 1）计算中间位置）计算中间位置 mid=(low

10、+high)/2mid=(low+high)/2取整。取整。（2 2）keykey与与Rmid.keyRmid.key比较比较 若若key=Rmid.keykey=Rmid.key则查找成功；则查找成功；若若keyRmid.key,keyRmid.key,keyRmid.key,则则low=mid+1,low=mid+1,转（转（3 3）。）。（3 3）若）若lowhigh,lowhigh,则重复（则重复（1 1）否则：查找不成功，结束。否则：查找不成功，结束。1/11/202313第7章 查找Searchlow1826324552668091highmid52668091 lowhighmi

11、d8091highLowmid用折半查找法在顺序表中用折半查找法在顺序表中查找关键字为查找关键字为8080的记录！的记录！1/11/202314第7章 查找low1826324552668091highmid lowhighmidhighLowmid18263245526680911826324552668091 low1826324552668091 high查找关键字为查找关键字为1010的记录！的记录！注意：使用折注意：使用折半查找算法时，半查找算法时，线性表中的元线性表中的元素必须按照关素必须按照关键字键字排列有序排列有序；并且必须以并且必须以顺顺序存储方式序存储方式存存储。储。1/1

12、1/202315第7章 查找int binsearch(DataType r,int n,int key)int binsearch(DataType r,int n,int key)int low,high,mid;int low,high,mid;low=0;low=0;high=n-1;high=n-1;while(low=high)while(low rmid.key)else if(key rmid.key)low=mid+1;low=mid+1;else high=mid-1;else high=mid-1;returu 1;returu 1;初始化初始化循环条件循环条件计算中间下

13、标计算中间下标查找成功查找成功前半部分前半部分后半部分后半部分查找失败查找失败1/11/202316第7章 查找int binsearch(DataType r,int n,int key)int low,high,mid;low=0;high=n-1;while(low rmid.key)low=mid+1;else high=mid-1;returu 1;low1826324552668091highmid52 66 80 91lowhighmid80 91highLow mid用折半查找法在顺序表中用折半查找法在顺序表中查找关键字为查找关键字为8080的记录！的记录！1/11/20231

14、7第7章 查找假设：查找关键字为假设：查找关键字为0-60-6的数据的数据折半法算法分析折半法算法分析3564102二叉判定树二叉判定树n假设：有序表长度为假设：有序表长度为n,n,且且n2n2h h-1-1n若若n=2n=2h h-1-1则：查找过程为一棵深度为则：查找过程为一棵深度为h h的满二叉树的满二叉树,n查找的过程形成二叉判定树查找的过程形成二叉判定树nASL=1/7(1+22+43)ASL=1/7(1+22+43)=2.43 =2.431/11/202318第7章 查找比顺序查找效率高比顺序查找效率高只适用于有序的顺序存储的表，只适用于有序的顺序存储的表，算法特点算法特点:ASL

15、log2(n+1)-1ASL=(1/n)2i-1 ii=1n则满二叉树的第则满二叉树的第 i i 层有层有2 2i-1i-1个结点。个结点。1/11/202319第7章 查找3.3.分块查找（索引顺序表查找）分块查找（索引顺序表查找）将顺序查找法与折半查找法结合将顺序查找法与折半查找法结合 基本思想：基本思想：使用分块查找算法时，要求将线性表均匀地使用分块查找算法时，要求将线性表均匀地分成若干分成若干块块，每块的元素不要求有序，但一，每块的元素不要求有序，但一定要保证定要保证块间有序块间有序。另外，对表要进行索引。另外，对表要进行索引存储。即新建一个索引表，存放各块中最大存储。即新建一个索引表

16、，存放各块中最大关键字。关键字。分块查找实际上是分块查找实际上是先先在索引表中进行在索引表中进行顺序查顺序查找找或或折半查找折半查找，再再在块内进行在块内进行顺序查找。顺序查找。1/11/202320第7章 查找索引表类型索引表类型:1.1.对单关键字建立索引表对单关键字建立索引表:2.2.对多关键字建立索引表对多关键字建立索引表:完全索引表完全索引表,多级索引表多级索引表.3.3.分块个数建立索引表分块个数建立索引表:等长等长,不等长不等长主表主表索引表索引表主表主表完全索完全索引表引表索引表索引表分块查找的基本过程如下：分块查找的基本过程如下：(1)(1)首先，将待查关键字首先，将待查关键

17、字K K与索引表中的关与索引表中的关键字进行比较，以确定待查记录所在的块。具键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。体的可用顺序查找法或折半查找法进行。(2)(2)进一步用顺序查找法，在相应块内查进一步用顺序查找法，在相应块内查找关键字为找关键字为K K的元素。的元素。1/11/202321第7章 查找 例如：例如：17 17，8 8，2121，1919，3131，3333，2525，2222，43 43，3737，35,4035,40，6161，7878，7373，5555分块分块1717，8 8，2121，1919，3131，3333，2525，2222

18、，43 43，3737，3535，40,6140,61，7373，7878，5555索引表：索引表：21 33 43 7821 33 43 7821334378关键字关键字 地址地址数据表数据表82131332543613735737819224055171/11/202322第7章 查找 typedef struct char name10;KeyType key;DataType;DataType rMax;typedef struct KeyType key;int link;indextype;indextype Lrm索引表结构：索引表结构：顺序表结构：顺序表结构：表结构说明：表结构

19、说明：1/11/202323第7章 查找int indexsearch(indextype Lr,DataType r,int key,int L,int m)int i,j;i=0;/*在索引表中顺序查找在索引表中顺序查找*/while(im&Lri.key=m)return-1;else /*在顺序表中顺序查找在顺序表中顺序查找*/j=Lri.link;while(key!=rj.key&j-Lri.linkL)j+;if(key=rj.key)return j;else return-1;索引表：索引表：Lr0 Lr0m-1m-1顺序表：顺序表：r r块长度：块长度：L L限制查找限制查

20、找的范围的范围1/11/202324第7章 查找int indexsearch(indextype Lr,DataType r,int key,int L,int m)int i,j;i=0;/*在索引表中顺序查找在索引表中顺序查找*/while(im&Lri.key=m)return-1;else /*在顺序表中顺序查找在顺序表中顺序查找*/j=Lri.link;while(key!=rj.key&j-Lri.linkL)j+;if(key=rj.key)return j;else return-1;演示演示:key=25:key=25L=4;M=3L=4;M=321033443882131

21、332543373519224017LrKey linkri=0i=1j=4j=5j=61/11/202325第7章 查找索引表采用顺序查找索引表采用顺序查找算法分析算法分析假设：长度为假设：长度为n n的顺序表分成的顺序表分成m m块，每块长度为块，每块长度为L,L,ASLb=(1/m)i =(m+1)/2i=1mASLw=(1/L)i =(L+1)/2i=1L块内采用顺序查找块内采用顺序查找ASLblocks=(m+1)/2+(L+1)/21/11/202326第7章 查找 效率介于顺序查找和折半查找之间效率介于顺序查找和折半查找之间 线性表存储结构为索引存储结构线性表存储结构为索引存储结

22、构算法特点算法特点索引表中采用折半查找索引表中采用折半查找ASLb=log2(m+1)-1ASLblocks=log2(m+1)-1+(L+1)/2ASLw=(L+1)/2总之：顺序表结构适用于查找操作，总之：顺序表结构适用于查找操作，不适于做插入和删除的操作。不适于做插入和删除的操作。1/11/202327第7章 查找7.3.7.3.基于树的查找基于树的查找用树结构存储记录既可查找又可插入和删除用树结构存储记录既可查找又可插入和删除1.1.树表查找方法：树表查找方法：二叉排序树查找二叉排序树查找 平衡二叉排序树查找平衡二叉排序树查找 B B-树查找树查找与折半查找类似，逐步缩小查找范围。与折

23、半查找类似，逐步缩小查找范围。2.2.二叉排序树查找二叉排序树查找1/11/202328第7章 查找(1)(1)二叉排序树的定义二叉排序树的定义:或是空树或是空树,或具有以下性质的二叉树或具有以下性质的二叉树:其左子树上所有结点的数据均其左子树上所有结点的数据均小于小于根结点的数据值根结点的数据值.其右子树上所有结点的数据均其右子树上所有结点的数据均大于或等于大于或等于根结点的根结点的数据值数据值.左、右子树又各是一棵二叉排序树。左、右子树又各是一棵二叉排序树。例：例：21181118201615101/11/202329第7章 查找（2 2）二叉排序树的生成）二叉排序树的生成生成一棵二叉排序

24、树生成一棵二叉排序树,过程如下过程如下:若二叉排序树为空，若二叉排序树为空，则令待插结点为根结点则令待插结点为根结点,若二叉排序树非空，若二叉排序树非空，则比较待插结点则比较待插结点(k1)(k1)和根结和根结点点(k2)(k2)的数据值。若的数据值。若k1k2,k1keykey)else if(s-keykey)t-L=insertbt(s,t-L);t-L=insertbt(s,t-L);else t-R=insertbt(s,t-R);else t-R=insertbt(s,t-R);return t;return t;1/11/202333第7章 查找插入的新结点都是二叉排序树的叶子结

25、插入的新结点都是二叉排序树的叶子结 点点.不必移动其它结点不必移动其它结点.常用于有序二叉树常用于有序二叉树 的插入的插入,删除删除.对二叉排序树采用中序遍历对二叉排序树采用中序遍历,其结果为一有序其结果为一有序序列序列.根结点的选择根结点的选择,决定二叉树的形状决定二叉树的形状,其形状决定其形状决定检索的效率检索的效率.根结点数据值最好选择元素序列根结点数据值最好选择元素序列的中间值的中间值.特点特点:1/11/202334第7章 查找BiTree*btsearch(BiTree*p,int key)/p指向二叉排序树的根结点指向二叉排序树的根结点while(p!=NULL)if(key=p

26、-key)return p;else if(keykey)p=p-L;else p=p-R;return NULL;结束条件结束条件查找成功查找成功在左子树中查找在左子树中查找在右子树中查找在右子树中查找查找失败查找失败3.3.二叉排序树查找二叉排序树查找1/11/202335第7章 查找BiTree*btsearch(BiTree*p,int key)/p指向二叉排序树的根结点指向二叉排序树的根结点while(p!=NULL)if(key=p-key)return p;else if(keykey)p=p-L;else p=p-R;return NULL;1510182118162511pp

27、pp演示：演示：Key=8Key=81/11/202336第7章 查找4.算法分析算法分析ASLlog2(n+1)-1二叉排序树查找与折半法查找类似，与关二叉排序树查找与折半法查找类似，与关键字比较的次数不会超过树的深度。键字比较的次数不会超过树的深度。最好情况：最好情况：二叉排序树为一棵平衡二叉树二叉排序树为一棵平衡二叉树最坏情况：最坏情况：二叉排序树为一棵单支树，二叉排序树为一棵单支树，与顺序查找情况相同。与顺序查找情况相同。(n+1)/2(n+1)/2适用于经常适用于经常做插入做插入,删删除和查找运除和查找运算的表算的表.1/11/202337第7章 查找7.4 7.4 哈希查找（散列查

28、找）哈希查找（散列查找）前述的查找方法建立在前述的查找方法建立在“比较比较”的基础的基础上，查找的次数依赖于查找过程中进行上，查找的次数依赖于查找过程中进行比较的次数。比较的次数。问题：问题：能否不用比较就能直接计算出记能否不用比较就能直接计算出记录的存储地址，从而找到所要的结点？录的存储地址，从而找到所要的结点？-采用散列（采用散列（hashhash）方法。）方法。1/11/202338第7章 查找1.1.哈希哈希(散列散列)表的基本概念表的基本概念哈希（又称杂凑、散列）的基本思想：哈希（又称杂凑、散列）的基本思想：以记录的关键字值以记录的关键字值k k为自变量，通过一定的函数关系为自变量，

29、通过一定的函数关系h h计算出对应的函数值计算出对应的函数值h(k),h(k),把这个值解释为记录的存储地址把这个值解释为记录的存储地址（哈希（哈希地址地址），将记录存入该地址中去。），将记录存入该地址中去。函数函数h-h-哈希函数哈希函数 h(k)-h(k)-哈希哈希地址地址基本区基本区-分配给哈希表的连续存储空间。分配给哈希表的连续存储空间。冲突的概念：冲突的概念：若对于不同的键值若对于不同的键值k1k1和和k2,k2,即即k1k1k2k2,但但h(k1)=h(k2)h(k1)=h(k2)，即具有相同的散列地址，称为冲突。即具有相同的散列地址，称为冲突。1/11/202339第7章 查找例

30、：例：key=3,15,20,24key=3,15,20,24，m=5m=5（连续内存长度），（连续内存长度），h(k)=k%mh(k)=k%m，h(15)=h(20)h(15)=h(20)，产生，产生冲突冲突。同义词同义词-发生冲突的两个或多个键值。发生冲突的两个或多个键值。哈希哈希(散列散列)表表-是根据设定的是根据设定的哈希哈希(散列散列)函数函数和和相应解决冲突的方法相应解决冲突的方法为一组结点建立的一张为一组结点建立的一张表表，表中的结点的存储位置依赖于，表中的结点的存储位置依赖于设定的哈希设定的哈希(散列散列)函数和处理冲突的方法。函数和处理冲突的方法。1/11/202340第7章

31、 查找哈希哈希(散列散列)表和查找表和查找哈希法主要包括以下两方面的内容哈希法主要包括以下两方面的内容：（1 1）如何选择一个好的哈希）如何选择一个好的哈希(散列散列)函数？要考函数？要考虑：虑：哈希哈希(散列散列)函数简单；将键值均匀地分布在整个函数简单；将键值均匀地分布在整个地址空间，使冲突机会尽量少。地址空间，使冲突机会尽量少。（2 2）如何解决冲突）如何解决冲突?选定一个解决冲突的办法（即如何存储冲突的同选定一个解决冲突的办法（即如何存储冲突的同义词）。义词）。下面分别介绍：下面分别介绍：假设假设:有有n n个数据元素个数据元素,存放在存放在m m个内存单元个内存单元.通常通常mnmn

32、。1/11/202341第7章 查找2.2.几种常用的哈希函数几种常用的哈希函数（1 1）直接定址法：）直接定址法：当关键字是整型数时，取关键字作为哈希地址。当关键字是整型数时，取关键字作为哈希地址。H(k)=k H(k)=k 或或H(k)=ak+b H(k)=ak+b（a a，b b为常数）为常数）特点：简单；浪费空间；特点：简单；浪费空间；例：一组关键码：例：一组关键码：例：一组关键码：例：一组关键码：942148,941269,940527,941630,942148,941269,940527,941630,941805,941558,942047,940001 941805,9415

33、58,942047,940001。散列函数为散列函数为散列函数为散列函数为 HH(k k)=)=k k -940000 940000 则有则有则有则有HH(942148)=2148 (942148)=2148 HH(941269)=1269(941269)=1269 H H(940527)=527 (940527)=527 HH(941630)=1630(941630)=1630 H H(941805)=1805 (941805)=1805 HH(941558)=1558(941558)=1558 H H(942047)=2047 (942047)=2047 HH(940001)=1(9400

34、01)=11/11/202342第7章 查找u（2 2）除留余数法：）除留余数法：选择一个适当的正整数选择一个适当的正整数P P，用，用P P去除键值，取其余数作为去除键值，取其余数作为散列地址，散列地址，即：即：h(kh(k)=k%P)=k%PP P的取法：小于等于的取法：小于等于哈希表表长哈希表表长 m m的最大素数的最大素数.例如，已知待散列元素为（例如，已知待散列元素为（18,7518,75，6060，4343，5454，9090，4646），），表长表长m=10m=10，p=7p=7，则有则有H(18)=18%7=4 H(75)=75%7=5 H(60)=60%7=4 H(18)=1

35、8%7=4 H(75)=75%7=5 H(60)=60%7=4 H(43)=43%7=1 H(54)=54%7=5 H(90)=90%7=6 H(46)=4 H(43)=43%7=1 H(54)=54%7=5 H(90)=90%7=6 H(46)=4 冲突较多。为减少冲突，可取较大的冲突较多。为减少冲突，可取较大的m m值和值和p p值，值，如如:m=p=13:m=p=13，结果如下：结果如下：1/11/202343第7章 查找H(18)=18%13=5 H(75)=75%13=10 H(60)=60%13=8 H(18)=18%13=5 H(75)=75%13=10 H(60)=60%13=

36、8 H(43)=43%13=4 H(54)=54%13=2 H(90)=90%13=12 H(43)=43%13=4 H(54)=54%13=2 H(90)=90%13=12 H(46)=46%13=7 H(46)=46%13=7 P P最好取最好取1.1n1.1n1.7n1.7n的素数的素数。n例：例：设设 n=7 n=7，P=11 P=11或或13 13 n则：则：n=100 P=113,127,139 n=100 P=113,127,1395443 1846 6075900 1 2 3 4 5 6 7 8 9 10 11 12 1/11/202344第7章 查找u（3 3）数字分析法数字

37、分析法 设有设有设有设有 n n 个个个个 d d 位数，每一位可能有位数，每一位可能有位数，每一位可能有位数，每一位可能有 r r 种不同的符号。种不同的符号。种不同的符号。种不同的符号。这这这这 r r 种不同的符号在各位上出现的频率不一定相同，可能种不同的符号在各位上出现的频率不一定相同，可能种不同的符号在各位上出现的频率不一定相同，可能种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某在某些位上分布均匀些；在某些位上分布不均匀，只有某在某些位上分布均匀些；在某些位上分布不均匀，只有某在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号

38、经常出现。可根据散列表的大小，选取其中各种几种符号经常出现。可根据散列表的大小，选取其中各种几种符号经常出现。可根据散列表的大小，选取其中各种几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。符号分布均匀的若干位作为散列地址。符号分布均匀的若干位作为散列地址。符号分布均匀的若干位作为散列地址。n n计算各位数字中符号分布的均匀度计算各位数字中符号分布的均匀度计算各位数字中符号分布的均匀度计算各位数字中符号分布的均匀度 k k 的公式：的公式：的公式：的公式：n n其中，其中，其中，其中，i ik k表示第表示第表示第表示第 i i 个符号在第个符号在第个符号在

39、第个符号在第 k k 位上出现的次数，位上出现的次数，位上出现的次数，位上出现的次数，n n/r r 表示各种符号在表示各种符号在表示各种符号在表示各种符号在 n n 个数中均匀出现的期望值。计算出的个数中均匀出现的期望值。计算出的个数中均匀出现的期望值。计算出的个数中均匀出现的期望值。计算出的 k k 值越小，表明在该位值越小，表明在该位值越小，表明在该位值越小，表明在该位 (第第第第k k 位位位位)各种符号分布得越均匀。各种符号分布得越均匀。各种符号分布得越均匀。各种符号分布得越均匀。1/11/202345第7章 查找例例:9 4 2 1 4 8 9 4 2 1 4 8 位，位，位，位，

40、1 1=510.60=510.60 9 4 1 2 6 9 9 4 1 2 6 9位，位，位，位，2 2=510.60=510.60 9 4 0 5 2 7 9 4 0 5 2 7位，位，位，位，3 3=110.60 =110.60 9 4 1 6 3 0 9 4 1 6 3 0位，位，位，位，4 4=110.60 =110.60 9 4 1 8 0 5 9 4 1 8 0 5位，位，位，位，5 5=110.60=110.60 9 4 1 5 5 8 9 4 1 5 5 8位，位，位，位，6 6=110.60=110.60 9 4 2 0 4 7 9 4 2 0 4 7 9 4 0 0 0 1

41、 9 4 0 0 0 1 数字分析法仅适用于事先明确知道表中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。选择哪几位要重新决定。选择哪几位要重新决定。选择哪几位要重新决定。n n若散列表地址范围有若散列表地址范

42、围有若散列表地址范围有若散列表地址范围有 3 3 3 3 位数字位数字位数字位数字,取各关键码的取各关键码的取各关键码的取各关键码的位做为位做为位做为位做为记录的散列地址。也可以把第记录的散列地址。也可以把第记录的散列地址。也可以把第记录的散列地址。也可以把第，和第和第和第和第位相加，舍去位相加，舍去位相加，舍去位相加，舍去进位位，变成一位数，与第进位位，变成一位数，与第进位位，变成一位数，与第进位位，变成一位数，与第，位合起来作为散列地址。还位合起来作为散列地址。还位合起来作为散列地址。还位合起来作为散列地址。还有其它方法。有其它方法。有其它方法。有其它方法。1/11/202346第7章 查

43、找n（4 4）折叠法）折叠法vv 此方法把关键码自左到右分成位数相等的几部分，每一部此方法把关键码自左到右分成位数相等的几部分，每一部此方法把关键码自左到右分成位数相等的几部分，每一部此方法把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数分的位数应与散列表地址位数相同，只有最后一部分的位数分的位数应与散列表地址位数相同，只有最后一部分的位数分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。可以短一些。可以短一些。可以短一些。vv 把这些部分的数据叠加起来，就可以得到具有该关键码的把这些部分的数据叠加起来，就可以得到具有该关键码的把这

44、些部分的数据叠加起来，就可以得到具有该关键码的把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。记录的散列地址。记录的散列地址。记录的散列地址。vv 两种叠加方法：两种叠加方法：两种叠加方法：两种叠加方法：移位法移位法移位法移位法 把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；分段分段分段分段折叠法折叠法折叠法折叠法 各部分不折断，沿各部分的分界来回折叠，各部分不折断，沿各部分的分界来回折叠，各部分不折断，沿各部分的分界来回折叠，各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。然后对

45、齐相加，将相加的结果当做散列地址。然后对齐相加，将相加的结果当做散列地址。然后对齐相加，将相加的结果当做散列地址。例：设给定的关键码为例：设给定的关键码为例：设给定的关键码为例：设给定的关键码为 keykey=23938587841=23938587841，若存储空若存储空若存储空若存储空间限定间限定间限定间限定 3 3 位位位位,则划分结果为每段则划分结果为每段则划分结果为每段则划分结果为每段 3 3 位位位位.上述关键码可划分上述关键码可划分上述关键码可划分上述关键码可划分为为为为 4 4段：段：段：段：239239 385385 878878 41411/11/202347第7章 查找n

46、 n把超出地址位数的最高位删去把超出地址位数的最高位删去把超出地址位数的最高位删去把超出地址位数的最高位删去,仅保留最低的仅保留最低的仅保留最低的仅保留最低的3 3位，做为可位，做为可位，做为可位，做为可用的散列地址。用的散列地址。用的散列地址。用的散列地址。239239 385385 878878 4141分段折叠分段折叠1/11/202348第7章 查找u（5 5）平方取中法）平方取中法n n此方法在词典处理中使用十分广泛。它先计算构成关键此方法在词典处理中使用十分广泛。它先计算构成关键此方法在词典处理中使用十分广泛。它先计算构成关键此方法在词典处理中使用十分广泛。它先计算构成关键码的标识

47、符的内码的平方，然后按照散列表的大小取中间码的标识符的内码的平方，然后按照散列表的大小取中间码的标识符的内码的平方，然后按照散列表的大小取中间码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。的若干位作为散列地址。的若干位作为散列地址。的若干位作为散列地址。n n设标识符可以用一个计算机字长的内码表示。因为内码设标识符可以用一个计算机字长的内码表示。因为内码设标识符可以用一个计算机字长的内码表示。因为内码设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对平方数的中间几位一般是由标识符所有字符决定，所以对平方数的中间几位一般是

48、由标识符所有字符决定，所以对平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同，即使其中有不同的标识符计算出的散列地址大多不相同，即使其中有不同的标识符计算出的散列地址大多不相同，即使其中有不同的标识符计算出的散列地址大多不相同，即使其中有些字符相同。些字符相同。些字符相同。些字符相同。n当无法确定关键字中哪几位分布较均匀时，当无法确定关键字中哪几位分布较均匀时，可以先求出可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都希地址。这是因为：平方后中

49、间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。相关，故不同关键字会以较高的概率产生不同的哈希地址。1/11/202349第7章 查找例如：下列八进制数的关键字及其哈希地址例如：下列八进制数的关键字及其哈希地址关键字关键字(关键字关键字)2 2哈希地址哈希地址0100001000001011001210000210120014400004401160137040037020614310541310206243147043142161473474173421624741304741216347456517451/11/202350第7章 查找(6).(6).伪随机数法

50、伪随机数法 采用一个伪随机函数作哈希函数，采用一个伪随机函数作哈希函数，即即H(key)=random(key)H(key)=random(key)。在在实实际际应应用用中中，应应根根据据具具体体情情况况，灵灵活活采采用用不不同同的的方法。方法。通常应考虑以下五个因素：通常应考虑以下五个因素：u计算哈希函数所需的时间（简单）。计算哈希函数所需的时间（简单）。u关键字的长度。关键字的长度。u哈希表的大小。哈希表的大小。u关键字的分布情况。关键字的分布情况。u记录查找的频率。记录查找的频率。1/11/202351第7章 查找3.3.哈希冲突解决方法哈希冲突解决方法四种处理冲突的基本方法：四种处理冲