【精品数据结构】查找1.ppt
《【精品数据结构】查找1.ppt》由会员分享,可在线阅读,更多相关《【精品数据结构】查找1.ppt(90页珍藏版)》请在三一文库上搜索。
1、第九章查找,9.1.基本概念,9.2顺序表,9.2.1顺序查找,9.2.2二分法查找,9.2.3分块查找,9.3散列表,9.3.1概述,9.3.2散列函数的构造方法,9.3.3处理冲突的方法,9.3.4散列表的性能分析,9.4 .树表,9.4.1 二叉排序树,9.4.2 平衡的二叉排序树,9.4.3 B树,小结,查找表:由同一类型的数据元素(记录)组成的集合,可以由任意的数据结构实现。,9.1 基本概念,查找表的操作:(1)查询某个“特定的”数据元素是否在查找表中;(2)查找某个“特定的”数据元素的属性;(3)在查找表中插入一个数据元素;(4)从查找表中删除某个数据元素。 静态查找表:若对查找
2、表只作前两种操作,此类查找表称静态查找表。 动态查找表:若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素, 此类查找表为动态查找表。,关键字:数据元素中某个数据项的值,用它可以标示查找表中的一个数据元素。主关键字可以唯一地标识一个记录,次关键字用以识别若干记录。,查找:就是根据给定的关键字值,在特定的查找表中确定一个其关键字与给定值相同的数据元素,并返回该数据元素在查找表中的位置。如果找到数据元素,则称查找成功,否则查找失败。,平均查找长度:为了确定数据元素在查找表中的位置需要和给定值进行比较的关键字个数期望值,称为查找算法在查找成功时的平均查找长度。,
3、对于长度为n的查找表,查找成功的平均查找长度为:,其中Pi为查找表中第i个数据元素的概率,Ci为找到查找表中第i个元素时,已经进行的比较次数。由于查找算法的基本元素是关键字之间的比较操作,所以可以平均查找长度来衡量查找算法的性能。,9.2顺序表,顺序表中相邻的两个记录Ri和Ri+1在存储器中的物理位置也是相邻的,因此存储结构采用的是顺序结构。,顺序结构有关C+语言描述的数据类型定义 :(为了简单起见,我们假设记录的排序码为整型,在本章以后讨论的顺序表中均采用这样的向量存储结构),顺序表的查找方法分为顺序查找法、二分法(折半)查找法以及分块(索引)查找法。,#define maxn 30 / 文
4、件中最大记录数 typedef struct int key; / 假设记录排序码为整数 char *other; / 记录中其它信息域,暂不用 record; typedef record recordfilemaxn;,9.2.1顺序查找,顺序查找(sequential search)用待查的关键字值与线性表里各结点的关键字值逐个比较,,查找第n个元素:比较次数1 查找第n-1个元素:比较次数2 . 查找第1个元素:比较次数 n 查找第i个元素:比较次数n+1-i 查找失败:比较次数n+1,监视哨,查找76,i,i,i,i,i,查找次数5,int seqserch(recordfile r
5、,int k,int n) /k为给定值,n为表长; /返回0表明查找不成功,否则返回关键字等于k的记录在表r中的序号. int i=n; r0.key=k; while(ri.key!=k) i-; return i;,顺序查找的算法:查找前对结点之间并没有排序要求.用C+语言描述的顺序查找算法如下 :,在此算法中,查找之前,先对r0的关键字赋值为k,目的在于免去查找过程中每一步都要检测整个表是否查找完毕。在此r0起了监视哨的作用,这种改进能使顺序查找在n1000时进行一次查找所需要的平均时间几乎减少一半,从而提高查找效率。,顺序查找方法的ASL:,有n个记录的表,查找成功时的平均查找长度为
6、,假设每个记录的平均查找概率相等即:Pi = 1/n 。 。,在顺序查找时,ci取决于所查记录在表中的位置。如查找记录rn时,仅需比较一次,而查找记录r1时,则需比较n次。一般地,ci=n-i+1。故顺序查找的平均查找长度为: ASL = np1 +(n-1)p2 + + 2pn-1 + pn 。,顺序查找法和后面将要讨论的其它查找法相比,其缺点是平均查找长度较大,特别是当 n 很大时,查找效率低。然而,它有很大的优点:算法简单且适用面广。它对表的结构无任何要求,无论记录是否按关键字有序均可应用,而且上述所有讨论对线性链表也同样适用。,算法的评价,9.2.2二分法查找,查找过程:每次将待查记录
7、所在区间缩小一半, 适用条件:采用顺序存储结构的有序表,算法实现: 设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时,令low=1,up=n,mid=(low+up)/2 让k与mid指向的记录比较 若k=rmid.key,查找成功 若krmid.key,则low=mid+1 重复上述操作,直至lowup时,查找失败,例:查找21,low,up,mid (1+11)/2=6,low,mid (1+5)/2=3,up,low ,mid (4+5)/2=4,up,例:查找83,low,up,mid (7+11)/2=9,low,mid (10+11
8、)/2=10,up, low,up ,Up low 查找失败,int bins(recordfile r, int K, int n) /二分查找 int l=1,u=n,m; / 置区间初值 while(lrm.key) l=m+1; / 修改下界 l 值 else if(Ku 查找不成功 ,二分查找的算法用C+语言描述如下,判定树:描述查找过程的二叉树叫判定树。有n个结点的判定树的深度为log2n+1 ; 二分查找成功时比较次数最多不超过树的深度 ;二分查找在查找不成功时和关键字比较的次数最多不超过 log2n +1;,算法查找的性能,二分查找的ASL 表的长度为:n=2h-1(h=log
9、2(n+1) 每个元素的查找概率相等Pi=1/n 平均查找长度 :,二分查找的效率比顺序查找高,但二分查找只能适用于有序表,且存储结构仅限于向量(对线性链表无法进行折半查找),当表经常需要插入或删除一个元素时,就需要来回移动元素。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。,算法的评价,将查找表分成若干个块(子表)块内无序,但块与块之间应有序构造一个索引表。其中每个索引项对应一个块并记录每个块的起始位置,以及每块中的最大关键字(或最小关键字)。索引表按关键字有序排列,9.2.3分块查找,查找过程:先根据索引表确定待查记录所在块,再在块内顺序查找 适用条件:分块有序表,例:查找37,
10、平均查找长度为: Lb为查找索引表确定所在块的平均查找长度,Lw为在块中查找元素的平均查找长度。,长度为n的表分成b块,每块含有s个记录,即b=n/s;表中每个记录的查找概率相等,则每块查找的概率为1/b,块中每个记录的查找概率为1/s 用顺序查找确定所在块,则平均查找长度为: 用二分查找确定所在块,则查找长度为:,分块查找的优点是:在线性表中插入或删除一个结点时,只要找到该结点应属的块,然后在块内进行插入和删除运算,由于块内结点的存放是任意的,所以插入或删除比较容易,不需要移动大量的结点。分块查找的主要代价是增加一个辅助数组的存储空间和将初始线性表分块排序的运算。另外当大量的插入和删除运算使
11、块中的结点数分布不均匀时,查找速度会下降。,算法的评价,基本思想:在记录的存储地址和它的关键字之间建立一个确定的对应关系;这样,不经过比较,一次存取就能得到所查元素的查找方法。,9.3散列表 9.3.1 概述,散列表定义: 记录的存储位置和它的关键字之间建立一个确定的对应关系h,使每个关键字和结构中一个唯一的存储位置相对应。查找时,根据h找到给定值k的映象h(k),若结构中存在关键字和k相等的记录,则必定在h(k)的存储位置上。我们称这个对应关系h为散列(Hash)函数用散列函数建立的表称为散列表。,例如,一张全国各地区的各民族人口统计表,以编号作关键字, 构造哈希函数:H(key)=key
12、H(1)=1 H(2)=2,特征位抽取法 构造:抽取关键字中某几位随机性较好的数位,然后把这些数位拼接起来作为散列地址。,9.3.2 散列函数的构造方法,直接定址法 构造:取关键字或关键字的某个线性函数作哈希地址,即H(key)=key 或 H(key)=akey+b 特点:直接定址法所得地址集合与关键字集合大小相等,不会发生冲突。实际中能用这种哈希函数的情况很少。,分析: 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以:取任意两位或两位 与另两位的叠加作散列 地址,平方取中法 构造:取关键字平方后中间几位作哈希地址适用于当无法确定关键字中哪几位分布比较均匀时,K的内部编码
13、为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01,B的内部编码为02。关键字“KEYA”的内部代码为11052501,同理得到关键字“KYAB”、“AKEY”的内部编码,然后进行对关键字平方运算,取出第7到第9位作为该关键字的散列地址,折叠法构造: 将关键字分割成位数相同的几部分,然后取这几部分的叠加和(舍去进位)做散列地址移位叠加:将分割后的几部分低位对齐相加间界叠加:从一端沿分割界来回折送,然后对齐相加适于关键字位数很多,且每一位上数字分布大致均匀情况如国际标准图书编号 0-442-20586-4采用这两种折叠法求得的散列地址分别如下所示:,除留余数法构造: 取关键字被某
14、个不大于散列表表长m的数p除后所得余数作散列地址,即H(key)=key MOD p,m特点:简单、常用,可与上述几种方法结合使用,表(18,75,60,43,54,90,46) m=p=13,18,75,60,43,54,90,46,H(18) 18 135,H(75) 75 1310,H(60) 60 138,H(43) 43 134,H(54) 54 132,H(90) 90 1312,H(46) 46 137,随机数法 构造:取关键字的随机函数值作散列地址,即H(key)=random(key) 适于关键字长度不等的情况,选取散列函数,考虑以下因素: 计算散列函数所需的时间( 包括硬件
15、指令的因素 ); 关键字的长度; 散列表的大小; 关键字的分布情况; 记录的查找频率,1、开放定址法: 方法:当冲突发生时,形成一个探查序列;沿此序列逐个地址探查,直到找到一个空位置(开放的地址),将发生冲突的记录放到该地址中,即Hi=(H(key)+di)MOD m,i=1,2,k(km-1) 其中:H(key)散列函数 m散列表表长 di增量序列,9.3. 3 处理冲突的方法,分类: 线性探测再散列:di=1,2,3,m-1 二次探测再散列:di=1,-1,2,-2,3,k(km/2) 伪随机探测再散列:di=伪随机数序列,例 表长为16的散列表中已填有关键字为19,70,33和38的记录
16、,H(key)=key MOD 13,现有第五个记录,其关键字为25, H(25)=12,冲突,25,不冲突,线性探测再散列,插入第六个记录,其关键字为18 , H(18)=5,冲突,线性探测再散列,冲突,冲突,不冲突,18,用二次探测再散列,不冲突,伪随机探测再散列,不冲突,18,18,2、再散列法 方法:构造若干个散列函数,当发生冲突时,计算下一个散列地址,即:Hi=Rhi(key) i=1,2,k 其中:Rhi不同的散列函数。 特点:计算时间增加。,3、链地址法: 方法:将所有关键字为同义词的记录存储在同一线性链表中并用一维数组存放头指针 用链地址法解决冲突的散列造表算法 :,#incl
17、ude #define listlen 13 struct record int key; record *next; ; typedef record RECFlistlen; int modh (int ); /Hash函数(除留余数法) void chainh(int ,RECF ,int (*hash)(int ); prhashlist(RECF ); /输出散列表,void main(void) int i,x; RECF r; for(i=0;ix; while(x) chainh(x,r,modh); cinx; prhashlist(r); / 其中参数int(*hash)(
18、int)是指向函数的指针,它返回一个整数(散列地址) /用链地址法解决冲突的散列造表算法 /根据(*hash)函数造散列表,void chainh(int k,RECF r,int (*hash)(int) int addr; record *p,*q; /用链地址法解决冲突 addr=(*hash)(k); if (!raddr.key)raddr.key=k; else if(raddr.key!=k) p=raddr.next; q= ,int modh (int k) /Hash函数(除留余数法) return(k % listlen); prhashlist(RECF r) /输出散
19、列表 int i; record *p; cout; p=ri.next; while(p) coutkey; p=p-next; coutendl; ,例:已知一组关键字(32,40,36,53,16,46,71,27,42,24,49,64),散列表表长为13,散列函数为H(key)key13,则用链地址法处理冲突的结果,散列查找过程仍是一个给定值与关键字进行比较的过程 评价散列查找效率仍要用ASL 散列查找过程与给定值进行比较的关键字的个数取决于: 1、散列函数 2、处理冲突的方法 3、散列表的填满因子=表中填入的记录数/散列表长度,9.3.4 散列表性能分析,已有散列表a16如图所示(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品数据结构 精品 数据结构 查找
链接地址:https://www.31doc.com/p-11887252.html