数据结构.第9章.查找.1.静态查找表.pptx

数据结构
Data Structures
张凯
计算机学院软件工程系
2011年3月12日
第9章查找
查找的基本概念
静态查找表
动态查找表
哈希表
查找的基本概念
§ 查找的基本概念
查找表:是由同一类型的具有相同可辨认特性的 数据元素(或记录)构成的集合。
对查找表经常进行的操作:
1. 查询某个“特定的”数据元素是否在查找表中;
2. 查询某个“特定的”数据元素的各种属性;
3. 在查找表中插入一个数据元素;
4. 删除查找表中的某个数据元素。
查找表的分类
§ 查找的基本概念
静态查找表
动态查找表:
仅作“查询”(检索)操作的查找表,
只查找,不改变数据元素集内的数据元素。
作“插入”和“删除”操作的查找表
既查找,又改变(增减)集合内的数据元素。
关键字
§ 查找的基本概念
在实际应用问题中,每个记录一般包含有多个数据域,查找是根据其中某一个指定的域进行的,这个作为查找依据的域称关键字(key)。
主关键字
可唯一标识一个记录的关键字。例:学号
次关键字
可识别若干记录的关键字。例:性别
关键字
§ 查找的基本概念
姓名
学号
性别
年龄
健康情况
王小林
790631
男
18
健康
陈红
790632
女
20
一般
刘建平
790633
男
21
健康
张立立
790634
男
17
健康
…
…
…
…
…
查找
§ 查找的基本概念
根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。
若表中存在这样的一个记录,则称查找是成功的,若表中不存在关键字等于给定值的记录,则称查找不成功。
静态查找如何进行查找
取决于查找表的结构,如字典,电话本
平均查找长度(Average Search Length)
§ 查找的基本概念
为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(ASL)。
对于含有n个记录的表,查找成功时的平均查找长度为
查找表中第i个
记录的概率,且
找表中关键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数
静态查找表
顺序表的查找
有序表的查找
索引顺序表的查找
§ 静态查找表
顺序表的查找
§ 静态查找表
顺序查找:从表的一端开始,逐个进行记录的关键 字和给定值的比较。
查找过程:
找64
5
37
19
21
13
56
64
92
88
80
75
0
1
2
3
4
5
6
7
8
9
10
11
64