数据结构查找

1、1、静态查找表、静态查找表2、动态查找表、动态查找表3、哈希查找表哈希查找表查找查找查找查找查找在某种数据结构中找出满足条件的结点：找到查找成功找不到查找失败关键字（键）能唯一确定结点的一个或多个域平均查找长度查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）顺序表的查找顺序表的查找静态查找表静态查找表算法思想：从表的一端开始，用给定值k与表中各个结点的键值逐个比较： 查找成功-找出相等键盘值； 查找失败-已到达表的另一端（可在此设置一个监视哨，作为下标越界的条件），即表中所有结点的键值都不等于k。012n-3n-2n-1nkey 8100100713i012n-3n-2n-1n

2、i数组数组 ST.elem key查找查找 key = 8 的结点所在的数组元素的下标。的结点所在的数组元素的下标。 8100100713顺序表的查找顺序表的查找key 8100100713i顺序表的查找顺序表的查找静态查找表静态查找表监视哨的作用：作为越界（即已查完）的检测条件，省去在循环中每次均要判定是否越界，从而节省比较的时间。顺序表的查找顺序表的查找结点类型定义：typedef struct int key; /*关键字*/ folat info; /*其它域*/JD;int search(JD r , int n, int k)int i = n; /*从表尾开始向前查找*/r0.k

3、ey = k; /*设置监视哨*/While(ri.key! = k) i-;return(i) ;顺序表查找算法：性能分析：性能分析： 平均查找长度平均查找长度ASL（Average Search Length ）成功查找情况下：设每个结点的查找概率相等成功查找情况下：设每个结点的查找概率相等一般查找情况下一般查找情况下( (包括成功、不成功两种情况包括成功、不成功两种情况) )：设成功与不成功两种情况可能性相等，每个结点的查找概设成功与不成功两种情况可能性相等，每个结点的查找概率也相等。率也相等。 顺序表的查找顺序表的查找顺序表的查找顺序表的查找顺序查找的特点：（1）算法简单，对线性表的逻

4、辑次序无要求（即不必按关键字值不增或不减的次序排列）（2）存储结构可采用顺序或链式存储结构均可，但其平均查找长度较大(（n+1)/2)有序表的查找有序表的查找折半查找（或二分查找法）折半查找（或二分查找法）二分法的特点：（1）线性表的表中结点必须按关键字有序；（2）线性表须采用顺序存储结构。二分法思想：（1）用给定的k与有序表的中间位置mid上的结 点的关键字比较，若相等，查完（2）若rmid.key k)，则执行（3）（3）在右子表中继续进行二分查找。查找查找 key = 9 的结点所在的数组元素的下标地址。的结点所在的数组元素的下标地址。数组数组 ST.elem 如下图所示有序如下图所示有

5、序数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemi+1. Key; i= 1, 2 ,n-1查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 7 （初始时为最大下标（初始时为最大下标 n ）;比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =4 4 8 9 10 11 13 19有序表的查找有序表的查找012mid=4 但但 key=9 8, 向右向右key 4 8 9 10 11 13 1934567high=3（mid-1）low=1012mid=3; k

6、ey 4 8 9 10 11 13 1934567high=3low=3查找查找 key = 5 的结点所在的数组元素的下标地址。的结点所在的数组元素的下标地址。数组数组 ST.elem 如下图所示有序如下图所示有序数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1查查找范围找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ;比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid =(low+high)/ 2 = 2有序表的查找有序表的查找012mid=4key 4 8

7、 9 10 11 13 1934567high=3 low=1012mid=4key 4 8 9 10 11 13 1934567high=7low=1012mid=2key 4 8 9 10 11 13 1934567high=3low=1有序表的查找有序表的查找012mid=2; 但但 key=5 8, 向左向左key 4 8 9 10 11 13 1934567high=1low=1012key 4 8 9 10 11 13 1934567high=3low=1012mid=2key 4 8 9 10 11 13 1934567high=1（mid-1）low=1有序表的查找有序表的查找

