《查找技术》ppt课件

《《查找技术》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章查找技术本章的主要内容是:查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术查找的基本概念关键码：可以标识一个记录的某个数据项。键值：关键码的值。主关键码：可以唯一地标识一个记录的关键码。次关键码：不能唯一地标识一个记录的关键码。7.1概述50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972年9月2003年7月1979年9月2003年7月1990年4月参加工作查找的基本概念查找：在具有相同类型的记录构成的集合中找出满足给定条件的记录。7.1

2、概述查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972年9月2003年7月1979年9月2003年7月1990年4月参加工作静态查找：不涉及插入和删除操作的查找。动态查找：涉及插入和删除操作的查找。7.1概述查找的基本概念静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：

3、查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。7.1概述查找的基本概念查找结构：面向查找操作的数据结构，即查找基于的数据结构。查找结构查找方法集合中元素之间不存在明显的组织规律，不便查找。集合线性表树表散列表本章讨论的查找结构：线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。树表：适用于动态查找，主要采用二叉排序树的查找技术。散列表：静态查找和动态查找均适用，主要采用散列技术。7.1概述查找结构：面向查找操作的数据结构，即查找基于的数据结构。

4、查找的基本概念顺序查找（线性查找）基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。101524612354098550123456789i7.2线性表的查找技术例：查找k＝35iii顺序查找（线性查找）7.2线性表的查找技术intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{i=n;while(i>0&&r[i]!=k)i--;returni;

5、}基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。7.2线性表的查找技术改进的顺序查找101524612354098550123456789i例：查找k＝35iii哨兵35查找方向基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。7.2线性表的查找技术改进的顺序查找101524612354098550123456789i例：查找k＝25ii

6、25查找方向iiiiiiiintSeqSearch2(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}7.2线性表的查找技术改进的顺序查找平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。7.2线性表的查找技术顺序查找的缺点：算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。顺序查找的优点：折半查找使用条件：线性表中的记

7、录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。7.2线性表的查找技术折半查找的基本思想7.2线性表的查找技术[r1………rmid-1]rmid[rmid+1………rn]如果krmid查找左半区查找右半区k（mid=(1+n)/2）例：查找值

8、为14的记录的过程：0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=2mid=131>1418>147<14low=2mid=214=147.2线性表的查找技术例：查找值为22的记录的过程：0123456789101112137