数据结构及算法-查找.ppt

第7章查找技术
本章的主要内容是:
查找的基本概念
线性表的查找技术
树表的查找技术
散列表的查找技术

1查找的基本概念
查找:在具有相同类型的记录构成的集合中找出满足
给定条件的记录。
查找表:具有相同类型的记录构成的集合
职工号姓名性别年龄参加工作
000王刚男38199年4月
0002
张亮男
2003年7月
003刘楠女471979年9月
0004
齐梅女25200年7月
005李爽女501972年9月

1查找的基本概念
关键码:可以标识一个记录的某个数据项。
键值:关键码的值。
主关键码:可以唯一地标识一个记录的关键码
次关键码:不能唯一地标识一个记录的关键码。
职工号姓名性别年龄参加工作
000王刚男319年4月
002张亮男252007月
0003
刘楠女471979年9月
_04齐梅女2520年7月
005李爽女501972年9月

1查找的基本概念
数据结构里的查找主要通过给定值和查找表中记录的
关键码进行比较
査找的结果:若在査找集合中找到了与给定值相匹配
的记录,则称查找成功;否则,称查找失败。
职工号姓名性别年龄参加工作
0001
王刚男38190年4月
「002张亮男25200年7月
定值k00刘楠女471979年9月
0004
齐梅女
2003年7月
0005
5李爽女501972年9月

1查找的基本概念
静态査找:不涉及插入和删除操作的查找。
动态查找:涉及插入和删除操作的查找。
静态査找适用于:查找集合一经生成,便只对其进行
查找,而不进行插入和删除操作,或经过一段时间的
查找之后,集中地进行插入和删除等修改操作
动态查找适用于:查找与插入和删除操作在同一个阶
段进行,例如当查找成功时,要删除查找到的记录,
当查找不成功时,要插入被查找的记录

1查找的基本概念
查找结构:面向查找操作的数据结构,即查找基于的
数据结构。
集合中元素之间不存在明显的组织规律,不便查找。
线性表
集合口>{树表
散列表
查找结构〓→查找方法
72线性表的查找技术
查找技术的分类
噸序查找
线性森的查找
技术
折冬查找
(静志)
查找技术〈「树表的查我
二又排序树
故术
(动态)
平衡二叉树
散列轰的查找故术
72线性表的查找技术

静态查找特点不涉及插入和删除操作的查找主要采
用线性査找结构
顺序查找
折半查找
0123456789
r[10]
□o
152461235409855
72线性表的查找技术

基本思想:从线性表的一端向另一端逐个将关键码与
给定值进行比较,若相等,则查找成功,返回该记录
在表中的位置;若整个表检测完仍未找到与给定值相
等的关键码,则查找失败,给出失败信息。
例:查找k=35或k=22
23456789
r[10]
152461235409855
72线性表的查找技术
顺序查找(线性查找)
int SeqSearchl(int r[], int n, int k)
∥数组r[1]~rm存放查找集合
while(i>0 & r[il=k)
return 1;
0
23456789
**********
9855