数据结构第9章查找试卷.ppt

二、链地址法 将所有关键字为同义词的记录链接在一个线性链表中 例如，假设关键字序列为{ 19,56,23,14,68,82,70,36,91 }，哈希表的表长为 7，哈希函数为 Hash(key)=key % 7，则构建的以链地址处理冲突的哈希表如flash9-4-2所示。 9.4.4 开放定址的哈希表的查找和插入 　 在利用开放定址处理冲突的哈希表中进行查找时， 首先应计算给定值的哈希函数值， 若表中该位置上没有记录， 则表明关键字等于给定值的记录不存在； 若该位置上的记录的关键字和给定值不等， 则依据建表时设定的增量值寻找“下一个”地址， 直至查找成功(即某个位置上的记录的关键字等于给定值)或查找不成功（哈希表中不存在关键字等于给定值的记录），且在查找不成功的情况下，该地址为新的记录的插入位置。 本章小结 在本章中介绍了查找表的三类存储表示方法：顺序表、树表和哈希表。这里的顺序表指的是顺序存储结构，包括有序表和索引顺序表，因此主要用于表示静态查找表，树表包括静态查找树、二叉查找树，树表和哈希表主要用于表示动态查找表。 　　查找树的特点是，每经过一次比较便可将继续查找的范围缩小到某一棵子树上，但查找树并不仅限于二叉树，以后还将介绍其它形式的查找树。 　 所有顺序结构的表和查找树的平均查找长度都是随之查找表中记录数的增加而增大，而哈希表的平均查找长度是装填因子的函数，因此有可能设计出使平均查找长度不超过某个期望值的哈希表。 课后习题 1.试分别画出在线性表(a,b,c,d,e,e,f)中进行折半查找，以查关键字等于 e、f 和 g 的过程。 2.选取哈希函数 H(k)=(3k) MOD 11。用开放定址法处理冲突，di = i((7k) MOD　10+1) (i=1,2,3,…)。试在 0～10 的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 第九章 查找 　 查找表（Search Table）是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。 关键字（key）是数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。 主关键字唯一地标识一个元素， 次关键字识别若干元素 查找（searching）根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。 定义：查找过程中先后和给定值进行比较的关键字个数的期望值称作查找算法的平均查找长度(Average Search Length)。 查找表通常可分两类： 1.静态查找表 2.动态查找表 如何评价查找算法的时间效率？ 对查找表经常进行的操作有：　　（1）查询某个特定的数据元素是否在表中；　　（2）检索某个特定的数据元素的各种属性；　　（3）在查找表中插入一个数据元素；　　（4）从查找表中删除某个数据元素。 9.1 静态查找表 9.1.1 顺序表的查找 实现静态查找表的最简单的方法是以“顺序存储结构的线性表-顺序表”表示之 。 查找过程为：从第一个或最后一个数据元素起，逐个进行“比较”直至其中某个数据元素的关键字等于给定值为止。 缺点：其平均查找长度较大，特别是当表中记录数 n 很大时，查找效率较低。 优点：算法简单且适应面广，无论表中记录是否按关键字有序排列均可应用，而且，上述讨论对链式存储的线性表也同样适用。 9.1.2 有序表的查找 折半查找(Binary Search)又称二分查找 折半查找的过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。 例如，在有序表(05,13,19,21,37,56,64,75,80,88,92)中查找关键字为21和85的数据元素。 算法 　　int Search_Bin ( SSTable ST, KeyType kval ) 　{　　// 在有序表ST中折半查找其关键字等于kval的数据元素，　　// 若找到，则函数值为该元素在表中的位置，否则为0。　　low = 1; high = ST.length;