什么是搭建网站_北京住房建设网官网_yandx引擎入口_网上在哪里打广告最有效

1、*查找属于数据的运算

*在哪里找？查找表（是由同一类型的数据元素构成的集合）

*什么查找？根据给定的某个值，在查找表中确定一个其关键字（用来标识一个数据元素的某个数据项的值）等于给定值。

——主关键字：唯一标识。     ——次关键字：识别若干记录

*查找成功：结果给出整个记录的信息，或者该记录的位置
查找失败：结果给出空记录或者空指针。

*查找的分类：静态查找表（仅查询）、动态查找表（插入、删除）

*查找算法的评价指标：平均查找长度ASL

*查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的

提高效率的一个方法：在集合中的数据元素之间人为加上某种确定的约束关系

线性表的查找

2、顺序查找

（1）适用条件：顺序表或线形链表表示的静态查找表、表内元素之间无序

（2）数据元素的类型定义

typedef struct{KeyType key;  //关键字域...           //其他域
}

顺序表结构类型定义 

typedef struct{ElemType *R;   //表基址int length;    //表长
}SSTable;
SSTable ST;      //定义顺序表ST

 （3）在顺序表中查找，从最后一个元素开始比较：

int Search_Seq(SSTable ST,KeyType key){//若成功返回其位置信息，否则返回0for(I=ST.length;i>=1;--i)if(ST.R[I].key==key) return I;return 0;
}

or

int Search_Seq(SSTable ST,KeyType key){for(I=ST.length;ST.[R].key!=key&&I>0;--i);if(I>0) return I;else return 0;
}

*针对每执行一次循环都要进行两次比较，可以进行改进：

把待查的关键字key存入表头（哨兵、监视岗），可免去查找过程中每一步都要检测是否已经查找完毕，加快速度。

int Search_Seq(SSTable ST,KeyType key){ST.R[0].key=key;for(I=ST.length;ST.R[I].key!=key;--i);return I;
}

*当ST.length较大时，此改进能使进行一次查找所需的平均时间几乎减少一半。

*比较次数与key位置有关：查找第i个元素，需要比较n-i+1次；查找失败比较n+1次；

*时间复杂度为O(n);设表中各记录查找概率相等，ASL（n)=(n+1)/2;

空间复杂度：一个辅助空间——O(1)

*

*