数据结构》 第九章查找
《数据结构》 第九章 查找
第九章查找 第九章查找 内容和要求 査找的概念,顺序査找、二分法查找、分块查 找的概念和方法,二叉排序树、平衡二叉树的 查找,哈希表查找。要求获得有关静态和动态 环境下几种基本的查找方法和技术知识。掌握 顺序、二分法和分块查找的方法;了解哈希表 是一种基本的存储结构、哈希表的背景和基本 思路。掌握哈希表处理冲突的方法 重点 分法查找方法;哈希表的动态查找 第2页
第九章 查找 第2页 第九章 查 找 内容和要求 查找的概念，顺序查找、二分法查找、分块查 找的概念和方法，二叉排序树、平衡二叉树的 查找，哈希表查找。要求获得有关静态和动态 环境下几种基本的查找方法和技术知识。掌握 顺序、二分法和分块查找的方法；了解哈希表 是一种基本的存储结构、哈希表的背景和基本 思路。掌握哈希表处理冲突的方法。 重点 二分法查找方法；哈希表的动态查找
基本概念 第九章查找 査找表由同一类型的数据元素(或记录)构成的集合 静态査找表仅作查询与检索(统称为查找)工作的查找 表 动态査找表除作査询与检索之外,还需作诸如插入、删 除之类更新操作的查找表 查找在一个含有众多数据元素(或记录)的查找表中找出某个 “特定的”数据元素(或记录)的过程 关键字能够标识一个数据元素(或记录)的某个数据项的值。 当数据元素只有一个数据项时,其关键字即为该数据元素的值。 主关键字能唯一地标识一个记录的关键字 给定一个值k,在含有n个记录(或数据元素)的表中找出关键字等 于给定值k的记录,若找到,则査找成功,查找结果为给出整个 记录的信息,或指示该记录在查找表中的位置;若找不到,则查 找不成功,查找结果为NULL值或值0
第九章 查找 第3页 查找表 由同一类型的数据元素（或记录）构成 的集合 基本概念 静态查找表 仅作查询与检索（统称为查找）工作的查找 表。 动态查找表 除作查询与检索之外，还需作诸如插入、删 除之类更新操作的查找表。 查找 在一个含有众多数据元素（或记录）的查找表中找出某个 “特定的”数据元素（或记录）的过程。 关键字 能够标识一个数据元素（或记录）的某个数据项的值。 当数据元素只有一个数据项时，其关键字即为该数据元素的值。 主关键字 能唯一地标识一个记录的关键字。 给定一个值k，在含有n个记录(或数据元素)的表中找出关键字等 于给定值k的记录，若找到，则查找成功，查找结果为给出整个 记录的信息，或指示该记录在查找表中的位置；若找不到，则查 找不成功，查找结果为NULL值或值0
基本概念 第九章查找 查找操作主要是关键字的比较,故通常把查找过程中对关键一 字需要执行的平均比较次数(亦称平均査找长度)作为衡量 个查找算法效率优劣的标准。 平均査找长度为了确定记录在查找表中的位置,需和给定值进 行比较的关键字个数的期望值(平均值)称为查找算法在查找成功 时的平均查找长度( Average Search Length) 对于含有n个记录的表,查找成功时的平均查找长度为 ASL (9-1) 其中 P P:表中第个记录被查找的概率,有 找到表中其关键字与给定值相等的第个记录时,所需 要的比较次数 若无特别声明,均认为表中每个记录的概率均相等,即 P= P P
第九章 查找 第4页 查找操作主要是关键字的比较，故通常把查找过程中对关键 字需要执行的平均比较次数（亦称平均查找长度）作为衡量一 个查找算法效率优劣的标准。 基本概念 平均查找长度 为了确定记录在查找表中的位置，需和给定值进 行比较的关键字个数的期望值(平均值)称为查找算法在查找成功 时的平均查找长度(Average Search Length)。 对于含有n个记录的表，查找成功时的平均查找长度为 (9-1) 其中 Pi：表中第i个记录被查找的概率，有 ； Ci：找到表中其关键字与给定值相等的第i个记录时，所需 要的比较次数。 若无特别声明，均认为表中每个记录的概率均相等，即
约定和宏定义 第九章查找 宏定义 tdefine Eo( a b)((a)==(b)) #define lT( a b)((a)<(b)) #define Lo( a, b)((a) (y)) 注:宏定义随不同的数据类型,有所不同
第九章 查找 第5页 约定和宏定义 宏定义 #define EQ( a, b ) ((a) == (b)) #define LT( a, b ) ((a) < (b)) #define LQ( a, b ) ((a) <= (b)) 注：宏定义随不同的数据类型，有所不同