数据结构第9章查找静态查找表ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2019年3月12日:第第9 9章章 查找查找查找的根本概念静态查找表动态查找表哈希表:v查找的根本概念查找的根本概念9.1 查找的根本概念查找的根本概念查找表：是由同一类型的具有一样可识别特性的 数据元素或记录构成的集合。 对查找表经常进展的操作： 1. 查询某个“特定的数据元素能否在查找表中； 2. 查询某个“特定的数据元素的各种属性； 3. 在查找表中插入一个数据元素； 4. 删除查找表中的某个数据元素。 :v查找表的分类查找表的分类9.1 查找的根本概念查找的根本

2、概念静态查找表动态查找表：仅作“查询检索操作的查找表，只查找，不改动数据元素集内的数据元素。作“插入和“删除操作的查找表既查找，又改动(增减)集合内的数据元素。:v关键字关键字9.1 查找的根本概念查找的根本概念 在实践运用问题中，每个记录普通包含有多个数据域，查找是根据其中某一个指定的域进展的，这个作为查找根据的域称关键字(key)。主关键字 可独一标识一个记录的关键字。例：学号次关键字 可识别假设干记录的关键字。例：性别:v关键字关键字9.1 查找的根本概念查找的根本概念姓名姓名学号学号性别性别年龄年龄 健康情况健康情况王小林 790631男18健康陈 红 790632女20一般刘建平 7

3、90633男21健康张立立 790634男17健康 :v查找查找9.1 查找的根本概念查找的根本概念 根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。 假设表中存在这样的一个记录，那么称查找是胜利的，假设表中不存在关键字等于给定值的记录，那么称查找不胜利。静态查找如何进展查找 取决于查找表的构造，如字典，本:v平均查找长度平均查找长度(Average Search Length)9.1 查找的根本概念查找的根本概念 为确定记录在查找表中的位置，需和给定值进展比较的关键字个数的期望值称为查找算法在查找胜利时的平均查找长度(ASL)。 对于含有n个记录的表，查找胜利时的平均

