文档介绍：查找“查找”(Searching)及“排序”(Sorting)是建立在数据结构上的两个重要运算。查找(或检索)是在给定信息集上寻找特定信息元素的过程。据统计,一些计算机、特别是商用计算机,其CPU处理时间约25%~75%花费在查找或排序上。所以对查找和排序问题的处理,有时直接影响到计算机的工作效率。一、概述待查找的数据单位(或数据元素)称为记录。记录由若干数据项(或属性)组成,如学生记录: 其中,“学号”、“姓名”、“性别”、“年龄”等都是记录的数据项。若某个数据项的值能标识(或识别)一个或一组记录,称其为关键字(key)。若一个key能唯一标识一个记录,称此key为主key。如“学号”的值给定就唯一对应一个学生,不可能多个学生的学号相同,故“学号”在学生记录里可作为主key。若一个key能标识一组记录,称此key为次key。如“年龄”值为20时,可能有若干同学的年龄为20岁,故“年龄”可作次key。下面主要讨论对主key的查找。学号姓名性别年龄……=(R1R2……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(AverageSearchLength):对给定k,查找表L中记录比较次数的期望值(或平均值),即:Pi为查找Ri的概率。等概率情况下Pi=1/n;Ci为查找Ri时key的比较次数(或查找次数)。二、顺序表的查找所谓顺序表(SequentialTable),是将表中记录(R1R2……Rn)按其序号存储于一维数组空间,如图所示。其特点是相邻记录的物理位置也是相邻的。记录Ri的类型描述如下: typedefstruct {keytypekey;//记录key// ……//记录其他项// }Retype; 其中,类型keytype是泛指,即keytype可以是int、float、char或其他的结构类型等等。为讨论问题方便,一般取key为整型。顺序表类型描述如下: #definemaxn1024;//表最大长度// typedefstruct{Retypedata[maxn];//顺序表空间// intlen;//当前表长,表空时len=0// }sqlist;若说明:sqlistr,则([1],……,[])为记录表(R1……Rn),[i].key,[0]称为监视哨,为算法设计方便所设。R1R2……Rn1顺序查找算法及分析顺序查找(SequentialSearch)是最简单的一种查找方法。算法思路设给定值为k,在表(R1R2……Rn)中,从Rn开始,查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k,则查找成功,返回记录序号i;否则,查找失败,返回0。算法描述 intsqsearch(sqlistr,keytypek)//对表r顺序查找的算法// {inti; [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==1; [n-1].key=-1=2; ……[i].key=k,Ci=n-i+1; ……[1].key=k,C1=n 故ASL=O(n)。而查找失败时,查找次数等于n+l,同样为O(n)。对