DS11查找与散列结构

1、DS11查找与散列结构主要内容根本概念静态查找表 动态查找表 哈希Hash表及其查找 查找查找表：由同一类型的数据元素或记录构成的集合。查找表的根本操作1) 查询某个“特定的数据元素是否在表中2) 检索某个“特定的数据元素的各种属性3) 插入一个数据元素4) 删去某个数据元素静态查找表：只作查询和检索操作的查找表。动态查找表：在查找过程中同时作插入或删除操作的查找表。 查找关键字：能标识一个数据元素或记录的数据项。主关键字：能唯一地标识一个记录的关键字。次关键字：用以识别假设干记录的关键字。 学号 姓名 专业 年龄 20030001 李莫愁 计算机 17 20030002 高 手 计算机 18

2、 20030003 王重阳 计算机 18 20030004 张无忌 信息工程 20 20030005 高 手 信息工程 19 查找 学号 姓名 专业 年龄 20030001 李莫愁 计算机 17 20030002 高 手 计算机 18 20030003 王重阳 计算机 18 20030004 张无忌 信息工程 20 20030005 高 手 信息工程 19查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，假设表中存在这样的记录，那么称查找成功，查找结果为记录信息或其位置；否那么称为查找不成功，查找结果通常为0或NULL。 查找查找方法评价：平均查找长度平均查找长度A

3、SL ( Average Search Length)：为确定记录在表中的位置，需和给定值进展比较的关键字的个数的期望值叫查找算法的平均查找长度。用于度量查找算法的效率时间复杂度 Ci：查找到第 i 个记录所需的比较次数 Pi：查找到第 i 个记录的概率 平均查找长度ASL = PiCi ( Pi=1 ) 查找静态查找在指定的表中查找某一个“特定的数据元素是否存在，检索某一个“特定数据元素的各种属性。动态查找在查找的过程中同时插入表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。静态查找顺序表的查找：顺序查找有序表的查找：折半查找索引顺序表的查找：分块查找静态查找表查找表可用线性表