8、mid=1,但但 key=5 high; 处于间隙中处于间隙中的键值导致这种情况！的键值导致这种情况！表示：表示：typedef struct ElemType * elem; int length; / length = n有序表的查找有序表的查找int halfsearch (JD r , int n, int k)int i, j, mid;i = 1, j = n;While (i = j)mid = ( i+j ) / 2;If ( k = = rmid.key ) return(mid);else if (k rmid.key ) j = mid-1; else i = mid+1

9、;Return(0); 性能分析性能分析 1、最坏情况分析：设、最坏情况分析：设 key 和中点的二次比较的时间代价和中点的二次比较的时间代价 1如果如果 n = 1, 则则 low = high = mid , 则代价为则代价为 1，记为，记为 S（1） 1如果如果 n 是奇数，那么中点元素的左、右段各有是奇数，那么中点元素的左、右段各有 (n-1)/2 个元素个元素如果如果 n 是偶数，中点元素的左段有是偶数，中点元素的左段有 n/2-1 个元素；右段有个元素；右段有 n/2 个元素个元素因此，算法工作的那一段，最多有因此，算法工作的那一段，最多有 n/2 项项 S（n）= 1 + S（

10、n/2 ）= 1 + 1 + S（ n/22 ）= 1 + 1 + 1 + S（ n/23 ） = 1 + 1 + 1 + + 1 + S（ n/2k ）当当 1 = n/2k 2 时；则时；则 n/2k = 1 此时：此时： 2k = n 2k+1 即即 k = log2n k+1注意：注意：k 不可为小数，它是正整数。不可为小数，它是正整数。 k = log2n 故：故： S（n）= 1 + log2n 有序表的查找有序表的查找012mid= 4 4 8 9 10 11 13 1934567high=7low=1012mid= 4 4 8 9 10 11 13 1934567low=1 2

11、0high=88有序表的查找有序表的查找 1、最坏情况分析：、最坏情况分析：定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为1+ log2n ，大体上和大体上和 log2n 成正比。也可用判定树的方法进行推导。成正比。也可用判定树的方法进行推导。如：如：16735248key = k4?012345678489101113192912345678 当寻找当寻找 key = 8 及小于、大于及小于、大于 8 的键值的相应结点时，查找的键值的相应结点时，查找次数最大。达到了判定树的深次数最大。达到了判定树的深度或高度。度或高度

12、。有序表的查找有序表的查找性能分析性能分析2、平均情况分析（在成功查找的情况下）：设每个、平均情况分析（在成功查找的情况下）：设每个 结点的查找概率相同结点的查找概率相同都为都为1/n。为了简单起见，设结点个数为为了简单起见，设结点个数为 n = 2t -1 （t = 1,2,3 ）。）。 经过经过 1 次比较确定的结点个数为次比较确定的结点个数为 1 = 20 个个 ，红色标识的结点。，红色标识的结点。 经过经过 2 次比较确定的结点个数为次比较确定的结点个数为 2 = 21 个个 ，绿色标识的结点。，绿色标识的结点。经过经过 3 次比较确定的结点个数为次比较确定的结点个数为 4 = 22

13、个个 ，灰色标识的结点。，灰色标识的结点。经过经过 t 次比较确定的结点个数为次比较确定的结点个数为 2t-1 个个 ，黑色标识的结点。，黑色标识的结点。注意：注意： 20 + 21 + 22 + + 2t-1 = 2t -1 最多经过最多经过 t 次比较可以找到有序表中的任何一个结点次比较可以找到有序表中的任何一个结点e.g: 当当 t = 4 时的例子：最多经过时的例子：最多经过 t=4 次比较找到任何一个结点次比较找到任何一个结点48910 1113192912345678324765778193999101112131415有序表的查找有序表的查找性能分析性能分析 Fibonacci

