数据查找顺序、二分、索引、哈希查找.doc

《数据查找顺序、二分、索引、哈希查找.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、选题八数据查找一、基本概念查找表：是由同一类型的数据元素(或记录)构成的集合。查找：也称检索，即根据给定的某个值，在查找表中确定一个其关键字等于给定值的第一条记录(元素)或全部记录。若表中存在这样的记录，则查找成功，通常要求返回该记录存储位置；若不存在这样的记录，表明查找失败，返回特定值。例：在下表中查找学号为“98182”的学生信息学号  姓名性别籍贯出生年月198131刘激扬男北京1979.12 298164衣春生男青岛1979.07398165卢声凯男天津1981.02498182袁秋慧女 广州 1980.10598203林

2、德康男上海1980.05平均查找长度：在查找成功情况下平均比较次数，可用作判定一个查找算法的时间复杂度：其中：n：查找表长；Pi：查找第i个元素；Ci：查找第i个元素比较次数。二、顺序查找1．查找思路顺序表：指线性表的顺序存储结构。本章讨论中，设顺序表采用一维数组A表示，其元素类型为ElemType，它含有关键字域key和其它一些数据域，并设定A的大小为整型常量MaxSize，数组的元素个数为n，n应小于等于MaxSize。　typedefstruct{　　KeyTypekey;　　… 　}ElemType;顺序查找：又称线性查找

3、，它是一种最简单最基本查找方法。查找思路：从顺序表的一端开始，依次将每个元素关键字同给定值K进行比较，若某个元素关键字等于K，则查找成功，返回该元素所在下标，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败，反回特定值(常用-1表示)。基本算法intSeqsch(ElemTypeA[],intn,KeyTypeK){ //从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1for(inti=0;i

4、否则返回-1   returni;else   return-1; }如下图：0123452345643278在顺序表中查找56，比较3次。改进算法对该算法作一改进：在表的尾端A[n]设一岗哨，在查找前先将K赋给A[n],这样每循环一次不需比较下标是否越界，当比较到第n位置时，由于A[n].key==K成立，必退出循环。intSeqsch(ElemTypeA[],intn,KeyTypeK){//从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1A[n].key=k;//设置岗哨 for(inti=0;

5、;i++)if(A[i].key==K)break;if(i

6、的关键字与K比较。如下图所示：例如：查找23：查找96：查找58：1．二分查找的递归算法intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){//在A[low]～A[high]内查找K,low初值为0,high初值n-1if(low<=high){intmid=(low+high)/2;//求中间点下标if(K==A[mid].key)returnmid;//查找成功返回elseif(K

7、eturnBinsch(A,mid+1,hign,K);//右子表上查找}elsereturn-1;//查找失败反回-1}2．二分查找的非递归算法在下面的递增有序序列中查找关键字6。四、索引查找1．概念索引查找：又称分级查找，计算机中为索引查找建立一张主表和各级索引表。索引存储的基本思想是：首先把一个线性表(主表)按一定的函数关系划分成若干逻辑上的子表，为每个子表分别建立一个索引项，由所有这些索引项构成主表的一个索引表，然后可采用顺序或链接方式存储索引表和子表。职工号姓名单位职称工资JS001王大明计算机教授680JS002吴进计

8、算机讲师440JS003邢怀学计算机讲师460DZ001赵利电子助教380DZ002刘平电子讲师480DZ003张卫电子副教授600JJ001安晓军机械讲师450JJ002赵京华机械讲师440HG001孙亮化工教授720HG002陆新化工副教授58