LV010-顺序查找

一、顺序查找

1. 查找方法

静态查找表用顺序存储结构表示时，顺序查找的查找过程为：设给定值为 k ，在表 $L=(R_1,R_2,\dots \dots ,R_n)$ 中，从 $R_n$ 开始，查找 $key=k$ 的记录。

实现代码如下：

int sqsearch(seqlist r, keytype k)  
{   
    int i;
	r.data[0].key = k;  /* k 存入监视哨 */
	i = r.len;          /* 取表长 */
	while(r.data[i].key != k) 
        i--;  
	return (i);
}

在程序中初始化创建查找表时，由于是顺序存储，所以会将所有的数据元素存储在数组中，但是把 第一个位置 留给了用户用于查找的关键字，顺序表的一端添加用户用于搜索的关键字，称作 监视哨。

2. ASL

表中有 n 个数据元素，查找第一个元素时需要比较 n 次；查找最后一个元素时需要比较 1 次，所以有 $C_i=n–i+1$，假设这 n 个数的被查找到的概率是相同的，则有：

$$ASL=\sum _{i=1}^n\frac{1}{n}(n-i+1)=\frac{n+1}{2}$$

这个平均查找长度是在假设查找算法每次都成功的前提下得出的。而对于查找算法来说，查找成功和查找失败的概率是相同的，查找算法的平均查找长度应该为 查找成功时的平均查找长度加上查找失败时的平均查找长度。若每次都查找失败，那么比较的次数都是 n + 1 ，所以最终 ASL 为：

$$ASL=\frac{1}{2}\sum _{i=1}^n\frac{1}{n}(n-i+1)+\frac{1}{2}(n+1)=\frac{3}{4}(n+1)$$

【缺点】这样算下来，查找的效率是很低的，查找某记录几乎要扫描整个表，当表长 n 很大时，会令人无法忍受。