6.3 顺序查找法★2◎3

6.3 顺序查找法★2◎3

6.3 顺序查找法★2◎3

　　顺序查找法又称线性查找法，是最基本的查找方法之一。其查找方法为：从表的一端开始，向另一端逐个按给定的值（key）与关键码进行比较。若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与key相同的关键码，则查找失败，给出失败信息。
　　【顺序查找算法】

　　

　　【算法分析】
　　对于n个数据元素的表，给定值key与表中第i个元素关键码相等，即定位第i个记录时，需进行n-i+1次关键码比较，即则查找成功时，顺序查找的平均查找长度为：

　　设每个数据元素的查找概率相等，即，则等概率情况下有：

　　查找不成功时，关键码的比较次数是n+1次，顺序查找的算法复杂度为O(n)。
　　许多情况下，查找表中数据元素的查找概率是不相等的。为了提高查找效率，需要依据查找概率越高，比较次数越少；查找概率越低，比较次数就较多的原则来存储数据元素。
　　顺序查找的缺点是当n很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求。顺序查找适用于查找顺序存储或链式存储的线性表。
 

6.3 顺序查找法★2◎3