14、数数定义：定义：F0 = 0，F1 = 1，Fn = Fn-1 + Fn-2 如：如：0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 Fibonacci Fibonacci 查找查找 实现实现 设结点的总数为设结点的总数为 n = Fu - 1，查找键值为查找键值为 key 的结点的结点 首先比较首先比较 key STFu1.key 如果如果 key STFu1.key ，则比较则比较 key 与与 STFu1+ Fu3.key Fibonacci Fibonacci 查找查找 注意：注意：设根结点（或子树的根结点）同它的左、右儿子的下标之设根结点

15、（或子树的根结点）同它的左、右儿子的下标之差为差为Fu3 那么，那么，根结点（或子树的根结点）的左儿子同它的儿子的下根结点（或子树的根结点）的左儿子同它的儿子的下标之差为标之差为Fu4 根结点（或子树的根结点）的右儿子同它的儿子的下标之差根结点（或子树的根结点）的右儿子同它的儿子的下标之差为为Fu5 可以设计类似于二分查找的算法。但先要把可以设计类似于二分查找的算法。但先要把 Fu3 、 Fu4 、 Fu5计算出来，它们也构成计算出来，它们也构成 Fibonacci 数数 Fibonacci Fibonacci 查找查找 n = F6 - 1 = 13 - 1 = 12个结点的查找过程个结点的

16、查找过程 Fu1 = 8 Fu3 = 3 Fu4 = 2 Fu5 = 1 311127105826419STFu1.key差为差为 Fu3 = 3 差为差为 Fu4 = 2差为差为 Fu5 = 1共共 Fu1 1817个结点个结点共共 Fu2 1514个结点个结点 Fibonacci Fibonacci 查找查找 优点：优点：只用只用 、法，不用除法。平均查找速度更快。、法，不用除法。平均查找速度更快。O(log2n)级。级。缺点：缺点：最坏情况下比二分查找法差。必须先给出最坏情况下比二分查找法差。必须先给出Fibonacci 数。数。 Fibonacci Fibonacci 查找查找除中点下

