《数据结构教学课件》第11章.pptx

1of151

第11章查找

主

要查找的基本概念

知静态查找表

识

点动态查找表

哈希表

2of151

查找概念

是指在数据集合中查询是否存在关键字等于某

个给定关键字的数据元素的过程。亦称作检索。

主关键字次关键字

能够惟一区分各通常不能惟一区分

个不同数据元素各个不同数据元素

查找成功

查找结果

查找不成功

3of151

11.1查找的基本概念

查找概念

○是指在数据集合中查询是否

存在关键字等于某个给定关

键字的数据元素的过程。亦

查找表

称作检索。

○以集合为逻辑结构、

○以查找为核心运算、

○包括其他运算的数据结构

4of151

查找分类查找表的存储结构是否发生变化

v静态查找:只查找，不改变数据元素集合内的数据

元素。

v动态查找:既查找，又改变（增减）集合内的数据

元素。

动态查找表

静态查找表

5of151

查找算法效率

平均查找长度：查找过程所需进行的关键字比较次数的平

均值,其数学定义为：

成功的平均

n查找长度

ASLpiCi

i1

查找的第i个数据查找的第i个数据元素所

元素出现的概率需的关键字比较次数

该指标是衡量查找算法效率的最主要标准,

6of151

查找数据元素

一个数据

张晓

00女89.

丽1986-11-01182.1

010林欢867.180.

女1987-11-01

2陈喜国63

00男177.

庆1985-10-0993.1数据类型是自定

030李栋78.1667.

男1985-09-21

4梁94义的结构类型

typedefstruct

{

intnum;

charnam