山东理工大学：《数据结构》课程教学课件（数学）CH9 查找表

第九章查我表

第九章 查找表 1

第九章查找表 9.1基本概念 9.2静态查找表 9.3动态查找树表 9.4哈希表

9.2 静态查找表 9.3 动态查找树表 9.4 哈希表 9.1 基本概念 第九章 查找表 2

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

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

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

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

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

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

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

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

例如： 准考 各科成绩 证号 姓 名 语 外 化 生 分 治 文 学 理 179321 陈红 84 179322 陆华 179333 张平 788 453 9339 776 373 645 145321 张平 76 64 75 88 66 67 81 73

例如： 准考 证号 姓 名 各科成绩 总 政 分 治 语 文 外 语 数 学 物 理 化 学 生 物 . . . 179321 179322 179333 . . . 145321 . . . 陈红 陆华 张平 . . . . 张平 . . . 84 76 85 . . . 76 . . . 76 84 88 . . 64. . . . 74 65 73. . . 75 . . . 93 87 79 . . . 88 . . . 87 69 62 . . . 66 . . . 76 57 63 . . . 67 . . . 87 71 78 . . 81 . . . 63 54 55 . . 73 7

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

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

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

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

第九章查找表 9.1基本概念 √9.2静态查找表 9.3动态查找树表 9.4哈希表

9.2 静态查找表 9.3 动态查找树表 9.4 哈希表 9.1 基本概念 第九章 查找表 10