数据结构-静态查找表.ppt

查找和静态查找表 1 查找问题的定义 2 静态查找表 3 小结和作业 查找问题的定义 1 查找表 2 查找表分类 3 关键字 4 查找 静态查找表 1 静态查找表的类型定义 2 顺序表的查找 3 有序表的查找 4 索引顺序表 查找表 定义 由同一类型的数据元素 或记录 构成的集合 查找表 对查找表经常进行的操作 1 查询 查询某个 特定的 数据元素是否在查找表中 2 检索 检索某个 特定的 数据元素的各种属性 3 插入 在查找表中插入一个数据元素 4 删除 从查找表中删去某个数据元素 查找表分类 仅作查询和检索操作的查找表 1 静态查找表 1 在查询之后 需要将 查询 结果为 不在查找表中 的数据元素插入到查找表中 2 从查找表中删除其 查询 结果为 在查找表中 的数据元素 2 动态查找表 关键字 关键字 是数据元素 或记录 中某个数据项的值 用以标识 识别 一个数据元素 或记录 主关键字 可以识别唯一的一个记录的关键字 次关键字 能识别若干记录的关键字 查找 查找 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素或 记录 查找成功 若查找表中存在这样一个记录 则称 查找成功 查找结果 给出整个记录的信息 或指示该记录在查找表中的位置 查找 查找不成功 若查找表中不存在这样一个记录 则称 查找不成功 查找结果 给出 空记录 或 空指针 如何进行查找 查找的方法取决于查找表的结构 由于查找表中的数据元素之间仅存在 同属于一个集合 的松散关系 不存在明显的组织规律 因此不便于查找 如何进行查找 1 静态查找表 2 动态查找表 3 哈希表 为了提高查找的效率 需要在查找表中的元素之间人为地附加某种确定的关系 换句话说 用另外一种结构来表示查找表 静态查找表 数据对象D 数据关系R D是具有相同特性的数据元素的集合 每个数据元素含有类型相同的关键字 可唯一标识数据元素 数据元素同属一个集合 ADTStaticSearchTable 静态查找表 Create Destroy Search ST key Traverse ST Visit 基本操作P ADTStaticSearchTable 静态查找表 基本操作 Create 操作结果 构造一个含n个数据元素的静态查找表ST Destroy 初始条件 静态查找表ST存在 操作结果 销毁表ST 静态查找表 基本操作 Search ST kval 初始条件 静态查找表ST存在 kval为和查找表中元素的关键字类型相同的给定值 操作结果 若ST中存在其关键字等于kval的数据元素 则函数值为该元素的值或在表中的位置 否则为 空 静态查找表 基本操作 初始条件 静态查找表ST存在 Visit是对元素操作的应用函数 操作结果 按某种次序对ST的每个元素调用函数Visit 一次且仅一次 一旦Visit 失败 则操作失败 Traverse ST Visit 顺序查找表 顺序存储 静态查找表的顺序存储结构为 typedefstruct ElemType elem 数据元素存储空间基址 建表时 按实际长度分配 0号单元留空intlength 表的长度 SSTable 静态查找表可以是顺序或链式存储结构 数据元素类型的定义为 typedefstruct keyTypekey 关键字域 其它属性域 ElemType TELemType 顺序查找适应于以顺序表或线性链表表示的静态查找表 顺序查找表 顺序存储 顺序查找1 顺序查找的过程 1 从前往后找 假设给定值e 64 要求ST elem i e 问 i ST elem i 7 假设给定值e 66 要求ST elem i e 问 i 假设给定值e 66 要求ST elem i e i 0 查找不成功 顺序查找1 intsearch SSTableL ElemType 顺序查找2 ST elem kval 64 64 i 7 顺序查找的过程 2 设置哨兵 从后往前找 查找成功 假设给定值kval 64 要求ST elem i kval 问 i 顺序查找2 ST elem kval 60 60 i 0 查找不成功 假设给定值kval 60 要求ST elem i kval 问 i 顺序查找2 intSearch Seq SSTableST KeyTypekval 在顺序表ST中顺序查找其关键字等于 key的数据元素 若找到 则函数值为 该元素在表中的位置 否则为0 ST elem 0 key kval 设置 哨兵 for i ST length i 从后往前找returni 找不到时 i为0 Search Seq ST elem i key kval 顺序查找性能分析 平均查找长度 AverageSearchLength ASL 查找算法的平均查找长度 为确定记录在查找表中的位置 需和给定值进行比较的关键字个数的期望值 顺序查找性能分析 平均查找长度 AverageSearchLength ASL n为表长Pi为查找表中第i个记录的概率 Ci为找到该记录时 曾和给定值比较过的关键字的个数 顺序查找性能分析 顺序表查找的平均查找长度为 对顺序表而言 Ci n i 1 ASL nP1 n 1 P2 2Pn 1 Pn 在等概率查找的情况下 顺序查找性能分析 顺序查找的特点 1 顺序查找表的查找算法简单 对表结构没有任何要求 适应于线性链表和顺序表2 平均查找长度较大 特别不适用于表长较大的查找表 顺序查找性能分析 若查找概率无法事先测定 则查找过程采取的改进办法是 在每次查找之后 将刚刚查找到的记录直接移至表尾的位置上 在不等概率查找的情况下 ASLss在Pn Pn 1 P2 P1时取极小值 有序表的查找 若以有序表表示静态查找表 则查找过程可以用 折半查找 来实现 折半查找 过程 1 确定待查记录所在的范围 然后逐步缩小范围2 直到找到或者找不到该查记录 有序表的查找 Low 查找区间的下界 mid low high 2 high 查找区间的上界 1 若kval ST elem mid keylow mid 1 high不变 2 若kval ST elem mid keyhigh mid 1 low不变 3 若kval ST elem mid key 查找成功 返回mid 4 若low high 查找失败 有序表的查找 例如 key 64的查找过程如下 ST elem ST length 有序表的查找 intSearch Bin SSTableST KeyTypekval low 1 high ST length 置区间初值while low high mid low high 2 if kval ST elem mid key returnmid 找到待查元素elseif kval ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 有序表的查找 1 2 2 3 3 3 3 4 4 4 4 折半查找性能分析 当有序表中有11个元素时 其元素的比较次数如下表所示 有序表的查找 判定树 6 3 9 1 2 5 7 8 10 11 4 有序表的查找 6 3 9 1 2 5 7 8 10 11 4 1 查找64的过程 6 9 7 2 查找30的过程 3 4 6 5 有序表的查找 判定树 1 用二叉树来描述折半查找 树中每个结点表示一个记录 结点中的值为该记录在表中的位置 这种描述查找过程的二叉树成为判定树 2 查找有序表中任一记录的过程就是走了一条从根结点到该记录相应结点的路径 3 和给定值进行比较的关键字个数为该结点在判定树上的层次 有序表的查找 假设n 2h 1并且查找概率相等 则 一般情况下 表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同 在n 50时 可得近似结果 有序表的查找 顺序表和有序表的查找性能对比 索引顺序表的查找 在建立顺序表的同时 建立一个索引 对顺序表进行分块查找 索引 索引顺序表的查找 索引顺序表 索引 顺序表 索引表 按关键字有序 顺序表 有序或者分块有序 索引 块内最大关键字 该块在顺序表中的起始位置 索引顺序表的查找 typedefstruct KeyTypemaxkey intstadr indexItem 索引项 typedefstruct indexItem elem intlength indexTable 索引表 索引顺序表的查找 索引顺序表的查找过程 1 由索引确定记录所在区间 2 在顺序表的某个区间内进行查找 索引顺序查找的过程也是一个 缩小区间 的查找过程 索引顺序表的查找 索引顺序查找的平均查找长度 查找 索引 的平均查找长度 查找 顺序表 的平均查找长度 索引可以根据查找表的特点来构造 小结和作业 1 查找问题的定义 2 常用查找方法 本节主要内容 索引顺序查找 顺序查找 折半查找 查找的结果 查找问题的描述 关键字的概念 各种查找方法的性能分析 平均查找长度 小结和作业 作业 9 1 9 3 关键字 ABCDEPi 0 20 30 050 30 15Ci 23123 三 静态查找树表 在不等概率查找的情况下 折半查找不是有序表最好的查找方法 例如 此时ASL 2 0 2 3 0 3 1 0 05 2 0 3 3 0 15 2 4 若改变Ci的值21323 则ASL 2 0 2 1 0 3 3 0 05 2 0 3 3 0 15 1 9 使达最小的判定树称为最优二叉树 其中 静态最优查找树 StaticoptimalsearchTree 为计算方便 令wi pi选择二叉树的根结点 使达最小 介绍一种次优查找树的构造方法 为便于计算 引入累计权值和 并设wl 1 0和swl 1 0 则推导可得 0 2 3 8 11 15 18 23 例如 l h 21 18 12 4 3 10 18 h 9 6 0 8 E C 2 1 A h 5 3 l h G 3 0 1 3 所得次优查找树如下所示 查找比较 总次数 3 2 4 1 2 5 3 3 1 4 3 3 2 5 52 查找比较 总次数 3 2 2 1 3 5 1 3 3 4 2 3 3 5 59 和折半