《数据结构》-静态查找表

9.1 概述,9.1.1 查找表,9.1.2 相关术语,9.1.3 类型说明,9.2 静态查找表,9.2.1 概述,9.2.2 顺序表的查找,9.2.3 有序表的查找,9.2.4 索引顺序表的查找,9.3 动态查找表,9.3.1 概述,9.3.2 二叉排序树和平衡二叉树,9.3.3 B-树和B+树,9.4 哈希表,9.4.1 定义,9.4.2 哈希函数的构造,9.4.3 处理冲突的方法,9.4.4 哈希表的查找及其分析,第九章查找,9.2 静态查找表,9.2.1 概述,ADT StaticSearchTable 数据对象D：D是具有相同特性的数据元素的集合。各个数据元 素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P： Create (初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit ( )一次且仅 一次。一旦visit ( )失败，则操作失败。 ADT StaticSearchTable,（1）静态查找表的抽象数据类型定义：,（2）查找操作的性能分析,衡量查找算法好坏的依据：其关键字和给定值进行过比较的记录个数的平均值。,平均查找长度（Average Search Length）：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。,对于含有n个记录的表，查找成功时的平均查找长度为：,（91）,查找算法的平均查找长度 查找成功时的平均查找长度 查找不成功时的平均查找长度,静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。,一、顺序查找表,顺序查找是最基本，最简单的查找方法。其查找过程为：从表中第n个记录开始,逐个进行记录的关键字和给定值的比较。若某个关见键字与给定值像相等，则查找成功，找到所查找记录；反之，若直之第一个记录，其关键字与给定值不等，则表明表中没有所查记录，查找不成功。,（1）顺序存储结构的类型定义 typedef struct ElemType *elem;/数据元素存储空间基址，建表时按/实际长度分配，0号单元留空int length; /表长度 SSTable,int Search_Seq(SSTable ST, KeyType kval) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = kval; / 设置“哨兵” for (i=ST.length; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq,ST.elemi.key!=kval;,（3）性能分析,假设nST.length，则顺序查找的平均长度为：ASL = nP1 + (n1)P2 + + 2Pn-1 + Pn,只考虑查找成功时的情况,在顺序查找的过程中，式（91）中Ci取决于所查记录在表中的位置。,假设查找每个记录的概率相等，即 Pi1/n。则在等概率情况下顺序查找的平均查找长度为：,（3）性能分析,考虑查找成功和查找不成功时的情况,顺序查找中，不论给定值key为何值，查找不成功时和给定值进行比较的关键字个数均为n1。,假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则Pi1/(2n)，此时顺序查找的平均查找长度为：,缺点：平均查找长度较大，特别是当n很大时，查找效率较低。,（4）顺序查找算法的特点,优点：算法简单且适应面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用。,上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。,二、有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,当表中记录关键字有序时（简成有序表），可以采取折半查找。折半查找是一种效率很高的查找方法，查找一个元素的平均查找时间是O（logn)。查找过程是将有序表中关键字的值Km（Km位于有序表的中间位置）与要查找的关键字K比较，若 KKm,则所要查找的记录在后半部表中，对后半部的表继续用折半查找，,例如：已知如下11个数据元素的有序表（关键字即为数据元素的值）： （05，13，19，21，37，56，64，75，80，88，92）现要查找关键字为21和85的数据元素。,给定值key21的查找过程：,ST.elemmid.key key, 令high = mid1, mid = 3；,ST.elemmid.key key, 令low = mid + 1, mid = 4；,ST.elemmid.key = key。查找成功。,（2）例子,给定值key85的查找过程：,ST.elemmid.key key, 令low = mid + 1, mid = 9；,ST.elemmid.key key, 令high = mid1, mid = 9；,因为下界low 上界high，说明表中没有关键字等于key的元素，查找不成功。,有序表的查找,（1）有序表查找的实现 折半查找（Binary Search）的查找过程：先选定待查记录所在范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。,int Search_Bin (SSTable ST, KeyType key) /在有序表ST中折半查找其关键字等于key的数据元素。/若找到，则函数值为该元素在表中的位置，否则为0。low = 1;/置区间初值high = ST.length;/low和high分别指示待查元素所在范围的下界和上界while (low 50)时，可有下列近似结果：,（4）折半查找算法的特点,特点：只适用于有序表，且限于顺序存储结构（对线性链表无法进行折半查找）。,（5）斐波那契查找,斐波那契序列：F0 = 0, F1= 1, Fi = Fi-1+ Fi-2, i2。,算法思想：假设开始时表中记录个数比某个斐波那契数小，即nFu-1，然后将给定值key和ST.elemFu-1.key进行比较，若相等，则查找成功；若key ST.elemFu-1.key，则继续在自ST.elem1至ST.elemFu-1的子表中进行查找，否则继续在自ST.elemFu-11至ST.elemFu-1的子表中进行查找，后一子表的长度为Fu-2-1。,特点：斐波那契查找的平均性能比折半查找好，但最坏情况下的性能 却比折半查找差。 分割时只需进行加、减运算。,（6）插值查找,插值查找时根据给定值key来确定进行比较的关键字ST.elemi.key的查找方法。,9.2.4 索引顺序表的查找,（1）分块查找 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需建立一个“索引表”。如下例所示。,例如，图9.2所示为一个表及其索引表，表中含有18个记录，可分成3个子表(R1, R2, , R6)、(R7, R8, , R12)和(R13, R14, , R18)。对每一个子表（或称块）建立索引项。索引表按关键字有序，则表或者有序或者分块有序。,图9.2表及其索引表,索引项包括： 关键字项：其值为该子表内的最大关键字。 指针项：指示该子表的第一个记录在表中的位置。,分块有序：即后一个子