数据结构导论第6章查找表.ppt

第6章查找表 查找 Search 的相关概念 查找 就是在数据集合中寻找满足某种条件的数据对象 查找表 是由同一类型的数据元素 或记录 组成的数据集合 查找的结果通常有两种可能 查找成功 即找到满足条件的数据对象 查找不成功 或查找失败 作为结果 报告一些信息 如失败标志 失败位置等 对查找表经常进行的操作 1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素的各种属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 静态查找表仅作查询和检索操作的查找表 动态查找表有时在查询之后 还需要将 查询 结果为 不在查找表中 的数据元素插入到查找表中 或者 从查找表中删除其 查询 结果为 在查找表中 的数据元素 表结构本身可以在查找过程中动态生成 关键字 Key 数据元素 记录 中某个数据项的值 用以标识一个数据元素 主关键字 可唯一地标识一个数据元素的关键字 次关键字 用以识别若干记录的关键字 使用基于主关键字的查找 查找结果应是唯一的 如何进行查找 查找的方法取决于查找表的结构 由于查找表中的数据元素之间不存在明显的组织规律 因此不便于查找 为了提高查找的效率 需要在查找表中的元素之间人为地附加某种确定的关系 换句话说 用另外一种结构来表示查找表 6 2静态查找表6 3动态查找树表6 4哈希表 散列表 衡量一个查找算法的时间效率的标准是 在查找过程中关键字的平均比较次数或平均读写磁盘次数 只适合于外部查找 这个标准也称为平均查找长度ASL AverageSearchLength 通常它是查找结构中对象总数n或文件结构中物理块总数n的函数 算法所需要的存储量和算法的复杂性等问题 6 2静态查找表 静态查找表用顺序表作为存储结构在静态查找表中 数据对象存放于数组中 利用数组元素的下标作为数据对象的存放地址 查找算法根据给定值x 在数组中进行查找 直到找到x在数组中的存放位置或可确定在数组中找不到x为止 6 2 1顺序表的查找 SequentialSearch 静态查找表的顺序存储结构为 definemaxsize静态查找表的表长typedefstruct ElemTypeitem maxsize 1 存储数据元素的数组空间 0号单元留空intn 表的长度 sqtable 数据元素类型ElemType的定义为 typedefstruct keyTypekey 关键字域 其它属性域 ElemType intSearch sqtable sqtableR KeyTypek 顺序查找的算法 0号元素为监视哨inti R item 0 key k for i R n R item i key K i returni 查找过程 从表中最后一个元素开始 顺序用各元素的关键字与给定值K进行比较 若找到与其值相等的元素 则查找成功 给出该元素在表中的位置 否则 若直到第一个记录仍未找到关键字与x相等的对象 则查找失败 顺序查找的时间性能 设查找第i个元素的概率为pi 查找到第i个元素所需比较次数为ci 则查找成功的平均查找长度 在顺序查找情形 ci n i 1 i 1 n 因此在等概率情形 pi 1 n 6 2 2有序表的查找 上述顺序查找表的查找算法简单 但平均查找长度较大 特别不适用于表长较大的查找表 若以有序表表示静态查找表 则查找过程可以基于 折半 进行 折半查找 二分查找 BinarySearch 折半查找 先求位于查找区间正中的对象的下标mid 用其关键字与给定值K比较 R item mid Key K 查找成功 R item mid Key K 把查找区间缩小到表的前半部分 再继续进行对分查找 R item mid Key K 把查找区间缩小到表的后半部分 再继续进行对分查找 每比较一次 查找区间缩小一半 如果查找区间已缩小到一个对象 仍未找到想要查找的对象 则查找失败 R item R length 例如 key 64的查找过程如下 low high mid low mid high mid low指示查找区间的下界 high指示查找区间的上界 mid low high 2 折半查找 1 mid low high 2 2 比较R item mid Key K 如果R item mid Key K 则查找成功 返回mid值如果R item mid Key K 则置high mid 1如果R item mid Keyhigh时 表明查找不成功 查找结束 intSearch Bin sqtableR KeyTypeK low 1 high R length 置区间初值while low high mid low high 2 if K R item mid Key returnmid 找到待查元素elseif key R item mid Key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 折半查找的性能分析 先看一个具体的情况 假设 n 11 判定树 与关键字的比较次数不会超过树的深度 log2n 1 一般情况下 表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同 查找第j层的数据要比较j次 第j层上共有结点2j 1个 假设n 2h 1并且查找概率相等则在n 50时 可得近似结果 折半查找的效率比顺序查找高 但折半查找只适用于有序表 且限于顺序存储结构 在建立顺序表的同时 建立一个索引 索引顺序表中的元素分块有序 升序或降序 第i块中的最大 小 值小 大 于第i 1块中的最 大 小值 块间有序 块内无序 6 2 3索引顺序表的查找 分块查找 索引 每个索引项有两个域 块内最大键值块起始地址 查找 1 先查索引表 折半查找 2 再查顺序表 顺序查找索引顺序查找的平均查找长度 查找 索引 的平均查找长度 在块中查找 顺序表 的平均查找长度 对比顺序表和有序表的查找性能 n 1 n 1 nlogn 几种查找表的特性 查找插入删除 无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表 n n logn n logn 1 1 n 1 nlogn 1 从查找性能看 最好情况能达 logn 此时要求表有序 2 从插入和删除的性能看 最好情况能达 1 此时要求存储结构是链表 可得如下结论 6 3树表 动态查找表 表结构本身是在查找过程中动态生成的 基本操作 InitDSTable 遍历查找表 6 3 1二叉排序树 BinarySortTree 定义二叉排序树 二叉查找树 或者是一棵空树 或者是具有下列性质的二叉树 每个结点都有一个作为查找依据的关键字 key 所有结点的关键字互不相同 左子树 若非空 上所有结点的关键字都小于根结点的关键字 右子树 若非空 上所有结点的关键字都大于根结点的关键字 左子树和右子树也是二叉排序树 例如 如果对一棵二叉排序树进行中序遍历 可以按从小到大的顺序 将各结点关键字排列起来 通常 取二叉链表作为二叉排序树的存储结构 typedefstructBiTNode 结点结构DataTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree 1 二叉排序树的查找算法 若二叉排序树为空 则查找不成功 否则1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 例如 二叉排序树 查找关键字 50 50 50 35 50 30 40 35 50 90 50 80 90 95 从上述查找过程可见 在查找过程中 生成了一条查找路径 从根结点出发 沿着左分支或右分支逐层向下直至关键字等于给定值的结点 查找成功或者从根结点出发 沿着左分支或右分支逐层向下直至指针指向空树为止 查找不成功 算法P135 二叉排序树上的构建 如何构造二叉排序树 构造过程 不断插入的过程 从空树出发 依次插入R1 Rn各数据值 1 如果二叉排序树是空树 则插入结点就是二叉排序树的根结点 2 如果二叉排序树是非空的 则插入值与跟结点比较 若小于根结点的值 就插入到左子树中去 否则插入到右子树中 示例 45 24 53 12 22 90 注意 输入的序列不同 构造的二叉排序树不同 2 二叉排序树的插入算法 根据动态查找表的定义 插入 操作在查找不成功时才进行 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子 查找算法描述如下 intSearchBST BiTreeT KeyTypekey BiTreef BiTree SearchBST 否则表明查找不成功 返回 指针p指向查找路径上访问的最后一个结点 并返回函数值为0 指针f指向当前访问 的结点的双亲 其初始调用值为NULL if T elseif key T data key elseif keydata key else p f return0 查找不成功 p T return1 查找成功 returnSearchBST T lchild key T p 在左子树中继续查找 returnSearchBST T rchild key T p 在右子树中继续查找 二叉排序树上插入结点的算法 intInsertBST BiTree InsertBST s BiTree malloc sizeof BiTNode 为新结点分配空间s data e s lchild s rchild NULL if p T s 插入s为新的根结点 elseif e keydata key p lchild s 插入 s为 p的左孩子elsep rchild s 插入 s为 p的右孩子 return1 插入成功 二叉排序树上的构建 如何构造二叉排序树 构造过程 不断插入的过程 从空树出发 依次插入R1 Rn各数据值 1 如果二叉排序树是空树 则插入结点就是二叉排序树的根结点 2 如果二叉排序树是非空的 则插入值与跟结点比较 若小于根结点的值 就插入到左子树中去 否则插入到右子树中 示例 45 24 53 12 22 90 注意 输入的序列不同 构造的二叉排序树不同 二叉排序树的删除算法 和插入相反 删除在查找成功之后进行 并且要求在删除二叉排序树上某个结点之后 仍然保持二叉排序树的特性 可分三种情况讨论 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 1 被删除的结点是叶子结点 例如 被删关键字 20 88 其双亲结点中相应指针域的值改为 空 2 被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 指向被删除结点的左子树或右子树 被删关键字 40 80 3 被删除的结点既有左子树 也有右子树 40 40 以其前驱替代之 然后再删除该前驱结点 被删结点 前驱结点 被删关键字 50 二叉排序树的删除递归算法 算法9 7 intDeleteBST BiTree 其中删除操作过程如下所描述 voidDelete BiTree p 从二叉排序树中删除结点p 并重接它的左子树或右子树if p rchild elseif p lchild else Delete 右子树为空树则只需重接它的左子树 q p p p lchild delete q q q 左子树为空树只需重接它的右子树 q p p p rchild delete q p p q q q p s p lchild while s rchild q s s s rchild s指向被删结点的前驱 左右子树均不空 p data s data if q p q rchild s lchild elseq lchild s lchild 重接 q的左子树delete s q s 查找性能的分析 折半查找长度为n的判定树是惟一的 而含有n个结点的二叉排序树却不惟一 含有n个结点的平均查找长度和树的形态有关 最差 单支树 深度为n ASL n 1 2最好 形态和折半查找的判定树相同 和log2n成正比 4 平衡二叉树 AVL树 一棵AVL树或者是空树 或者是具有下列性质的二叉查找树 它的左子树和右子树都是AVL树 且左子树和右子树的高度之差的绝对值不超过1 结点的平衡因子balance balancefactor 每个结点附加一个数字 该结点右子树的高度减去左子树的高度所得的高度差 根据AVL树的定义 任一结点的平衡因子只能取 1 0和1 如果一棵二叉查找树是高度平衡的 它就成为AVL树 如果它有n个结点 其高度可保持在O log2n 平均查找长度也可保持在O log2n 是平衡树 不是平衡树 构造二叉平衡 查找 树的方法是 在插入过程中 采用平衡旋转技术 P235 6 4哈希表 6 4 1什么叫哈希表 以上两节讨论的表示查找表的各种结构的共同特点 记录在表中的位置和它的关键字之间不存在一个确定的关系 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 用这类方法表示的查找表 其平均查找长度都不为零 对于频繁使用的查找表 希望ASL 0 办法 预先知道所查关键字在表中的位置 即 要求 记录在表中位置和其关键字之间存在一种确定的关系 例如 为每年招收的1000名新生建立一张查找表 其关键字为学号 其值的范围为xx000 xx999 前两位为年份 若以下标为000 999的顺序表表示 则查找过程可以简单进行 取给定值 学号 的后三位 不需要经过比较便可直接从顺序表中找到待查关键字 因此 需在关键字与记录在表中的存储位置之间建立一个函数关系 以f key 作为关键字为key的记录在表中的位置 通常称这个函数f key 为哈希函数 Zhao Qian Sun Li Wu Chen Han Ye Dei 例如 对于如下9个关键字 设哈希函数f key Ord 第一个字母 Ord A 1 2 Chen Zhao Qian Sun Li Wu Han Ye Dei 问题 若添加关键字Zhou 怎么办 能否找到另一个哈希函数 1 哈希 Hash 函数是一个映象 即 将关键字的集合映射到某个地址集合上 它的设置很灵活 只要这个地址集合的大小不超出允许范围即可 可见 2 由于哈希函数是一个压缩映象 因此 在一般情况下 很容易产生 冲突 现象 即 key1 key2 而f key1 f key2 有相同函数值的关键字称为 同义词 3 很难找到一个不产生冲突的哈希函数 一般情况下 只能选择恰当的哈希函数 使冲突尽可能少地产生 因此 在构造这种特殊的 查找表 时 除了需要选择一个 好 尽可能少产生冲突 的哈希函数之外 还需要找到一种 处理冲突 的方法 哈希表的定义 根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 如此构造所得的查找表称之为 哈希表 6 4 2构造哈希函数的方法 原则 经哈希函数映像到地址集合中任何一个地址的概率是相等的 均匀的哈希函数 对数字的关键字可有下列构造方法 若是非数字关键字 则需先对其进行数字化处理 哈希函数为关键字的线性函数H key key或者H key a key b 1 直接定址法 此法仅适合于 地址集合的大小 关键字集合的大小 此方法仅适合于 能预先估计出全体关键字的每一位上各种数字出现的频度 2 数字分析法 假设关键字集合中的每个关键字都是由s位数字组成 u1 u2 us 分析关键字集中的全体 并从中提取分布均匀的若干位或它们的组合作为地址 以关键字的平方值的中间几位作为存储地址 求 关键字的平方值 的目的是 扩大差别 同时平方值的中间各位又能受到整个关键字中各位的影响 3 平方取中法 此方法适合于 关键字中的每一位都有某些数字重复出现频度很高的现象 将关键字分割成若干部分 然后取它们的叠加和为哈希地址 有两种叠加处理的方法 移位叠加和间界叠加 4 折叠法 此方法适合于 关键字的数字位数特别多 每一位数字分布均匀 5 除留余数法 设定哈希函数为 H key keyMODp其中 p m 表长 并且p应为不大于m的素数或是不含20以下的质因子 6 随机数法 设定哈希函数为 H key Random key 其中 Random为伪随机函数 通常 此方法用于对长度不等的关键字构造哈希函数 实际造表时 采用何种构造哈希函数的方法取决于建表的关键字集合的情况 包括关键字的范围和形态 总的原则是使产生冲突的可能性降