顺序表的查找-顺序查找

本文主要是介绍顺序表的查找-顺序查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

查找（search）：给定结点的关键字值 x ，查找值等于 x 的结点的存储地址。

按关键字 x 查：

① 成功，表中有 x ，返回 x 的存储地址；

② 不成功，x 不在表中，返回无效地址。

顺序查找就是以表的一端为起点，向另一个端点逐个元素查看，

可以是从 表头 → 表尾的顺序，也可以是从 表尾 → 表头的顺序

顺序查找方法，既适用于无序表，又适用于有序表。

顺序查找属于 “穷尽式搜索法”：通常以 查找长度，度量查找算法的时间复杂性。

查找长度：即查找过程中测试的节点数目。

顺序查找的查找长度 = for 循环体的执行次数，最小为1，最多为n。

等概率下：平均查找长度 = （n + 1）/ 2

最坏情况和平均情况：T（n）= O（n）    效率最低的查找算法

我们观察一下上图那两个 for循环体，不难发现，每次执行都需要 判断两个条件：

① 测试是否循环到头；

② 测试是否找到元素 x。

因此我们不妨使用 “监督元” 技术，不仅简化了程序结构，也提高了查找速度。

 若从 表尾 → 表头 的顺序查找，监督元则在表头处，称为 “表头监督元”，如下图：

若从 表头 → 表尾 的顺序查找，监督元则在表头处，称为 “表尾监督元”，如下图：

带表头监督元的顺序查找算法：

int SQsearch（int a[]，int x，int n）{ // SQsearch 是函数名，仅此。

　　int i；

　　i = n；

　　a[0] = x；

　　while（a[i] != x）

　　　　i -- ；

　　return i；

}

算法思想：

① i = n；// 设置查找起点

② a[0] = x；// 放置监督元，因为在进入循环体之前，已经预先在 a[0] 放置了一个元素 x，所以 x 无论是否真的在表中，总能找到 x ，使第三句的循环中止。注意！！！a[1] 到 a[n] 存储的才是真正的表元素。

如果 x 真存在表中，必然在某个 i 大于 0 时找到 x，循环终止。

如果循环变量 i 的值变到 0 时循环才终止，那就说明 x 不在表中。

③ while（a[i] != x）

　　i --； // 从右向左查。

④ return i；// 判定查找结果。查找结果由变量 i 的值判定，

x 在表中，i ≠ 0

x 不在表中，i = 0

只牺牲一个存储单元，就能将查找效率提升一倍。这在表长 n 较大，查找频繁的情况下是很合算的，“空间换时间”。虽然查找速度提高一倍，但时间复杂性的阶不变，仍是O(n)，只是时间复杂性函数的常系数变小了。

这篇关于顺序表的查找-顺序查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！