数据结构第九章查找课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构第九章查找课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第九 查找 课件
- 资源描述:
-
1、中国科大C+程序设计实习 数据结构课程本章内容9.1 查找的基本概念查找的基本概念9.2 静态查找表静态查找表9.3 动态查找表动态查找表9.4 哈希表哈希表中国科大数据结构9-3 9.1 查找的基本概念中国科大数据结构9-4 9.1 查找的基本概念中国科大数据结构9-5 9.1 查找的基本概念中国科大数据结构9-6 9.2 静态查找表中国科大数据结构9-7 9.2 静态查找表中国科大数据结构9-8 9.2 静态查找表监视哨兵监视哨兵i=11i=7,找到找到i=8i=9i=10比较次数比较次数=5比较次数分析:比较次数分析:查找第查找第n n个元素:个元素:1 1次次查找第查找第n-1n-1个
2、元素:个元素:2 2次次.查找第查找第1 1个元素:个元素:n n次次查找第查找第i i个元素:个元素:n+1-in+1-i次次查找失败查找失败:n+1n+1次次 0 1 2 3 4 5 6 7 8 9 10 1162513192137566275808892中国科大数据结构9-9 9.2 静态查找表中国科大数据结构9-10 9.2 静态查找表中国科大数据结构9-11 9.2 静态查找表中国科大数据结构9-12 9.2 静态查找表1 2 3 4 5 6 7 8 9 10 11513192137566275808892low=1mid=6high=11第一步:第一步:low=1,high=11,
3、mid=6 STmid=ST6=5662,则改变则改变high;第三步:第三步:high=mid-1=8,mid=7 high=8mid=7STmid=ST7=62=62,找到!找到!62中国科大数据结构9-13 9.2 静态查找表1 2 3 4 5 6 7 8 9 10 11513192137566275808892high=6low=7找找61u 当下界当下界lowlow大于上界大于上界highhigh时,说明有序时,说明有序 表中没有关键字等于表中没有关键字等于K K的元素,查找失败的元素,查找失败中国科大数据结构9-14 9.2 静态查找表n判定树上每个结点需要的查找次数刚好为该结点所
4、在的层数;判定树上每个结点需要的查找次数刚好为该结点所在的层数;n查找成功时查找次数不会超过判定树的深度查找成功时查找次数不会超过判定树的深度nn个结点的判定树的深度为个结点的判定树的深度为 log2n +1n比较次数最多不超过比较次数最多不超过 log2n +1n折半查找的算法复杂度为折半查找的算法复杂度为 log2n +13941756102118判定树判定树中国科大数据结构9-15 9.2 静态查找表中国科大数据结构9-16 9.2 静态查找表中国科大数据结构9-17 9.2 静态查找表 1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755
5、929主表主表索引表索引表中国科大数据结构9-18 9.2 静态查找表1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表找找62中国科大数据结构9-19 9.2 静态查找表中国科大数据结构9-20 9.3 动态查找表p动态查找表动态查找表 如果应用问题涉及的数据量很大,而且数据经常发生变化,如如果应用问题涉及的数据量很大,而且数据经常发生变化,如图书馆经常购进图书,每购进新书,需将新书记录插入图书表,对图书馆经常购进图书,每购进新书,需将新书记录插入图书表,对这类表除了提供前面的介绍的查找外,还要提供动态查找功能:这类
6、表除了提供前面的介绍的查找外,还要提供动态查找功能:1.查找某个查找某个“特定特定”元素是否在表中,若不在,将该元素插入;元素是否在表中,若不在,将该元素插入;2.查找某个查找某个“特定特定”元素是否在表中,若在,从表中删除;元素是否在表中,若在,从表中删除;p如何组织动态查找表?如何组织动态查找表?用静态查找方法不能满足要求了。本节介绍几种方法。用静态查找方法不能满足要求了。本节介绍几种方法。中国科大数据结构9-21 9.3 动态查找表21二叉排序树二叉排序树非二叉排序树非二叉排序树56645923788198021137560566459237881980211375中国科大数据结构9-2
7、2 9.3 动态查找表566459237881980211375例例1:在右图二叉排序树中查找关键字值等于:在右图二叉排序树中查找关键字值等于3737找到找到例例2:在右图二叉排序树中查找关键字值等于:在右图二叉排序树中查找关键字值等于88找到找到例例3:在右图二叉排序树中查找关键字值等于:在右图二叉排序树中查找关键字值等于94无此数无此数中国科大数据结构9-23 9.3 动态查找表56645923788198021137594中国科大数据结构9-24 9.3 动态查找表566492888075中国科大数据结构9-25 9.3 动态查找表566459237881980211375中国科大数据结
8、构9-26 9.3 动态查找表中国科大数据结构9-27 9.3 动态查找表566459237881980211375中国科大数据结构9-28 9.3 动态查找表566453719211392888075中国科大数据结构9-29 9.3 动态查找表566459237888019211375中国科大数据结构9-30 9.3 动态查找表808892647521191356375中国科大数据结构9-31 9.3 动态查找表808892647521191356375中国科大数据结构9-32 9.3 动态查找表阿德尔森一维尔斯和阿德尔森一维尔斯和兰迪斯兰迪斯566459237881980211375605
9、65641913753780928821AVLAVL树树非非AVLAVL树树中国科大数据结构9-33 9.3 动态查找表56564191375378092882100-10-1000100中国科大数据结构9-34 9.3 动态查找表p非平衡二叉树的平衡处理非平衡二叉树的平衡处理若一棵二叉排序树是平衡二叉树,扦入某个结点后,可能会变若一棵二叉排序树是平衡二叉树,扦入某个结点后,可能会变成非平衡二叉树,这时,就可以对该二叉树进行平衡处理,使其变成非平衡二叉树,这时,就可以对该二叉树进行平衡处理,使其变成一棵平衡二叉树。成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比处理的原则应
10、该是处理与插入点最近的、而平衡因子又比1大大或比或比-1小的结点。下面将分四种情况讨论平衡处理。小的结点。下面将分四种情况讨论平衡处理。中国科大数据结构9-35 9.3 动态查找表CBA210CBA000中国科大数据结构9-36 9.3 动态查找表2.LR型的处理型的处理(左右型左右型)n如下图所示,在如下图所示,在C的左孩子的左孩子A上扦入一个右孩子上扦入一个右孩子B,使的,使的C的平的平衡因子由衡因子由1变成了变成了2,成为不平衡的二叉排序树。,成为不平衡的二叉排序树。n平衡处理:将平衡处理:将B变到变到A与与C 之间,使之成为之间,使之成为LL型,然后按第型,然后按第1种种情形情形LL型
展开阅读全文