数据结 第8章查找表 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第8章查找表 胡建华 2021/2/19 计算机教研室 第 1 页 第 8 章 查找表
@基本概念 ■查找表是由同一类型的数据元素(或记录)构成的集合。 营·由于“集合”中的数据元素之间存在着松散的关系,因 此查找表是一种应用灵便的结构 数对查找表经常进行的操作: 1)查询某个“特定的”数据元素是否在查找表中 2)检索某个“特定的”数据元素的各种属性; 83)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素。 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第2页 基本概念 ▪ 查找表是由同一类型的数据元素(或记录)构成的集合。 ▪ 由于“集合”中的数据元素之间存在着松散的关系，因 此查找表是一种应用灵便的结构。 ▪ 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素
查找表可分为两类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 有时在查询之后,还需要将“查询”结果为“不 在查找表中”的数据元素插入到查找表中;或者,从 查找表中删除其“查询”结果为“在查找表中”的数 据元素。 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第3页 查找表可分为两类 ▪ 静态查找表 仅作查询和检索操作的查找表。 ▪ 动态查找表 有时在查询之后，还需要将“查询”结果为“不 在查找表中”的数据元素插入到查找表中；或者，从 查找表中删除其“查询”结果为“在查找表中”的数 据元素
关键字是数据元素(或记录)中某个数据项的值,用 以标识(识别)一个数据元素(或记录)。 若此关键字可以识别唯一的一个记录,则称之谓“主 关键字”。若此关键字能识别若干记录,则称之谓 “次关键字” .查找根据给定的某个值,在查找表中确定一个其关键 字等于给定值的数据元素。 若查找表中存在这样一个记录,则称“查找成功”。查找结 果给出整个记录的信息,或指示该记录在查找表中的位置; 否则称“查找不成功”。查找结果给出“空记录”或“空指 针 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第4页 • 关键字是数据元素（或记录）中某个数据项的值，用 以标识（识别）一个数据元素（或记录）。 • 若此关键字可以识别唯一的一个记录，则称之谓“主 关键字”。若此关键字能识别若干记录，则称之谓 “次关键字” 。 • 查找根据给定的某个值，在查找表中确定一个其关键 字等于给定值的数据元素。 –若查找表中存在这样一个记录，则称“查找成功”。查找结 果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”。查找结果给出“空记录”或“空指 针”
如何进行查找? 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织 规律,因此不便于查找。 为了提高查找的效率,需要在查找表中的元素之 间人为地附加某种确定的关系,换句话说,用另外 种结构来表示查找表 静态查找表 动态查找树表 哈希表 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第5页 如何进行查找？ • 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织 规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之 间人为地 附加某种确定的关系，换句话说， 用另外 一种结构来表示查找表 – 静态查找表 – 动态查找树表 – 哈希表