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

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

2、在查找成功情况下平均比较次数，可用作判定一个查找算法的时间复杂度：nASLPi C ii1其中：n ：查找表长；Pi：查找第i 个元素；Ci：查找第i 个元素比较次数。随意编辑精品文档二、顺序查找1查找思路顺序表：指线性表的顺序存储结构。本章讨论中，设顺序表采用一维数组A 表示，其元素类型为ElemType ，它含有关键字域key 和其它一些数据域，并设定A 的大小为整型常量 MaxSize ，数组的元素个数为n ， n 应小于等于MaxSize 。typedef struct KeyType key;ElemType;顺序查找：又称线性查找，它是一种最简单最基本查找方法。查找思路：从顺序表的

3、一端开始，依次将每个元素关键字同给定值K 进行比较，若某个元素关键字等于K ，则查找成功，返回该元素所在下标，若直到所有元素都比较完毕，仍找不到关键字为K 的元素，则查找失败，反回特定值(常用 -1 表示 ) 。基本算法int Seqsch(ElemType A ,int n,KeyType K)/ 从顺序表A 的 n 个元素中顺序查找关键字为K 的元素，若成功返回其下标，否则返回 -1for(int i=0;i<n;i+)if(Ai.key=K)break;随意编辑精品文档if(i<n)/ 查找成功返回下标，否则返回-1return i;elsereturn -1;如下图：012

4、3452345643278在顺序表中查找56 ，比较 3 次。改进算法对该算法作一改进：在表的尾端An 设一岗哨 ，在查找前先将K 赋给 An, 这样每循环一次不需比较下标是否越界，当比较到第n 位置时， 由于 An.key=K成立，必退出循环。int Seqsch(ElemType A ,int n,KeyType K)/ 从顺序表 A 的 n 个元素中顺序查找关键字为K 的元素，若成功返回其下标，否则返回 -1An.key=k; /设置岗哨for(int i=0; ;i+)if(Ai.key=K)break;随意编辑精品文档if(i<n)return i;elsereturn -1;

5、在顺序表中查找56 ，设 A6=56为岗哨：0123456234564327856性能描述平均查找长度为：ASLn1 nPi Cii ( n 1) / 2i 1n i 1顺序查找时间复杂度为O(n) 。缺点：速度较慢，查找成功最多需比较n 次，平均查找长度约为表长一半。优点：算法简单，适应面广，对表结构无任何要求。三、二分查找二分查找又称折半查找。作为二分查找对象的表必须是顺序存储的有序表。查找过程：首先取整个有序表A0 An-1的中点元素Amid(mid=- 1)/2(n的关键字与 K 比较。如下图所示：随意编辑精品文档例如：查找 23：查找 96：查找 58：随意编辑精品文档1二分查找的递归算法int Binsch(ElemType A ,int low,int high,KeyType K)/ 在 Alow Ahigh内查找 K,low初值为 0,high初值 n-1if(low<=high)int mid=(low+high)/2; /求中间点下标if(K=Amid.key)return mid; /查找成功返回else if(K<Amid.key)return Binsch(A,low,mid-1,K); /左子表上查找elseretur