首页计算机计算机基础数据结构 07 第七章 查找.pptx

07 第七章 查找.pptx

页数:49页文件大小:626.5 KB来源: 数据结构ppt课件

本课件为数据结构第七章查找,先说明查找的基本概念与平均查找长度,介绍顺序查找、折半查找与分块查找等静态查找表方法,随后讲解二叉排序树的查找、插入与删除及平衡二叉树的调整,最后介绍哈希函数的构造方法与冲突处理策略。

第七章查找目录页,列出静态查找表、哈希表与处理冲突方法等主要章节
查找基本概念页,给出查找表、查找与关键字的定义及查找表的常用操作
查找方法评价页,说明查找速度、存储空间与平均查找长度及静态动态查找表分类
查看本课件的文字版(共 49 页,供检索与复制)

第1页:第七章查找目录

查找静态查找表哈希表本章小结第七章查找课后作业

第2页:查找表与关键字

查找表
由同一类型的数据元素(或记录)构成的集合
查找
也叫检索,是根据给定的某个值,在表中确定一个关键字等于给定值的记录或数据元素
关键字
是数据元素中某个数据项的值,它可以标识一个数据元素 对查找表经常进行的操作: 查询某个“特定的”数据元素是否在查找表中; 检索某个“特定的”数据元素的各种属性; 在查找表中插入一个数据元素; 从查找表中删去某个数据元素。
typedefstruct{ int num;char name[30];int mark[5];}STU;查找

第3页:查找方法的评价

查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(AverageSearchLength):为确定记录在表中的位置,需要与给定值进行比较的次数的期望值叫查找算法的~ 查找表可分为两类

静态查找表
仅作查询和检索操作的查找表;
动态查找表
在查找过程中同时插入不在查找表中的数据元素,或者删除其在查找表中存在的数据元素。平均查找长度ASL:查找

第4页:静态查找方法分类

静态查找表StaticSearch Table顺序表查找---顺序查找有序表查找---折半查找索引顺序表查找---分块查找静态查找表:仅作查询和检索操作的查找表静态查找方法比较

第5页:静态查找表ADT定义

ADTStaticSearchTable{数据对象:D是具有相同特性的数据元素的集合。每个数据元素含有类型相同、可唯一标识数据元素的关键字。数据关系:R数据元素同属一个集合。基本操作:Create(&ST, n);构造一个含n个数据元素的静态查找表STDestroy(&ST);销毁静态查找表STSearch(ST, key);在静态查找表ST中查找关键字为key的数据元素,返回其值或在表中位置,若不存在则返回“空”}ADTStaticSearchTable抽象数据类型静态查找表的定义静态查找表

第6页:顺序查找的存储结构