17、标的选择和二分查找不同外，除中点下标的选择和二分查找不同外，其余类似。用于其余类似。用于关键字值均匀的情况，平均特性更好。关键字值均匀的情况，平均特性更好。实现实现设设 mid 为中点的下标。为中点的下标。low 为具有最小关键字值结点的下为具有最小关键字值结点的下标，标，high为具有最大关键字值结点的下标。为具有最大关键字值结点的下标。mid =(high-low+1)(key-ST.elemlow.key)/ (ST.elemhigh.key - ST.elemlow.key） 差值查找差值查找分块查找分块查找存储方式：存储方式：线性表分成若干块，每个块内的元素的关键字不线性表分成若干块

18、，每个块内的元素的关键字不一定有序（一定有序（“块内无序块内无序”）块与块之间必须按键值有序，即前一块中的最大块与块之间必须按键值有序，即前一块中的最大键值小于后一块中的最小键值（键值小于后一块中的最小键值（“分块有序分块有序”）。）。附加索引表：附加索引表：索引表的一块索引表结点由键域、链域组成。索引表的一块索引表结点由键域、链域组成。存放相应块的最大键值。存放指向本块第一个结点的指针。查找查找 key = 47 的结点索引。查索引表，确定在第三块内进的结点索引。查索引表，确定在第三块内进行顺序查找行顺序查找387363521406012345678947索引索引顺序表顺序表83660147

19、块最大关键字块最大关键字块起始地址块起始地址索引表索引表块最大关键字有序块最大关键字有序块内关键字无序（也可有序）块内关键字无序（也可有序）分块查找分块查找 应用范围：有序表、查找概率不等。应用范围：有序表、查找概率不等。EBDAC 举例：已知举例：已知 A、B、C、D、E；查找概率分别为：查找概率分别为：0.1、0.2、0.1、0.4、0.2 求成功查找时的平均查找长度？求成功查找时的平均查找长度？AECBD平均查找长度平均查找长度 10.1+20.1+ 20.2+ 30.2+ 30.4 2.5平均查找长度平均查找长度10.4+20.2+ 20.2+ 30.1+ 30.1 1.8静态树表的查

20、找静态树表的查找 例子说明越接近根结点，例子说明越接近根结点， 那么代价之和将越小。那么代价之和将越小。 n PH = Wi Hi j=1 PH 值最小的二叉树为最优查找树。值最小的二叉树为最优查找树。静态树表的查找静态树表的查找 次最优查找树：次最优查找树：HEGDF 举例：已知举例：已知 A、B、C、D、E、F、G、H、I；查找概率分别为：查找概率分别为：1、 1、2、 5、3、 4、4、 3、5 建造次最优查找树。建造次最优查找树。ADEBCDECABBIA建造方法：建造方法：1、两边权值等、两边权值等 2、根结点或子树的根结点应尽量大。、根结点或子树的根结点应尽量大。A、B、C、D、E

21、1 30 2 29 3静态树表的查找静态树表的查找定义：定义：或是空树，或是具有如下性质的二叉树：（1）若它的lc非空，则lc上所有结点的key 根的key（3）它的lc、rc本身又是一棵二叉排序树二叉排序树二叉排序树性质：性质：对二叉排序树按中序遍历所得到的中序序列是一个递增的有序序列。特点：特点：用非线性结构表示一个线性有序表。二叉排序树二叉排序树45125333724100619078按中序遍历：按中序遍历：3，12，24，37，45，53，61，78，90，100递增二叉排序树二叉排序树Typedef struct nodeint key;struct node *lc, *rc;JD

22、;采用二叉链表作存储结构采用二叉链表作存储结构，它是一种动态数据结构，这种上结构的插入、删除操作非常方便方便，无需移动大量的元素。结点类型定义结点类型定义在一棵给定的二叉排序树中插入新结点，只要保证插入仍符合二叉排序树的定义即可。插入的方法是：插入的方法是：若二叉排序树（以r为根）为空，则待插入结点*s作为根结点插入空树中，否则（非空），在二叉排序树中查找给定的结点，若找到（即：将待插入结点的关键字（前者）和树根的关键字（后者）比较，两者相等），则无须插入，否则（查找必停止在左指针或右指针处）：若前者后者，插入到右子树中。插入运算插入运算在一棵给定的二叉排序树中插入新结点，只要保证插入仍符合二

23、叉排序树的定义即可。插入结点时，不需要遍历树，仅需走一条从根到某个有空子树的结点的路径。而插入的结点作为叶子结点。插入运算插入运算在下图给定的二叉排序树中插入结点20。4512533372410061907820插入运算插入运算Status Inset BST ( BiTree &T，Element e ) / 在二叉分类树中不存在 e.key 时，插入并返回 TRUE，否则返回 FALSE。 if ( ! SearchBST ( T，e.key，NULL，p ) s = ( Bitree ) malloc ( sizeof ( BitNode ) ); s-data = e; s-l

24、child = s-rchild = NULL; if ( ! p ) T = s; else if ( LT( e.key , p -data. key ) ) p - lchild = s; else p - rchild = s; return TRUE; return FALSE; / Insert BST 程序实现程序实现 插入算法插入算法在一棵给定的二叉排序树中查找键值为k的结点的方法是：若树为空，返回空指针，否则：若k key，在左子树检索k，否则：若k r-key，在右子树检索k，否则：k = r-key，找到，返回k的指针；若找到某个结点的左子树或右子树是空，则查找失败并返回

25、空指针。查找运算查找运算显然，在二叉排序树中查找某结点其实是从根结点出发走了一条从根到待查结点的路径。考虑如下两种不同插入次序的序列构成的二叉排序树，插入次序分别为：4024551237122437405540，24，12，37，55 12，24，37，40，55查找运算查找运算插入次序分别为：4024551237122437405540，24，12，37，55 12，24，37，40，55显然，第 i 层结点需比较 i 次。在等概率的前提下，上述两图的平均查找长度为：)(35/ )54321 ()(2 . 25/ )23221 (11右图左图niiiniiicpcp查找运算查找运算由上例分析易知：由上例分析易知：在二叉排序树中进行查找的平均查找长度和二叉树的在二叉排序树中进行查找的平均查找长度和二叉树的