数据结构-查找算法.ppt

第10章 查找 10.1 查找的基本概念 10.2 静态查找表 1.顺序表 10.3 动态查找表 构造哈希表时 ，冲突是不可避免的，有关因素主要有如下三个： 2.哈希函数的构造方法 一、除留余数法 三、数字分析法 一、开放定址法 (2)平方探查法 二、链表法 100 20 60 120 180 5 10 25 40 80 110 116 132 189 200 100 20 60 120 180 5 10 25 40 80 116 132 189 200 (a)初始状态 (b)删去110后的状态 （b）假如要删除关键字结点的关键字个数n等于m/2+1，说明删去该关键字后该结点将不满足B_树的定义，此时若该结点的左（或右）兄弟结点中关键字个数n大于m/2+1，则把该结点的左（或右）兄弟结点中最大（或最小）的关键字上移到双亲结点中，同时把双亲结点中大于（或小于）上移关键字的关键字下移到要删除关键字的结点中，这样删去关键字后该结点以及它的左（或右）兄弟结点都仍旧满足B_树的定义。其过程如图(c)所示 100 20 40 120 180 5 10 25 60 116 132 189 200 (c)删去40后的状态 100 20 40 180 5 10 25 60 120 132 189 200 (d)删去116后的状态 （c）假如要删除关键字结点的关键字个数n等于m/2+1并且该结点的左和右兄弟结点（如果存在的话）中关键字个数n均等于m/2+1，这时需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。其过程如图(d)所示 另一种是在非叶结点上删除关键字。在非叶结点上删除关键字时，假设要删除关键字Ki（1≤i≤n），在删去该关键字后，以该结点Pi所指子树中的最小关键字Kmin来代替被删关键字Ki所在的位置（Pi所指子树中的最小关键字Kmin一定是在叶结点上），然后再以指针Pi所指结点为根结点查找并删除Kmin(在非叶结点上删除问题就转化成了叶结点上的删除问题)。其过程如图(e)所示 100 20 40 189 5 10 25 60 120 132 200 (e)删去189后的状态 10.4 哈希表 哈希函数：数据元素的关键字和该数据元素的存放位置之间的映射函数 哈希表：通过哈希函数来确定数据元素存放位置的一种特殊表结构。 1.哈希表的基本概念 构造方法是：设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续内存单元，分别以每个数据元素的关键字Ki为（0≤i≤n-1）为自变量，通过哈希函数h(Ki)，把Ki映射为内存单元的某个地址h(Ki)，并把该数据元素存储在这个内存单元中。哈希函数h(Ki)实际上是关键字Ki到内存单元的映射，因此，h(Ki)也称为哈希地址，哈希表也称作散列表。 构造哈希表时出现Ki≠Kj（i≠j）,但h(Ki)=h(Kj)的现象称作哈希冲突。这种具有不同关键字而具有相同哈希地址的数据元素称作“同义词”，由同义词引起的冲突称作同义词冲突。 解决哈希冲突的基本思想是通过哈希冲突函数（设为hl(K)（l=1,2,…,m-1））产生一个新的哈希地址使hl(Ki)≠hl(Kj)。把要存储的n个数据元素通过哈希函数映射到了m个连续内存单元中，从而完成了哈希表的构造。 可见，构造哈希表时一定要使用主关键字，不能使用次关键字。 例10-3 建立数据元素集合a的哈希表,a = {180,750,600,430,541,900,460},并比较m取值不同时的哈希冲突情况。 (1)装填因子。装填因子是指哈希表中已存入的数据元素个数ｎ与哈希地址空间大小ｍ的比值，即α＝ｎ/ｍ，α越小，冲突的可能性就越小，但哈希表中空闲单元的比例就越大； α越大（最大可取1）时，冲突的可能性就越大，但哈希表中空闲单元的比例就越小，存储空间的利用率就越高。 (2)与所采用的哈希函数有关。 (3)与解决哈希冲突的哈希冲突函数有关。 常用的哈希函数构造方法有： 1.除留余数法 2.直接定址法 3.数字分析法 函数设计目标:使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上，同时使计算过程尽可能简单以达到尽可能高的时间效率。 h(K) = K mod m 优点：计算简单，适用范围广 关键：选好哈希表长度m 技巧：哈希表长m取质数时效果最好 二、直接定址法 h(K)