算法13--静态查找表PPT课件

第8章查找 2 本章主要内容8 1静态查找表8 2动态查找表8 3哈希表 3 基本概念 1 什么是查找表是由同一类型的数据元素 或记录 组成的数据集合 2 对查找表经常进行的操作1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素的各种属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 4 3 查找表分类 动态查找表 静态查找表 4 关键字是数据元素 或记录 中某个数据项的值 用以标识 识别 一个数据元素 或记录 若此关键字可以识别唯一的一个记录 则称之谓 主关键字 若此关键字能识别若干记录 则称之谓 次关键字 5 5 查找 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素或 记录 若查找表中存在这样一个记录 则称 查找成功 查找结果 给出整个记录的信息 或指示该记录在查找表中的位置 否则称 查找不成功 查找结果 给出 空记录 或 空指针 例 高考成绩表示 typedeffloatKeyType 实型typedefintKeyType 整型typedefchar KeyType 字符串型数据元素类型定义为 typedefstruct KeyTypekey 关键字域 其它域 ElemType 典型的关键字类型说明 对两个关键字的比较约定为如下的宏定义 对数值型关键字 defineEQ a b a b defineLT a b a b defineLQ a b a b 对字符串型关键字 defineEQ a b Strcmp a b defineLT a b Strcmp a b 0 defineLQ a b Strcmp a b 0 典型的关键字类型说明 对两个关键字的比较约定为如下的宏定义 对数值型关键字 defineEQ a b a b defineLT a b a b defineLQ a b a b 对字符串型关键字 defineEQ a b Strcmp a b defineLT a b Strcmp a b 0 defineLQ a b Strcmp a b 0 典型的关键字类型说明 静态查找数据类型定义 ADTStaticSearchTable 数据对象D D是具有相同特性的数据元素的集合 各个数据元素均含有类型相同 可唯一标识数据元素的关键字 数据关系R 数据元素同属一个集合 8 1静态查找表 4 22 2020 8 1 1顺序表的查找 静态查找表的顺序存储结构 typedefstruct ElemType elem 数据元素存储空间基址 建表时按实长度分配 0号单元留空intlength 表长度 SSTable 8 1 1顺序表的查找 intSearch Seq SSTableST KeyTypekey ST elem 0 key key 哨兵 for i ST length EQ ST elem I key key i 从后往前找Returni 找不到时 i为0 Search Seq 4 22 2020 顺序 的含义 从表尾 或表头 开始以顺序方式搜索查找表 将关键字与给定值进行比较 查找的顺序与数据元素的存储位置有关系 与数据元素的值没有关系 ST elem 回顾顺序表的查找过程 假设给定值e 64 要求ST elem i e i 20 7 ST elem ST elem 60 kval 64 kval 60 64 哨兵 改进 查找成功时平均查找长度 ASL 为确定记录在查找表中的位置 需和给定值进行比较的关键字个数的期望值其中 n为表长 Pi为查找表中第i个记录的查找概率 且Ci为找到该记录时 曾和给定值比较过的关键字的个数 分析顺序查找的时间性能 在等概率查找的情况下 顺序表查找的平均查找长度为 ASL nP1 n 1 P2 2Pn 1 Pn 对顺序表 a1 a2 an 而言 C1 n Ci n i 1 Cn 1 如果查找概率无法事先测定 则查找过程采取的改进办法是 1 在每次查找之后 将刚刚查找到的记录直接移至表尾的位置上 2 每个记录附设一访问频度域 按访问频度非递减有序排列 在不等概率查找的情况下 如果已知每个数据元素的概率 则当Pn Pn 1 P2 P1时 ASLss取极小值 即 为提高查找效率 概率大的记录应该放在表尾 2有序表的查找 折半查找 二分法查找 1 算法思想 要求n个记录存放在一个顺序表L中 并按其关键码从小到大排好了序 称此表为有序表 先求位于查找区间正中的记录的下标mid 用其关键码与给定值x比较 L mid Key x 查找成功 L mid Key x 把查找区间缩小到表的前半部分 再继续进行对分查找 L mid Key x 把查找区间缩小到表的后半部分 再继续进行对分查找 每比较一次 查找区间缩小一半 如果查找区间已缩小到一个记录 仍未找到想要查找的记录 则查找失败 2有序表的查找 折半查找 二分法查找 4 22 2020 4 22 2020 4 22 2020 折半查找算法描述 intSearch Bin SSTableST KeyTypekey 在有序表ST中折半查找其关键字等于key的数据元素 若找到 则函数值为该元素在表中的位置 否则为0 low 1 high ST length 置区间初值while low high mid low high 2 if key ST elem mid key returnmid 找到待查元素elseif key ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 4 22 2020 从折半查找法可知 找到第6个数仅需比较1次 找到第3和第9个数需2次 找到第1 4 7 10个数需3次 找到第2 5 8和11个数需4次 查找过程可以用下图的二叉树来表示 查找某个结点所比较的次数等于该结点的层次数 实际上查找某个结点的过程就是从根结点到相应的结点的路径 4 22 2020 查找成功时进行比较的次数最多不超过该树的深度 而具有n个结点的判定树的深度为 log2n 1 所以折半查找法在查找成功时的比较次数最多为 log2n 1次 如果考虑到查找不成功的情况 则判定树如下所示 方框表示查找不成功的情况 由此可见 查找不成功时的最多比较次数也是 log2n 1 4 22 2020 246810131518202224252730 15 6 2 4 10 8 13 24 20 27 18 22 25 30 算法分析 List 1234567891011121314 折半查找的判定树 有2n 1个结点 高度不超过完全二叉树 4 22 2020 最多的比较次数不超过完全二叉树的高度 所以 最坏情况下的查找长度是 查找成功的平均查找长度 设查找任一记录的概率都相等 即 pi 1 n在第k层上最多有2k 1个结点 在第k层上的结点需比较k次 所以 4 22 2020 4 22 2020 ASL n 1 n log2 n 1 1 log2 n 1 1优点 比较次数少 检索速度快 缺点 要将元素按关键码排序 且只适用于顺序存储结构 折半查找法的优缺点 3 静态树表的查找 在概率不等的查找情况下 折半查找不是有序表最好的查找方法 关键字 ABCDEPi 0 10 20 10 40 2Ci 23123 例如 此时ASL 2 0 1 3 0 2 1 0 1 2 0 4 3 0 2 2 3 若改变Ci的值32312 则ASL 3 0 1 2 0 2 3 0 1 1 0 4 2 0 2 1 8 4 22 2020 如果只考虑查找成功的情况 则使其查找性能达最佳的判定树是其带权内路径长度之和PH值 和平均查找长度成正比 取最小值的二叉树 称PH值取最小的二叉树为静态最优查找树 由于构造静态最优查找树花费的时间代价较高 所以构造近视最优查找树的有效算法 4 22 2020 选择二叉树的根结点 使达最小 为便于计算 引入累计权值和并设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 4 22 2020 查找比较 总次数 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 E C G B D F 和折半查找相比较 D B A C F E G 所得次优二叉树如下 A 4 22 2020 4 22 2020 4 22 2020 StatusSecondOptimal BiTree 生成结点 构造次优二叉树的算法 4 22 2020 if i low T lchild NULL 左子树空elseSecondOptimal T lchild R sw low i 1 构造左子树if i high T rchild NULL 右子树空elseSecondOptimal T rchild R sw i 1 high 构造右子树returnOK SecondOptimal 4 22 2020 StatusCreateSOSTre SOSTree CreatSOSTree 4 22 2020 a b 4 22 2020 三 索引顺序表的查找 分块查找 索引顺序表的查找是鉴于顺序查找和折半查找的一种查找 索引顺序表是由索引表和顺序表两部分组成 索引顺序表的特点是把若干个数据元素分成若干块 每一块称为一个顺序表 要求块与块之间要有序 即第i 1块的所有元素的关键字要大于第i块的所有元素的关键字 为了查找方便 为每一块建立一个索引项 索引项 key addr key域标记该块中最大记录的关键字 addr域指向该块的起始地址 索引表是由若干索引项组成的有序表 4 22 2020 例 4 22 2020 分块查找的数据结构 D d1 d2 dn 1 将n个数据元素分为s个块B1 B2 Bs 2 块之间有序 Bi 1中的任一元素小于Bi中的任一元素 i 1 2 n 1 3 为每个Bi块设一索引项 keyi addri 4 s个索引项构成索引表 5 块内可有序也可无序 4 22 2020 在索引顺序表中查找的基本思想 首先在索引表中查找 确定该查找的元素在哪个块中 可以是折半查找 也可以是顺序查找 2 先确定待查记录所在块 再在块内查找 顺序查找 3 算法实现typedefstructIndexType keyTypemaxkey 块中最大的关键字 intstartpos 块的起始位置指针 Index 4 22 2020 intBlock search RecTypeST Indexind KeyTypekey intn intb 在分块索引表中查找关键字为key的记录 表长为n 块数为b inti 0 j k while ib printf nNotfound return 0 j ind i startpos while jn EQ ST j key key j 0 printf nNotfound return j 4 22 2020 4 算法分析 设表长为n个记录 均分为b块 每块记录数为s 则b n s 设记录的查找概率相等 每块的查找概率为1 b 块中记录的查找概率为1 s 则平均查找长度ASL 设在索引表中和块内都是顺序查找 索引表中查找 ALSindex s 1 2块中查找 ALSlock n s 1 2所以 ALSbs s 1 2 n s 1 2 n s s 2 1显然它与s的取值有关 当时 ASLbs有最小值 4 22 2020 例n 10000 s 100 则顺序查找 ASL n 1 2 5000次 索引顺序表退化成有序表 即可进行折半查找 索引顺序表退化成顺序表 即可进行顺序查找 当s n时 当s 1时 4 22 2020 Fibonacci查找 Fibonacci查找方法是根据Fibonacci数列的特点对查找表进行分割 Fibonacci数列的定义是 F 0 0 F 1 1 F j F j 1 F j 2 1查找思想设查找表中的记录数比某个Fibonacci数小1 即设n F j 1 用Low High和Mid表示待查找区间的下界 上界和分割位置 初值为Low 1 High n 取分割位置Mid Mid F j 1 比较分割位置记录的关键字与给定的K值 4 22 2020 相等 查找成功 大于 待查记录在区间的前半段 区间长度为F j 1 1 修改上界指针 High Mid 1 转 小于 待查记录在区间的后半段 区间长度为F j 2 1 修改下界指针 Low Mid 1 转 直到越界 Low High 查找失败 2算法实现在算法实现时 为了避免频繁计算Fibonacci数 可用两个变量f1和f2保存当前相邻的两个Fibonacci数 这样在以后的计算中可以依次递推计算出 4 22 2020 intfib intn inti f f0 0 f1 1 if n 0 return 0 if n 1 return 1 for i 2 i n i f f0 f1 f0 f1 f1 f return f intFib search RecTypeST KeyTypekey intn 在有序表ST中用Fibonacci方法查找关键字为key的记录 intLow 1 High