文档介绍：FARJIGH!做江学际
查找
A
嵌入式学院
华请远见旗下品牌
“查找”( Searching)及“排序”( Sorting)是建立在数据结构上的两个重
要运算。査找(或检索)是在给定信息集上寻找特定信息元素的过程。据统计
一些计算机、特别是商用计算机,其CPU处理时间约25%~75%花费在査找
或排序上。所以对査找和排序问题的处理,有时直接影响到计算机的工作
效率
概述
待査找的数据单位(或数据元素)称为记录。记录由若干数据项(或
属性)组成,如学生记录
学号姓名性别年龄
其中,“学
姓名”、“性别
年龄”等都是记录的数
据项。若某个数据项的值能标识(或识别)一个或一组记录,称其为关键字
key)。若一个key能唯一标识一个记录,称此key为主key。如“学号”的值
给定就唯一对应一个学生,不可能多个学生的学号相同,故“学号”在学
生记录里可作为主key。若一个key能标识一组记录,称此key为次key。如
“年龄”值为20时,可能有若干同学的年龄为20岁,故“年龄”可作次key
下面主要讨论对主key的查找
嵌入式学院
1查找定义
清远见旗下品牌
设记录表L=(R1R2…Rn),其中R(sn)为记录,对给定的某个值k
在表L中确定key=k的记录的过程,称为查找。若表L中存在一个记录R
的key=k,记为Rkey=k,则查找成功,返回该记录在表L中的序号(或
R的地址),否则(查找失败)返回(或空地址Nu
査找方法很多,有顺序查找、折半査找、分块查找、树表查找及Hash
表査找等等。査找算法的优劣将影响到计算机的使用效率,应根据应用
场合选择相应的査找算法
评价一个算法优劣的量度,一是时间复杂度Tan),n为问题的体积,
此时为表长;二是空间复杂度Dωn);三是算法的结构等其他特性
对査找算法,主要分析其Tm)。查找过程是key的比较过程,时间主
要耗费在各记录的key与给定k值的比较上。比较次数越多,算法效率越
差(即T(n)量级越高),故用“比较次数”刻画算法的T(ωn)。另外,显
然不能以查找某个记录的时间来作为T(m),一般以“平均查找长度”来
衡量T(n)。
平均查找长度ASL( Average Search Length):对给定k,查找表L中
记录比较次数的期望值(或平均值),即:ASL=∑PC
P为查找R的概率。等概率情况下P=1/m;C为查找R时key的?较次数(或查找次数)
嵌入式学院
二、顺序表的查找
A
清远见旗下品牌
所谓顺序表( Sequential Table),是将表中记录(R1R2……R)按其序号
存储于一维数组空间,如图所示。其特点是相邻记录的物理位置也是相
邻的。
R
记录R的类型描述如下:
IR,
typedef struct
keytype key;∥记录key∥
∥录其他项∥
Rn
其中,类型 keytype是泛指,即 keytype可以是int、 float、char或其他的结
构类型等等。为讨论问题方便,一般取key为整型
顺序表类型描述如下
# define maxn1024;∥表最大长度∥
typedef struct{ Retype data[maxn];∥顺序表空间∥
tlen;∥当前表长,表空时len=O∥
Esql
若说明: sqlist r,则( r datal
, r )为记录表(R…Rn),
Rkey为 rdata[i]. key,r; data[O]称为监视哨,为算法设计方便所设
1顺序查找算法及分析
A
嵌入式学院
请青远见旗下品牌
顺序查找( Sequential Search)是最简单的一种查找方法
算法思路
设给定值为k,在表(R1R2…Rn)中,从R开始,查找key=k的记录。若
存在一个记录R1(1n)的key为k,则查找成功,返回记录序号i;否
则,查找失败,返回0。
算法描述
nt sqsearch( (sqlist r, keytype k)∥对表r顺序查找的算法/∥
r data[O]. key=k;/k存入监视哨∥
n;∥取表长
while(.datai]. keyl=k)
i-;∥顺序查找∥
return(1)
算法用了一点技巧:先将k存入监视哨,若对某个i(≠0)有
rdatai]. key=k,则查找成功,返回i;若in递减到1都无记录的key为k,
i再减1为0时,必有 r datal0key=k,说明查找失败,返回i=0。
顺序查找
A
嵌入式学院
请青远