南京航空航天大学：《数据结构》课程教学资源（PPT课件讲稿）第九章 查找

教育部—一微软精品课程建设项目 第九章查找 南京航空航天大学数据结构课题组版权所有

第九章 查找

教育部—微软精品课程建设项目 何谓查找表? 查找表是由同一类型的数据元素 (或记录)构成的集合 由于“集合”中的数据元素之间存在 着松散的关系,因此查找表是一种应用 灵便的结构。 京航空航天大学数据结构题组版权所有

何谓查找表 ？ 查找表是由同一类型的数据元素 (或记录)构成的集合。 由于“集合”中的数据元素之间存在 着松散的关系，因此查找表是一种应用 灵便的结构

教育部—微软精品课程建设项目 对查找表经常进行的操作: 1)查询某个“特定的”数据元素是 否在查找表中; 2)检索某个“特定的”数据元素的 各种属性; 3)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素。 京航空航天大学数据结构题组版权所有

对查找表经常进行的操作: • 1）查询某个“特定的”数据元素是 否在查找表中； • 2）检索某个“特定的”数据元素的 各种属性； • 3）在查找表中插入一个数据元素； • 4）从查找表中删去某个数据元素

教育部—微软精品课程建设项目 奎找表可分为两类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 有时在查询之后,还需要将“查询”结 果为“不在查找表中”的数据元素插入 到查找表中;或者,从查找表中删除其 “查询”结果为“在查找表中”的数据 京航空航天大学数据结构题组版权所有

仅作查询和检索操作的查找表。 静态查找表 有时在查询之后，还需要将“查询”结 果为“不在查找表中”的数据元素插入 到查找表中；或者，从查找表中删除其 “查询”结果为“在查找表中”的数据 元素。 动态查找表 查找表可分为两类:

教育部—微软精品课程建设项目 关键字 是数据元素(或记录)中某个数据项 的值,用以标识(识别)一个数据元 素(或记录)。 若此关键字可以识别唯一的一个 录,则称之谓“主关键字” 若此关键字能识别若干记录,则称 之谓“次关键字”。 京航空航天大学数据结构题组版权所有

是数据元素（或记录）中某个数据项 的值，用以标识（识别）一个数据元 素（或记录）。 关键字 若此关键字可以识别唯一的一个记 录，则称之谓“主关键字” 。 若此关键字能识别若干记录，则称 之谓“次关键字”

教育部—微软精品课程建设项目 查找 根据给定的某个值,在查找表中确定一个 其关键字等于给定值的数据元素或(记录) 若查找表中存在这样一个记录,则称 “查找成功”。查找结果给出整个记录的 信息,或指示该记录在查找表中的位置 否则称“查找不成功”。查找结果给出 “空记录”或“空指针”。 京航空航天大学数据结构题组版权所有

根据给定的某个值，在查找表中确定一个 其关键字等于给定值的数据元素或（记录）。 查找 若查找表中存在这样一个记录，则称 “查找成功” 。查找结果给出整个记录的 信息，或指示该记录在查找表中的位置； 否则称“查找不成功” 。查找结果给出 “空记录”或“空指针”

教育部—微软精品课程建设项目 如何进行查找? 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明 的组织规律,因此不便于查找 为了提高查找的效率,需要在查找表中 的元素之间人为地附加某种确定的关系, 换句话说,用另外一种结构来表示查找 京航空航天大学数据结构题组版权所有

由于查找表中的数据元素之间不存在明 显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中 的元素之间人为地 附加某种确定的关系， 换句话说， 用另外一种结构来表示查找表。 如何进行查找？ 查找的方法取决于查找表的结构

教育部—微软精品课程建设项目 9.1静态查找表 92动态查找树表 9.3哈希表 南京航空航天大学数握结构题组版权所有

9.1 静态查找表 9.2 动态查找树表 9.3 哈希表

教育部—微软精品课程建设项目 9。1 静态查找表 京航空航天大学数据结构题组版权所有

9.1 静 态 查 找 表

教育部—微软精品课程建设项目 ADT StaticSearchTable i 数据对象D:D是具有相同特性的数 据元素的集合。每个数 据元素含有类型相同的 关键字,可唯一标识数 据元素 数据关系R:数据元素同属一个集 京航空航天大学数据结构题组版权所有

数据对象D： 数据关系R： D是具有相同特性的数 据元素的集合。每个数 据元素含有类型相同的 关键字，可唯一标识数 据元素。 数据元素同属一个集合。 ADT StaticSearchTable {