DS009 查找课件.ppt

第9章 查找 数据结构 唐厚俭 数据结构 西安电子科技大学·理学院 第九章 查找 西安电子科技大学·理学院 hjTang@xidian.edu.cn 基本概念 查找表——同一类型数据元素构成的集合 操作 查询特定元素是否在查找表中 检索某个特定元素的各种属性 在查找表中插入一个元素 从查找表中删除一个元素 静态查找表——只作前两种操作 动态查找表 基本概念 关键字(Key)—数据元素(记录)中某个数据项的值，用它可以标识一个数据元素或记录 主关键字(Primary Key)——可以唯一地标识一个记录 次关键字(Secondary Key) 查找(Searching)根据某个特定地值，在查找表中查找一个其关键字等于给定值地记录或数据元素 查找成功/不成功 基本定义 #typedef float/int/(char *) KeyType; #define EQ(a, b) ((a)==(b)) #define LT(a, b) ((a)(b)) #define GT(a, b) ((a)(b)) // char * #define EQ(a, b)) (!strcmp((a), (b))) // float #define EQ(a, b)) (fabs((a)-(b)) 1e-6) $9.1 静态查找表 顺序表的查找 有序表的查找 静态树表的查找 （※） 索引顺序表的查找 有关线性表顺序表示的算法 静态顺序表 顺序表的查找 无序表上的查找 有序表上的查找 顺序表的排序 选择排序 插入排序 冒泡排序 顺序表的查找 顺序查找 从表中的第一个记录开始，逐个进行记录关键字和给定值的比较，如果比较值相等，则查找成功；反之，若直至最后一个记录的关键字的值与给定值不相等，表明表中没有所查找的记录，查找不成功 查找性能分析 平均查找长度ASL Pi为查找第i个记录的概率 顺序查找的Pi Ci = (i+1) Pi = 1/N 查找不成功的概率 假定查找成功的概率为1/2： 查找不成功要查找的长度为 N+1 查找每个元素的概率为 1/2N 平均查找长度ASL 有序表的查找——折半查找 折半查找(查找失败) 折半查找性能分析 索引顺序表的查找 索引顺序查找＝分块查找 建立索引表 平均查找长度 ASLbs = Lb + Lw Lb 策略 ＋ lw策略 $9.3 Hash表 记录位置随机，和关键字无关 查找的理想情况：一次查到 方法：在存储位置和关键字之间建立一个确定的对应关系f，根据对应关系f找到给定关键字K的像(位置)。 特点：若结构中存在的关键字和K相等，则必在f(K)的存储位置上 称对应关系f为Hash函数 Hash函数 将关键字按照某种顺序存放 将名字按字符加起来，再模11 f(john) = (‘j’+’o’+’h’+’n’)%11 f(john) = (431)%11 = 2 f(mike) = (422) % 11 = 4 f(dave) = (416) % 11 = 9 f(mary) = (441) % 11 = 1 我们称函数f为一个Hash函数 Hash函数： 将关键字变换到[0~N)地址的函数 Hash表特点 Hash函数值域在[0, n)之间 查找只需要一次计算即可 问题:冲突——不同的关键字得到同一索引 Hash表：根据设定的Hash函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续地址集上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表称为Hash表，这一映象过程称为Hash表的散列，得到的存储位置称为Hash地址或散列地址。 Hash函数 f(john) = (431) % 11 = 2 f(mike) = (422) % 11 = 4 f(dave) = (416) % 11 = 9 f(mary) = (441) % 11 = 1 f(bill) = (419) % 11 = 1? 二、Hash函数的构造方法 好Hash函数，就是均匀的：对于关键字集合中的任一关键字，经Hash函数映象到地址集合中的任意个地址的概率是相等的。 直接地址法： H(key) = a * key + b; 例1：从1岁到100岁的人口统计表，则 H(key) = key; key 为岁数 例2：解放后出身的人口调出表 H(key) = key – 1948; 数字分析法 分析原始数据中的规律，找出无规律的内容 平方取中法 取关键字平方后中间的几位为Hash地址 折叠法 图书编号0-442-20586-4拆开为 4+4220+5684 = 10088 4685+0224+40=4949 除留余数法 公式：H(key) = key MOD p (p= m) 一般的经验：选P为质数或包含不小于20