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

1、第第9 9章章 查找查找查找的基本概念静态查找表动态查找表哈希表v查找的基本概念查找的基本概念9.1 查找的基本概念查找的基本概念查找表：是由同一类型的具有相同可辨认特性的 数据元素（或记录）构成的集合。 对查找表经常进行的操作： 1. 查询某个“特定的”数据元素是否在查找表中； 2. 查询某个“特定的”数据元素的各种属性； 3. 在查找表中插入一个数据元素； 4. 删除查找表中的某个数据元素。 v查找表的分类查找表的分类9.1 查找的基本概念查找的基本概念静态查找表动态查找表：仅作“查询”（检索）操作的查找表，只查找，不改变数据元素集内的数据元素。作“插入”和“删除”操作的查找表既查找，又改

2、变(增减)集合内的数据元素。v关键字关键字9.1 查找的基本概念查找的基本概念 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称关键字(key)。主关键字 可唯一标识一个记录的关键字。例：学号次关键字 可识别若干记录的关键字。例：性别v关键字关键字9.1 查找的基本概念查找的基本概念姓名姓名学号学号性别性别年龄年龄 健康情况健康情况王小林 790631男18健康陈 红 790632女20一般刘建平 790633男21健康张立立 790634男17健康 v查找查找9.1 查找的基本概念查找的基本概念 根据给定的某个值，在查找表中确定一个其

3、关键字等于给定值的记录或数据元素。 若表中存在这样的一个记录，则称查找是成功的，若表中不存在关键字等于给定值的记录，则称查找不成功。静态查找如何进行查找 取决于查找表的结构，如字典，电话本v平均查找长度平均查找长度(Average Search Length)9.1 查找的基本概念查找的基本概念 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(ASL)。 对于含有n个记录的表，查找成功时的平均查找长度为1niiiASLC P查找表中第i个记录的概率，且找表中关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数11niiPv

4、静态静态查找表查找表 顺序表的查找 有序表的查找 索引顺序表的查找9.2 静态查找表静态查找表v顺序表的查找顺序表的查找9.2 静态查找表静态查找表顺序查找：从表的一端开始，逐个进行记录的关键 字和给定值的比较。 查找过程： 找645371921135664928880750123456789101164v顺序查找的算法顺序查找的算法9.2 静态查找表静态查找表int Search_seq(SSTable ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 537192113566492888

5、07501234567891011找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&(i=0)60v顺序查找的算法顺序查找的算法9.2 静态查找表静态查找表int Search_seq(SSTable ST , int n, int key) ST0.key=ke

6、y; 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。 例如，当第n个元素的关键字为key时，需要进行1次比较(n-n+1=1)，又如，当第一个元素为所求时，需要进行n次比较(n-1+1=n)。因此，查找成功时，顺序查找的平均查找长度为 1nii

7、iASLC PPi每个元素的查找概率，假设所有元素的查找概率均相等。1iPnv顺序查找的算法分析顺序查找的算法分析9.2 静态查找表静态查找表 对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需要n-i+1次关键字比较，即Ci=n-i+1。 例如，当第n个元素的关键字为key时，需要进行1次比较(n-n+1=1)，又如，当第一个元素为所求时，需要进行n次比较(n-1+1=n)。因此，查找成功时，顺序查找的平均查找长度为 1121(1)2niinnASLPnin v顺序查找的算法分析顺序查找的算法分析9.2 静态查找表静态查找表 若查找失败，则算法一直遍历到Elem0，总共比

8、较n+1次。5371921135664928880750123456789101160v顺序查找的算法分析顺序查找的算法分析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优点：算法简单，无需排序，采用顺序和链式存储均可。缺点：当n很大时，平均查找长度较大。v有序表的查找有序表的查找9.2 静态查找表静态查找表折半查找 又称为二分法查找，每次将待查记录所在区间缩小一半查找思想 先确定待查找

9、记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止前提条件 必须在具有顺序存储结构的有序表中进行v有序表的查找有序表的查找9.2 静态查找表静态查找表81423374655687991lowhighmid例例:查找查找23high = mid-1keymid keyhigh = nlow = 1mid = (low+high)/2mid = (low+high)/2mid keylow = mid +1mid = (low+high)/2v有序表的查找有序表的查找9.2 静态查找表静态查找表81423374655687991lowhighmid例例:查找查找79low = mid

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

11、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=1）2k-1个423156789101112131415v二叉树二叉树的性质的性质6.2 二叉树二叉树性质4：具有n个结点的完全二叉树的高度为 log2n + 1证明： 设完全二叉树的高度为k，则有 (2k-1 -1 )

12、n (2k -1) 或 2k-1 n 2k 两边取对数 k-1 log2n k 因为k是整数，所以k = log2n + 1v算法性能分析算法性能分析9.2 静态查找表静态查找表8142337465568799112345678946911468823375579比较次数 log2n +1 查找不成功： v算法性能分析算法性能分析9.2 静态查找表静态查找表8142337465568799112345678946911468823375579查找不成功： v算法性能分析算法性能分析9.2 静态查找表静态查找表 若在树的高度为k的满二叉树n=2k-1中，树的第i层有2i-1个结点，树的第i层结点

13、的全部查询次数为i*2i-1，在等概率的情况下，Pi=1/n，因此，折半查找的平均查找长度为10111122112(1 2222)1log (1)1lognnikiiiiASLPCiknnnnnn v算法性能分析算法性能分析9.2 静态查找表静态查找表0111125(1 2222)(1 1223442)99kASLkn 81423374655687991123456789v算法性能分析算法性能分析9.2 静态查找表静态查找表 折半查找的效率相当高，在最坏的情况下(即查找失败时)的关键字比较次数也不超过判定树的深度，而且折半查找的最坏性能与平均性能相当接近。 但折半查找只能用于有序表中，而排序本

14、身是一件很费时的事情。折半查找还要求对数据元素随机访问，因此只能用顺序存储的线性表中，因此适用于查找频繁，但是有序表元素改动少的应用中。9.2 静态查找表静态查找表8142337465568799112345678946911468823375579v静态树表的查找静态树表的查找9.2 静态查找表静态查找表ABCDE12345CADBE0.20.20.20.20.251iiiASLPC0.220.2 30.2 10.220.2 32.2 v静态树表的查找静态树表的查找9.2 静态查找表静态查找表ABCDE12345CADBE0.10.20.10.40.251iiiASLPC0.1 20.2 3

15、0.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 v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 折半查找的平均查找长度的前提是查找表中各个记录被查找的概率相同。如果表中各个记录被查找的概率不同，那么折半查找是否是在有序表中进行查找的最好选择呢？ 这就说明，当有序表中各记录

16、的查找概率不等时，折半查找性能未必是优的。 那么此时应如何进行查找呢?v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 若只考虑查找成功的情况，则使查找性能达最佳的判定树是其带权内路径长度之和PH值取最小值的二叉树。 其中：n为二叉树上结点的个数(即有序表的长度)；hi为第i个结点在二叉树上的层次数；结点的权wi=cpi(i=1，2，n)，其中pi为结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。1niiiPHwhv静态树表的查找静态树表的查找9.2 静态查找表静态查找表0.10.20.10.40.2ABC

17、DE123451.8ASL 最优查找树= ？最优二叉树(哈夫曼树)左儿子比根节点小，右儿子比根节点大?哈夫曼树的节点不是原始的数据节点v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 由于构造静态最优查找树花费的时间代价较高，因此在此介绍一种构造近似最优查找树的有效算法。v静态树表的查找静态树表的查找9.2 静态查找表静态查找表 若某个二叉树的PH 值在所有具有同样权值的二叉树中近似为最小，则称它为“次优查找树”(Nearly Optimal Search Tree) 次优查找树（近似最优查找树） 假设按关键字从小到大有序排列的记录序列为： (rl , rl+1, , rh) 其中

18、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, , ri-1) 和 (ri+1 , ri+2, , rh) 构造两 棵次优查找树，并分别设为根结点的左子树和右子树。 11hiijjj ij lPww 例：例： 0123456789A B C D E F G HI112534435 j Keyj

