数据结构8.ppt

数据结构 DATASTRUCTURE 计算机科学与技术学院 2 第九章查找 基本概念静态索引结构动态索引结构散列 3 基本概念 查找表 由同一类型的数据元素 记录 构成的集合 分为静态查找表和动态查找表两类静态查找表 仅对查找表进行查找操作 而不能改变的表动态查找表 对查找表除进行查找操作外 可能还要进行向表中插入数据元素 或删除表中数据元素的表 查找 简单地说 查找就是给定一个值K 在含有众多数据元素的查找表中找出关键字等于给定值K的记录 4 查找也是计算机中经常遇到的操作 特别是当问题所涉及的数据量相当大时 查找的效率就显得格外重要 查找运算的主要操作是关键字的比较 所以 通常把查找过程中需要执行的关键字的平均比较次数 也称为平均查找长度 作为衡量一个查找算法效率优劣的标准 5 9 1静态查找表 9 1 1顺序表的查找又称线性查找 是最基本的查找方法之一基本思想 从表的一端开始 向另一端逐个按给定值k与关键码进行比较 若找到 表明查找成功 若直到所有元素都比较完毕 仍未找到与k相同的关键码 则表明查找失败 适用的数据结构 顺序表 线性链表算法实现 静态查找表的顺序存储结构 typedefstruct ElemType elem 数组基址 intlength 表长度 SSTable 6 算法 intS search SSTableST KeyTypek ST elem 0 key k 作为监测哨兵 for i ST length ST elem i key k i 从表尾端向前找 returni 返回k元素在数组中的下标 否则返回0 设置哨兵的好处 在顺序表中总可以找到待查结点 否则 必须将判断条件i 0加进for语句 7 4 性能分析 分析查找算法的效率 通常用平均查找长度ASL衡量在查找成功时 平均查找长度ASL是指为确定数据元素在表中的位置所进行的关键字比较次数的期望值 其中 Pi为查找表中第i个数据元素的概率 Ci为查找表中第i个元素所需比较次数 查找成功时 顺序查找的平均查找长度为 查找不成功时 关键码的比较次数总是n 1次 8 9 1 2有序表的查找 有序表即是表中数据元素按关键码升序或降序排列 二分查找又称为折半查找适用的数据结构 顺序存储的有序表基本思想 在有序表中 取中间元素作为比较对象 若给定值与中间元素的关键码相等 则查找成功 若给定值小于中间元素的关键码 则在中间元素的左半区继续查找 若给定值大于中间元素的关键码 则在中间元素的右半区继续查找 不断重复上述查找过程 直到查找成功 或所查找的区域无数据元素 查找失败 9 假设静态查找表ST递增有序 折半查找过程为 low 1 high length 设置初始区间 若low high 返回查找失败信息 当前查找区间为空 查找失败 若low high mid low high 2 取中点a 若kST elem mid key low mid 1 转 查找在右半区进行c 若k ST elem mid key 返回元素在表中位置 查找成功 3 算法实现 10 举例 0513192137566475808892 051319213756 6475808892 051319213756647580 8892 查找K 85的过程 查找失败 051319213756647580 8892 11 4 性能分析 从折半查找过程看 以表的中点为比较对象 并以中点将表分割为两个子表 对定位到的子表继续这种操作 因而对表中每个数据元素的查找过程可用二叉树描述 称此描述查找过程的二叉树为判定树 查找表中任一元素的过程 即是判定树中从根到该元素结点路径上各结点关键码的比较次数 也即该元素结点在树中的层次数 12 例 0513192137566475808892 判定树 借助于判定树很容易求得二分查找的平均查找长度 设结点总数为 树中第k层上的结点个数不超过 13 因此 在等概率假设下 二分查找的平均查找长度为 二分查找的算法复杂度为 优点 查找的效率较高缺点 要求被查找序列事先按关键字排好序 而排序本身是一种很费时的运算 另外 二分查找只适用于顺序存储结构 14 9 1 3索引顺序表的查找 分块查找 是一种性能介于顺序查找和二分查找之间的查找算法1 数据结构设置 将长度为n的查找表R n 均分成b块 子表 要求 每一块中的关键字不一定有序 但前一块中的最大关键字必须小于后一块中的最小关键字 即要 分块有序 建立索引表ID b 其中ID i 存放第i块中的最大关键字及该块在查找表中的起始位置 由于表R n 分块有序 所以索引表ID b 递增有序 15 首先查找索引表ID 以确定待查结点在哪一分块 由于索引项按关键码字有序 可用顺序或折半查找 然后 在已确定的那一块中进行顺序查找 3 算法实现数据结构定义 长度为n的查找表采用顺序表 SSTableST索引表的结构typedefstruct 索引表结点结构 keytypekey intaddr IDtable IDtabelID b 索引表 2 算法基本思想 16 4 性能分析 分块查找由索引表查找和子表查找两步完成 故整个算法的平均查找长度是两次查找的平均查找长度之和 ASL ASL索引表 ASL子表设查找表长为n 分为b个子表 每块中均有s n b个元素若用二分查找来确定块 则分块查找的平均查找长度约为 若用顺序查找来确定块 则分块查找的平均查找长度约为 对于后一种情况 当时 平均查找长度为极小值 在实用中 可根据表的具体情况进行分块 17 分块查找的性能介于顺序查找和二分查找之间 例如对长度为10000的线性表 它们的平均查找长度分别是 顺序查找 ASL n 1 2 5000分块查找 ASL log2 b 1 1 S 1 2 57或ASL b 1 2 S 1 2 101二分查找 ASL log2 n 1 1 14优点 把线性表分成若干逻辑子表 提高了查找效率缺点 增加了一索引存储空间 和将初始表进行分块的运算 18 9 2动态查找表 9 2 1二叉排序树 BinarySearchTree 定义 二叉搜索树或者是一棵空树 或者是具有下列性质的二叉树 每个结点都有一个作为搜索依据的关键码 key 所有结点的关键码互不相同 左子树 如果存在 上所有结点的关键码都小于根结点的关键码 右子树 如果存在 上所有结点的关键码都大于根结点的关键码 左子树和右子树也是二叉排序树 2 存储结构 二叉链表 19 几个二叉排序树的例子 20 3 二叉排序树上的查找算法 在二叉排序树上进行搜索 是一个从根结点开始 沿某一个分支逐层向下进行比较判等的过程 假设想要在二叉排序树中搜索关键字为x的元素 搜索过程从根结点开始 如果给定值等于根结点的关键码 则搜索成功 如果给定值小于根结点的关键码 则继续递归搜索根结点的左子树 否则 递归搜索根结点的右子树 21 二叉搜索树的搜索插入新结点88 每次结点的插入 都要从根结点出发搜索插入位置 然后把新结点作为叶结点插入 22 查找过程走了一条从根到该元素结点路径 比较次数等于该结点所在层次数 其中 Pi 查找某元素的概率 等概率情况下1 nCi 该元素结点在二叉排序树中的层次数最坏情况 单支树 树的高度达到最大 ASL n 1 2最好情况 与二叉判定树相似ASL log2 n 1 1平均 O nlog2n 4 查找分析 23 5 二叉排序树的插入 在插入之前 先使用搜索算法在树中检查要插入元素是否已经存在 搜索成功 树中已有这个元素 不再插入 搜索不成功 把新元素加到搜索停止的地方 新插入的结点一定是一个新添加的叶子结点 并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点 二叉排序树生成 从空树出发 经过一系列的查找 插入操作之后 可生成一棵二叉排序树 24 6 二叉排序树的删除 在二叉搜索树中删除一个结点时 必须将因删除结点而断开的二叉链表重新链接起来 同时确保二叉搜索树的性质不会失去 为保证在执行删除后 树的搜索性能不至于降低 还需要防止重新链接后树的高度增加 删除叶结点 只需将其双亲结点指向该结点的指针清空 再释放它即可 被删结点无右子树 可以拿该结点左孩子结点顶替它的位置 再释放它 被删结点无左子树 可以拿该结点右孩子结点顶替它的位置 再释放它 25 被删结点左 右子树都存在 有两种处理方式 用该结点的左孩子代替该结点 将其右子树插入到中序遍历该结点左子树时最后访问结点的右孩子上 用该结点的直接前驱或直接后继代替该结点 在处理其前驱或后继的删除问题 算法 P230 231 26 27 29 9 2 2AVL树高度平衡的二叉排序树 1 AVL树的定义 一棵AVL树或者是空树 或者是具有下列性质的二叉排序树 它的左子树和右子树都是AVL树 且左子树和右子树的高度之差的绝对值不超过1 高度不平衡的二叉搜索树高度平衡的二叉搜索树 30 结点的平衡因子 BF BalanceFactor 任一结点的左子树的高度减去右子树的高度所得的高度差称为该结点的平衡因子BF 根据AVL树的定义 任一结点的平衡因子只能取 1 0和1 如果一个结点的平衡因子的绝对值大于1 则这棵二叉排序树就失去了平衡 不再是AVL树 如果一棵二叉排序树是高度平衡的 它就成为AVL树 如果它有n个结点 其高度可保持在O log2n 平均查找长度也可保持在O log2n 31 2 如何构造平衡二叉排序树 基本思想 在构造二叉排序树的过程中 每当插入一个新结点时 首先检查是否因插入而破坏了树的平衡性 若是 则找出其中最小不平衡子树 在保持二叉排序树特性的前提下 调整最小不平衡子树中各结点之间的连接关系 以达到新的平衡 最小不平衡子树 以离插入结点最近 且平衡因子绝对值大于1的结点作为根的子树 假设二叉排序树的最小不平衡子树的根结点为A 则有四种形态需要调整 32 LL型 右旋 33 RR型 左旋 E 34 LR型 先左旋后右旋 35 RL型 先右旋后左旋 36 9 2 3B 树 为什么采用B 树和B 树 大量数据存放在外存中 由于海量数据 不可能一次调入内存 要多次访问外存 硬盘的驱动受机械运动制约 速度慢 主要矛盾变为减少访外次数 在1970年由Rbayer和Emacreight提出用B 树作为索引组织文件 提高访问速度 减少时间 E G 用二叉树组织文件 当文件的记录个数为100000时 要找到给定关键字的记录 需访问外存17次 log100000 50 25 10 75 15 35 60 90 20 30 40 55 70 80 95 索引文件 数据文件 文件头 可常驻内存 37 一棵m阶B 树是一棵平衡的m路搜索树 它或者是空树 或者是满足下列性质的m叉树 树中每个结点至多有m棵子树 若根结点不是叶子结点至少有2棵子树 除根结点以外的所有非终端结点至少有 m 2 棵子树 所有的非终端结点中包含以下信息数据 n A0 K1 A1 K2 Kn An 其中 Ki i 1 2 n 为关键字 且Ki Ki 1 Ai为指向子树根结点的指针 i 0 1 n 且指针Ai 1所指子树中所有结点的关键码均小于Ki i 1 2 n An所指子树中所有结点的关键码均大于Kn m 2 1 n m 1 n为关键码的个数 所有的叶子结点都出现在同一层次上 且不带信息 可以看作是外部结点或查找失败的结点 实际上这些结点不存在 指向这些结点的指针为空 例如 m 4阶B 树 39 例 一棵5阶的B 树 其深度为4 一棵5阶的B 树 40 1 B 树的搜索算法 B 树的查找类似二叉排序树的查找 所不同的是B 树每个结点上是多关键码的有序表 在到达某个结点时 先在 多关键码的 有序表中查找 若找到 则查找成功 否则 到按照对应的指针信息指向的子树中去查找 当到达叶子结点时 则说明树中没有对应的关键码 查找失败 即在B 树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程 41 42 B 树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程 即 在B 树上找结点 在结点中找关键码 因此 B 树的搜索时间与B 树的阶数m和B 树的高度h直接有关 在B 树上进行搜索 搜索成功所需的时间取决于关键码所在的层次 搜索不成功所需的时间取决于树的高度 需要了解树的高度h与树中的关键码个数N之间的关系 查找分析 43 2 B 树的插入 关键字插入在最底层某个非终端结点中添加一个关键码 若该结点上关键字个数不超过m 1个 则可直接插入到该结点上 否则 该结点上关键码个数将达到m个 要进行调整 即结点的 分裂 实现结点 分裂 的方法 关键码加入结点后 将结点中的关键码分成三部分 前后两部分成为两个结点 中间的一个结点将其插入到父结点中 若插入父结点而使父结点中关键码个数超过m 1 则父结点继续分裂 直到插入某个父结点 其关键码个数小于m 可见 B 树是从底向上生长的 44 例 从空树开始逐个加入关键码建立3阶B 树 45 46 3 B 树的删除 在B 树上删除一个关键码时 首先需要找到这个关键码所在的结点 从中删去这个关键码 删除分两种情况 1 删除最底层结点中关键码 2 删除非底层结点中关键码 47 1 在最底层结点中删除有3种情况 a 若结点中关键码个数大于 m 2 1 直接删去 48 b 被删关键码所在结点删除前关键字个数等于 m 2 1 而与该结点相邻的右兄弟 或左兄弟 结点的关键字个数大于 m 2 1 则可按以下步骤调整该结点 右兄弟 或左兄弟 结点以及其双亲结点 49 例 结点联合调整 50 例 51 c 被删除关键码所在结点和其相邻兄弟结点的关键码个数均等于 m 2 1 则必须按以下步骤合并这两个结点 合并结点过程中 双亲结点中关键码个数减少了 若双亲结点的关键码个数小于 m 2 1 则该双亲结点应从树中删除 重复上述合并步骤 最坏情况下这种结点合并处理要自下向上直到根结点 52 例 结点合并 53 例 结点合并 54 2 删除非底层结点中关键码 若所删除非底层结点中关键码Ki 则可用指针Ai所指子树中的最小关键码X替代Ki 然后在相应结点中删去X 直到这个X在最底层结点上 即转为 1 的情形 55 例 删除非底层结点中关键码 56 结点合并与调整 57 58 59 9 2 4B 树 B 树可以看作是B 树的一种变形 在实现文件索引结构方面比B 树使用得更普遍 一棵m阶的B 树和m阶的B 树的差异在于 有n棵子树的结点中含有n个关键码 所有的叶子结点中包含了全部关键码的信息 及指向含有这些关键码记录的指针 且叶子结点本身依关键码的大小自小而大的顺序链接 所有的非终端结点可以看成是索引部分 结点中仅含有其子树根结点中最大 或最小 关键码 60 例 一棵4阶的B 树 一棵4阶的B 树 61 通常在B 树上有两个头指针 一个指向根结点 另一个指向关键码最小的叶子结点 在B 树上进行随机搜索 插入和删除的过程基本上与B 树类似 只是在搜索过程中 若非终端结点上的关键码等于给定值 搜索并不停止 而是继续沿右指针向下 一直查到叶结点上的这个关键码 在B 树 不管查找成功与否 每次查找都是走了一条从根到叶子结点的路径 1 B 树的搜索 62 B 树的插入仅在叶结点上进行 每插入一个关键码后都要判断结点中的子树棵数是否超出范围 2 B 树的插入 63 B 树的删除仅在叶结点上进行 当在叶结点上删除一个关键码后 结点中子树棵数不少于 m 2 属于简单删除 其上层索引可以不改变 若删除关键码是该结点的最大关键码 因其上层副本只起了一个引导搜索的 分界关键码 的作用 所以上层副本仍可保留 如果在叶结点中删除一个关键码后 该结点中的子树棵数n小于结点子树棵数的下限 m 2 必须做结点的调整或合并工作 结点的调整与合并过程亦和B 树类似 3 B 树的删除 64 9 3哈希表 散列Hashing 9 3 1什么是哈希表散列 hashing 是一种存储和查找方法 其基本思想 在记录的关键字K与记录的存储为置之间建立一个确定的对应关系f 存储时 使关键字为K的记录存入函数值f k 所指的存储为置中 查找时 再根据要查找的关键字K 用同样的函数计算出存储地址 然后到相应单元中去取要找的记录 哈希方法中使用的转换函数称为哈希函数 杂凑函数 按这个思想构造的表称为哈希表 杂凑表 65 冲突 若某个哈希函数H key1 key2 而H key1 H key2 即经过哈希函数变换后 可能将不同的关键字映射到同一个哈希地址上 这种现象称为冲突 Collision 映射到同一哈希地址上的关键码称为同义词 哈希函数可以灵活设置 最好是一一对应函数 但冲突不可能避免 只能尽可能减少 哈希方法需要解决以下两个问题 构造好的哈希函数 对于给定的一个关键字集合 选择一个计算简单且地址分布比较均匀的哈希函数 避免或尽量减少冲突制定解决冲突的方案 66 9 3 2哈希函数的构造方法 1 构造哈希函数时的几点要求 构造原则 散列函数的定义域必须包括需要存储的全部关键字 如果散列表允许有m个地址时 其值域必须在0到m 1之间 散列函数计算出来的地址应能均匀分布在整个地址空间中 若key是从关键码集合中随机抽取的一个关键码 散列函数应能以同等概率取0到m 1中的每一个值 即尽量是一一对应函数 散列函数的运算尽可能简单 能在较短的时间内计算出结果 67 2 构造方法举例 直接定址法 取关键码的某个线性函数值作为散列地址 Hash key a key b a b为常数 这类散列函数是一对一的映射 一般不会产生冲突 但是 它要求散列地址空间的大小与关键码集合的大小相同 68 数字分析法 设有n个d位数 每一位可能有r种不同的符号 这r种不同符号在各位上出现频率不一定相同 可能在某些位上分布均匀 在某些位上分布不均匀 可根据散列表大小 选取其中各种符号分布均匀的若干位作为散列地址 数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况 它完全依赖于关键字集合 如果换一个关键码集合 选择哪几位要重新决定 69 除留余数法 设散列表中允许的地址数为m 取一个不大于m 但最接近于或等于m的质数p 利用以下公式把关键码转换成散列地址 散列函数为 hash key key pp m 70 乘余取整法 使用此方法时 先让关键码key乘上一个常数A 0 A 1 提取乘积的小数部分 然后再用整数n乘以这个值 对结果向下取整做为散列地址 散列函数为 hash key n A key 1 其中 A key 1 表示取A key小数部分 A key 1 A key A key 71 平方取中法 先计算构成关键字的标识符的内码的平方 然后按照散列表的大小取中间的若干位作为散列地址 72 折叠法 把关键码自左到右分成位数相等的几部分 每一部分的位数应与散列表地址位数相同 只有最后一部分的位数可以短一些 把这些部分的数据叠加起来 就可以得到具有该关键码的记录的散列地址 73 9 3 3处理冲突的构造方法 处理冲突就是为发生地址冲突的记录找到一个空的Hash地址 1 开放地址法 由关键字得到的哈希地址一旦产生了冲突 即该地址已经存放了数据元素 就去寻找下一个空的哈希地址 只要哈希表足够大 空的哈希地址总能找到 并将数据元素存入 找空哈希地址方法很多 下面介绍三种 线性探测法 LinearProbing Hi Hash key di modm 1 i m 其中 Hash key 为哈希函数m为哈希表长度di为增量序列1 2 m 1 且di i 74 线性探测法可能使第i个哈希地址的同义词存入第i 1个哈希地址 这样本应存入第i 1个哈希地址的元素变成了第i 2个哈希地址的同义词 因此 可能出现很多元素在相邻的哈希地址上 堆积 起来 降低了查找效率 堆积 二次聚集 在处理冲突的过程中 两个第一哈希地址不同的记录争夺同一后继地址的现象 可采用二次探测法 或双哈希函数探测法 以改善 堆积 问题 75 二次探测法 quadraticprobing Hi Hash key di modm其中 Hash key 为哈希函数M为哈希表长度 m要求是某个4k 3的质数 k是整数 Di为增量序列12 12 22 22 q2 q2且q m 1 随机探测法 di为随机数序列 76 2 再哈希法 双散列法 Hi ReHashi key 其中ReHashi key 是不同于Hash key 的哈希函数 再哈希法先用第一个函数Hash key 对关键字计算哈希地址 一旦产生地址冲突 再用第二个函数ReHash key 计算哈希地址 Rehash 的取法很多 例如 当m是质数时 可定义ReHash key key m 2 1ReHash key key m m 2 1优点 不容易产生 堆积 缺点 增加了计算时间 77 3 链地址法 查找时按H key 地址得到链表