《数据结构》课程教学资源：课程教学资源（PPT课件讲稿）第九章 查找表

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

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

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

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

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

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

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

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

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

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

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

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

91静态查找表 92动态查找树表 93哈希表

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

9.1 静态查找表

9.1 静 态 查 找 表

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

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

基本操作P Create(&st, n) Destroy(&st Search(st, key) Traverse(ST, visito) 3 ADT StaticSearchTable

Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit()); 基本操作 P： } ADT StaticSearchTable