数据结构--第九章课件.ppt

1、数据结构-第九章 查找1第八章第八章 集合与检索集合与检索8 8.1 .1 静态查找表静态查找表8 8.2 .2 动态查找表动态查找表8 8.3 .3 哈希表哈希表 查找是计算机中最重要、最频繁的应用之一。被查查找是计算机中最重要、最频繁的应用之一。被查找的数据对象逻辑结构可认为是找的数据对象逻辑结构可认为是集合集合，选取不同的存储，选取不同的存储结构，查找以及其它操作的效率也会有所不同。结构，查找以及其它操作的效率也会有所不同。数据结构-第九章 查找2术语术语查找查找 指定某个值，在查找表中确定是否存在一个记录，该记录的关键字等于给定值。查找表查找表 是同一类型的记录(数据元素)的集合。关键

2、字关键字 是记录(数据元素)中的某个数据项的值。主关键字主关键字 该关键字可以唯一地标识一个记录。次关键字次关键字 该关键字不能唯一标识一个记录。静态查找表静态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表动态查找表 在查找的过程中同时插入不存在的 记录，或删除某个已存在的记录。查找成功查找成功 查找表中存在满足查找条件的记录。查找不成功查找不成功 查找表中不存在满足查找条件的记录。数据结构-第九章 查找3内查找内查找 整个查找过程都在内存中进行。外查找外查找 在查找过程中需要访问外存。平均查找长度平均查找长度ASLASL 为确定记录在查找表中的位置，需将关键字和给定

3、值比较次数的期望值。查找成功时的ASL计算方法：n：记录的个数 pi：查找第i个记录的概率(不特别 声明时认为等概率 pi=1/n)ci：找到第i个记录所需的比较次数本章约定：关键字的类型为整型niiicpASL1数据结构-第九章 查找48.1 8.1 静态查找表静态查找表 不考虑在查找的同时修改表不考虑在查找的同时修改表8.1.1 8.1.1 顺序表的查找顺序表的查找 (a1,a2,.an)0 1 2 n r0.n a1 a2 an r0.key=K算法描述算法描述int SeqSearch(Seqlist R,KeyType K)R0.key=K;for(i=n;Ri!=K;i-);ret

4、urn(i);/SeqSearch#define n 100Typedef struct KeyType key;InfoType otherinfo;NodeType:Typedef NodeType Seqlistn+1;数据结构-第九章 查找5程序设计技巧程序设计技巧 设置监视哨R0，提高算法效率。性能分析性能分析 空间复杂度：一个辅助空间。时间复杂度：1)查找成功时的平均查找长度 设表中各记录查找概率相等 ASLs(n)=(1+2+.+n)/n=(n+1)/22)查找不成功时的平均查找长度 ASLf=n+1算法特点算法特点 此算法也适合链式存储结构 n很大时查找效率较低 改进措施：非等

5、概率查找时，可将查找概率高的记录尽量排在表前部。niiiCP1数据结构-第九章 查找68.1.2 8.1.2 有序表的查找有序表的查找 满足 Ri.key Ri+1.key,1 i n折半折半(对半对半/二分二分)查找法查找法 0 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid high =(low+high)/2 K=21 l h m K=85 l h m 1 11 6 1 11 6 1 5 3 7 11 9 4 5 4 10 11 10 10 9数据结构-第九章 查找7算法描述算法描述int BinSearc

6、h(Seqlist R,KeyType K)low=1;high=n;while(lowK)high=mid-1;else low=mid+1;return(0);/BinSearch数据结构-第九章 查找8性能分析性能分析 h=log2n+1 同完全二叉树，二叉树性质4成功查找时的平均查找长度：ASLs=不成功查找时的查找长度：h-1或h次特点特点 查找效率高，但需有序，且无法在链表上实现。1)1(log1)1(log1212211nnnnjnhjj(n50)判定树 -13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外结点内结点=数据

7、结构-第九章 查找98.1.4 索引顺序索引顺序表的查找表的查找 表的构造表的构造 索引表索引表 index1.bindex1.b 最大关键字值 22 42 86 起始地址 1 5 9 主表主表 r 1.nr 1.n（分块有序（分块有序/有序）有序）1 2 3 4 5 6 7 8 9 10 11 12 key 12 22 13 8 28 33 38 42 86 76 50 63 其它项分块查找步骤分块查找步骤1)折半或者顺序查找索引表，确定所在块2)在已确定的块中顺序查找/折半查找数据结构-第九章 查找10性能分析性能分析 设b为索引表长度，s为块中记录个数 顺序查找索引表+顺序查找被确定的块