4、表示L1=(45,61,12,3,37,24,90,53,98,78顺序查找从最后一个第一个记录开场，逐个进展比较 查找不成功的标记 用顺序表表示静态查找表 用线性链表表示静态查找表 静态查找表第 10 页顺序表类型定义 typedef struct ElemType *elem; / 0号单元留空 int length; SSTable;静态查找表 0 1 2 3 4 5 6 7 8 9 10 m-1 45 61 12 3 37 24 90 53 98 78ST.elemSSTable ST;10第 11 页int Search_Seq ( SSTable ST, KeyType key )

5、 /在顺序表ST中顺序查找其关键字等于key的数据元素。假设找到，那么函数值为该元素在表中的位置，否那么为0。 ST.elem0.key = key; / “哨兵 for ( i=ST.length; !EQ(key, ST.elemi.Key); -i )； return i; / 假设表中不存在待查元素, i=0 /Search_Seq静态查找表 0 1 2 3 4 5 6 7 8 9 10 m-1 45 61 12 3 37 24 90 53 98 78ST.elemkey免去查找过程中每一步都要检测整个表是否查找完毕11第 12 页例1：在下表中查找 key = 8 的结点。静态查找表

6、8012n-3n-2n-1nST.elem key100100713iiiiiii查找不成功，i = 08012n-3n-2n-1nST.elem key例2：在下表中查找 key = 8 的结点。100100813iii查找成功，i = n-212顺序查找特点无排序要求；算法简单；存储构造：顺序、链式；效率不高 静态查找表查找表：用有序表表示查找方法：折半查找二分查找查找过程：先确定待查记录所在的范围区间，然后逐步缩小范围直到找到或找不到该记录为止。例：有原始查找表45,61,12,3,37,24,90,53,98,78为进展折半查找，需要先进展排序： L=(3,12,24,37,45,53

7、,61,78,90,98) 静态查找表-有序表查找例：查找 Key=24 的记录。 静态查找表-有序表查找 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98lowmid high 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98lowmid high 2445 2412 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98Low highmidbool Search_Bin ( SSTable ST, KeyType key ) /在有序表ST中折半

8、查找法查找其关键字等于key的数据元素。假设找到，那么返回该元素在表中的位置，否那么返回false。 low=1; high=ST.length; while ( lowkey，因此令highmid1high=7mid=4low=1low=1high=3mid=2此时ST.elemmid.key5 key，因此令highmid1low=1mid=1此时ST.elemmid.key4 high查找不成功折半查找的特点要求元素按关键字有序。存储构造：顺序。 静态查找表-有序表查找查找表的组织：分块有序，除表本身以外，尚需建立一个“索引表。查找方法：查找索引表；在数据块内顺序查找 静态查找表-索引顺

9、序表的查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38查找方法比较 静态查找表ASL最大最小两者之间表构造有序表、无序表有序表分块有序表存储构造顺序存储构造线性链表顺序存储构造顺序存储构造线性链表顺序查找折半查找分块查找动态查找二叉排序树：或者是一棵空树；或者是具有以下性质的二叉树： 1假设左子树不空，那么左子树上所有结点的值均小于根结点的值； 2假设右子树不空，那么右子树上所有结点的值均大于根结点的值； 3根

10、结点的左、右子树也分别为二叉排序树。 动态查找表二叉排序树的查找过程1假设给定值等于根结点的关键字，那么查找成功；2假设给定值小于根结点的关键字，那么继续在左子树上进展递归查找；3假设给定值大于根结点的关键字，那么继续在右子树上进展递归查找。从根结点开场，假设二叉排序树为空，那么查找不成功；否那么，在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 查找成功 查找不成功性能分析查找表：3,12,24,37,45,53,61,78,90,98 动态查找表 45 12 3 37

11、 53 90 24 78 98 61ASL=(1+22+34+43)/10 4512337539024789861单支树一般情况下，没有对二叉排序树的深度进展控制。在构造二叉排序树的过程中进展“平衡化处理，成为平衡二叉树AVL树。平衡二叉树：左子树和右子树的深度之差的绝对值不超过1。 动态查找表二叉排序树的特点动态查找 (插入删除的时机)含有n个结点的二叉排序树不唯一，与结点插入的顺序有直接关系。删除某个结点后，二叉排序树要重组。可得到平衡二叉树。二叉排序树的适用范围用于组织规模较小的、内存中可以容纳的数据。对于数据量较大必须存放在外存中的数据，那么无法快速处理。 动态查找表问题引入：前面讨论

12、的各种构造，记录在构造中的相对位置是随机的，和记录的关键字之间不存在确定关系，因此，在构造中查找记录时需要进展一系列和关键字的比较。 哈希表理想情况是希望不经过任何比较，一次存取就能得到所查记录解决方法：在记录的存储位置和其关键字之间建立一个确定的对应关系f，使每个关键字和构造中的唯一的存储位置相对应。 在查找时，只要根据该对应关系f可找到给定值K的存储位置f(K)。假设构造中存在关键字和K相等的记录，那么一定在f(K)的存储位置上，所以不需要进展比较即可直接得到所查记录。哈希表：对应关系f为哈希函数，根据上述思想建立的表为哈希表。 哈希表 哈希表根本概念哈希函数构造方法哈希函数冲突处理根本思

13、想： 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。即：通过简单计算直接得到数据的地址。1) 哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字。 哈希表关键字集合存储地址集合hash2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突现象，即：key1 key2，而 f(key1) = f(key2)。3) 很难找到一个

