《数据结构课件查找》由会员分享，可在线阅读，更多相关《数据结构课件查找（93页珍藏版）》请在金锄头文库上搜索。
1、第九章 查找 由于查找运算的使用效率很高 几乎在任意一个计算 机系统软件和应用软件中都会涉及到 所以当问题所涉及 的数据量相当大时 查找方法的效率就显得格外重要 在一些实事查询系统中尤其如此 因此 本章将系统 地讨论各种查找方法 并通过对它们的效率分析来比较各 种查找方法的优劣 Date1 第九章 查找 9 1 静态查找表 9 2 动态查找表 9 3 哈希表 Date2 查找的基本概念 查找又称为查询或检索 是在一批记录中依照某个域 的指定域值 找出相应的记录的操作 在计算机中 被查找的数据对象是由同一类型的记录 构成的集合 可称之为查找表 search table 在实际应用问题中 每个记录
2、一般包含有多个数据域 查找是根据其中某一个指定的域进行的 这个作为 查找依据的域称为关键字 key Date3 对于给定的关键字的值 如果在表中经过查找能找到相应 的记录 则称查找成功 一般可输出该记录的有关信息或 指示该记录在查找表中的位置 若表中不存在相应的记录 则称查找不成功 此时应该给出不成功的信息 查找算法中的基本运算是记录的关键字与给定值所进行的 比较 其执行时间通常取决于比较的次数 因此 通常以 关键字与给定值进行比较的记录个数的平均值 作为衡量 查找算法好坏的依据 Date4 查找表操作及分类 操作 1 查询某个 特定的 数据元素是否在查找表中 2 某个 特定的 数据元素的各种
3、属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 分类 若对查找表只作 1 和 2 两种操作 则称此类查找表为 静态查找表 若在查找过程中同时插入查找表中不存在的数据元素 或者从查找表中删除已存在的某个数据元素 则称此类查找 表为动态查找表 Date5 9 1 静态查找表 抽象数据类型静态查找表的定义 ADT StaticSearchTable 数据对象D D是具有相同属性的数据 元素的集合 数据关系R 数据元素同属一个集合 基本操作P Create Destroy Search ST key Traverse ST Visit ADT StaticSearchTable
4、Date6 一 顺序查找 顺序查找的基本思想是 顺序查找的基本思想是 从线性表的一端开始 依次将扫描到得结点关键字和给定值K相比较 若当前扫描到得结点关键字与K相等 则查找成功 若扫描结束后 仍 未找到关键字等于K的结点 则查找失败 顺序查找的存储结构要求 顺序查找的存储结构要求 顺序查找方法既适用于线性表的顺序存储结构 也适用于线性表的链 式存储结构 使用单链表作为存储结构时 扫描必须从第一个结点开始 顺序查找对数据在表中存放的先后次序没有任何要求 在表的组织方式中 线性表是最简单的一种 顺序查找 是一种最简单的查找方式 Date7 顺序查找的线性表定义如下 typedef struct E
5、lemType elem int length 每个结点包含两部分 内容 Key 和info 其他 信息 Date8 2 算法的实现 技巧 把待查关键字key存入表头或表尾 俗称 哨兵 这样可以加快执行速度 例 若将待查找的特定值key存入顺序表的首部 如0号单元 则顺序查找的实现方案为 从后向前逐个比较 int Search Seq SSTable ST KeyType key 在顺序表ST中 查找关键字与key相同的元素 若成功 返回其位 置信息 否则返回0 ST elem 0 key key 设立哨兵 可免去查找过程中每一步 都要检测是否查找完毕 0单元被当作监视哨 用来判断表是否查 找
6、完毕 技巧 当n 1000时 查找时间将减少一半 for i ST length ST elem i key key i 不要用for i n i 0 i 或 for i 1 i0 i if ST elem i key key return i 使用了监视哨 在查 找过程中 不用每一 步都去判断是否查找 结束 0单元被当作监 视哨 用来判断表是 否查找完毕 技巧 当n 1000时 查找 时间将减少一半 找到 返回元素在线 性表中的存储位置 未找到 返回0 Date10 查找效率怎样计算 用平均查找长度ASL衡量 讨论 平均查找长度 为确定记录在查找表中的位置 需和给定值进行比较的 关键字个数的
7、期望值称为查找算法在查找成功时的平均查 找长度 Average Search Length Date11 平均查找长度 ASL average search length 其中 n是文件记录个数 Pi是查找第i个记录的查找概率 通常取等概率 即Pi 1 n Ci是找到第i个记录时所经历的比较次数 统计意义上的 数学期望值 物理意义 假设每一元素被查找的概率相同 则查找每 一元素所需的比较次数之总和再取平均 即为ASL 显然 ASL值越小 时间效率越高 Date12 讨论 如何计算ASL 分析 查找第1个元素所需的比较次数为1 查找第2个元素所需的比较次数为2 查找第n个元素所需的比较次数为n
8、总计全部比较次数为 1 2 n 1 n n 2 未考虑查找不成功的 情况 查找哨兵所需 的比较次数为n 1 这是查找成功的情况 若求某一个元素的平均查找次数 还应当除以n 等概率 即 ASL 1 n 2 时间效率为 O n Date13 u 如果查找不成功的情况不能忽略时 ASL的计算步骤 查找成功的概率为1 2 那么查找成功时第i个记录的概率 pi 1 2n 所以查找成功时的ASL n i 1 n 1 n i 1 1 2n 4 1 1 2 查找不成功的概率为1 2 所以查找不成功时的ASL n 1 所以所以 ASLss 3 4 n 1 Date14 顺序查找算法分析 顺序查找的优点是算法简单
9、 适应面广 且不要求表中数据有序 缺点是平均 查找长度较大 特别是当n较大时 查找 效率较低 不宜采用 Date15 二 有序表的查找 折半查找 折半查找 Birary search 也称为二分查找 它的 查找速度比顺序查找快 但它要求数据在线性表中数据在线性表中 按查找的关键字域有序排列 按查找的关键字域有序排列 设n个数据存放于数组r中 且已经过排序 按由小 到大递增的顺序排列 采用二分查找 首先用要查找的给定值k与表正中 间元素的关键值相比较 此元素的下标 Date16 比较结果有三种可能 如果r m key k 说明如果存在欲查找的元素 该元 素一定在数组的前半部分 查找范围缩小了一半
10、 修改 查找范围的的上界high m 1 继续对数组的前半部分进 行二分查找 如果r m key k 说明如果存在欲查找的元素 该元 素一定在数组的后半部分 查找范围缩小了一半 修改 查找范围的的下界low m 1 继续对数组的后半部分进行 二分查找 如果r m key k 查找成功 m所指的记录就是查找 到的数据 Date17 重复上述过程 查找范围每次缩小1 2 当范围不断缩小 出现查找范围的下界大于上界时 则查找失败 确定关键字 为key的记录不存在 二分查找是一种效率较高的算法 最好的情况是第一次比较 即找到所查元素 即使一次比较没有找到 也把进一步查找 的范围缩小一半 与此类似 每比
11、较一次均使查找范围减半 故最坏的情况所需比较次数为O log2n 对于较大的n显 然较顺序查找速度快得多 Date18 查找23和79的过程如下图 mid low high 2不进位取整 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 low highmid 08 14 23 37 46 55 68 79 91 low high mid 1mid 08 14 23 37 46 55 68 79 91 low mid 1high mid 08 14 23 37 46 55 68 79 91 lowhigh mid 08 14 23 37
12、 46 55 68 79 91 lowhigh mid 08 14 23 37 46 55 68 79 91 low high mid Date19 折半查找的c语言算法程序 int Search Bin SSTable ST int n int key int low high mid low 1 high n while low high mid low high 2 if ST mid key key return mid 查找成功 else if key50n 50时 可得近似结果时 可得近似结果 ASLbs 2 n 1 1 Date22 二分查找的性能分析 具体例子 11个元素 查找
13、过程可用判定树 描述 查找成功时进行比较的 关键字个数最多不超过 树的深度 log2n 1 当n较大时 平均查找长度为 ASLbs log2 n 1 1 6 3 1 9 4710 25811 Date23 三 静态树表的查找 u 当有序表中各记录的查找概率相等时 按照 判定树描述的查找过程来进行折半查找 性能 最优 有序表中各记录的查找概率不等时 二分查 找性能不一定最优 u 可由具体例子说明 u 静态最优查找树和次优查找树方法可解决这 一问题 Date24 例如 关键字 A B C D E ci 2 3 1 2 3 此时 ASL 2 0 2 3 0 3 1 0 05 2 0 3 3 0 15
14、 2 4 若改变ci的值 2 1 3 2 3 则 ASL 2 0 2 1 0 3 3 0 05 2 0 3 3 0 15 1 9 不是中间的比 而是根据概率值得不同具体选择 不是中间的比 而是根据概率值得不同具体选择 C AD B 12345 pi 0 2 0 3 0 05 0 3 0 15 E Date25 在概率不等的情况下 在概率不等的情况下 如何能够使平均查找长度最小 如何能够使平均查找长度最小 查找概率大的查找路径要短 判定树该如何设计判定树该如何设计 PH wihi n i 1 其中 wi cpi c为常量 pi为结点i的查找概率 hi为结点所 在的层次 称PH值最小的判定二叉树为
15、静态最优查找树 这里只考虑查找成功的情况 如果只考虑查找成功的情况 则使查找性能达到最佳的判 定树是其带全路径长度之和PH值 取最小的二叉树 Date26 构建静态最优查找树的代价很高 这里介绍一种构建静态最优查找树的代价很高 这里介绍一种 构造近似最有树的算法构造近似最有树的算法 次优查找树 次优查找树 二 次优查找树的构造二 次优查找树的构造 已知一个序列 rl rl 1 rh 递增有序 其中 rl key rl 1 key data k return b Date38 二叉排序树查找递归算法 if kdata return search b left k else return sear
16、ch b right k Date39 非 递 归 算 法 btree treesearch btree b int k btree p p b while p NULL if p data k return p else if kdata p p left else p p right return NULL Date40 二叉排序树的插入 二叉排序树是一种动态树表 特点是树 的结构不是一次生成 而是在查找过程 中 当树中不存在关键字等于给定值的 结点时再进行插入 新插入的结点一定是一个新添加的叶子 结点 并且是查找不成功时查找路径上 访问的最后一个结点的左孩子或右孩子 结点 Date41 二叉排序树的插入 续 从空树出发 经过一系列的查找插入操 作之后 可生成一棵二叉排序树 设查找的关键字序列为 45 12 53 3 37 50 98 1 8 43 60 则生成的二叉排序树如下 中序遍历二叉排序树可得到 一个关键字的有序序列 插入时 不必移动结点 45 12 3 53 375098 843 1 60 Date42 二叉排序树的删除 一般二叉树删除存在的问题 如何在二叉排序树上删除结