8、 ASLbs=当s取 时，ASLbs取最小值 折半查找索引表+顺序查找被确定的块 ASLbs=log2(b+1)-1+(s+1)/2 log2(n/s+1)+s/2 实用中：各块大小不一定相等；各块可以分别顺序存储，也可分别链式存储 分块查找效率介于顺序查找和折半查找之间n1)(1)(11211211ssnsbisjbsibj1n数据结构-第九章 查找118.2 动态查找表动态查找表 表的插入与删除操作频繁表的插入与删除操作频繁 以树表作为存储形式，可以兼顾高效率的查找和对表的维护。例如：二叉排序树、B-树8.2.1 二叉排序树二叉排序树BST(二叉查找二叉查找/搜索树搜索树)定义定义 二叉排

9、序树或者是空树，或者是满足如下性质的二叉树：1)若其左子树非空，则左子树上所有 结点的值均小于根结点的值；2)若其右子树非空，则右子树上所有 结点的值均大于等于根结点的值；3)其左右子树本身又各是一棵二叉排序树452453122890数据结构-第九章 查找12性质性质 中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列。操作操作 查找 插入 生成 删除 53 20 90 10 50 86 95 4 12 41 52 88 91 30 45 87 89 92 39452453122890bstK=28 查找成功452453122890bst32K=32 查找失败(1)(2)(2)(3)

10、数据结构-第九章 查找13平衡二叉树的引入平衡二叉树的引入按如下插入顺序构成二叉排序树：12,24,28,37,53平衡二叉树特点：是排序二叉树 树中任一结点的左右子树的高度大致相同AVL（苏Adelson-Velsii 和 Landis，1962年）树：任一结点的左右子树的高度之差的绝对值不超过1。1224283753数据结构-第九章 查找148.2.2 B-树树 平衡的多路查找树 一棵4阶B-树(m=4)1 40 非叶根则2m棵子树 1 20 3 49 58 72 1 10 1 25 2 41 43 1 51 1 65 1 99 实用中，与每个关键字存储在一起的不是相关信息域，而是一个指针

11、，它指向该关键字的记录。m/2 m棵子树数据结构-第九章 查找158.3 哈希表哈希表(杂凑表、散列表杂凑表、散列表)8.3.1 概述概述哈希表的技术特点哈希表的技术特点 通过对记录的关键字进行某种运算后，直接寻址，进行关键字查找时不需比较，使查找的期望时间为O(1)。术语术语 哈希表哈希表：一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。哈希函数哈希函数：记录的存储位置与它的关键字之间存在的一种对应关系。Loc(ri)=H(keyi)冲突冲突：对于keyikeyj，i j，出现的H(keyi)=H(keyj)的现象。数据结构-第九章 查找16 同义词同义词：在同一地址出现冲突的各关键

12、字。哈希哈希(散列散列)地址地址：根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。装填因子装填因子：表中填入的记录数n和哈希表表长 m之比。=n/m设计哈希表的过程设计哈希表的过程 1)明确哈希表的地址空间范围。即确定哈希函数的值域。2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。3)设定处理冲突的方法。哈希表bb+(m-1)L数据结构-第九章 查找178.3.2 哈希函数的基本构造方法哈希函数的基本构造方法 构造原则：算法简单，运算量小；均匀分布，减少冲突。直接定址法直接定址法 H(key)=a key+b 特点：计算

13、简单，冲突最少。数字分析法数字分析法 取关键字的若干数位作为哈希地址。例：8 1 3 4 6 5 3 2（共70个记录，则取随机性好的两位）平方取中法平方取中法 取关键字平方后的中间几位作为哈希地址。数据结构-第九章 查找18折叠法折叠法 将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几个部分的叠加和(舍去进位)作为哈希地址。除留余数法除留余数法H(key)=key MOD p (pm)m:哈希表的表长；p:最好为素数 随机数法随机数法H(key)=random(key)特点：较适于关键字长度不等时的情况。0 1m-1例：m=100p=97数据结构-第九章 查找198.3.3 处理冲突的常用方法处理冲突的常用方法开放定址法开放定址法(空缺编址法空缺编址法)Hi=(H(key)+di)MOD m 0 H(key)m-1 i=1,2,.,k (km-1)m:哈希表的表长；di:增量序列链地址法链地址法 为每个哈希地址建立一个单链表，存储所有具有同义词的记录。b b+L fire to b+(m-1)L seeks