顺序表的查找-顺序查找

2021/4/12 19:00:40

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

查找(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),只是时间复杂性函数的常系数变小了。



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


扫一扫关注最新编程教程