《数据结构：ch9 查找》由会员分享，可在线阅读，更多相关《数据结构：ch9 查找（54页珍藏版）》请在金锄头文库上搜索。
1、第九章 查找查找也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元素 关键字是数据元素中某个数据项的值，它可 以标识一个数据元素 查找方法评价 v查找速度 v占用存储空间多少 v算法本身复杂程度 v平均查找长度ASL(Average Search Length)：为确定 记录在表中的位置，需和给定值进行比较的关键字的 个数的期望值叫查找算法的9.1 静态查找表 9.1.1顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给 定值的比较 算法描述i例 0 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找
2、6464监视哨iiii比较次数=5比较次数： 查找第n个元素： 1 查找第n-1个元素： 2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1顺序查找方法的ASL9.2.2折半查找查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 v设表长为n，low、high和mid分别指向待查元素所在 区间的上界、下界和中点,k为给定值 v初始时，令low=1,high=n,mid=(low+high)/2 v让k与mid指向的记录比较 l若k=rmid.key，查找成功 l若krmid.key，则low=mid+1 v重复上述操作，直至low
3、high时，查找失败算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8
4、 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92low high mid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 5
5、6 64 75 80 88 92算法评价v判定树：描述查找过程的二叉树叫 v有n个结点的判定树的深度为log2n+1 (P220注) v折半查找法在查找过程中进行的比较次数最多不超 过其判定树的深度 v折半查找的ASL9.1.3 分块查找查找过程：将表分成几块，块内无序，块间有序； 先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 v用数组存放待查记录,每个数据元素至少含有关键字域 v建立索引表，每个索引表结点含有最大关键字域和指向 本块第一个结点的指针 算法描述1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9
6、 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表 查38分块查找方法评价ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存储结构 线性链表顺序存储结构 顺序存储结构 线性链表查找方法比较顺序查找折半查找分块查找9.2 哈希查找基本思想：在记录的存储地址和它的关键字之间 建立一个确定的对应关系；这样，不经过比较， 一次存取就能得到所查元素的查找方法 定义 v哈希函数在记录的关键字与记录的存储地址之间 建立的一种对应关系叫 l哈希函数是一种映象，是从关键字空间到存储地址 空间的一种映象 l哈希函数可写成：add
7、r(ai)=H(ki) uai是表中的一个元素 uaddr(ai)是ai的存储地址 uki是ai的关键字 关键字 集合存储地址 集合hash 哈希表应用哈希函数，由记录的关键字确定记 录在表中的地址，并将记录放入此地址，这样构成 的表叫 哈希查找又叫散列查找，利用哈希函数进行查找的 过程叫例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19从
8、例子可见： l哈希函数只是一种映象，所以哈希函 数的设定很灵活，只要使任何关键字 的哈希函数值都落在表长允许的范围 之内即可 l冲突：key1key2，但 H(key1)=H(key2)的现象叫 l同义词：具有相同函数值的两个关键 字，叫该哈希函数的 l哈希函数通常是一种压缩映象，所以 冲突不可避免，只能尽量减少；同时 ，冲突发生后，应该有处理冲突的方 法 哈希函数的构造方法 v直接定址法 l构造：取关键字或关键字的某个线 性函数作哈希地址，即H(key)=key 或 H(key)=akey+b l特点 u直接定址法所得地址集合与关键 字集合大小相等，不会发生冲突 u实际中能用这种哈希函数的情
9、况 很少v数字分析法 l构造：对关键字进行分析，取关键字的若干位或其 组合作哈希地址 l适于关键字位数比哈希地址位数大，且可能出现的 关键字事先知道的情况例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5. 分析： 只取8只取1只取3、4只取2、7、5数字分布近乎随机 所以：取任意两位或两位与另两位的叠加作哈希地址v平方取中法 l构
10、造：取关键字平方后中间几位作哈希地址 l适于不知道全部关键字情况 v折叠法 l构造：将关键字分割成位数相同的几部分，然后取 这几部分的叠加和（舍去进位）做哈希地址 l种类 u移位叠加：将分割后的几部分低位对齐相加 u间界叠加：从一端沿分割界来回折送，然后对 齐相加 l适于关键字位数很多，且每一位上数字分布大致均 匀情况例 关键字为 ：0442205864，哈希地址位数为45 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088移位叠加5 8 6 4 0 2 2 4 0 46 0 9 2 H(key)=6092间界叠加v除留余数法 l构造：取关键字被某个不大于哈希表表长
11、 m的数p除后所得余数作哈希地址，即 H(key)=key MOD p，pm l特点 u简单、常用，可与上述几种方法结合使 用 up的选取很重要；p选的不好，容易产生 同义词 v随机数法 l构造：取关键字的随机函数值作哈希地址 ，即H(key)=random(key) l适于关键字长度不等的情况v选取哈希函数，考虑以下因素： l计算哈希函数所需时间 l关键字长度 l哈希表长度（哈希地址范围） l关键字分布情况 l记录的查找频率处理冲突的方法 v开放定址法 l方法：当冲突发生时，形成一个探查序列；沿此序 列逐个地址探查，直到找到一个空位置（开放的地 址），将发生冲突的记录放到该地址中，即 Hi=
12、(H(key)+di)MOD m，i=1,2,k(km-1) 其中：H(key)哈希函数m哈希表表长di增量序列 l分类 u线性探测再散列：di=1,2,3,m-1 u二次探测再散列：di=1,-1,2,- 2,3,k(km/2) u伪随机探测再散列：di=伪随机数序列例 表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 10 60 17 29(1) H(38)=38 MOD 11=5 冲突H1=(5+1) MOD 11=6 冲突H2=(5+2) M
