基本查找算法---顺序表查找

196 阅读 0 评论 130 点赞

我是靠谱客的博主乐观薯片，这篇文章主要介绍基本查找算法---顺序表查找，现在分享给大家，希望可以做个参考。

查找概论

查找表是由同一类型的数据元素(或记录)构成的集合。
关键字是数据元素中某个数据项的值，又称为键值，用它来标示一个数据元素。也可以标示一个记录的某个数据项(字段)的值，称之为关键码。

若此关键字课可以唯一的标示一个记录，那么此关键字为主关键字。主关键字所在的数据项称为主关键码。
对于那些可以识多个数据元素(或记录)的关键字，我们称之为此次关键字。次关键字可以理解为是不以唯一标示一个数据元素的关键字，它对应的数据项就是次关键码

按照查找表操作方式可以分为：静态查找表和动态查找表
静态查找表：只做查找操作的查找表
主要的操作：

查询某个”特定的“数据元素是否在查找表中。
检索某个”特定的“数据元素和各种属性。
动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
动态查找表的操作：
查找时插入数据元素
查找时删除数据元素

为了提高查找的效率，专门为查找操作设置数据结构，这种面向查找操作的数据结构成为查找结构

顺序表查找

又叫做线性查找，是查找算法中最基本的查找，它的过程是：从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有所差的记录，查找不成功。
算法实现如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	/**
* 顺序表查找
* @param a
* @param n
* @param key
* @return
*/
public int Sequential_Search(Object[] a, int n, Object key) {
for (int i = 0; i < n; i++) {
if(a[i] == key) {
return i;
}
}
return 0;
}

顺询表查找优化：
设置哨兵

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	/**
* 顺序表查找的优化
* 设置哨兵
* 注意数组中元素值下标从1开始
* @param a
* @param n
* @param key
* @return
*/
public int Sequential_Search2(Object[] a, int n, Object key) {
int i = n;
a[0] = key;
i = n;
while(a[i] != key) {
i--;
}
return i;
}