ch8- 查找.ppt

第8章 查找 8.1 基本概念 讨论： （4）如何评估查找方法的优劣？ 8.2 静态查找表 一、顺序查找（ Linear search，又称线性查找 ） （2）算法的实现： 讨论① 查不到怎么办？ 二、折半查找（又称二分查找或对分查找） 折半查找举例： 讨论① 若关键字不在表中，怎样得知和停止？ 平均每个数据的查找时间还要除以n，所以： 折半查找效率分析法2（参见教材P220）： 三、静态树表的查找 四、分块查找（索引顺序查找） 查找步骤分两步进行： 8.3 动态查找表 一、二叉排序树/二叉查找树的定义 二、二叉排序树的插入与删除 讨论1：二叉排序树的插入和查找操作 二叉排序树的查找插入算法如何实现？ 讨论2：二叉排序树的删除操作 *p有两棵子树时，如何进行删除操作？ 例：请从下面的二叉排序树中删除结点P。 三、二叉排序树的查找分析 最好情况：即：与折半查找中的判定树相同（形态比较均衡） 四、平衡二叉树 1）LL平衡旋转： 3）LR平衡旋转： 例：请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53） 8.4 哈希查找表 一、哈希表的概念 例2 ： 若干术语 冲突现象举例： 在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。 二、哈希函数的构造方法 1、直接定址法 2、数字分析法 3、平方取中法 5、除留余数法 6、随机数法 三、冲突处理方法 1、开放定址法（开地址法） 例： 讨论： 2. 二次探测法 2、再哈希法（双哈希函数法） 3、链地址法(拉链法） 四、哈希表的查找及分析 四、哈希表的查找及分析 讨论： 本章小结 若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。 (以B为旋转轴） A B C A B C 若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。 (以B为旋转轴） 2）RR平衡旋转： A B C A B C 若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。 (以插入的结点C为旋转轴） 4）RL平衡旋转： A B C A B C A B C 若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。 (以插入的结点C为旋转轴） A B C A B C A B C 这种调整规则可以保证二叉排序树的次序不变 0 13 0 37 0 24 0 13 0 37 -1 13 0 24 -1 24 -2 13 需要RR平衡旋转 (绕B逆转,B为根） 0 90 -1 24 -1 37 0 53 1 90 -2 37 需要RL平衡旋转 (绕C先顺后逆） 0 37 0 90 0 53 0 37 0 90 0 53 一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分析 哈希表：即散列存储结构。 散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！ 例1：若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V[01]单元； 将2001011810202的所有信息存入V[02]单元； …… 将2001011810231的所有信息存入V[31]单元。 欲查找学号为2001011810216的信息，便可直接访问V[16]！ 有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。 （注：H（k）＝k称为散列函数） 解：根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……， 对应散列存储表（哈希表）如下： 讨论：如何进行散列查找？ 根据存储时用到的散列函数H(k)表达式，迅即可查到结果！ 例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功； 若查不到，应当设法返回一个特殊值，例如空指针或空记录。 … 14 … 11 … 9 … 内容 地址 … 39 … 25 24 23 14 11 9 23 25 39 缺点：空间效率低！ 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。 通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。 哈希方法(杂凑法) 哈希函数(杂凑函数) 哈希表 (杂凑表) 冲 突 哈希方法