数据结构课件-第八章.ppt

二、散列函数的构造方法 1、除留余数法是最为简单常用的一种方法，它是以表长m来除关键字，取余数作为散列地址，即 h(key) = key%m。该方法的关键就是选取m。m一般取为略大于元素个数的第一个素数。 2、举例：如果给出一组数据(20,30,70,14,8,12,18,60,1,11),因为 一共10个数据，那么m应该选取为略大于10的素数11， 散列函数h(key) = key%11。 0 1 2 3 4 5 6 7 8 9 10 20 30 70 14 8 同义词 12 18 60 1 同义词 11 三、处理冲突的方法 1、开放定址法是在表中某个存储单元发生冲突时，去探测 未存储数据的存储单元，将关键字存在空的存储单元。 0 1 2 3 4 5 6 7 8 9 10 20 30 70 14 8 同义词 12 18 60 1 同义词 11 用线性探查法解决冲突，开放地址法的公式为： h(key)=(h(key)+i)%m i=1,2,…,m-1 2、拉链法是将散列表中地址相同的关键字链接形成一个单 链表，每个单链表第一个结点的地址对应存储在散列表 相应的存储单元中。 哈希查找过程 给定k值 计算H(k) 此地址为空 关键字==k 查找失败 查找成功 按处理冲突 方法计算Hi Y N Y N 对于给定值 K, 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 否则 “求下一地址 Hi” ， 直至r[Hi] = NULL (查找不成功) 或r[Hi].key = K (查找成功) 为止。 若需要在给定的哈希表上进行查找，则： 8.6 回到工作场景 通过学习，同学们应该已经掌握了各种查找算法的定义以及实现代码，足以完成工作场景中的任务。下面回到8.1节的工作场景中，完成工作任务。 【工作过程一】问题解析： 【工作过程二】编写代码，实现算法： 【工作过程3】系统运行 8.7 应用实践：利用哈希查找实现数据快速查询  1. 实践内容 实现哈希查找，包括首先要根据哈希函数构造哈希地址，然后根据哈希地址进行查找。 2. 实践目的 掌握哈希查找的算法思想及实现方法。 培养学生利用查找的相关知识解决实际问题的能力。 3、实践过程 数据结构 主编 许绘香 段明义 中国水利水电出版社 第八章 查找 查找又称检索，就是从一个数据元素集合中找出某个特定的数据元素。它是数据处理中使用频繁的一种重要操作。当所涉及的数据量较大时，查找算法的优劣将直接影响到整个软件系统的效率。 8.1工作场景导入  【工作场景】 某学校要开发一个学生成绩管理系统，学生信息主要包括学号和成绩，并按照成绩递增的顺序排列。现在为了方便成绩管理，需要根据分数查找该学生的学号信息，请编写程序实现之，得到如图8-1-1所示的输出结果。 【引导问题】 （1）如何选择合适的查找算法 （2）如何实现该查找功能，效率如何？ 8.2查找的基本概念 查找（Searching）也称检索，是在数据元素（或称对象）集合中查找是否存在关键码等于某个给定关键码的数据元素。 查找操作所依赖的数据结构是查找表，查找的依据是记录的关键字（key）。 查找表的分类： 静态查找：仅作查询和检索操作的查找表，如：顺序查找、折半查找、索引查找 动态查找：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。如：二叉排序树查找 散列查找：用散列函数得到元素的存储地址，如：散列查找 查找的基本运算：比较 查找效率的指标：平均查找长度ASL(Average Search Length) 8.2查找的基本概念 8.3.1 顺序查找  顺序查找思想： 从表的一端开始,逐个将记录关键字与给定的值比较。若相等,则查找成功；若所有n 个记录的关键字值都已比较,其关键字和给定值都不相等,则查找失败。 若要在顺序表上进行查找，其类型定义： typedef int KeyType; //关键字类型 typedef struct { KeyType key; //关键字 // other fields; //其它数据项