《静态查找表2动态查找表3哈希查找表.ppt》由会员分享，可在线阅读，更多相关《静态查找表2动态查找表3哈希查找表.ppt（51页珍藏版）》请在三一办公上搜索。
1、1、静态查找表2、动态查找表3、哈希查找表,查找,查找,查找在某种数据结构中找出满足条件的结点：找到查找成功找不到查找失败关键字（键）能唯一确定结点的一个或多个域平均查找长度查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）,顺序表的查找,静态查找表,算法思想：从表的一端开始，用给定值k与表中各个结点的键值逐个比较：查找成功-找出相等键盘值；查找失败-已到达表的另一端（可在此设置一个监视哨，作为下标越界的条件），即表中所有结点的键值都不等于k。,0,1,2,n-3,n-2,n-1,n,key,8,100,10,0,7,1,3,i,0,1,2,n-3,n-2,n-1,n,i,数组
2、ST.elem,key,查找 key=8 的结点所在的数组元素的下标。,8,100,10,0,7,1,3,顺序表的查找,key,8,100,10,0,7,1,3,i,顺序表的查找,静态查找表,监视哨的作用：作为越界（即已查完）的检测条件，省去在循环中每次均要判定是否越界，从而节省比较的时间。,顺序表的查找,结点类型定义：typedef struct int key;/*关键字*/folat info;/*其它域*/JD;,int search(JD r,int n,int k)int i=n;/*从表尾开始向前查找*/r0.key=k;/*设置监视哨*/While(ri.key!=k)i-;r
3、eturn(i);,顺序表查找算法：,性能分析：平均查找长度ASL（Average Search Length）成功查找情况下：设每个结点的查找概率相等,一般查找情况下(包括成功、不成功两种情况)：设成功与不成功两种情况可能性相等，每个结点的查找概率也相等。,顺序表的查找,顺序表的查找,顺序查找的特点：（1）算法简单，对线性表的逻辑次序无要求（即不必按关键字值不增或不减的次序排列）（2）存储结构可采用顺序或链式存储结构均可，但其平均查找长度较大(（n+1)/2),有序表的查找,折半查找（或二分查找法）,二分法的特点：（1）线性表的表中结点必须按关键字有序；（2）线性表须采用顺序存储结构。二分法
4、思想：（1）用给定的k与有序表的中间位置mid上的结 点的关键字比较，若相等，查完（2）若rmid.key k)，则执行（3）（3）在右子表中继续进行二分查找。,查找 key=9 的结点所在的数组元素的下标地址。,数组 ST.elem 如下图所示有序数组 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,有序表的查找,有序表的查找,查找 key=9 的结点所在的
5、数组元素的下标地址。,有序表的查找,查找 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,有序表的查找,0,1,2,mid=4,key,4,8,9,10,11,13,19,3,4,5,6,7,high=3,low=1,0,1,2,mid=4,key,4,8,9,10,11,13,19,3,4,5,6,7,high=7,low=1,0
6、,1,2,mid=2,key,4,8,9,10,11,13,19,3,4,5,6,7,high=3,low=1,有序表的查找,0,1,2,mid=2;但 key=5 8,向左,key,4,8,9,10,11,13,19,3,4,5,6,7,high=1,low=1,0,1,2,key,4,8,9,10,11,13,19,3,4,5,6,7,high=3,low=1,0,1,2,mid=2,key,4,8,9,10,11,13,19,3,4,5,6,7,high=1（mid-1）,low=1,有序表的查找,mid=1,但 key=5 4,向右,失败条件：low high;处于间隙中的键值导致这种
7、情况！,表示：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;Return(0);,性能分析,1、最坏情况分析：设 key 和中点的二次比较的时间代价 1如果 n=1,则 low=high=mid,则代价为 1，记为 S（1）1如果 n 是奇数，那么中点
8、元素的左、右段各有(n-1)/2 个元素如果 n 是偶数，中点元素的左段有 n/2-1 个元素；右段有 n/2 个元素因此，算法工作的那一段，最多有 n/2 项 S（n）=1+S（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,有序表的查找,有序表的查找,1、最坏情况分析：定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为1+log2n，大体上和 log2n 成正比
9、。也可用判定树的方法进行推导。如：,1,6,7,3,5,2,4,8,key=k4,?,0,1,2,3,4,5,6,7,8,当寻找 key=8 及小于、大于 8 的键值的相应结点时，查找次数最大。达到了判定树的深度或高度。,有序表的查找,性能分析,2、平均情况分析（在成功查找的情况下）：设每个 结点的查找概率相同都为1/n。为了简单起见，设结点个数为 n=2t-1（t=1,2,3）。经过 1 次比较确定的结点个数为 1=20 个，红色标识的结点。经过 2 次比较确定的结点个数为 2=21 个，绿色标识的结点。经过 3 次比较确定的结点个数为 4=22 个，灰色标识的结点。经过 t 次比较确定的结
10、点个数为 2t-1 个，黑色标识的结点。注意：20+21+22+2t-1=2t-1 最多经过 t 次比较可以找到有序表中的任何一个结点e.g:当 t=4 时的例子：最多经过 t=4 次比较找到任何一个结点,4,8,9,10,11,13,19,29,1,2,3,4,5,6,7,8,32,47,65,77,81,93,99,9,10,11,12,13,14,15,有序表的查找,性能分析,Fibonacci 数定义：F0=0，F1=1，Fn=Fn-1+Fn-2 如：0,1,2,3,5,8,13,21,34,55,89,144,233,Fibonacci 查找,实现 设结点的总数为 n=Fu-1，查找
11、键值为 key 的结点 首先比较 key STFu1.key 如果 key STFu1.key，则比较 key 与 STFu1+Fu3.key,Fibonacci 查找,注意：设根结点（或子树的根结点）同它的左、右儿子的下标之差为Fu3 那么，根结点（或子树的根结点）的左儿子同它的儿子的下标之差为Fu4 根结点（或子树的根结点）的右儿子同它的儿子的下标之差为Fu5 可以设计类似于二分查找的算法。但先要把 Fu3、Fu4、Fu5计算出来，它们也构成 Fibonacci 数,Fibonacci 查找,n=F6-1=13-1=12个结点的查找过程 Fu1=8 Fu3=3 Fu4=2 Fu5=1,3,
12、11,12,7,10,5,8,2,6,4,1,9,STFu1.key,差为 Fu3=3,差为 Fu4=2,差为 Fu5=1,共 Fu1 1817个结点,共 Fu2 1514个结点,Fibonacci 查找,优点：只用、法，不用除法。平均查找速度更快。O(log2n)级。缺点：最坏情况下比二分查找法差。必须先给出Fibonacci 数。,Fibonacci 查找,除中点下标的选择和二分查找不同外，其余类似。用于关键字值均匀的情况，平均特性更好。,实现设 mid 为中点的下标。low 为具有最小关键字值结点的下标，high为具有最大关键字值结点的下标。mid=(high-low+1)(key-ST
13、.elemlow.key)/(ST.elemhigh.key-ST.elemlow.key）,差值查找,分块查找,存储方式：线性表分成若干块，每个块内的元素的关键字不一定有序（“块内无序”）块与块之间必须按键值有序，即前一块中的最大键值小于后一块中的最小键值（“分块有序”）。附加索引表：索引表的一块索引表结点由键域、链域组成。,存放相应块的最大键值。,存放指向本块第一个结点的指针。,查找 key=47 的结点索引。查索引表，确定在第三块内进行顺序查找,3,8,7,36,35,21,40,60,1,2,3,4,5,6,7,8,9,47,索引,顺序表,8,36,60,1,4,7,块最大关键字,块起
14、始地址,索引表,块最大关键字有序,块内关键字无序（也可有序）,分块查找,应用范围：有序表、查找概率不等。,E,B,D,A,C,举例：已知 A、B、C、D、E；查找概率分别为：0.1、0.2、0.1、0.4、0.2 求成功查找时的平均查找长度？,A,E,C,B,D,平均查找长度 10.1+20.1+20.2+30.2+30.4 2.5,平均查找长度10.4+20.2+20.2+30.1+30.1 1.8,静态树表的查找,例子说明越接近根结点，那么代价之和将越小。,n PH=Wi Hi j=1,PH 值最小的二叉树为最优查找树。,静态树表的查找,次最优查找树：,H,E,G,D,F,举例：已知 A、
15、B、C、D、E、F、G、H、I；查找概率分别为：1、1、2、5、3、4、4、3、5 建造次最优查找树。,A,D,E,B,C,D,E,C,A,B,B,I,A,C,建造方法：1、两边权值等 2、根结点或子树的根结点应尽量大。,A、B、C、D、E1 30 2 29 3,静态树表的查找,定义：或是空树，或是具有如下性质的二叉树：（1）若它的lc非空，则lc上所有结点的key 根的key（3）它的lc、rc本身又是一棵二叉排序树,二叉排序树,性质：对二叉排序树按中序遍历所得到的中序序列是一个递增的有序序列。特点：用非线性结构表示一个线性有序表。,二叉排序树,45,12,53,3,37,24,100,61
16、,90,78,按中序遍历：3，12，24，37，45，53，61，78，90，100,递增,二叉排序树,Typedef struct nodeint key;struct node*lc,*rc;JD;,采用二叉链表作存储结构，它是一种动态数据结构，这种上结构的插入、删除操作非常方便方便，无需移动大量的元素。,结点类型定义,在一棵给定的二叉排序树中插入新结点，只要保证插入仍符合二叉排序树的定义即可。插入的方法是：若二叉排序树（以r为根）为空，则待插入结点*s作为根结点插入空树中，否则（非空），在二叉排序树中查找给定的结点，若找到（即：将待插入结点的关键字（前者）和树根的关键字（后者）比较，两者
17、相等），则无须插入，否则（查找必停止在左指针或右指针处）：若前者后者，插入到右子树中。,插入运算,在一棵给定的二叉排序树中插入新结点，只要保证插入仍符合二叉排序树的定义即可。插入结点时，不需要遍历树，仅需走一条从根到某个有空子树的结点的路径。而插入的结点作为叶子结点。,插入运算,在下图给定的二叉排序树中插入结点20。,45,12,53,3,37,24,100,61,90,78,20,插入运算,Status Inset BST(BiTree/Insert BST,程序实现,插入算法,在一棵给定的二叉排序树中查找键值为k的结点的方法是：若树为空，返回空指针，否则：若k key，在左子树检索k，否则
18、：若k r-key，在右子树检索k，否则：k=r-key，找到，返回k的指针；若找到某个结点的左子树或右子树是空，则查找失败并返回空指针。,查找运算,显然，在二叉排序树中查找某结点其实是从根结点出发走了一条从根到待查结点的路径。考虑如下两种不同插入次序的序列构成的二叉排序树，插入次序分别为：,40,24,55,12,37,12,24,37,40,55,40，24，12，37，55 12，24，37，40，55,查找运算,插入次序分别为：,40,24,55,12,37,12,24,37,40,55,40，24，12，37，55 12，24，37，40，55,显然，第 i 层结点需比较 i 次。在
19、等概率的前提下，上述两图的平均查找长度为：,查找运算,由上例分析易知：在二叉排序树中进行查找的平均查找长度和二叉树的形态有关，即，最坏:（n+1)/2（单支树）最好：log2n（形态匀称，与二分查找的判定树相似）,查找运算,Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree/SearchBST,程序实现,查找运算,在一棵给定的二叉排序树中删除一个结点，必须保证删除后仍符合二叉排序树的定义。关键是要找出替换结点。递归描述：当r（根）为空时返回，否则：当r-key大于k，在r的左子树中删除之，当r-key小于k，在r的右子树中删除之，当r的左
20、子树为空时，用r的右子树代替，当r的右子树为空时，用r的左子树代替，当r的左、右子树不空时，找出r的左子树的“最右下”（最大结点）代替r。,删除运算,非递归描述：(1)若被删结点无右孩子，则用它的左孩子代替该结点；,f,p,s,(2)若被删结点无左孩子，则用它的右孩子代替该结点；,f,rc,p,s,lc,p为被删结点,p为被删结点,S为替换结点,S为替换结点,删除运算,非递归描述：(3)若被删结点有左、右孩子，则用它的前驱结点s（被删结点的左子树中数据域值最大的结点，即左子树“最右下”的结点）代替被子删结点，此时，由于s结点无右孩子（参见下图），可按上述第（1）种情况删除s结点。,f,prc,p,s,p为被删结点,S为替换结点q为替换结点的双亲。,plc,slc,q,删除运算,在一棵给定的二叉排序树中删除一个结点示例：,10,3,6,2,4,18,12,15,6,3,4,2,18,12,15,删除10,删除运算,在一棵给定的二叉排序树中删除一个结点示例：,6,3,4,2,18,12,15,删除12,6,3,4,2,18,15,删除运算,在一棵给定的二叉排序树中删除一个结点示例：,6,3,4,2,18,15,6,3,4,2,15,删除18,删除运算,删除运算,Status DeleteBST(BiTree/DeleteBST,
