数据结构中的查找表.pdfVIP

数据结构（DataStructure）

数据结构（）

DataStructure

第9章查找表（SearchTable）

第9章查找表（SearchTable）

主讲：李耀国

第9章查找表

§查找的目的在于从一些数据中寻找出一个

特定的值。

关键字

图001高等数学樊映川S01……

书002理论力学罗远祥L01……

详

003高等数学华罗庚S01……

细

目004线性代数栾汝书S02……

录∶∶∶∶∶

查找代号为‘003’

的图书情况

第9章查找表

§查找的基本概念

§查找表(serachtable)是由同一类型数据元素（或

记录）构成的集合。

§对查找表的操作包括：

n（1）查询某个特定的数据元素是否在表中；

n（2）检索某个特定的数据元素的各个属性；

n（3）在查找表中插入一个数据元素；

n（4）从查找表中删除某个数据元素。

若只对查找表做前两种统称为“查找”

次类查找表为静态查找表(staticsearchtable)；

若在查找过程中同时插入不存在的数据元素，或者从

查找表中删除已存在的某个数据元素，则称此类查找

表为动态查找表(dynamicsearchtable)。

第9章查找表

§查找的基本概念

§关键字(key)是数据元素中某个数据项的值，用它可

以唯一地标识一个数据元素。

§查找(search)：根据给定的某个值，在查找表中确

定一个其关键字等于给定值的记录或数据元素。若表

中存在这样一个记录则称查找是成功的，查找结果为

整个记录（或指示该记录在查找表中的位置）；若表

中不存在这样一个记录则称查找是不成功的，此时查

找的结果为空（空记录或空指针）。

§本章所涉及的数据元素描述为：

typedefstruct{

KeyTypekey;//关键字项

……//其他数据项

}Elemtype;//数据元素

第9章查找表

§9.1静态查找表n9.3哈希表及其查找

§9.1.1顺序查找n9.3.1什么是哈希表

§9.1.2折半查找n9.3.2构造哈希函数的几

种方法

§9.1.3分块查找

n9.3.3处理冲突的方法和

§9.2动态查找表建表实例

§9.2.1二叉查找树n9.3.4哈希表的查找及其

+