第十章 查我 10.1查找的基本撬念 102戌性表的查找 10.3树表的查找 104哈希表查找
1 10.1 查找的基本概念 10.2 线性表的查找 10.3 树表的查找 10.4 哈希表查找 第十章 查找
10.1查找的基本概念 查龙:也叫检索,是根据给定的某个值,在表 中确定一个关键字等于给定值的记录或数据元 素的过程。 ●查结果 >查找成功tabe中存在给定值的记录,返回 该记录的信息或该记录在表中的位置 >查不成tabe中不存在给定值的记录 返回相关的指示信息。 2
2 ⚫ 查找：也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元 素的过程。 ⚫ 查找结果： ➢ 查找成功(table中存在给定值的记录，返回 该记录的信息或该记录在表中的位置） ➢ 查找不成功(table中不存在给定值的记录， 返回相关的指示信息。 10.1 查找的基本概念
10.1查找的基本概念 就表 search table:是由同一类型的数据元素 (或记录)构成的集合,集合中的数据元素之间 的关系是完全松散的 查找表的主要缲作: 查询某个“特定的”数据元素是否在表中 检索某个“特定的”数据元素的各种属性 >在查找表中插入一个数据元素 >从查找表中删去某个数据元素 查找表分为: >静态查花表对表中的DE不进行插入和删除) 3 >动态查龙表对表中的DE可进行插入和删除);
3 ⚫ 查找表(search table):是由同一类型的数据元素 （或记录）构成的集合，集合中的数据元素之间 的关系是完全松散的。 ⚫ 查找表的主要操作： ➢查询某个“特定的”数据元素是否在表中； ➢检索某个“特定的”数据元素的各种属性； ➢在查找表中插入一个数据元素； ➢从查找表中删去某个数据元素。 ⚫ 查找表分为： ➢静态查找表(对表中的DE不进行插入和删除)； ➢动态查找表(对表中的DE可进行插入和删除)； 10.1 查找的基本概念
10.1查找的基本概念 平均查线长度 average search length):查找过程中, 对关键字进行比较的平均次数即比较次数的期望值。 ASL=∑Pc i=1 其中:n是结点个数,p是查找第个结点的概率 C是查找第个结点所需的比较次数 4
4 ⚫ 平均查找长度(average search length):查找过程中, 对关键字进行比较的平均次数即比较次数的期望值。 = = n i ASL pi ci 1 其中：n是结点个数，pi是查找第i个结点的概率 Ci是查找第i个结点所需的比较次数 10.1 查找的基本概念
102线性表的查找 线性表是表的组织方式中最简单的一种,在其上 我们主要介绍顺序查线二分查找和分块查 版序查找( Sequential search):从表的一端开 始,顺序扫描线性表,依次将扫描到的结点关键字和 给定值进行比较,若当前扫描到的结点值与给定值相 等,则查找成功;反之,若扫描到最后,仍未找到关 键宇等于k的结点,则查找失败。适用于顺序存储结 构和链表存储结构
5 10.2 线性表的查找 线性表是表的组织方式中最简单的一种，在其上 我们主要介绍顺序查找、二分查找和分块查找。 一、顺序查找（Sequential Search)：从表的一端开 始，顺序扫描线性表，依次将扫描到的结点关键字和 给定值进行比较，若当前扫描到的结点值与给定值相 等，则查找成功；反之，若扫描到最后，仍未找到关 键字等于k的结点，则查找失败。适用于顺序存储结 构和链表存储结构