[农学]第 9 章 集合.ppt

第9章 集合 本章目录 9.1 基本概念 9.2 线性表上的查找 9.2.1 顺序表的查找 9.2.2 有序表的查找 9.3.1 分块查找 9.4 树表上的查找 9.4.1 二叉排序树 9.4.2 平衡二叉树 *9.4.3 B- 树 *9.4.4 键树 9.5 哈希表 9.5.1哈希表查找的基本概念 9.5.2 构造哈希函数的方法 9.5.3哈希冲突的解决方法 9.5.4哈希表的查找及分析 *9.6 算法设计举例 主要内容 知识点 1．集合数据结构，元素间不存在任何逻辑关系。 2. 三种方法（静态查找表，动态查找表，哈希表）实现集合的运算。 3．静态查找表：顺序表，有序表，静态树表，索引顺序表。 4．动态查找表：二叉排序树，平衡二叉树，B-树，B+树，键树。 5．哈希表。 重点难点 1．静态查找表中各种方法及其运算。 2．二叉排序树的建立、查找，插入和删除算法。 3．最佳二叉排序树，平衡二叉树的性质和手工绘制。 4．B-树是多路平衡外查找树，手工模拟B-树插入和删除。 5．键树中每个结点是关键字的一个字符，键树的插入和删除。 6．哈希表的建立、查找。 7. 平均查找长度（ASL)的计算 基本概念 基本概念 基本概念 查找的方法：静态查找表、动态查找表和哈希表 平均查找长度（Average Search Length）:和给定值进行比较的关键字个数的“期望值”称为查找算法的平均查找长度。是衡量查找算法性能的主要依据。 查找成功时的平均查找长度为 ： 静态查找表上的查找 集合（查找表）中的元素是无序的，由于元素间不存在逻辑关系，为了查找的方便，可以把元素按某种方法组织成顺序表，从而可以采用顺序表的方法来实现查找。 顺序表的查找 有序表的查找 索引顺序查找 顺序表的查找  顺序表的查找分析 有序表的查找 思想：首先，将给定的查找关键字k与线性表的中间位置上的元素进行比较，若相等，则查找成功。否则，中间元素将线性表分成两个部分，前一部分中的元素均小于中间元素，而后一部分中的元素则均大于中间元素。在前后两部分重复上述过程，直至查找成功或失败。 有序表的查找分类 按确定“中间位置”的方式不同，分为： 折半查找 菲波那契查找 插值查找 折半查找示例 示例 折半查找非递归算法 折半查找递归算法 折半查找的判定树 带外部结点的判定树 折半查找的性能 折半查找的平均查找长度 : 画出含有12个元素的有序表的二叉判定树 菲波那契查找 方法： 根据菲波那契序列对表进行分割。菲波那契序列为：0,1,1,2,3,5,8,13,21,…。 , 菲波那契序列中任意两个相邻的菲波那契数的差的绝对值还是菲波那契数。 12个结点的菲波那契树 菲波那契查找算法（续） case kr[mid].key: ∥比较大 if(n1=1) mid=0; ∥查找失败 else {mid=mid+n2;∥右子树新的菲波那契数 n1=n1-n2; ∥前一个菲波那契数 n2=n2-n1; ∥后一个菲波那契数 } break; case k=r[mid].key: return mid; ∥查找成功，返回元素位置 }//end of switch }//while return 0; ∥查找失败 } ∥SearchFib 插值查找 方法： 根据数据的实际分布情况计算可能的位置，适合于数据分布均匀的情况 步骤： 设查找的区间为[low,high]，kh和kl分别表示上、下界对应的关键字的值。则插值查找使用下面的式子计算出进行比较的记录位置mid： 其中k为待查找的关键字。通过计算出的mid的值，使k与r[m