《查找的概念顺序查找折半查找分块查找哈希查找》由会员分享，可在线阅读，更多相关《查找的概念顺序查找折半查找分块查找哈希查找（30页珍藏版）》请在金锄头文库上搜索。
1、l查找的概念l顺序查找l折半查找l分块查找l哈希查找第六章第六章 查查 找找查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价v查找速度v占用存储空间多少v算法本身复杂程度v平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的查找的概念顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述i例例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 7
2、5 80 88 92找找6464监视哨监视哨iiii比较次数比较次数=5比较次数：比较次数：查找第查找第n个元素：个元素： 1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素： n查找第查找第i个元素：个元素： n+1-i查找失败：查找失败： n+1顺序查找顺序查找#define MAXITEM 100struct element int key; / 关键字 int data; / 其他数据;typedef struct element sqlistMAXITEM;int seqsrch(sqlist r, int k, int n)/ k为给定值，返回i为关键字等于k的记
3、录在表r中的序号，/ i值为0表示查找不成功 r0.key=k; i=n; while (ri.key!=k) i - - ; return (i);顺序查找方法的ASL折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现v设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值v初始时，令low=1,high=n,mid=(low+high)/2v让k与mid指向的记录比较l若k=rmid.key，查找成功l若krmid.key，则low=mid+1v重复上述操作，直至lowhigh时，查找失败算法描述lowhighmi
4、d例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56
5、 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92折半查找折半查找in
6、t binsrch(sqlist r, int k, int n)/ k为给定值，返回i为关键字等于k的记录在表r中的序号，/ i值为0表示查找不成功 int i, low=1, high=n, mid, find=0; while (low=high & !find) mid=(low+high)/2; if (krmid.key) low=mid+1; else i=mid; find=1; if (!find) i=0; return (i);算法评价v判定树：描述查找过程的二叉树叫v有n个结点的判定树的深度为log2n+1v折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度v
7、折半查找的ASL分块查找（索引顺序查找）查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找适用条件：分块有序表算法实现v用数组存放待查记录,每个数据元素至少含有关键字域v建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针算法描述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最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、
8、无序表 有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构 顺序存储结构顺序存储结构线性链表线性链表查找方法比较查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找哈希查找哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义v哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫l哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象l哈希函数可写成：addr(ai)=H(ki)uai是表中的一个元素uaddr(ai)是ai的存储地址u
9、ki是ai的关键字关键字关键字集合集合存储地址存储地址集合集合hashv哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫v哈希查找又叫散列查找，利用哈希函数进行查找的过程叫例例 30个地区的各民族人口统计表个地区的各民族人口统计表编号编号 地区别地区别 总人口总人口 汉族汉族 回族回族.1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造构造哈希函数：哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区以地区别作关键字，取地区名称第一个拼音字母的序号名称第一个拼音字母的序号作哈希函数：作哈希函数：H(Beijing)
10、=2 H(Shanghai)=19 H(Shenyang)=19从例子可见：l哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可l冲突：key1key2，但H(key1)=H(key2)的现象叫l同义词：具有相同函数值的两个关键字，叫该哈希函数的l哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法v直接定址法l构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+bl特点u直接定址法所得地址集合与关键字集合大小相等，不会发生冲突u
11、实际中能用这种哈希函数的情况很少v数字分析法l构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址l适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例例 有有80个记录，关键字为个记录，关键字为8位十进制数，哈希地址为位十进制数，哈希地址为2位十进制数位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析：分析： 只取只取8 只取只取1 只取只取3、4 只取只取2、7、
12、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位 与另两位的叠加作哈希地址与另两位的叠加作哈希地址v平方取中法l构造：取关键字平方后中间几位作哈希地址l适于不知道全部关键字情况v折叠法l构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址l种类u移位叠加：将分割后的几部分低位对齐相加u间界叠加：从一端沿分割界来回折送，然后对齐相加l适于关键字位数很多，且每一位上数字分布大致均匀情况例例 关键字为关键字为 ：0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088
13、移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加v除留余数法l构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pml特点u简单、常用，可与上述几种方法结合使用up的选取很重要；p选的不好，容易产生同义词v随机数法l构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)l适于关键字长度不等的情况v选取哈希函数，考虑以下因素：l计算哈希函数所需时间l关键字长度l哈希表长度（哈希地址范围）l关键字分布情况l记录的查找频率处理冲突的方法v开放定址法l方法：当冲突发生时，
14、形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函数 m哈希表表长 di增量序列l分类u线性探测再散列：di=1,2,3,m-1u二次探测再散列：di=1,-1,2,-2,3,k(km/2)u伪随机探测再散列：di=伪随机数序列例例 表长为表长为11的哈希表中已填有关键字为的哈希表中已填有关键字为17，60，29的记录，的记录， H(key)=key MOD 11,现有第现有第4个记录，其关键字为个记录，其关键字为38， 按三种处理冲突的方法，将它填
15、入表中按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 冲突冲突 H1=(5+1) MOD 11=6 冲突冲突 H2=(5+2) MOD 11=7 冲突冲突 H3=(5+3) MOD 11=8 不冲突不冲突 38(2) H(38)=38 MOD 11=5 冲突冲突 H1=(5+1) MOD 11=6 冲突冲突 H2=(5-1) MOD 11=4 不冲突不冲突38(3) H(38)=38 MOD 11=5 冲突冲突 设伪随机数序列为设伪随机数序列为9，则：，则： H1=(5+9) MOD 11=3 不冲突不冲
16、突38v再哈希法l方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=RHi(key) i=1,2,k其中：RHi不同的哈希函数l特点：计算时间增加v链地址法l方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 11427795568198420102311哈希查找过程及分析v哈希查找过程给定给
17、定k值值计算计算H(k)此地址为空此地址为空关键字关键字=k查找失败查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiYNYNv哈希查找分析l哈希查找过程仍是一个给定值与关键字进行比较的过程l评价哈希查找效率仍要用ASLl哈希查找过程与给定值进行比较的关键字的个数取决于：u哈希函数u处理冲突的方法u哈希表的装填因子 =表中填入的记录数表中填入的记录数/哈希表长度哈希表长度例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：哈希函数为：H(key)=key MOD 13, 哈希表长为哈希表长为m=16， 设每个记录
18、的查找概率相等设每个记录的查找概率相等(1) 用线性探测再散列处理冲突，即用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突，冲突，H1=(3+1)MOD16=4 冲突，冲突，H2=(3+2)MOD16=5H(79)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4 冲突，冲突，H4=(1+4)MOD16=5 冲突，冲突，H5=(1+5)MOD16=6 冲突，冲突，H6=(1+6)MOD16=7 冲突，冲突，H7=(1+7)MOD16=8 冲突，冲突，H8=(1+8)MO
19、D16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，冲突，H1=(6+1)MOD16=7 冲突，冲突，H2=(6+2)MOD16=8H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，冲突，H1=(10+1)MOD16=11 冲突，冲突，H2=(10+2)MOD16=12(2) 用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希查找算法实现v用线性探测再散列法处理冲突l实现u查找过程：同前u删除：只能作标记，不能真正删除u插入：遇到空位置或有删除标记的位置就可以插入l算法描述：v用外链表处理冲突算法
