数据结构查找ppt课件.ppt

第9章查找 1 查找表 SearchTable 是由同一类型的数据元素 或记录 构成的集合 前面已介绍了各种线性或非线性的数据结构 本章讨论另一种在实际应用中大量使用的数据结构 查找表 由于 集合 中的数据元素之间存在着完全松散的关系 因此查找表是一种非常灵便的数据结构 2 对查找表经常进行的操作 1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素的各种属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 3 查找表可分为两类 若对查找表只作查询和检索操作 则称此类查找表为静态查找表 StaticSearchTable 若在查找过程中同时插入查找表中不存在的数据元素 或者从查找表中删除已存在的某个数据元素 则称此类查找表为动态查找表 DynamicSearchTable 4 在各种系统软件或应用软件中 查找表是最常见的结构之一 如编译程序中符号表 信息处理系统中信息表等 综上所述 所谓 查找 即为在一个含有众多的数据元素 或记录 的查找表中找出某个 特定的 数据元素 或记录 关于 特定的 词的具体含义 关键字 Key 是数据元素 或记录 中某个数据项的值 用它可以标识一个数据元素 或记录 主关键字 PrimaryKey 若此关键字可以惟一地标识一个记录 则称此关键字为主关键字 对不同的记录 其主关键字均不同 5 次关键字 SecondaryKey 用以识别若干记录的关键字为次关键字 当数据元素只有一个数据项时 其关键字即为该数据元素的值 查找 Searching 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素 或记录 查找成功 若表中存在这样的一个记录 则查找成功 此时查找的结果为给出整个记录的信息 或指示该记录在查找表中的位置 查找不成功 若表中不存在关键字等于给定值的记录 则查找不成功 此时查找的结果可给出一个 空 记录或 空 指针 6 此表为一个查找表 表中每一行为一个记录 学生的学号为记录的关键字 若给定值为20010985 则通过查找可得学生王五的各项信息 此时查找是成功的 若给定值为20011930 则由于表中没有关键字为20011930的记录 则查找不成功 招生录取登记表 例 7 如何进行查找 在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位 即 对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起 这个关系是人为加上的 因为查找表中数据元素之间原本仅存在 同属于一个集合 的松散关系 例 查英文单词 字典是按单词的字母在字母表中的次序编排的 则查找时不需要从字典中第一个单词比较起 而只要根据待查单词中每个字母在字母表中的位置查到该单词 字典这种查找表的数据元素之间原本仅存在着 同属于一个集合 的松散关系 给查找带来不便 对字典按单词的字母在字母表中的次序进行编排 就是对字典这种查找表人为加上的一种关系 以便按某种规则进行查找 8 总之 查找的方法取决于查找表的结构 由于查找表中的数据元素之间不存在明显的组织规律 因此不便于查找 为了提高查找的效率 需要在查找表中的元素之间人为地附加某种确定的关系 换句话说 用另外一种结构来表示查找表 9 内查找和外查找 若整个查找过程全部在内存进行 则称为内查找 若在查找过程中还需要访问外存 则称为外查找 本书仅介绍内查找 平均查找长度ASL 查找算法的效率 主要看要查找的值与关键字的比较次数 通常用平均查找长度来衡量 10 对一个含n个数据元素的表 查找成功时 其中 Pi为找到表中第i个数据元素的概率 且有 Ci为查找表中第i个数据元素所用到的比较次数 不同的查找方法有不同的Ci 查找是许多程序中最消耗时间的一部分 因而 一个好的查找方法会大大提高运行速度 11 9 1静态查找表 9 2动态查找表 9 3哈希表 本章内容 12 9 1静态查找表 13 1 顺序表的查找 静态查找表的存储结构可用顺序表或线性链表表示 本节只讨论在顺序存储结构中查找的实现 顺序查找的基本思想 从表中最后一个记录开始 逐个进行记录的关键字和给定值的比较 若某个记录的关键字和给定值比较相等 则查找成功 找到所查记录 反之 若直至第一个记录 其关键字和给定值比较都不等 则表明表中没有所查记录 查找不成功 14 64 监视哨 比较次数 5 比较次数 查找第n个元素 1查找第n 1个元素 2 查找第1个元素 n查找第i个元素 n i 1查找失败 n 1 15 64 监视哨 defineM500typedefstruct intkey floatinfo JD intseqsrch JDr intn intk inti n r 0 key k while r i key k i return i 16 监测哨的作用 1 省去判定循环中下标越界的条件 从而节约比较时间 2 保存查找值的副本 查找时若遇到它 则表示查找不成功 这样在从后向前查找失败时 不必判断查找表是否检测完 从而达到算法统一 上述算法中 对于有n个数据元素的表 给定值k与表中第i个元素的关键字相等 即定位第i个记录时 需进行 n i 1次关键字比较 即Ci n i 1 则查找成功时 顺序查找的平均查找长度为 顺序查找性能分析 对一个含有n个数据元素的表 查找成功时有 17 设每个数据元素的查找概率相等 即Pi 则等概率情况下有 查找不成功时 关键字的比较次数总是n 1次 算法中的基本工作就是关键字的比较 因此 查找长度的量级就是查找算法的时间复杂度为O n 顺序查找缺点是当n很大时 平均查找长度较大 效率低 优点是对表中数据元素的存储没有特殊要求 18 2 有序表的查找 以有序表表示静态查找表时 可用折半查找法来实现查找 折半查找的基本思想 在有序表中 取中间元素作为比较对象 若给定值与中间元素的关键字相等 则查找成功 若给定值小于中间元素的关键字 则在中间元素的左半区继续查找 若给定值大于中间元素的关键字 则在中间元素的右半区继续查找 不断重复上述查找过程 直到查找成功 或所查找的区域无数据元素 查找失败 折半查找也叫二分查找 是一种效率较高的查找方法 但前提是表中元素必须按关键字有序 按关键字递增或递减 排列 19 算法实现 设表长为n low high和mid分别指向待查元素所在区间的上界 下界和中点 k为给定值 初始时 令low 1 high n mid low high 2 让k与mid指向的记录比较 若k r mid key 则查找成功若kr mid key 则low mid 1重复上述操作 直至low high时 查找失败 20 算法描述 21 22 intbinsrch JDr intn intk intlow high mid found low 1 high n found 0 found为找到标志 值为0表示未找到 while lowr mid key low mid 1 elseif k r mid key found 1 elsehigh mid 1 if found 1 如果已找到return mid 找到的记录的下标肯定为midelsereturn 0 defineM500typedefstruct intkey floatinfo JD 23 折半查找的性能分析 从折半查找的过程看 每次查找都是以表的中点为比较对象 并以中点将表分割为两个子表 对定位到的子表继续作同样的操作 所以 对表中每个数据元素的查找过程 可用二叉树来描述 称这个描述查找过程的二叉树称为判定树 判定树中每一结点对应表中一个记录 但结点值不是某个记录的关键字 而是某个记录在表中的位置序号 根结点对应当前区间的中间记录 左子树对应前一子表 右子树对应后一子表 24 从上面判定树可看到 查找第一层的根结点56 一次比较即可找到 查找第二层的结点19和80 二次比较即可找到 查找第三层的结点5 21 64 88 三次比较即可找到 查找第四层的结点13 37 75 92 四次比较即可找到 25 n个结点的判定树 树高为k 则有2k 1 1 n 2k 1 即k 1 log2 n 1 k 所以k log2 n 1 因此 二分查找在查找成功时 进行的关键字比较次数至多为log2 n 1 查找表中任一元素的过程 即是判定树中从根到该元素结点路径上各结点关键字的比较次数 也即该元素结点在树中的层次数 以树高为k的满二叉树 n 2k 1 为例 假设表中每个元素的查找是等概率的 即Pi 则树的第i层有2i 1个结点 二分查找的平均查找长度为 26 所以 二分查找的时间复杂度为 O log2n 二分查找的优点 效率高 二分查找的缺点 必须按关键字排序 有时排序也很费时 只适用顺序存储结构 所以进行插入 删除操作必须移动大量的结点 二分查找适用于一经建立就很少改动 而又经常需要查找的线性表 对于经常需要改动的线性表 可采用链表存储结构 进行顺序查找 27 3 索引顺序表的查找 若以索引顺序表表示静态查找表 可用分块查找法实现查找 分块查找又称索引顺序查找 是顺序查找的一种改进方法 查找过程 将表分成几块 块内无序 块间有序 先确定待查记录所在块 再在块内查找 算法实现 用数组存放待查记录 每个数据元素至少含有关键字域 建立索引表 每个索引表结点含有最大关键字域和指向本块第一个结点的指针 28 typedefstruct intkey intlink SD typedefstruct intkey floatinfo JD 29 intblocksrch JDr SDd intb intk intn inti 1 j while k d i key 索引表长 顺序表长 30 分块查找方法评价 31 32 9 2动态查找表 33 动态查找表特点 动态查找表用于频繁进行插入 删除 查找 表结构本身是在查找过程中动态生成的 即对于给定值key 若表中存在其关键字等于key的记录 则查找成功返回 否则插入关键字等于key的记录 本节讨论以各种树结构表示动态查找表时的插入 删除 查找的实现方法 34 1 二叉排序树 1 二叉排序树的定义 二叉排序树或者是一棵空树 或者是具有如下特性的二叉树 1 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 2 若它的右子树不空 则右子树上所有结点的值均大于根结点的值 3 它的左 右子树也都分别是二叉排序树 35 50 30 80 20 90 10 85 40 35 25 23 88 例如 是二叉排序树 66 不 36 37 typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左 右指针 BiTNode BiTree 通常 以二叉链表作为二叉排序树的存储结构 38 2 二叉排序树的查找算法 若二叉排序树为空 则查找不成功 否则 1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 39 50 30 80 20 90 85 40 35 88 32 例如 二叉排序树 查找关键字 50 50 50 35 50 30 40 35 50 90 50 80 90 95 40 从上述查找过程可见 在查找过程中 生成了一条查找路径 从根结点出发 沿着左分支或右分支逐层向下直至关键字等于给定值的结点 或者 从根结点出发 沿着左分支或右分支逐层向下直至指针指向空树为止 查找成功 查找不成功 41 StatusSearchBST BiTreeT KeyTypekey BiTreef BiTree 在右子树中继续查找 42 30 20 10 40 35 25 23 f T 设key 48 f T f T 22 p f T f T T T T f f f p 43 二叉排序树的查找分析 在二叉排序树上查找其关键字等于给定值结点的过程 恰是走了一条从根结点到该结点的路径的过程 含有n个结点的二叉树是不唯一的 如何来进行查找分析呢 44 例如 上图两棵二叉排序树中 结点的个数和值均相同 但 a 的深度为3 而 b 的深度为6 其等概率平均查找长度分别为 ASL a 1 1 2 2 3 3 6 14 6ASL b 1 1 2 1 3 1 4 1 5 1 6 1 6 21 6 因此 二叉排序树的平均查找长度和二叉树的形态有关 最好情况下 二叉排序树在生成过程中 树的形态比较均匀 其最终得到的是一颗形态与二分查找的判定树相似的二叉排序树 如图 a 所示 最坏情况下 二叉排序树通过一个有序表的n个结点依次插入生成的 此时所得的二叉排序树为一颗深度为n的单支树 如图 b 所示 它的平均查找长度和单链表的顺序查找相同 也是 n 1 2 对均匀的二叉排序树进行插入或删除结点后 应对其进行调整 使其依然保持均匀 45 3 二叉排序树的插入算法 根据动态查找表的定义 插入操作在查找不成功时才进行 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 46 StatusInsertBST BiTree 47 s BiTree malloc sizeof BiTNode 为新结点分配空间s data e s lchild s rchild NULL if p T s 插入s为新的根结点elseif LT e key p data key p lchild s 插入 s为 p的左孩子elsep rchild s 插入 s为 p的右孩子returnTRUE 插入成功 48 4 二叉排序树的删除算法 和插入相反 删除在查找成功之后进行 并且要求删除二叉排序树上某个结点之后 仍然保持二叉排序树的特性 可分三种情况讨论 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 49 50 30 80 20 90 85 40 35 88 32 被删除的结点是叶子结点 例如 被删关键字 20 88 其双亲结点中相应指针域的值改为 空 50 50 30 80 20 90 85 40 35 88 32 被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 指向被删除结点的左子树或右子树 被删关键字 40 80 51 50 30 80 20 90 85 40 35 88 32 被删除的结点既有左子树 也有右子树 40 40 以其前驱替代之 然后再删除该前驱结点 被删结点 前驱结点 被删关键字 50 52 StatusDeleteBST BiTree 继续在右子树中进行查找 删除 53 voidDelete BiTree p 从二叉排序树中删除结点p 并重接它的左子树或右子树if p rchild elseif p lchild else 其中删除操作过程如下所描述 54 右子树为空树则只需重接它的左子树 q p p p lchild free q p p 55 左子树为空树只需重接它的右子树 q p p p rchild free q p p 56 q p s p lchild 转左while s rchild 转左后 到右尽头 q s s s rchild q指向s的双亲 s指向被删结点的前驱p data s data 以前驱结点的数据替换被删结点的数据if q p q rchild s lchild 重接 q的右子树elseq lchild s lchild 重接 q的左子树free s 左右子树均不空 p q s 57 5 二叉排序树的构造过程 例 记录的关键字序列为 33 50 42 18 39 9 77 44 2 11 24 则构造一棵二叉排序树的过程如下 从空树开始建立二叉排序树的过程图示 58 一个无序序列可以通过构造二叉排序树而成为一个有序序列 每次插入新结点都是二叉排序树上新的叶子结点 不必移动其它结点 仅需改动某个结点指针 由空变为非空即可 59 includetypedefintTElemType typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左 右指针 BiTNode BiTree 生成二叉排序树的算法 60 voidInsBST BiTree 如果输入值大于它的根结点 则作为此根结点的右孩子 61 BiTreeCreateBST BiTreeT T是一个指针变量 指向二叉排序树的根结点TElemTypeK T NULL printf 请输入一个整数关键字 输入0时结束输入 scanf d 62 例如 5 4 8 2 5 4 8 2 1 是平衡树 不是平衡树 平衡二叉树的定义 又称AVL树 它或者是一棵空树 或者是具有下列性质的二叉树 1 它的左子树和右子树高度之差的绝对值不超过1 2 它的左子树和右子树都是平衡二叉树 2 二叉平衡树 63 二叉树上结点的平衡因子 为该结点的左子树的深度减去它的右子树的深度 平衡二叉树上所有结点的平衡因子只可能是 1 0 1 64 65 在插入过程中 采用平衡旋转技术 例如 依次插入的关键字为5 4 2 8 6 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转一次 先向右旋转再向左旋转 构造二叉平衡树的方法 66 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 67 当平衡的二叉排序树因插入结点而失去平衡时 仅需对离插入结点最近的最小不平衡子树进行平衡旋转处理即可 平衡旋转处理可分为下列4种情况 1 单向右旋 顺时针 2 单向左旋 逆时针 3 先左后右双向旋转 4 先右后左双向旋转 68 例 已知一棵平衡二叉排序树如图 a 所示 在A的左子树的左子树上插入15后 导致失衡 如图 b 所示 为恢复平衡并保持二叉排序树的特性 可将A改为B的右子 B原来的右子改为A的左子 如图 c 所示 这相当于以B为轴 对A做了一次顺时针旋转 不平衡二叉树的调整 1 69 例 已知一棵平衡二叉排序树如图 a 所示 在A的右子树B的右子树上插入70后 导致失衡 如图 b 所示 为恢复平衡并保持二叉排序树的特性 可将A改为B的左子 B原来的左子改为A的右子 如图 c 所示 这相当于以B为轴 对A做了一次逆时针旋转 不平衡二叉树的调整 2 70 例 已知一棵平衡二叉排序树如图 a 所示 在A的左子树B的右子树上插入45后 导致失衡 如图 b 所示 为恢复平衡并保持二叉排序树的特性 可首先将B改为C的左子 而C原来的左子改为B的右子 然后将A改为C的右子 C原来的右子改为A的左子 如图 c 所示 这相当于对C做了一次逆时针旋转 对A做了一次顺时针旋转 71 不平衡二叉树的调整 3 72 例 已知一棵平衡二叉排序树如图 a 所示 在A的右子树的左子树上插入55后 导致失衡 如图 b 所示 为恢复平衡并保持二叉排序树的特性 可首先将B改为C的右子 而C原来的右子改为B的左子 然后将A改为C的左子 C原来的左子改为A的右子 如图 c 所示 这相当于对C做了一次顺时针旋转 对A做了一次逆时针旋转 73 不平衡二叉树的调整 4 74 在二叉平衡树上进行查找的过程和二叉排序树相同 因此 查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度 二叉平衡树的查找性能分析 问 含n个关键字的二叉平衡树可能达到的最大深度是多少 75 n 0 空树 最大深度为0 n 1 最大深度为1 n 2 最大深度为2 n 4 最大深度为3 n 7 最大深度为4 先看几个具体情况 76 反过来问 深度为h的二叉平衡树中所含结点的最小值Nh是多少 h 0 N0 0 h 1 h 2 h 3 一般情况下 N1 1 N2 2 N3 4 Nh Nh 1 Nh 2 1 利用归纳法可证得 Nh Fh 2 1 77 因此 在二叉平衡树上进行查找时 查找过程中和给定值进行比较的关键字的个数和log n 相当 即 在二叉平衡树上进行查找的时间复杂度为Olog n 由此推得 深度为h的二叉平衡树中所含结点的最小值Nh h 2 5 1 78 9 3哈希表 79 1 什么是哈希表 以上讨论的查找方法 由于数据元素的存储位置与关键字之间不存在确定的关系 因此 查找时 需要进行一系列对关键字的查找比较 即查找算法是建立在比较的基础上的 查找效率由比较一次缩小的查找范围决定 理想的情况是依据关键字直接得到其对应的数据元素位置 即要求关键字与数据元素间存在一一对应关系 通过这个关系 能很快地由关键字得到对应的数据元素位置 80 例 11个元素的关键字分别为18 27 1 20 22 6 10 13 41 15 25 选取关键字与元素位置间的函数为 f key keymod11 1 通过这个函数对11个元素建立查找表如下 012345678910 查找时 对给定值kx通过这个函数计算出地址 再将kx与该地址单元中元素的关键字比较 若相等 查找成功 81 哈希表与哈希方法 选取某个函数 依据该函数按关键字计算数据元素的存储地址 并按此地址存放数据元素 查找时 由同一个函数对给定值kx计算出地址 将kx与该地址单元中数据元素的关键字进行比较 确定查找是否成功 这就是哈希方法 哈希方法中使用的转换函数称为哈希函数 哈希方法中计算的存储地址称为哈希地址或散列地址 按这个思想构造的查找表称为哈希表 82 对于n个数据元素的集合 总能找到关键字与存放地址一一对应的函数 若最大关键字为m 可以分配m个数据元素存放单元 选取函数f key key即可 但这样会造成存储空间的很大浪费 甚至不可能分配这么大的存储空间 通常关键字的集合比哈希地址集合大得多 因而经过哈希函数变换后 可能将不同的关键字映射到同一个哈希地址上 这种现象称为冲突 83 冲突不可能避免 只能尽可能减少 所以 哈希方法需要解决以下两个问题 1 构造好的哈希函数a 所选函数尽可能简单 以便提高转换速度 b 所选函数对关键字计算出的地址 应在哈希地址集中大致均匀分布 以减少空间的浪费 2 制定解决冲突的方案 换句话说 就是使关键字经过哈希函数得到一个随机的地址 以便使一组关键字的哈希地址均匀分布在整个地址区间中 从而减少冲突 84 2 哈希函数的构造方法 1 直接定址法 Hash key a key b a b为常数 即 取关键字的某个线性函数值为哈希地址 这类函数是一一对应函数 不会产生冲突 但要求地址集合与关键字集合大小相同 因此 对于较大的关键字集合不适用 实际中能使用这种哈希函数的情况很少 例 关键字集合为 20 30 50 60 80 90 选取哈希函数为 Hash key key 10 则存放如下 85 2 除留余数法 Hash key keymodp p是一个整数 即 取关键字除以p的余数作为哈希地址 使用除留余数法 选取合适的p很重要 若哈希表表长为m 则要求p m 且接近m或等于m p一般选取质数 也可以是不包含小于20质因子的合数 这是一种最简单 也最常用的构造哈希函数的方法 86 3 平方取中法 对关键字平方后 按哈希表大小 取中间的若干位作为哈希地址 例 若存储区域可存100个记录 关键字 4731则4731 4731 22382361取地址82 例 若存储区域可存10000个记录 关键字 14625则14625 14625 213890625取地址8906 取的位数由表长决定 这是一种较常用的构造哈希函数的方法 87 3 处理冲突的方法 1 开放定址法 所谓开放定址法 即是由关键字得到的哈希地址一旦产生了冲突 也就是说 该地址已经存放了数据元素 就去寻找下一个空的哈希地址 只要哈希表足够大 空的哈希地址总能找到 并将数据元素存入 1 线性探测法Hi Hash key di modm 1 i m 其中 Hash key 为哈希函数m为哈希表长度di i i 1 2 3 m 1 88 47 7 11 16 92均是由哈希函数得到的没有冲突的哈希地址而直接存入的 Hash 29 7 哈希地址上冲突 需寻找下一个空的哈希地址 由H1 Hash 29 1 mod11 8 哈希地址8为空 将29存入 另外 22 8同样在哈希地址上有冲突 也是由H1找到空的哈希地址的 89 而Hash 3 3 哈希地址上冲突 由H1 Hash 3 1 mod11 4仍然冲突 H2 Hash 3 2 mod11 5仍然冲突 H3 Hash 3 3 mod11 6找到空的哈希地址 存入 线性探测法可能使第i个哈希地址的同义词存入第i 1个哈希地址 这样本应存入第i 1个哈希地址的元素变成了第i 2个哈希地址的同义词 因此 可能出现很多元素在相邻的哈希地址上 堆积 起来 大大降低了查找效率 为此 可采用二次探测法 或双哈希函数探测法 以改善 堆积 问题 90 2 二次探测法 平方探测法 对关键字寻找空的哈希地址只有3这个关键字与上例不同 Hash 3 3 哈希地址上冲突 由H1 Hash 3 12 mod11 4仍然冲突 H2 Hash 3 12 mod11 2找到空的哈希地址 存入 91 3 双哈希函数探测法 Hi Hash key i ReHash key modm i 1 2 m 1 其中 Hash key ReHash key 是两个哈希函数 m为哈希表长度 双哈希函数探测法 先用第一个函数Hash key 对关键字计算哈希地址 一旦产生地址冲突 再用第二个函数R