《数据结构_09_查找》由会员分享，可在线阅读，更多相关《数据结构_09_查找（123页珍藏版）》请在金锄头文库上搜索。
1、第9章 查 找9.1 静态查找表9.2 动态查找表9.3 哈希表1第9章 查 找 查找表是由同一类型的数据元素(或记录)构 成的集合。 对查找表经常进行的操作: w查询某个“特定的”数据元素是否 在查找表中； w检索某个“特定的”数据元素的各 种属性； w在查找表中插入一个数据元素； w从查找表中删去某个数据元素。2第9章 查 找 静态查找表：仅作查询和检索操作的查找 表。 动态查找表：在查询过程中，同时插入查 找表中不存在的数据元素；或者从查找表中 删除已存在的数据元素。 关键字(Key)：是数据元素(或记录)中某个数 据项的值，用它可以标识一个数据元素。 主关键字：可以惟一标识一个记录的关
2、键字 次关键字：用以识别若干记录的关键字。3第9章 查 找 查找：根据给定的某个值，在查找表中确 定一个其关键字等于给定值的记录。 w若表中存在这样一个记录，则称 查找成功，此时查找的结果为该记录 的信息，或指示该记录在查找表中的 位置； w若表中不存在这样的记录，则称 查找不成功，此时可给出一个“空”记 录或“空”指针。 查找的方法取决于查找表的结构。 w静态查找表、动态查找表49.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找9.1.3 静态树表的查找9.1.4 索引顺序表的查找59.1 静态查找表ADT StaticSearchTable 数据对象D：D是具有相同特性的数
3、据元素的 集合。每个数据元素含有类型相同的关键字 ，可唯一标识数据元素。 数据关系R：数据元素同属一个集合。 基本操作P：Create(Destroy(Search(ST, key);Traverse(ST, Visit(); ADT StaticSearchTable69.1.1 顺序表的查找 应用范围：顺序表或线性链表表示的静态查 找表。表内元素之间无序。 查找过程：从表的一端开始逐个进行记录的 关键字和给定值的比较。静态查找表的顺序存储结构为 typedef struct ElemType *elem; / 数据元素存储空间基址，/ 按实际长度分配，0号单元留空int length; /
4、 表的长度 SSTable;7ST.elemi64查找成功！0 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92ST.Lengthiiii9.1.1 顺序表的查找例1 找64监视哨8ST.elemi60查找不成功！0 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92ST.Length9.1.1 顺序表的查找例2 找609int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于/ key的数据元素。若找到，则函数值为
5、/ 该元素在表中的位置，否则为0。ST.elem0.key = key; / “哨兵”for(i=ST.length; ST.elemi.key != key; -i) ; / 从后往前找return i; / 找不到时，i为0 / Search_Seq算法 9.1 顺序表的查找109.1.1 顺序表的查找性能分析 平均查找长度 (Average Search Length) ： 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值。其中: n 为表长，Pi 为查找表中第i个记录的概率，且 ， Ci为找到该记录时，曾和给定值比较过的关键字的个数。119.1.1 顺序表的查找查找
6、第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i 个元素： n-i+1 顺序表中查找成功，比较次数：Ci = n-i+1 在等概率查找的情况下，Pi=1/n 平均查找长度：129.1.1 顺序表的查找查找失败，比较次数：n+1 在不等概率查找的情况下， wASL在PnPn-1P2P1 时取极 小值。 w若查找概率无法事先测定，则可 在每次查找之后，将刚刚查找到的记 录直接移至表尾。139.1.1 顺序表的查找 优点： w算法简单， w适应面广。 缺点： w平均查找长度较大， wn很大时，查找效率较低。149.1.2 有序表的查找一、折半查找 适用条件：采用顺序存储结
7、构的有序表。 查找过程：每次将待查记录所在区间缩小 一半。159.1.2 有序表的查找 算法描述(1)设表长为n，low、high和mid分别指向待查元素 所在区间的上界、下界和中点，k为给定值。(2)初始时，low=1, high=n, mid=(low+high) / 2。(3)让k与mid指向的记录比较：a)若k=rmid.key，查找成功；b)若krmid.key，则low=mid+1；mid=(low+high) / 2 。(4)重复操作(3)，直至lowhigh时，查找失败。169.1.2 有序表的查找high1 2 3 4 5 6 7 8 9 10 115 13 19 21 37
8、 56 64 75 80 88 92ST.Lengthlowmidmidhigh midlow查找成功！找21例1179.1.2 有序表的查找high1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92ST.Lengthlowmidmidhigh midlow查找不成功！low midlow例2找7718算法 9.2 折半查找 int Search_Bin(SSTable ST,KeyType key)low = 1; high = ST.length; / 置区间初值while (low 50时，可得近似结果 229.1.2 有序表的查
9、找二、斐波那契查找 Fibonacci数：F0=0，F1=1，Fn=Fn-1+Fn-2 算法描述 w设结点总数为n=Fu -1，查找键值为key 的结点 w首先比较 key 和 STFu-1.key 1)若=：查找成功 2)若：比较 key 和 STFu-1 + Fu-3.key239.1.2 有序表的查找FuFu-1Fu-2-1Fu-1-1第一次KeySTFu-1.KeyFu-2Fu-3Fu-1Fu-2249.1.2 有序表的查找二、斐波那契查找 优点： w平均性能比折半查找好； w分割时只需进行加、减运算。 缺点： w最坏情况下性能比折半查找差。三、插值查找 P222259.1.3 静态树
10、表的查找 应用范围：有序表、查找概率不等。 例：已知 A、B、C、D、E；查找概率分别为：0.1 、0.2、0.1、0.4、0.2求成功查找时的平均查找长度 ？EBDAC 平均查找长度 10.1+20.1+20.2+30.2+30.4 = 2.5AECBD平均查找长度 10.4+20.2+20.2+30.1+30.1 1.8269.1.3 静态树表的查找 查找成功的判定树的带权内路径长度之和: PH值最小的二叉树为静态最优查找树。 构造静态最优查找树的时间代价较高，因此 构造PH值近似最小的次优查找树。279.1.3 静态树表的查找次优查找树的构造方法：关键字序列 (r1, r2, rn) 选
11、ri作为根结点，使得 取 Pi=min Pj 对(r1,r2,ri-1)和(ri+1,ri+2,rn)再构造次优二叉树， 作为根的左右子树。 如果根的权值小，调整邻近权值较大的作为根。289.1.3 静态树表的查找 例1：已知关键字A, B, C, D, E, F, G, H, I， 查找概率分别为: 1, 1, 2, 5, 3, 4, 4, 3, 5，建 造次优查找树。HEGDFBIAC299.1.3 静态树表的查找 例2：关键字A、B、C、D、E，查找概率 分别为： 1、30、2、29、3，建造次优查 找树。ADEBCDECAB309.1.4 索引顺序表的查找 索引顺序查找（分块查找），除
12、表本身还需建立一 个“索引表”。 分块有序：数据分成若干子表，每个子表中的关键 字都比后一子表中的小(子表内部可有序也可无序) 。索引表 最大关键字 起始地址2212138920334244382448605874498653第1块第2块第3块2248862248861713特点：分块有序319.1.4 索引顺序表的查找 查找过程： （1）先确定待查记录所在的块（子表 ） （2）然后在块中顺序查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 4
13、8 861 7 13索引表 查38329.1.4 索引顺序表的查找平均查找长度：ASLbs=Lb+LwLb：查找索引表确定所在块的平均查找长度。Lw：在块中查找元素的平均查找长度。 若将表长为n的表平均分成b块，每块含s个记录， 且每个记录查找概率相等，则：(1)用顺序查找确定所在块(2)用折半查找确定所在块339.2 动态查找表9.2.1 二叉排序树9.2.2 平衡二叉树9.2.3 B- 树9.2.4 B+ 树349.2 动态查找表 表结构本身是在查找过程中动态生成的，即 对于给定值key， 若表中存在其关键字等于key的记录，则查 找成功， 否则插入关键字等于key的记录。359.2 动态
14、查找表ADT DynamicSearchTable 数据对象D：D是具有相同特性的数据元素的集合。 每个数据元素含有类型相同的关键字， 可唯一标 识数据元素。 数据关系R：数据元素同属一个集合。 基本操作P：InitDSTable(InsertDSTable(DeleteDSTable(TraverseDSTable(DT, Visit(); ADT DynamicSearchTable369.2.1 二叉排序树1. 二叉排序树的定义2. 二叉排序树的查找算法3. 二叉排序树的插入4. 二叉排序树的删除5. 二叉排序树的查找分析371. 二叉排序树的定义 二叉排序树(又称二叉查找树)：或者是一棵 空树；或者是具有下列性质的二叉树： w若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； w若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； w它的左、右子树也都分别是二叉 排序树。381. 二叉排序树的定义1225301120910232150308020901085403525
