概述
- 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：查找成功和查找失败。
- 查找表（Search Table)
是由同一类型的数据元素（或记录）构成的集合。
- 静态查找表
- 查询某个“特定的”数据元素是否在查找表中。
- 检索某个“特定的”数据元素和各种属性。
- 关键字
是数据元素中某项数据的值。 若此关键字可以唯一地标识一个记录， 则称此关键字为主关键字(Primary Key). 若此关键字可以识别多个数据元素（或记录）的关键字， 则称此关键字为次关键字(Secondary Key).
- 平均查找长度
- 顺序查找
- 分块查找（索引顺序查找） 吸收了顺序查找和折半查找各自的有点，既有动态结构又适于快速查找。
索引顺序表 = 索引 + 顺序表
基本思想：将查找表分为若干个子快。块内元素可以无序，但块内是有序的。
查找过程：
- 在索引表中待查记录所在的块
- 在快内顺序查找
查找结构（查找表）：用于查找的数据集合称为查找结构（查找表），它可以是一个链表，也可以是一个数组或其他数据类型。对于查找表经常进行的操作一般有四种：
- 查询某个特定的数据元素是否在查找表中；
- 检索满足条件的某个特定的数据元素的各种属性；
- 在查找表中插入一个数据元素；
- 从查找表中删除某个数据元素
静态查找表(Static Search Table)又称作线性查找， 是最基本的查找技术。 它的查找过程是：从表中第一个（或最后一个）记录开始， 逐个进行记录的关键字和给定值比较，某个记录的关键字和给定值相等，则查找成功， 找到所查的记录； 如果直到最后一个（或第一个）记录， 其关键字和给定值比较不等时，则表中没有所查记录， 查找不成功。
只涉及1、2的操作，则无须动态地修改查找表则成为静态查找表。
适合静态查找的方法有：
- 顺序查找
- 折半查找
- 散列查找
动态查找(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素， 或者从查找表中删除已经存在的某个数据元素。
主要操作：
- 查找时插入数据元素
- 查找时删除数据元素
用途：
- 二叉排序树的查找
- 散列查找
顺序表查找算法：
int Sequential_Search(int *a, int n, int key)
{
int i;
for(i = 1; i <= n; ++i)
{
if ( a[i] == key)
return i;
}
}
优化后：
int Sequential_Search2(int *a, int n, int key)
{
int i;
a[0] = key
i = n;
while(a[i] != key)
{
i--;
}
return i;
}
时间复杂度o(n)
最后
以上就是勤奋萝莉为你收集整理的查找的全部内容，希望文章能够帮你解决查找所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复