第5章常用算法查找.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,零基础学算法,第,5,章,:,常用算法,查找,课程安排,5.1 查找的基本概念,5.2 简单查找,5.3 二叉排序树,5.4 索引查找,5.5 哈希表,5.1,查找的基本概念,主关键字和次关键字,查找结果,静态查找表和动态查找表,5.2,简单查找,顺序查找,从线性表的一端开始，依次将每个记录的关键字与给定值进行比较，若某个记录的关键字等于给定值，表示查找成功，返回记录序号；若将线性表中所有记录都比较完，仍未找到关键字与给定值相等的记录，则表示查找失败，返回一个失败值。,折半查找,又称为二分查找。这种查找方法要求查找表的数据是线性结构保存，并且还要求查找表中的数据是按关键字由小到大有序排列。,69,65,90,37,92,6,28,54,5.2,简单查找,折半查找,5.3,二叉排序树,插入结点,查找结点,删除结点,5.3,二叉排序树,删除叶结点,5.3,二叉排序树,删除无右子树结点,5.3,二叉排序树,删除有左右子树结点,5.4,索引查找,主表和索引表,创建索引的一般过程,索引的特点,5.4.1,索引的概念,5.4,索引查找,在索引表中进行查找,引查找的过程是：,（,1,）首先根据给定的关键字,key,，按定义的函数计算出索引值,index1,，在索引表上查找出索引值等于,index1,的索引项，以确定对应子表在主表中的开始位置和长度，,（,2,）接着根据从索引表中获取的开始序号,start,，在主表指定位置（即子表的开始处）顺序查找关键字,key,。,向主表中插入数据,在线性表的索引存储结构上进行插入和删除运算的算法，与查找算法类似，其具体过程如下：,（,1,）根据待插入元素的值查找索引表，确定出对应的子表。,（,2,）接着，根据待插入元素的关键字，在该子表中做插入元素的操作。,（,3,）插入完成后，修改索引表中的相应子表的长度。,5.4.1,索引查找算法,5.5,哈希表,哈希表的基本思想是：以线性表中每个元素的关键字,key,为自变量，通过一定的函数关系,h(key),计算出函数的值，把这个值作为数组的下标，将元素存入对应的数组元素中。,函数,h(key),称为哈希函数，函数的值称为哈希地址。,5.5.1,哈希表概述,线性表：,哈希函数：,5.5,哈希表,直接定址法,除法取余法,数字分析法,平方取中法,折叠法,5.5.2,构造哈希函数,5.5,哈希表,开放地址法,线性探测法,双哈希函数探测法,5.5.3,处理冲突,链接法,性格决定命运,专注成就人生,