数据结构第21次课查找c.pptVIP

基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~ 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~ 从例子可见： 冲突：key1?key2，但H(key1)=H(key2)的现象叫~ 同义词：具有相同函数值的两个关键字，叫该哈希函数的~ 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 8.4.1 哈希函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少 数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况 平方取中法 构造：取关键字平方后中间几位作哈希地址 适用于不知道全部关键字情况 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况 除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，p?m 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率 8.4.2 处理冲突的方法 开放定址法（类似于看电影找座位） 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di) MOD m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 分类 线性探测再散列：di=1,2,3,……m-1 二次探测再散列：di=12,-12,22,-22,32,……±k2(k?m/2) 伪随机探测再散列：di=伪随机数序列 再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的哈希函数 特点：计算时间增加 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针 8.4.3 哈希查找过程及分析 哈希查找过程 哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL衡量 哈希查找过程与给定值进行比较的关键字的次数取决于： 哈希函数 处理冲突的方法 哈希表的填满因子 ?=表中填入的记录数/哈希表长度 P261 本章小结 顺序查找(适用于…，ASL…，表结构…） 二分查找(适用于…，ASL…，表结构…） 分块查找(适用于…，ASL…，表结构…） 作业题目： 静 态 动 态 排序二叉查找(插入、查找、删除方法） 平衡树(有哪些信誉好的足球投注网站过程中动态平衡化) B-/B+树 （结点的形态、插入删除方法） 散列法(函数构造6、冲突处理方法3、查找分析) * 数据结构 计算机与信息学院 刘勇 * 数据结构 一只小猪、一只绵羊和一头乳牛，被关在同一个畜栏里。有一次，牧人捉住小猪，它大声号叫，猛烈地抗拒。绵羊和乳牛讨厌它的号叫，便说：「他常常捉我们，我们并不大呼小叫」。小猪听了回答道：「捉你们和捉我完全是两回事，他捉你们，只是要你们的毛和乳汁，但是捉住我，却是要我的命呢! 」　　 立场不同、所处环境不同的人，很难了解对方的感受；因此对别人的失意、挫折、伤痛，不宜幸灾乐祸，而应要有关怀、了解的心情。要有宽容的心！ 每课一贴 针对动态查找表的查找算法主要有： 8.3 动态查找表 一、二叉排序树（BST） 二、平衡二叉树（AVL树） 三、 B- 、 B+树 B-树的形态和本质 三 B－、B+树 1 11 35 1 1 18 1 27