检索查找技术教学讲座PPT.ppt

第九章查找技术 课前思考题 猜价格游戏 已知主持人手中物品价格为1至31元之间的整数 猜中者可得到该奖品 1 如果你猜错时主持人只告诉你所猜价格错了让你重新猜 平均要几次才能猜对 2 如果你猜错时主持人告诉你所猜价格是高了还是低了再让你重新猜 最少要几次才可以保证对任意一个价格都能猜对 9 1 1查找的基本概念 关键码 可以标识一个记录的某个数据项 键值 关键码的值 主关键码 可以唯一地标识一个记录的关键码 次关键码 不能唯一地标识一个记录的关键码 查找 在具有相同类型的记录构成的集合中找出满足给定条件的记录 查找的结果 若在查找集合中找到了与给定值相匹配的记录 则称查找成功 否则 称查找查找失败 概述 静态查找 不涉及插入和删除操作的查找 动态查找 涉及插入和删除操作的查找 查找结构 面向查找操作的数据结构 本章讨论的查找结构 线性表 适用于静态查找 主要采用顺序查找技术 折半查找技术 树表 适用于动态查找 主要采用二叉排序树的查找技术 散列表 静态查找和动态查找均适用 主要采用散列技术 概述 9 1 2查找算法的性能 查找算法时间性能通过关键码的比较次数来度量 算法 问题规模 待查关键码在查找集合中的位置 查找算法的时间复杂度是问题规模n和待查关键码在查找集合中的位置k的函数 记为t n k 概述 将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度asl 计算公式为 asl 其中 n 问题规模 查找集合中的记录个数 pi 查找第i个记录的概率 ci 查找第i个记录所需的关键码的比较次数 概述 例 某班级30人 按姓名先后次序查找某人 则其查找成功的平均查找长度为 查找失败的情况 概述 线性表 9 2 1顺序查找 线性查找 基本思想 从线性表的一端向另一端逐个将关键码与给定值进行比较 若相等 则查找成功 给出该记录在表中的位置 若整个表检测完仍未找到与给定值相等的关键码 则查找失败 给出失败信息 1 顺序表的顺序查找 201015246123540985 0123456789 查找方向 2 改进算法设置 哨兵 哨兵就是待查值 将它放在查找方向的 尽头 处 免去了在查找过程中每一次比较后都要判断查找位置是否越界 从而提高查找速度 伪代码1 设置哨兵k 置于查找方向的 尽头 2 设置查找的起始下标 3 若r i 与k相等 则返回当前i的值 否则 继续比较下一个记录 线性表 01234567891011 513192137566475808892 找64 64 哨兵 比较次数 5 比较次数 查找第n个元素 1查找第n 1个元素 2 查找第1个元素 n查找第i个元素 n 1 i查找失败 n 1 平均查找长度 asl 1 2 3 n n n 1 2 o n 线性表 线性表检索用的头文件文件名 seqlist h include definemaxsize100 预定义最大的数据域空间 typedefintdatatype 假设数据类型为整型 typedefstruct datatypedata maxsize intlen 线性表长度 seqlist 预定义的顺序表类型 线性表 算法9 1给出了基于顺序查找表的顺序检索方法 顺序检索算法文件名 s search c 函数名 seqsearch1 seqsearch2 include seqlist h 顺序查找的非递归实现 intseqsearch1 seqlistl datatypekey intk l len 1 while k 0 线性表 顺序查找的递归实现 intseqsearch2 seqlistl intn datatypekey intk 0 if n 1 k 1 elseif l data n key k n elsek seqsearch2 l n 1 key return k 算法9 1线性表的顺序检索 顺序存储 线性表 9 2 2二分法检索 二分法检索又称为折半查找 采用二分法检索可以大大提高查找效率 它要求线性表结点按其关键字从小到大 或从大到小 按序排列并采用顺序存储结构 采用二分搜索时 先求位于搜索区间正中的对象的下标mid 用其关键码与给定值x比较 x l mid key 搜索成功 xl mid key 把搜索区间缩小到表的后半部分 线性表 下面分析在其中二分检索关键字20的过程 线性表 每比较一次 搜索区间缩小一半 如果搜索区间已缩小到一个对象 仍未找到想要搜索的对象 则搜索失败 例 有一组有序的线性表如下 10 14 20 32 45 50 68 90 100 120 分析二分检索关键字95的过程 线性表 例 有一组有序的线性表如下 10 14 20 32 45 50 68 90 100 120 下面给出二分检索法的非递归与递归实现算法 算法中使用seqlist h中定义的顺序查找表 二分查找算法文件名 b search c 函数名 binsearch1 binsearch2 二分查找的非递归实现 intbinsearch1 seqlistl datatypekey intlow 0 high l len 1 mid while low high 线性表 mid low high 2 二分 if l data mid key returnmid 检索成功返回 if l data mid key high mid 1 继续在前半部分进行二分检索 elselow mid 1 继续在后半部分进行二分检索 return 1 当low high时表示查找区间为空 检索失败 线性表 二分查找的递归实现 intbinsearch2 seqlistl datatypekey intlow inthigh intmid k if low high return 1 检索不成功的出口条件 else mid low high 2 二分 if l data mid key returnmid 检索成功返回 if key l data mid returnelsereturn binsearch2 l key low mid 1 binsearch2 l key mid 1 high 递归地在前半部分检索 递归地在后半部分检索 线性表 搜索成功的情形搜索不成功的情形 从有序表构造出的二叉搜索树 判定树 若设n 2h 1 则描述对分搜索的二叉搜索树是高度为h 1的满二叉树 2h n 1 h log2 n 1 第0层结点有1个 搜索第0层结点要比较1次 第1层结点有2个 搜索第1层结点要比较2次 一 查找过程可用二叉树描述 每个记录用一个结点表示 结点中值为该记录在表中位置 这个描述查找过程的二叉树称为判定树 n个元素的表的折半查找的判定树是唯一的 即 判定树由表中元素个数决定 二 查找某关键字的比较次数 为该结点在判定树上的层次数 1 找到有序表中任一记录的过程就是 走了一条从根结点到与该记录相应的结点的路径 查找成功时比较的关键字个数最多不超过树的深度d d log2n 1 2 查找不成功的过程就是走了一条从根结点到外部结点的路径 线性表 aslbins 在假定每个结点的查找概率相同的情况下 二分检索的asl为 用数学归纳法容易证明 aslbins 线性表 课堂练习9 1 任选一题 1 已知一个有序表 15 26 34 39 45 56 58 63 74 76 83 94 顺序存储于一维数组a 12 中 1 画出二叉搜索树 判定树 2 根据折半搜索过程填写成功搜索下表中所给元素34 56 58 63 94时的比较次数 3 在等概率情况下 求查找成功时的平均查找长度 2 对有序表 1 0 1 3 4 6 8 10 12 进行折半查找 1 画出二叉搜索树 判定树 2 求查找12需要比较的次数 3 求等概率情况下搜索成功的平均搜索长度 3 假设在有序线性表a 20 上进行折半查找 1 画出二叉搜索树 判定树 2 求平均查找长度 树表 9 3二叉排序树 bst 二叉排序树 二叉查找树 二叉搜索树 它或者是一棵空的二叉树 或者是具有下列性质的二叉树 1 左子树的所有结点均小于根的值 2 右子树的所有结点均大于根的值 3 它的左右子树也分别为二叉排序树 下列2种图形 是不是二叉排序树 讨论 对左图中序遍历后的结果是什么 树表 12345678910 二叉排序树用的头文件 文件名 bstree h include includetypedefintdatatype typedefstructnode 二叉排序树结点定义 datatypekey 结点值 structnode lchild rchild 左 右孩子指针 bsnode typedefbsnode bstree 二叉排序树存储结构定义 树表 1 二叉排序树的查找 在二叉排序树中查找给定值k的过程是 若root是空树 则查找失败 若k root data 则查找成功 否则 若k root data 则在root的左子树上查找 否则在root的右子树上查找 上述过程一直持续到k被找到或者待查找的子树为空 如果待查找的子树为空 则查找失败 二叉排序树的查找效率就在于只需要查找二个子树之一 树表 50 50 50 30 40 35 50 50 80 90 在二叉排序树中查找关键字值等于50 35 90 95 树表 基于二叉排序树的检索算法文件名 t search c 函数名 bssearch1 bssearch2 二叉排序树的非递归查找 voidbssearch1 bstreet datatypex bstree p bstree q q返回待查结点x在二叉排序树中的地址 p返回待查结点x的父结点地址 p null q t while q 树表 if x q key return p q q xkey q lchild q rchild return 二叉排序树的递归查找 bstreebssearch2 bstreet datatypex 在二叉排序树t中查找关键字为x的结点 若找到则返回该结点的地址 否则返回null if t null x t key returnt 树表 if xkey returnbssearch2 t lchild x 递归地在左子树中检索 elsereturnbssearch2 t rchild x 递归地在右子树中检索 算法分析 在二叉排序树上进行检索的方法与二分检索相似 和关键字的比较次数不会超过树的深度 因此 在二叉排序树上进行检索的效率与树的形状有密切的联系 树表 在最坏的情况下 含有n个结点的二叉排序树退化成一棵深度为n的单支树 类似于单链表 它的平均查找长度与单链表上的顺序检索相同 即asl n 1 2 在最好的情况下 二叉排序树形态比较匀称 对于含有n个结点的二叉排序树 其深度不超过log2n 此时的平均查找长度为o log2n a b 图9 4两棵具有不同检索效率的二叉排序树 树表 例如 对于图9 4中的两棵二叉排序树 其深度分别是4和10 在检索失败的情况下 在这两棵树上的最大比较次数分别是4和10 在检索成功的情况下 若检索每个结点的概率相等 则对于图9 4 a 所示的二叉排序树其平均查找长度为 asla 对于图9 4 b 所示的二叉排序树其平均查找长度为 aslb 1 2 3 4 5 6 7 8 9 10 10 5 5 树表 2 二叉排序树的插入 分析 二叉排序树的插入操作应该是在查找不成功时才进行 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 问题描述 在已存在的一个二叉排序树新插入一个结点 树表 例 插入值为98的结点 树表 基于二叉排序树的结点插入算法 文件名 t insert c函数名 insertbstree voidinsertbstree bstree t datatypex bstreef p p t while p 查找插入位置 if x p key return 若二叉排序树t中已有key 则无需插入f p f用于保存新结点的最终插入位置 p xkey p lchild p rchild 树表 p bstree malloc sizeof bsnode 生成待插入的新结点 p key x p lchild p rchild null if t null t p 原树为空 elseif xkey f lchild p elsef rchild p 程序9 5基于二叉排序树的结点的插入算法 树表 3 二叉排序树的构造 输入序列 53 78 65 17 87 09 81 45 23 左小右大 输入序列不同 则建立的二叉搜索树不同 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 树表 建立二叉排序树的算法如下 二叉排序树的建立算法 文件名 t creat c函数名 creatbstree bstreecreatbstree void 根据输入的结点序列 建立一棵二叉排序树 并返回根结点的地址 bstreet null datatypekey printf n请输入一个以 1为结束标记的结点序列 n 树表 scanf d 返回建立的二叉排序树的根指针 算法9 6生成一棵二叉排序树 树表 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列 每次插入的新结点都是二叉排序树上新的叶子结点 找到插入位置后 不必移动其它结点 仅需修改某个结点的指针 在左子树 右子树的查找过程与在整棵树上查找过程相同 新插入的结点没有破坏原有结点之间的关系 二叉排序树小结 树表 课堂练习 4 依次输入表 30 15 28 20 24 10 12 68 35 50 46 55 中的元素 生成一棵二叉搜索树 试画出生成之后的二叉搜索树 对该二叉搜索树进行中序遍历 试写出遍历序列 假定每个元素的查找概率相等 试计算该二叉搜索树的平均查找长度 课堂练习 任选一题 5 在一棵空的二叉查找树中依次插入关键字序列为12 7 17 11 16 2 13 9 21 4 请画出所得到的二叉查找树 6 画出依次插入序列 50 72 43 85 75 20 35 45 65 30 后建立的二叉搜索树 并求出查找元素35要进行元素间的比较次数 例 编制一个将百分制转换成五级分制的程序 if a 60 b 不及格 elseif a 70 b 及格 elseif a 80 b 中等 elseif a 90 b 良好 elseb 优良 哈夫曼树 哈夫曼树 9 5哈夫曼树及哈夫曼编码 1 哈夫曼树 相关概念 叶子结点的权值对叶子结点赋予的一个有意义的数值量 二叉树的带权路径长度设二叉树具有n个带权值的叶子结点 从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和 wpl wk 第k个叶子结点的权值lk 从根结点到第k个叶子结点的路径长度 哈夫曼树 哈夫曼树 哈夫曼树 给定一组具有确定权值的叶子结点 可以构造出不同的二叉树 其中带权路径长度最小的二叉树 哈夫曼树 哈夫曼编码和译码 报文 abbcddabccdcdddddddd a 0100110110011010011000010011111111共34码 b 0001011011110001101011101111111111111111共40码 初始化由给定的n个权值 w1 w2 wn 构造n棵只有一个根结点的二叉树 从而得到一个二叉树集合f t1 t2 tn 选取与合并在f中选取根结点的权值最小的两棵二叉树分别作为左 右子树构造一棵新的二叉树 这棵新二叉树根结点的权值为其左 右子树根结点的权值之和 删除与加入在f中删除作为左 右子树的两棵二叉树 并将新建立的二叉树加入到f中 重复 两步当集合f中只剩下一棵二叉树时 这棵二叉树便是哈夫曼树 哈夫曼算法基本思想 哈夫曼树的构造过程 1初始化 2选取与合并 给出叶子结点的权值集合为w 5 2 9 11 8 3 7 的哈夫曼树的构造过程 哈夫曼树 3删除与加入 4重复2 3两步 哈夫曼树 4重复2 3两步 哈夫曼树 4重复2 3两步 哈夫曼树 4重复2 3两步 哈夫曼树 哈夫曼树 散列表 9 7 1概述 散列的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系 这样 不经过比较 一次存取就能得到所查元素的查找方法 散列技术 查找时是根据记录的存储位置和它的关键码之间建立的一个确定对应关系h来进行的查找 散列函数 将关键码映射为散列表中适当存储位置的函数 散列表 采用散列技术将记录存储在一块连续的存储空间中 这块连续的存储空间称为散列表 散列地址 所得的存储位置 散列存储 通过散列函数计算出存储地址 例如 函数为loc key asc left key 1 8 散列表 冲突 对于两个不同关键码k1 k2 有h k1 h k2 即 两个不同的记录需要存放在同一个存储位置的现象 则 k1和k2相对于h称做同义词 散列技术的关键问题 散列函数的设计如何设计一个简单 均匀 存储利用率高的散列函数 冲突的处理如何采取合适的处理冲突方法来解决冲突 散列表 9 7 2散列函数的设计 1 直接定址法 直接定址法的散列函数是关键码的线性函数 即 h key a key b a b为常数 例 关键码集合为 10 30 50 70 80 90 选取的散列函数为h key key 10 则散列表为 0123456789 10 30 50 70 80 90 适用范围 地址集合的大小 关键码集合的大小 散列表 2 除留余数法 选择某个适当的正整数p 以关键码除以p的余数作为散列地址 即 h key keymodp 散列函数的设计成功与否关键在于选取合适的p 若p选的不好 则容易产生同义词 散列表 示例 有一个关键字key 962148 散列表大小m 25 取质数p 23 散列函数hash key key p 则散列地址为 hash 962148 962148 23 12可以按计算出的地址存放记录 需要注意的是 使用上面的散列函数计算出来的地址范围是0到22 因此 从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的 只可能在处理溢出时到达这些地址 散列表 9 7 3处理冲突的方法 1 开放定址法 由关键码得到的散列地址一旦产生了冲突 就去寻找下一个空的散列地址 只要散列表足够大 空的散列地址总能找到 并将记录存入 用开放定址法处理冲突得到的散列表叫闭散列表 如何寻找下一个空的散列地址 散列表 1 线性探测法 是指当发生冲突时 从冲突位置的下一个位置起 依次寻找空的散列地址 对于键值key 设h key d 闭散列表的长度为m 则发生冲突时 寻找下一个散列地址的公式为 hi h key di m di 1 2 m 1 散列表 例 关键码集合为 47 7 29 11 16 92 22 8 3 散列表表长为11 散列函数为h key keymod11 用线性探测法处理冲突 则闭散列表为 0123456789 47 7 29 11 16 92 29 22 22 8 8 3 3 3 3 在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象称为堆积 散列表 基于线性探测法构造的散列表的查找算法 散列表 基于线性探测法构造的散列表的查找伪代码 计算散列地址j 2 若ht j 为空 则将待查值插入相应位置 返回 3 若ht j k 则查找成功 返回记录在散列表中的下标 否则j指向下一单元 直至ht j 为空 将待查值插入相应位置或ht j k 查找成功 返回记录在散列表中的下标 散列表 inthashsearch1 intht intm intk j h k if ht j k returnj 没有发生冲突 比较一次查找成功i j 1 m while ht i empty 查找不成功时插入 散列表 2 二次探测法 当发生冲突时 寻找下一个散列地址的公式为 hi h key di m di 12 12 22 22 q2 q2且q m 2 0123456789 47 7 29 11 16 92 29 22 22 8 8 3 3 3 例 关键码集合为 47 7 29 11 16 92 22 8 3 散列表表长为11 散列函数为h key keymod11 用线性探测法处理冲突 则闭散列表为 散列表 3 随机探测法 当发生冲突时 下一个散列地址的位移量是一个随机数列 即公式为 hi h key di m di是一个随机数列 i 1 2 m 1 小结 1 开放地址法就是为产生冲突的地址 通过hi h key di modm