14、不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 哈希表 1 2 3 51 52年份人数 1949 1950 1951 1999 2000 2000 2100 2200 4400 4420例 某地区的人口统计表H(年度）=年度-1948 哈希表例 30个地区的各民族人口统计表编号 地区 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19哈希表应用哈希函数，由记录

15、的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找又叫散列查找，利用哈希函数进展查找的过程叫哈希查找。 哈希表哈希函数的构造方法 构造哈希函数的准那么：使关键字经过哈希函数得到一个“随机的地址，以便使一组关键字的哈希地址均匀地分布在逐个地址区间，从而减少冲突。 常用的构造方法：1直接定址法：取关键字或关键字的某个线性函数值为哈希地址,如年龄。2数字分析法：假设关键字是以 r 为基的数，并且哈希表中可能出现的关键字都是事先知道的，那么可取关键字的假设干数位组成哈希地址 哈希表 常用的构造方法：2数字分析法：假设事先知道关键字集合，且关键字的位数比哈希表的地址位数多，

16、那么可选取数字分布比较均匀的假设干位作为散列地址。例如，有一组8位数字组成的关键字： 经过分析可知，前三位和第五位分布不均匀，所以，假设表长为1000，那么可取4、6、7位的数字作为哈希地址，假设表长为100，那么可取4、6与7、8位之和并舍去进位作为散列地址。关键字散列地址1散列地址287142653 87172232 8718274587107136 87127281 87137394465723874013228339990432370327 哈希表3平方取中法：取关键字平方后的中间几位为哈希地址。 通常，要预先估计关键字的数字分布并不容易，要找数字均匀分布的位数更难。此时可采用平方取中

17、法：即先通过求关键字的平方来扩大差异，再取其中的几位或其组合作为散列地址。 例如：一组关键字： (0100，0110，1010，1001，0111)平方结果为：(0010000，0012100，1020210，1002001，0012321)假设表长为3位，那么可取中间三位作为散列地址集： (100，121，201，020，123) 哈希表4折叠法：假设关键字位数较多，可将关键字分割成位数一样的几段最后一段的位数可以不同，段的长度取决于哈希表的地址位数，然后将各段的迭加和舍去进位作为哈希地址。 例如，对于key=58242324169 582 423 241 + 69 1315H(key)=3

18、15移位迭加 582 324 241 + 96 1243H(key)=243间界迭加 哈希表5除留余数法：选择一个适当的正整数P，用P去除关键字，取所得的余数作为哈希地址，即： H(key) = key%P这个方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大素数比较好。例如： m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1019除余法的地址计算公式简单，而且在很多情况下效果较好，因此是一种常用的构造哈希函数的方法。 哈希表 实际工作中需视情况的不同而采用不同的

19、哈希函数。 通常需要考虑的因素有： A. 计算哈希函数所需时间; B. 关键码的长度; C. 哈希表的大小; D. 关键码的分布情况; E. 记录的查找频率。 哈希表在构造这种特殊的“查找表 时，除了需要选择一个“好尽可能少产生冲突的哈希函数之外，还需要找到一种“处理冲突 的方法。“处理冲突 的实际含义是：为产生冲突的地址寻找下一个哈希地址。常用的解决冲突的方法：开放定址法，链地址法，再哈希法，建立一个公共溢出区。 哈希表处理冲突的方法1 开放定址法 用开放地址法解决冲突的根本思想是：当冲突发生时，使用某种方法在散列表中形成一个探测序列，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一

20、个开放的地址单元为空为止。插入时碰到开放的地址，即可将待插入新结点放到该地址单元中；查找时碰到开放的地址，那么说明表中没有待查的关键字。 形成探测的方法不同，所得到的解决冲突的方法也不同。 哈希表1 开放定址法在根本区域内形成一个探测序列 Hi = (H(key) + di)MOD m, i = 1, 2, , k ( k m-1)其中：m为表长，di为增量序列，可有多种取法： A. di = 1, 2, 3, , m-1, 称线性探测再散列; B. di = 12, -12, 22, -22, , k2, -k2 (k m/2) 称为二次探测再散列； C. di = 伪随机数序列，称伪随机探测再散列。 哈希表例：在长度为11的哈希表中已有关键字分别为17，60，29的记录哈希函数H(key)=key MOD 11,现有第四个记录，其关键字为38，由哈希函数得到的哈希地址是5，产生冲突。假设用线性探测再散列方法处理，得到下一个地址6，仍冲突；再求一个地址7，仍冲突；直到哈希地址是8的位置为“空时止，处理冲突过程完毕，将记录填入哈希表中序号为8的位置。 哈希表60172901234567891011601729382 再哈希法 Hi = R Hi(key) i = 1, 2, , k R Hi均是不同的哈希函数，即在同义词产生地址冲突时