数据结构与算法：Java版-顺序查找平均查找长度

可以对顺序表或链表作为数据存储结构的线性表进行顺序查找，它对记录在表中存放的先后次序没有任何要求。

顺序查找算法描述：从表的一端开始，依次将每个元素的关键字与给定的值进行比较，若有相等者，则查找成功；否则继续比较，直到比较完所有的元素，仍未有相等者，则查找不成功。

1.顺序表上进行顺序查找

设顺序表存储在数组SSTable（Sequence Search Table）中，从表的第一个元素SSTable[0]开始，依次对数组中的元素SSTable[i]（i∈[0，n-1]）和给定值value进行比较，若当前记录的关键字与value相等，则查找成功，返回记录在表中的位置序号；若扫描结束仍未找到关键字等于value的记录，则查找不成功，返回-1。

注：其实在顺序表类SeqList（第2章介绍的）中indexOf（T key）已经将该操作实现了，只不过indexOf返回的是查找到的元素。(www.xing528.com)

如果每个记录的查找概率相等，则ip=1/n；ci表示如果第i个记录的关键字和给定值相等，要找到这个记录需和给定值进行比较的次数。显然，ci取决于所查记录在表中的位置，即ci=i。这样，在等概率情况下，顺序表查找成功的平均查找长度为

在上述查找中若出现不成功的情况，一定是将整个表的记录都比较以后才可确定，所以顺序表上顺序查找不成功的查找长度为n，即

2.单链表上进行顺序查找

从表的表头开始，依次对链表中的元素和给定值value进行比较，若当前记录的关键字与value相等，则查找成功，返回该结点指针；若扫描结束仍未找到关键字等于value的记录，则查找不成功，返回null。查找算法程序类似上面顺序表的顺序查找程序，仅是循环的次数换为对链表的循环即可。同样，在第2章中介绍的LinkedList链表中，查找操作是indexOf（T key）方法，它会返回第一次出现该元素的索引，如果没有则返回-1。需要用到的时候直接调用即可。