19、 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 1111() () ()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

20、i i GI根 Pj 0 0 i i ACEBGACFHDIPH = 71 PH = 83 当各关键字 查找概率不 等时，次优 查找树的查 找性能优于 折半查找。 v索引顺序表的查找（分块查找）索引顺序表的查找（分块查找） 9.2 静态查找表静态查找表普通搜索存在的问题： 当数据对象个数n很大时，如果用无序表形式的静态搜索结构存储，采用顺序搜索，则搜索效率极低。如果采用有序表存储形式的静态搜索结构，则插入新记录进行排序，时间开销也很可观。这时可采用索引方法来实现存储和搜索。v索引顺序表的查找（分块查找）索引顺序表的查找（分块查找） 9.2 静态查找表静态查找表示例：有一个存放职工信息的数据表，

21、每一个职工对象有近1k字节的信息, 正好占据一个页块的存储空间。建立一个索引表便于数据的搜索。v索引顺序表的查找（分块查找）索引顺序表的查找（分块查找） 9.2 静态查找表静态查找表索引的优势：l有时数据文件很大不能一次全部装入内存，所以搜索一个数据对象无论是顺序搜索或对分搜索，都需要多次读取外存记录。l索引文件比数据文件要小的多，从外存中把索引表读入内存，经过搜索索引后确定了职工对象的存储地址，再经过1次读取对象操作就可以完成搜索。v索引顺序表的查找（分块查找）索引顺序表的查找（分块查找） 9.2 静态查找表静态查找表几个概念：v 稠密索引：即一个索引项对应数据表中一个对象的索引结构。此时对

22、象在外存中可不按关键码有序存放。此索引结构叫做索引非顺序结构。前面的例子就是一个稠密索引结构。v索引顺序表的查找（分块查找）索引顺序表的查找（分块查找） 9.2 静态查找表静态查找表几个概念：v 稀疏索引：当对象在外存中按关键码有序存放时，可以把所有 n 个对象分为 b 个子表(块)存放，一个索引项对应数据表中一组对象(子表)。下图是一个稀疏索引的例子。这样的索引结构叫做索引顺序结构。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 1822 12 13 8