4、查找长度为1niiiASLC P查找表中第i个记录的概率，且找表中关键字与给定值相等的第i个记录时，和给定值已进展过比较的关键字个数11niiP:v静态查找表静态查找表v顺序表的查找顺序表的查找v有序表的查找有序表的查找v索引顺序表的查找索引顺序表的查找9.2 静态查找表静态查找表:v顺序表的查找顺序表的查找9.2 静态查找表静态查找表顺序查找：从表的一端开场，逐个进展记录的关键 字和给定值的比较。 查找过程： 找645371921135664928880750123456789101164:v顺序查找的算法顺序查找的算法9.2 静态查找表静态查找表int Search_seq(SSTable

5、 ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 53719211356649288807501234567891011找60找不到时，i为0&(i=0):v顺序查找的算法顺序查找的算法9.2 静态查找表静态查找表int Search_seq(SSTable ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 53719211356649288807501234567891011找60&(

6、i=0)60:v顺序查找的算法顺序查找的算法9.2 静态查找表静态查找表int Search_seq(SSTable ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 53719211356649288807501234567891011找6060监视哨监视哨监视哨作用：防止每步都去判别能否查找终了:v顺序查找的算法分析顺序查找的算法分析9.2 静态查找表静态查找表 对于n个数据元素的表，假设给定值key与表中第i个元素的关键字相等，那么需求n-i+1次关键字比较，即Ci=n-i+1。 例如

7、，当第n个元素的关键字为key时，需求进展1次比较(n-n+1=1)，又如，当第一个元素为所求时，需求进展n次比较(n-1+1=n)。因此，查找胜利时，顺序查找的平均查找长度为 1niiiASLC PPi每个元素的查找概率，假设一切元素的查找概率均相等。1iPn:v顺序查找的算法分析顺序查找的算法分析9.2 静态查找表静态查找表 对于n个数据元素的表，假设给定值key与表中第i个元素的关键字相等，那么需求n-i+1次关键字比较，即Ci=n-i+1。 例如，当第n个元素的关键字为key时，需求进展1次比较(n-n+1=1)，又如，当第一个元素为所求时，需求进展n次比较(n-1+1=n)。因此，查

8、找胜利时，顺序查找的平均查找长度为 1121(1)2niinnASLPnin :v顺序查找的算法分析顺序查找的算法分析9.2 静态查找表静态查找表 假设查找失败，那么算法不断遍历到Elem0，总共比较n+1次。5371921135664928880750123456789101160:v顺序查找的算法分析顺序查找的算法分析9.2 静态查找表静态查找表查找胜利时的平均查找次数为： ASL=(1+2+3+4+n)/n = (n+1)/2 查找不胜利时的比较次数为： ASL=(n(n+1)/n = n+1 那么顺序查找的平均查找长度为： ASL=( + )/2 = 3(n+1)/4优点：算法简单，无

9、需排序，采用顺序和链式存储均可。缺陷：当n很大时，平均查找长度较大。:v有序表的查找有序表的查找9.2 静态查找表静态查找表折半查找 又称为二分法查找，每次将待查记录所在区间减少一半查找思想 先确定待查找记录所在的范围，然后逐渐减少范围，直到找到或确认找不到该记录为止前提条件 必需在具有顺序存储构造的有序表中进展:v有序表的查找有序表的查找9.2 静态查找表静态查找表81423374655687991lowhighmid例例:查找查找23high = mid-1keymid keyhigh = nlow = 1mid = (low+high)/2mid = (low+high)/2mid ke

10、ylow = mid +1mid = (low+high)/2:v有序表的查找有序表的查找9.2 静态查找表静态查找表81423374655687991lowhighmid例例:查找查找79low = mid + 1keymid keyhigh = nlow = 1mid = (low+high)/2mid = (low+high)/2mid keylow = mid +1mid = (low+high)/2:v有序表的查找有序表的查找9.2 静态查找表静态查找表81423374655687991lowhighmid例例:查找查找80low = mid + 1Key=80mid keyhigh

11、 = nlow = 1mid = (low+high)/2mid = (low+high)/2mid keylow = mid +1mid = (low+high)/2mid keyhigh = mid - 1:v折半查找的算法折半查找的算法9.2 静态查找表静态查找表int Search_Bin( SSTable ST , int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if (STmid.key = key) return mid; else if ( key=12k-1

12、个423156789101112131415:v二叉树的性质二叉树的性质6.2 二叉树二叉树性质4：具有n个结点的完全二叉树的高度为 log2n + 1证明： 设完全二叉树的高度为k，那么有 (2k-1 -1 ) n (2k -1) 或 2k-1 n 2k 两边取对数 k-1 log2n k 由于k是整数，所以k = log2n + 1:v算法性能分析算法性能分析9.2 静态查找表静态查找表8142337465568799112345678946911468823375579比较次数 log2n +1 查找不胜利： :v算法性能分析算法性能分析9.2 静态查找表静态查找表81423374655

13、68799112345678946911468823375579查找不胜利： :v算法性能分析算法性能分析9.2 静态查找表静态查找表 假设在树的高度为k的满二叉树n=2k-1中，树的第i层有2i-1个结点，树的第i层结点的全部查询次数为i*2i-1，在等概率的情况下，Pi=1/n，因此，折半查找的平均查找长度为10111122112(1 2222)1log (1)1lognnikiiiiASLPCiknnnnnn :v算法性能分析算法性能分析9.2 静态查找表静态查找表0111125(1 2222)(1 1223442)99kASLkn 81423374655687991123456789:

14、v算法性能分析算法性能分析9.2 静态查找表静态查找表 折半查找的效率相当高，在最坏的情况下(即查找失败时)的关键字比较次数也不超越断定树的深度，而且折半查找的最坏性能与平均性能相当接近。 但折半查找只能用于有序表中，而排序本身是一件很费时的事情。折半查找还要求对数据元素随机访问，因此只能用顺序存储的线性表中，因此适用于查找频繁，但是有序表元素改动少的运用中。:9.2 静态查找表静态查找表8142337465568799112345678946911468823375579:v静态树表的查找静态树表的查找9.2 静态查找表静态查找表ABCDE12345CADBE0.20.20.20.20.25

15、1iiiASLPC0.220.2 30.2 10.220.2 32.2 :v静态树表的查找静态树表的查找9.2 静态查找表静态查找表ABCDE12345CADBE0.10.20.10.40.251iiiASLPC0.1 20.2 30.1 10.420.2 32.3 :0.10.20.10.40.2v静态树表的查找静态树表的查找9.2 静态查找表静态查找表ABCDE12345CBDAE51iiiASLPC0.1 30.220.1 30.4 10.221.8 :0.10.20.10.40.2v静态树表的查找静态树表的查找9.2 静态查找表静态查找表ABCDE123451.8ASL 2.3ASL

16、:v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 折半查找的平均查找长度的前提是查找表中各个记录被查找的概率一样。假设表中各个记录被查找的概率不同，那么折半查找能否是在有序表中进展查找的最好选择呢？ 这就阐明，当有序表中各记录的查找概率不等时，折半查找性能未必是优的。 那么此时应如何进展查找呢?:v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 假设只思索查找胜利的情况，那么使查找性能达最正确的断定树是其带权内途径长度之和PH值取最小值的二叉树。 其中：n为二叉树上结点的个数(即有序表的长度)；hi为第i个结点在二叉树上的层次数；结点的权wi=cpi(i=1，2，n)，其

17、中pi为结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。1niiiPHwh:v静态树表的查找静态树表的查找9.2 静态查找表静态查找表0.10.20.10.40.2ABCDE123451.8ASL 最优查找树= ？最优二叉树(哈夫曼树)左儿子比根节点小，右儿子比根节点大?哈夫曼树的节点不是原始的数据节点:v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 由于构造静态最优查找树破费的时间代价较高，因此在此引见一种构造近似最优查找树的有效算法。:v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 假设某

18、个二叉树的PH 值在一切具有同样权值的二叉树中近似为最小，那么称它为“次优查找树(Nearly Optimal Search Tree) 次优查找树近似最优查找树 假设按关键字从小到大有序陈列的记录序列为： (rl , rl+1, , rh) 其中 rl .key rl+1.key rh.key 与每个记录相应的权值为 wl , wl+1, , wh :v静态树表的查找静态树表的查找9.2 静态查找表静态查找表构造次优查找树方法： 从序列 (rl , rl+1, , rh) 中选取第 i (l i h) 个记录作为次优 二叉树的“根结点，要求 取最小值。 然后分别对子序列 (rl , rl+1

19、, , ri-1) 和 (ri+1 , ri+2, , rh) 构造两 棵次优查找树，并分别设为根结点的左子树和右子树。 11hiijjj ij lPww :例：例： 0123456789A B C D E F G HI112534435 j Keyj Wj Pj 27 25 22 15 7 0 8 15 23 11hiijjj ij lPww 为便于计算，引入累计权 值和： iijj lswwSWj 0 1 2 4 9 12 16 20 23 28 0 l h 并设并设 wl -1 = 0 和和 swl -1 = 0， 111iiljj lswsww那么那么 1hhijj iswsww 11

20、11() () ()ihiilhliiPswswswswswswsw sw i 根根 FPj h 11 9 6 1 9 11)( iilhiswswswswP根根 i Dl h 8 1 7 i HPj l h 3 1 2 根根 i B 0 i E 0 0 i i GI根 Pj 0 0 i i ACEBGACFHDIPH = 71 PH = 83 当各关键字 查找概率不 等时，次优 查找树的查 找性能优于 折半查找。 :v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表普通搜索存在的问题： 当数据对象个数n很大时，假设用无序表方式的静态搜索构造存储，采用顺序搜索，那

21、么搜索效率极低。假设采用有序表存储方式的静态搜索构造，那么插入新记录进展排序，时间开销也很可观。这时可采用索引方法来实现存储和搜索。:v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表例如：有一个存放职工信息的数据表，每一个职工对象有近1k字节的信息, 正好占据一个页块的存储空间。建立一个索引表便于数据的搜索。:v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表索引的优势：有时数据文件很大不能一次全部装入内存，所以搜索一个数据对象无论是顺序搜索或对分搜索，都需求多次读取外存记录。索引文件比数据文件要小的多，从外存中把索引表读入内存，经

22、过搜索索引后确定了职工对象的存储地址，再经过1次读取对象操作就可以完成搜索。:v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表几个概念：稠密索引：即一个索引项对应数据表中一个对象的索引构造。此时对象在外存中可不按关键码有序存放。此索引构造叫做索引非顺序构造。前面的例子就是一个稠密索引构造。:v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表几个概念：稀疏索引：当对象在外存中按关键码有序存放时，可以把一切 n 个对象分为 b 个子表(块)存放，一个索引项对应数据表中一组对象(子表)。以下图是一个稀疏索引的例子。这样的索引构造叫做索引顺

23、序构造。:v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表分块查找：是顺序查找的一种改良方法，就是把被查找的表分成假设干块，每块中记录的存放顺序是无序的，但块与块之间必需按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。:22 12 13 8 9 20 v索引顺序表的查找分块查找索引顺序表的查找分块查找 9.2 静态查找表静态查找表条件：1. 将表分成几块，且表或者有序，或者分块有序； 2. 建立“索引表每个结点含有最大关键字域和 指向本块第一个结点的指针，且按关键字有序。 1 7 1322 48 86索引表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1