数据结构 查找技术1--静态查找表.ppt

第九章
查找
1
本章的主要内容是:
查找的基本概念(难度系数*)
静态查找表(难度系数**)
动态查找表(难度系数****)
哈希表(难度系数***)
2
何谓查找表?
查找表是由同一类型的数据元素(或记录)构成的集合。
由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。
查找的基本概念
3
对查找表经常进行的操作:
1)查询某个“特定的”数据元素是否在查找表中;
2)检索某个“特定的”数据元素的各种属性;
3)在查找表中插入一个数据元素;
4)从查找表中删去某个数据元素。
4
不涉及插入和删除操作的查找。
涉及插入和删除操作的查找。
查找的基本概念
静态查找适用于:查找集合一经生成,便只对其进行查找,而不进行插入和删除操作,或经过一段时间的查找之后,集中地进行插入和删除等修改操作;
动态查找适用于:查找与插入和删除操作在同一个阶段进行,例如当查找成功时,要删除查找到的记录,当查找不成功时,要插入被查找的记录。
静态查找表
动态查找表
5
是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。
关键字
若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。
若此关键字能识别若干记录,则称
之谓“次关键字”。
6
50
女
李爽
0005
25
女
齐梅
0004
47
女
刘楠
0003
25
男
张亮
0002
38
男
王刚
0001
年龄
性别
姓名
职工号





工作时间
7
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)。
查找
若查找表中存在这样一个记录,则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在查找表中的位置;
否则称“查找不成功”。查找结果给出
“空记录”或“空指针”。
8
由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。
为了提高查找的效率, 需要在查找表中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表。
如何进行查找?
查找的方法取决于查找表的结构。
9
静态查找表
动态查找树表
哈希表
主要采用顺序查找技术和折半查找技术。
主要采用二叉排序树的查找技术。
静态查找和动态查找均适用,
主要采用散列技术。
10