《计算机软件基础ppt》由会员分享，可在线阅读，更多相关《计算机软件基础ppt（55页珍藏版）》请在金锄头文库上搜索。
1、下一页 计算机软件基础 of 讲：刘志强 西安交通大学 计算机教学实验中心 第 6单元 查找 下一页 上一页 停止放映 第 2 页 教学目标 了解有关查找的 基本概念 查找的主要算法 下一页 上一页 停止放映 第 3 页 教学要求 通过本单元的学习，了解、掌握有关查找的： 基本概念 查找、平均查找长度 主要查找算法 顺序查找、折半查找、分块查找 树表查找、哈希查找 下一页 上一页 停止放映 第 4 页 本单元涉及的内容 第 3章 么是查找 序表查找 表查找 希查找 102 下一页 上一页 停止放映 第 5 页 一、基本概念 查找 查找表 静态查找 动态查找 平均查找长度 下一页 上一页 停止放
2、映 第 6 页 查找 查找 就是在给定的 存在这样的结点 ， 查找成功；否则 ， 查找失败 。 查找表 是一组待查数据元素的集合 。 静态查找 是仅仅进行查询和检索操作 ， 不改变查找表中数据元素间的逻辑关系的查找 。 动态查找 是除了进行查询和检索操作外 ， 还对查找表进行插入 、 删除操作的查找 ， 动态地改变查找表中数据元素之间的逻辑关系 。 下一页 上一页 停止放映 第 7 页 平均查找长度 平均查找长度 （ 在查找过程中 ， 对每个结点记录中的关键字要进行反复比较 ， 以确定其位置 。 因此 ， 与关键字进行比较的平均次数 ， 就成为平均查找长度 。 它是用来评价一个算法好坏的一个依
3、据 。 对含有 查找成功时的平均查找长度为： * 中： 查找表中第 且 1 显然 ， i=1 n i=1 n 下一页 上一页 停止放映 第 8 页 二、主要查找算法 顺序查找 折半查找 分块查找 树表查找 哈希查找 下一页 上一页 停止放映 第 9 页 1、顺序查找 顺序查找是最简单 、 最普通的查找方法 。 查找步骤： 第 1个元素开始查找； 待查关键字值与各结点 （ 记录 ） 的关键字值逐个进行比较；若找到相等的结点 ，则查找成功；否则 ， 查找失败 。 查找表的存储结构： 既适用于顺序存储结构 也适用于链式存储结构 下一页 上一页 停止放映 第 10 页 顺序查找算法 3-1 n , n
4、 , i=0 ; i 0) d,dn”, 下一页 上一页 停止放映 第 13 页 算法讨论 平均查找长度 等概率的情况下 , i = () = 一般情况下 , 优点 : 对结点的逻辑次序 (不必有序 )和存储结构 (顺序、链表均可）无要求； 当序列中的记录 “ 基本有序 ” 或 较好的算法； 缺点： 讨论：能否减少比较次数，以提高效率。例如，二分法等。 i=1 n n 1 2 n+1 2 n i=1 n 下一页 上一页 停止放映 第 14 页 2、折半查找 二分查找是一种高效的查找方法 。 它可以明显减少比较次数 ， 提高查找效率 。 但是 ， 二分查找的先决条件是查找表中的数据元素必须有序
5、。 算法步骤： 先确定整个查找区间的中间位置 ， （ / 2 待查关键字值与中间位置的关键字值进行比较； 若相等 ， 则查找成功； 若大于 ， 则在后半区域继续进行二分查找； 若小于 ， 则在前半区域继续进行二分查找 。 对确定的缩小区域再按二分公式 ， 重复上述步骤； 最后 ， 得到结果： 要么 ， 查找成功 ， 要么 ， 查找失败 。 存储结构 用一维数组存放 。 下一页 上一页 停止放映 第 15 页 折半查找算法举例 对给定数列（有序） 3， 5， 11， 17， 21， 23，28， 30， 32， 50，按折半查找算法，查找关键字值为 30的数据元素。 第 1次： 3， 5， 11
6、， 17， 21， 23， 28， 30， 32， 50 （ 1+10） /2 = 5 第 2次： 23， 28， 30， 32， 50 （ 6+10） /2 = 8 一页 上一页 停止放映 第 16 页 折半查找算法 3-3 n , n, ; ; ( ; 1; “ n”); “ n”); 1; 下一页 上一页 停止放映 第 17 页 折半查找算法 3#) s10=1,2,3,4,5,6,7,8,9,10,11,12; s,12,11); d , dn, 下一页 上一页 停止放映 第 18 页 算法讨论 优点 : 每经过一次比较 ,查找范围就缩小一半。经 计较就可以完成查找过程。 缺点： 因要
7、求有序，所以对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不大便利。 考虑： 能否一次比较抛弃更多的部分（即一次比较，使查找范围缩得更小），以达到提高效率的目的； 把两种方法（顺序查找和二分查找）结合起来，来达到提高效率的目的。 下一页 上一页 停止放映 第 19 页 3、分块查找 分块查找又称索引顺序查找 ， 这是顺序查找的一种改进方法 。 方法描述：将 按块有序 ” 划分为 m n） 。 每一块中的结点不必有序 ， 但块与块之间必须 “ 按块有序 ” ；即第 1快中任一元素的关键字都必须小于第 2块中任一元素的关键字；而第 2块中任一元素又都必须小于第3块中的
8、任一元素 ， 。 每个块中元素不一定是有序的 。 下一页 上一页 停止放映 第 20 页 分块查找算法描述 选取各块中的最大关键字构成一个索引表； 找分两个部分： 先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中； 在已确定的块中用顺序法进行查找。 下一页 上一页 停止放映 第 21 页 索引表结构定义 # 下一页 上一页 停止放映 第 22 页 ,s, m,l) i,j; i=0; i i+; if(i=m) n); 1); * 否则 ， 查找成功处理 */ 下一页 上一页 停止放映 第 23 页 分块查找子函数（续） j=lsi=sj & (ia2,取第 3个块 ;在第 3块中用
9、顺序法查找 ,比较两次 ,就可以找出 60的元素来。 44 22 74 22 12 13 9 8 33 42 44 38 24 48 60 58 74 47 下一页 上一页 停止放映 第 26 页 算法讨论 设索引表使用二分法，则有： （ n/S +1） + S/2 其中： 设各块长度相等）。 优点： 插入、删除操作方便；只要找到对应的块，在块中任意位置操作均可。 缺点： 索引表增加了辅助存储空间。 注： 索引表在数据库系统中广泛使用。 下一页 上一页 停止放映 第 27 页 4、树表（二叉排序树）查找 前三种查找方法各有千秋 。 二分法查找效率高 ， 顺序法可以采用链表存储结构 ， 操作灵活
10、 。 但最好是既有二分法的高效率 ， 又有链表灵活性的查找方法 。 二叉排序树实际上就是将数据元素组织成二叉树形式 ， 以达到与二分法相同的查找效率 ， 而又具有链表的插入 、删除操作的灵活性 。 下一页 上一页 停止放映 第 28 页 二叉排序树查找（算法 3 先建立起二叉排序树 。 待查关键字值与树根结点进行比较 ， 若相等 ， 查找成功； 则根据比较结果确定查找路径： 若小于根结点的关键字值 ， 则与左子树的根结点的关键字值进行比较； 若大于等于根结点的关键字值 ， 则与右子树的根结点的关键字值进行比较 。 复上述步骤 ， 直到要么找到 ， 查找成功；要么找不到 ， 查找失败 。 下一页 上一页 停止放映 第 29 页 存储结构描述 二叉排序树结点结构： * 下一页 上一页 停止放映 第 30 页 ! n”); roo
