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