2.2.2 顺序表中基本操作的实现

　二、元素定位操作

　　在顺序表中"查询"是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。动画
　		  



　
　		  
  算法 算法 2.5
　　int LocateElem(SqList L, ElemType e,
　　　　　　　　　　void (*compare)(ElemType, ElemType))
　{
　　// 在顺序表L中查找第1个值与 e 满足判定条件compare( )的元素，
　　// 若找到，则返回其在 L 中的位序，否则返回0。
　　i = 1;　　　　　　　　　// i 的初值为第1元素的位序
　　p = L.elem; 　　　　　　// p 的初值为第1元素的存储位置
　　while (i <= L.length && !(*compare)(*p++,e))
　　　++i;　 　　　　　　　// 依次进行判定
　　if (i <= L.length) return i;
　　　　　　　　　　　　　// 找到满足判定条件的数据元素为第 i 个元素
　　else return 0;　　　　// 该线性表中不存在满足判定的数据元素
　} // LocateElem

　　此算法的时间复杂度为：O ( ListLength(L)) 		 


如果你对这里的分析有疑问的话，请查看1.3.3节的有关叙述。：
　　算法中的基本操作是"判定"，它出现在 while 循环中，而函数 compare() 的时间复杂度显然是个常量。因此执行判定的次数取决于元素在线性表中的　"位序"，至多和表长相同。