数据结构查表.ppt

第九章 查找 概述 查找表——数据结构 同各种线性或非线性的数据结构一样，查找表也是一种在实际应用中大量使用的数据结构。 静态查找表和动态查找表 对查找表的常见操作： （1）查询某个“特定的”数据元素是否在查找表中； （2）检索某个“特定的”数据元素的各种属性； （3）在查找表中插入一个数据元素； （4）从查找表中删除某个数据元素。 查找 关键字，数据元素中某个数据项的值，用它可以标识一个数据元素。若它可以唯一标识一个数据元素，则称此关键字为主关键字(Primary Key)(对不同的记录，其主关键字均不同)。反之，用以识别若干数据元素的关键字为次关键字(Secondary Key)。 例子 例子 电话号码簿中查阅电话 字典中查阅某个词 编译程序中符号表 信息处理系统中的信息表 如何进行查找 在一个结构中查找某个数据元素的过程，依赖于数据元素在结构中的地位，即依赖于数据元素的组织关系（人为的）。 9.1 静态查找表 查找表的结构 查找过程描述 查找性能分析 查找方法比较 静态查找表的抽象数据类型 P216 9.1.1 顺序表的查找 查找表 用一般的顺序表或者线性链表来表示静态查找表。 顺序查找(Sequential Search) 从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，返回该记录在查找表中的位序；反之，若直至第一个记录，其关键字和给定值比较都不相等，则表中无此记录，查找失败，返回0。 查找性能分析 以其关键字和给定值进行过比较的记录个数的平均值作为衡量查找算法好坏的依据。 查找成功时的平均查找长度ASL 顺序查找的平均查找长度 查找不成功时的ASL 当查找不成功的情形不能忽视时，查找算法的平均查找长度应该是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。 顺序表的优缺点： 缺点：平均查找长度较大，特别是当n很大时，查找效率较低。 优点：算法简单，适用面广。它对表结构无任何要求，无论记录是否按关键字有序均可。并且以上讨论对于线性链表同样适用。 9.1.2 有序表的查找 查找表 当静态查找表是有序表（顺序表） 折半查找(Binary Search) 例如，已知有如下11个数据元素的有序表（关键字即为数据元素的值）: ( 05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92)。现在要求查找关键字为21和85的数据元素。 例子 给定值key = 21的查找过程: 给定值key = 85的查找过程: int Search_Bin( SSTable ST，KeyType key ){low = 1; high = ST.length;while( low = high ){ mid = ( low + high ) /2; if EQ( key , ST.elem[mid].key ) return mid; else if LT( key , ST.elem[mid].key ) high = mid-1; else low = mid +1;}return 0;} 折半查找性能分析 折半查找的判定树 树中每个结点表示表中的一个记录，结点中的值为该记录在表中的位置。这样一棵二叉树可以用来描述折半查找过程。 折半查找性能分析 折半查找查找成功的过程就是走了一条从根结点到与该记录相应的结点的路径，与给定值进行比较的关键字个数恰为该结点在判定树上的层次数。 折半查找查找失败的过程，就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数。 因此，折半查找法在查找成功时进行比较的关键字个 数最多不超过树的深度 ，在查找不成功时和 给定值进行比较的关键字个数最多也不超过 折半查找的ASL 假设有序表的长度为n=2h-1，则描述折半查找的判定树是深度为h的满二叉树。 该树中层次为1的结点有1个，层次为2的结点有2个，…，层次为h的结点有2h-1个。 假设有序表中每个记录的查找概率相等(Pi = 1/n)。 折半查找的优缺点 优点：效率比顺序查找高； 缺点：只适用于有序表，且限于顺序存储结构，对线性链表无法进行折半查找。 9.1.3 静态树表的查找 当有序表中各记录的查找概率不相等时，单纯的折半查找的效率并不是最高的 构造一个静态最优查找树，这样的二叉树的查找性能才是最佳的 9.1.4 索引顺序表的查找 查找表—— 以索引顺序表表示静态查找表，则Search函数用分块查找来实现。因此，分块查找又称索引顺序查找，是顺序查找的一种改进。 分块查找(索引顺序表查找