14.查找概论与顺序查找，14查找概论顺序

14.查找概论与顺序查找，14查找概论顺序

一、查找概论 1.查找：即根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素(或纪录)。若表中不存在关键字等于给定值的纪录，则称查找不成功，此时查找的结果可给出一个"空"纪录或"空"指针。另外，查找表按照操作方式来分有两大种：静态查找表和动态查找表。 (1)查找表(Search table)：是由同一类型的数据元素(或纪录)构成的集合； (2)关键字(Key)：是数据元素中某个数据项的值，又称为键值，用它可以标志一个数据元素，也可以标志一个纪录的某个数据项(字段)，又称关键码; (3)主关键字：若此关键字可以唯一地标志一个纪录，则称此关键字为主关键字(Primary Key)，主关键字所在的数据项成为主关键码; (4)次关键字(Secondary Key)：对于那些可以识别多个数据元素(或纪录)的关键字，我们称为次关键字；
2.静态查找表(Static Search Table)：只作查找操作的查找表。 它的主要操作有： (1)查询某个"特定的"数据元素是否在查找表中; (2)检索某个"特定的"数据元素和各种属性。 3.动态查找(Dynamic Search Table)     在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。它的主要操作有： (1)查找时插入数据元素; (2)查找时删除元素数据元素; 注释：为了提供查找的效率，我们需要专门为查找操作设置数据结构，即改变数据元素之间的关系(表、树等结构)。
二、顺序表查找 1.定义：顺序查找又称线性查找，是最基本的查找技术，它的查找过程是：从表中第一个(或者最后一个)纪录开始，逐个进行纪录的关键字和给定值比较，若某个纪录的关键字和给定值相等，则查找成功，找到所查的纪录；如果直到最后一个(或第一个)纪录，其关键字和给定值比较都不等时，则表中没有所查的纪录，查找不成功。 2.顺序表查找算法 /*顺序查找：a为数组，n为要查找的数组个数，key为要查找的关键字*/ int  Sequential_Search(int *a,int n,int key) {     int i;     for(i=1;i<n;i++)     {             if(a[i]==key)                     return i;    //返回该关键字的纪录位置     } } 3.顺序表查找优化     由于一般的顺序查找算法每次循环时，都需要对i是否小于等于n作判断。从某些程序上来说，当总数据量很多的时候，该判断无疑降低了查找的效率。我们可以通过在尽头设置一个"哨兵"的方法，来解决每次i与n作出比较的问题来提高查找效率。优点：实现简单，小型数据查询效率较高。缺点：n很大时，查找效率很低。 /*有哨兵顺序查找*/ int Sequential_Search2(int *a,int n,int key) {     int i;     a[0]=key;        //设置a[0]为关键字值，我们称之为"哨兵"     i=n;                //循环从数组尾部开始     while(a[i]~=key)     {             i--;     } return i;            //返回0则说明查找失败 } 分析：此代码从尾部开始查找，如果在a[i]中有key则返回i值，查找成；否则一定在最终的a[0]处等于key，此时返回的是0，即说明a[1]~a[n]中没有关键字key，查找失败。 时间复杂度：最好情况为O(1)，最坏为O(n)；查找失败n+1次时间复杂度为O(n)；平均查找次数为(n+1)/2，即平均复杂度为O(n)。