typedefstruct{ ElemType *elem;//数据元素存储空间基址int length;//表的长度}SSTable;表的顺序存储结构 查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较 适用条件:以顺序表或线性链表表示的静态查找表typedefstruct{ KeyType key;//关键字域……//其它域}ElemType;数据元素类型静态查找表——顺序查找

第7页:顺序查找过程示例

i64监视哨iiii比较次数=查找第n个元素:查找第n-1个元素:……….查找第1个元素:查找第i个元素:查找失败:5例0 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92查找64静态查找表——顺序查找 查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较 适用条件:以顺序表或线性链表表示的静态查找表查找成功12nn+1-in+1比较次数

第8页:顺序查找算法

算法描述int Search_Seq( SSTable ST, KeyType key){int i;ST.elem[0].key=key;

for(i=ST.length;ST.elem[i].key!=key;i--);return(i);}查找成功——返回元素下标查找失败——返回0静态查找表——顺序查找设置”监视哨”的好处——①省去for循环中循环条件i>=0;②能够实现查找失败返回0设置”监视哨”

第9页:顺序查找的ASL

顺序查找方法的ASL 优点:算法简单,对表的逻辑次序和存储结构无要求 缺点:平均查找长度较大静态查找表——顺序查找静态查找表

第10页:折半查找的过程

查找过程:每次将待查记录所在区间缩小一半 适用条件:采用顺序存储结构的有序静态查找表 算法实现: 设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时,令low=1,high=n,mid= (low+high)/2 将mid指向的记录与k比较(假设有序表升序) 若k==r[mid].key,查找成功 若k<r[mid].key,则high=mid-1 若k>r[mid].key,则low=mid+1 重复上述操作,直至找到记录,查找成功;或low>high,查找失败静态查找表——折半查找

第11页:折半查找示例

静态查找表——折半查找5613372119588807564921 2 3 4 5 6 7 8 9 10 11lowhighmid查找21查找成功5613372119588807564921 2 3 4 5 6 7 8 9 10 11lowhighmid查找70查找失败

第12页:折半查找算法

算法描述:int Search_Bin( SSTableST, KeyTypek){ int low,high,mid;low=1; high=ST.length;

while(low<=high){mid=(low+high)/2;if(k>ST.elem[mid].key)low=mid+1;else if(k==ST.elem[mid].key)return mid;elsehigh=mid-1;}return(0);}静态查找表——折半查找在顺序表ST中查找关键值为k的记录设置初始上下界当区域有效时,折半查找查找成功,返回元素下标查找失败,返回0

第13页:折半查找的判定树

1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92 判定树:描述查找过程的二叉树叫~ 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 有n个结点的判定树的深度为 log2n +1静态查找表——折半查找 算法分析:6391471025811判定树具有n个结点的完全二叉树的深度为 log2n +1lowhighmidlowhighmid判定树与结点数相同的完全二叉树:63914710258116391471051128

第14页:折半查找的ASL

折半查找的ASL静态查找表——折半查找6391471025811设判定树是深度为h的满二叉树判定树

第15页:折半查找ASL推导

折半查找的ASL静态查找表——折半查找设判定树是深度为h的满二叉树判定树123114589121367101415深度为k的二叉树上至多含2k-1个结点(k≥1)在二叉树的第i层上至多有2i-1个结点(i≥1)

第16页:折半查找的特点

折半查找的特点静态查找表——折半查找 优点:平均查找长度较小,查找效率高于顺序查找 缺点:只适用于顺序存储的有序表,不适用于一般顺序表和链式存储结构L57头结点16^12n比较次数顺序查找折半查找静态查找表

第17页:索引顺序查找过程

查找过程:将线性表分成几块,块内无序,块间有序;先确定待查记录所在块,再在块内查找 适用条件:分块有序表静态查找表——索引顺序查找 索引表顺序查找(又称为分块查找)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 53查找38索引顺序查找的过程也是一个“缩小区间”的查找过程

第18页:索引顺序查找实现

算法实现:建立索引表,每个索引表结点含有一个数据域(本块最大关键字)和一个指针域(指向本块第一个结点)221索引表查找38查找成功静态查找表——索引顺序查找 索引表顺序查找(又称为分块查找)48867131 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 53

  • 索引表查找可使用何方法?
  • 块内查找可使用何方法?
  • 数据可否用链式存储??
  • 顺序、折半查找
  • 只能使用顺序查找
  • 可以使用链式存储

第19页:索引表类型定义

静态查找表——索引顺序查找

typedefstruct{ KeyTypeMaxKey;//本块最大关键字intFirstLink;//本块第一个结点下标}IndexTable;typedefstruct{ ElemType *elem;//数据元素存储空间基址intlength;//表的长度}SSTable;表的顺序存储结构typedefstruct{ KeyTypekey;//关键字域……//其它域}ElemType;数据元素类型索引表类型

第20页:索引顺序查找算法

静态查找表——索引顺序查找int Seach_Index(SSTableST,IndexTableIT[ ],intb,intn,KeyTypek){ int i=1,j;

while((k>IT[i].MaxKey)&&(i<=b))i++;if(i>b){ printf("\nNot found"); return(0); }j=IT[i].FirstLink;while((k!=ST.elem[j].key)&&(ST.elem[j].key<=IT[i].MaxKey)&&(j<n))j++;if(k!=ST.elem[j].key){j=0; printf("\nNot found"); }return(j);}索引表查找块内查找输出查找结果

第21页:索引顺序查找的ASL

索引顺序查找方法的ASL静态查找表——索引顺序查找将表长为n的表平均分成b块,每块含s个记录,并设表中每个记录的查找概率相等,则(1)用顺序查找确定所在块:(2)用折半查找确定所在块:静态查找表

第22页:查找方法比较

三种静态查找方法的比较:从平均查找长度、表结构与存储结构三方面对比顺序查找、折半查找与分块查找的适用条件。

顺序查找、折半查找与分块查找的对比
查找方法平均查找长度表结构存储结构
顺序查找最大有序表、无序表顺序存储结构、线性链表
折半查找最小有序表顺序存储结构
分块查找两者之间分块有序表顺序存储结构、线性链表

第23页:哈希表目录

哈希表HashTable哈希表的概念哈希函数的构造方法处理冲突的方法哈希查找过程与分析为什么研究哈希表?

第24页:为什么研究哈希表

哈希表HashTable通常查找方法的共同特点: 记录在表中的位置和它的关键字之间不存在一个确定的关系 查找过程为给定值依次与各个关键字进行比较 查找效率取决于比较的次数 只有一个办法:预先知道所查关键字在表中的位置 即,要求记录的位置和其关键字之间存在一种对应关系对于频繁使用的查找表,希望ASL=01 2 3 4 5 6 7 8 9 10 11例46 13 29 21 7 16 64 50 80 12 9找21例某酒店按客人的姓氏分配房间:安白常严赵1232526…………哈希表

第25页:哈希函数的基本思想

基本思想:在记录的存储地址和它的关键字之间建立一个确定的对应关系;这样,不经过比较,一次就能得出所查元素是否存在关键字集合存储地址集合hash 哈希函数是一种映象,是从关键字集合到存储地址集合的一种映象 哈希函数可写成:addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字 定义 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~哈希表HashTable

第26页:哈希表与哈希查找

哈希表
应用哈希函数,由记录的关键字确定记录在表中的地址,并将记录放入此地址,这样构成的表叫~
哈希查找
又叫散列查找,利用哈希函数在哈希表中进行查找的过程叫~例某酒店按客人的姓氏分配房间:安白常严赵1232526…………哈希表HashTable

第27页:哈希函数示例:编号

例30个地区的各民族人口统计数据编号地区别总人口汉族回族…...1北京2上海…...…...30沈阳以编号作关键字,构造哈希函数:H(key)=keyH(1)=1H(2)=2……北京上海…………………………沈阳1230...哈希表HashTable

第28页:哈希函数示例:拼音序号

以地区别作关键字,取地区名称第一个拼音字母的序号作哈希函数:H(Beijing)=2H(Shanghai)=19H(Shenyang)=19北京………………上海……1230..19沈阳怎么办?哈希表HashTable编号地区别总人口汉族回族…...1北京2上海…...…...30沈阳例30个地区的各民族人口统计数据

第29页:哈希函数与冲突

从例子可见: 哈希函数只是一种映象,所以哈希函数的设定很灵活,只要使任何关键字的哈希函数值都落在哈希表长允许的范围之内即可 冲突:key1 key2,但H(key1)=H(key2)的现象叫~,又称碰撞 同义词:具有相同函数值的两个关键字,叫该哈希函数的~ 哈希函数通常是一种压缩映象,所以冲突不可避免,只能选择一个好的哈希函数,尽量减少产生冲突的机率;同时,冲突发生后,应该有处理冲突的方法 选择一个好的哈希函数的标准:能将关键字均匀的分布在存储空间中哈希表HashTable例有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……哈希表

第30页:直接定址法

直接定址法 构造:取关键字或关键字的某个线性函数作哈希地址,即H(key)=key或H(key)=a·key+b 特点 直接定址法所得地址集合与关键字集合大小相等,不会发生冲突 实际中能用这种哈希函数的情况很少例有一个从1岁到100岁的人口数字统计表,其中年龄作为关键字,哈希函数取关键字自身:地址01 02 03 …… 25 26 27 …… 100年龄1 2 3 …… 25 26 27 …… 100人数3000 2000 5000 …… 1050 1100 2030 …… 10000……哈希函数构造方法

第31页:数字分析法

数字分析法(数字选择法) 构造:对关键字进行分析,取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大,且可能出现的关键字事先知道的情况例有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 78 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、5 数字分布近乎随机所以:取 任意两位或两位与另两位的叠加作哈希地址哈希函数构造方法

第32页:平方取中法

平方取中法构造哈希函数:取关键字平方后的中间几位作为哈希地址,使平方值的中间位受到关键字各位的共同影响,适合事先不知道全部关键字的情况。

关键字平方取中法示例(哈希地址位数为 3)
记录关键字(关键字)²哈希地址
101000 010 000010
211001 210 000210
312001 440 000440
411601 370 400370
520614 310 541310
620624 314 704314
721614 734 741734

第33页:折叠法

哈希函数构造方法 折叠法 构造:将关键字分割成位数相同的几部分(最后一部分可以不同),取这几部分的叠加和(舍去进位)作为哈希地址 种类 移位叠加:将分割后的几部分低位对齐相加 间界叠加:从一端沿分割界来回折送,并对齐相加 适于关键字位数很多,且每一位上数字分布大致均匀的情况例关键字为:0123795864,哈希地址位数为4移位叠加5 8 6 42 3 7 90 18 2 4 4H(key)=82445 8 6 49 7 3 20 1间界叠加15 5 9 7H(key)=5597

第34页:除留余数法

除留余数法 构造:取关键字被p除后所得余数作哈希地址(p是某个不大于哈希表表长m的数)即H(key)=keyMOD p,p m 特点 简单、常用 p的选取很重要;p选的不好,容易发生冲突 p一般取小于等于表长m的最大素数哈希函数构造方法Hash函数值在0~(p-1)范围内

第35页:选取哈希函数的考虑因素

选取哈希函数,考虑以下因素:

计算哈希函数所需时间
哈希函数不应太复杂 关键字长度 哈希表长度(哈希地址范围) 关键字分布情况
记录的查找频率
查找频率高的记录应尽量避免冲突哈希函数构造方法哈希表

第36页:处理冲突的方法

冲突处理方法“处理冲突”——为产生冲突的地址寻找下一个哈希地址开放定址法再哈希法链地址法哈希表

第37页:开放定址法

开放定址法 方法:当冲突发生时,形成一个探查序列di;沿此序列逐个地址探查,直到找到一个空位置(开放的地址),将发生冲突的记录放到该地址中。令:Hi——新的哈希地址H(key)——哈希函数di——增量序列m——哈希表表长则: 分类 线性探测再散列:di=1,2,3,……m-1 二次探测再散列:di=1²,-1²,2²,…,±k²(k m/2) 伪随机探测再散列:di=伪随机数序列冲突处理方法H(key)+di( )MODmHi=对表长m取余,保证函数值在0~(m-1)范围内

第38页:开放定址法举例

例表长为12的哈希表中已填有关键字为17,60,29的记录,H(key)=keyMOD11,现有第4个记录,其关键字为38,按三种探测再散列处理冲突的方法,将它填入哈希表中哈希函数值:3838380 1 2 3 4 5 6 7 8 9 10 11176029开放定址法处理冲突举例H(38)=38MOD11=5(1)线性探查:冲突H3=(5+3)MOD12=8H1=(5+1)MOD12=6冲突H2=(5+2)MOD12=7冲突不冲突H2=(5-1²)MOD12=4(2)二次探查:H1=(5+1²)MOD12=6冲突不冲突(3)设伪随机数序列为9,则:H1=(5+9)MOD12=2不冲突657

第39页:线性探测再散列举例

开放定址法处理冲突举例例如:关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定哈希函数H(key) =keyMOD11(表长m=12)190123145568若采用线性探测再散列处理冲突118236H(23)=1H(19)=8H1=(1+1) MOD12=2H(01)=1H(14)=3H(55)=0H(68)=2H1=(2+1) MOD12=3H2=(2+2) MOD12=4H(11)=0H1=(0+1) MOD12=1H2=(0+2) MOD12=2H3=(0+3) MOD12=3H4=(0+4) MOD12=4H5=(0+5) MOD12=5H(82)=5冲突,H1=(5+1) MOD12=6H(36)=3冲突,H1=(3+1) MOD12=4冲突,H2=(3+2) MOD12=5冲突,H3=(3+3) MOD12=6冲突,H4=(3+4) MOD12=7构造结束不冲突不冲突冲突,不冲突不冲突冲突,冲突,冲突,冲突,冲突,冲突,冲突,

第40页:二次探测再散列举例

开放定址法处理冲突举例例如:关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定哈希函数H(key) =keyMOD11(表长m=12)190123145568若采用二次探测再散列处理冲突H(23)=1H(19)=8不冲突冲突,H1=(1+12) MOD12=2H(01)=1不冲突H(14)=3不冲突H(55)=0不冲突H(68)=2冲突,H1=(2+12) MOD12=3冲突,H2=(2-12) MOD12=1冲突,H3=(2+22) MOD12=6H(11)=0冲突,H1=(0+12) MOD12=1冲突,H2=(0-12+12) MOD12=1111H(82)=5不冲突82H(36)=3冲突,H1=(3+1) MOD12=436构造结束处理冲突

第41页:再哈希法

再哈希法 方法:构造若干个哈希函数,当发生冲突时,使用另外一个哈希函数计算哈希地址,即:Hi=Rhi(key)i=1,2,……k,直到不发生冲突为止其中:Rhi——不同的哈希函数 特点:不易再次产生冲突,但计算时间增加冲突处理方法

第42页:再哈希法举例

冲突处理方法例如:关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定哈希函数H1(key) =keyMOD11(表长m=11 )设H2(key)=(3*key) MOD10+1190155143668118223H(23)=1H(19)=8不冲突冲突,H1=(3*23) MOD10+1=10H(01)=1不冲突H(14)=3不冲突H(55)=0不冲突H(68)=2不冲突H(11)=0H(82)=5不冲突H(36)=3构造结束冲突,H1=(3*11) MOD10+1=4冲突,H1=(3*36) MOD10+1=9处理冲突

第43页:链地址法

链地址法(外链法) 方法:将所有关键字为同义词的记录存储在一个单链表中,并用一维数组存放单链表的头指针冲突处理方法例已知一组关键字(19, 01, 23, 14, 55, 68, 11, 82, 36)哈希函数为:H(key)=keyMOD7,用链地址法处理冲突1968821401361155230123456^^^^^^^514562105处理冲突

第44页:哈希查找过程

哈希查找过程哈希查找过程及分析关键字==k查找失败查找成功按处理冲突方法计算Hi给定k值计算H(k)此地址为空YNYN——与哈希表构造过程一致

第45页:哈希查找分析

哈希查找分析 由于冲突的存在,哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL,选取不同的哈希函数及处理冲突的方法,其ASL的计算不同 哈希查找过程中,与给定值进行比较的关键字的个数取决于: 哈希函数影响产生冲突的频率 处理冲突的方法哈希查找过程及分析

第46页:线性探测的ASL计算

例如:关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定哈希函数H(key) =keyMOD11(表长m=11 )190123145568若采用线性探测再散列处理冲突118236H(23)=1H(19)=8不冲突冲突,H1=(1+1) MOD11=2H(01)=1不冲突H(14)=3不冲突H(55)=0不冲突H(68)=2冲突,H1=(2+1) MOD11=3冲突,H2=(2+2) MOD11=4H(11)=0冲突,H1=(0+1) MOD11=1冲突,H2=(0+2) MOD11=2冲突,H3=(0+3) MOD11=3冲突,H4=(0+4) MOD11=4冲突,H5=(0+5) MOD11=5H(82)=5冲突,H1=(5+1) MOD11=6H(36)=3冲突,H1=(3+1) MOD11=4冲突,H2=(3+2) MOD11=5冲突,H3=(3+3) MOD11=6冲突,H4=(3+4) MOD11=7112136251ASL=(1*4+2*2+3*1+5+6)/9=22/9哈希查找过程及分析

第47页:再哈希法的ASL计算

冲突处理方法例如:关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定哈希函数H1(key) =keyMOD11(表长m=11 )设H2(key)=(3*key) MOD10+1190155143668118223H(23)=1H(19)=8不冲突冲突,H1=(3*23) MOD10+1=10H(01)=1不冲突H(14)=3不冲突H(55)=0不冲突H(68)=2不冲突H(11)=0H(82)=5不冲突H(36)=3冲突,H1=(3*11) MOD10+1=4冲突,H1=(3*36) MOD10+1=9111121221ASL=(1*6+2*3)/9=12/9

第48页:链地址法的ASL计算

链地址法(外链法) 方法:将所有关键字为同义词的记录存储在一个单链表中,并用一维数组存放单链表的头指针例已知一组关键字(19, 01, 23, 14, 55, 68, 11, 82, 36)哈希函数为:H(key)=keyMOD7,用链地址法处理冲突1968821401361155230123456^^^^^^^ASL=(1*6+2*2+3*1)/9=13/9哈希查找过程及分析哈希表

第49页:第七章本章小结

本章小结掌握顺序查找、折半查找的算法及性能分析,了解索引顺序查找方法掌握哈希表,包括哈希函数的构造、解决冲突的方法、查找及分析

顶部目录