顺序表查找类SqListSearchclass1/顺序表查找类publicclass SqListSearchclass//表示最多元素个数final int MAxN=100;//R[0..n-1]表示查找表RecType[] R;int n;//实际元素个数publicvoidCreateR（int[la）//由关键字序列a构造顺序表RR=new RecType[MAXN];for（int i=o;i<a.length;i++)R[i]=new RecType(a[i]);n=a.length;//输出顺序表public void Disp()for （int i=o;i<n;i++)System.out.print(R[i].key+"");System.out.println();各种顺序表查找算法，后面讨论11/64
顺序表查找类SqListSearchClass public class SqListSearchClass //顺序表查找类 { final int MAXN=100; //表示最多元素个数 RecType[] R; //R[0.n-1]表示查找表 int n; //实际元素个数 public void CreateR(int[] a) //由关键字序列a构造顺序表R { R=new RecType[MAXN]; for (int i=0;i<a.length;i++) R[i]=new RecType(a[i]); n=a.length; } public void Disp() //输出顺序表 { for (int i=0;i<n;i++) System.out.print(R[i].key+" "); System.out.println(); } //各种顺序表查找算法，后面讨论 } 11/64
顺序查找9.2.11.顺序查找算法基本思路从顺序表的一端开始依次遍历，将遍历的元素关键字和给定值相比较，若两者相等，则查找成功，返回该元素的序号。若遍历结束后，仍未找到关键字等于的元素，则查找失败，返回-1。默认从顺序表的前端开始遍历。12/64
1. 顺序查找算法 从顺序表的一端开始依次遍历，将遍历的元素关键字和给定值k相比较， 若两者相等，则查找成功，返回该元素的序号。 若遍历结束后，仍未找到关键字等于k的元素，则查找失败，返回-1。 默认从顺序表的前端开始遍历。 12/64
1/顺序查找算法1public int SeqSearchi(int k)( int i=o;while (i<n && R[i].key!=k)从表头往后找i++;//未找到返回-1if (i>=n) return-1;//找到后返回其序号ielse return i;简单比较方法13/64
public int SeqSearch1(int k) //顺序查找算法1 { int i=0; while (i<n && R[i].key!=k) i++; //从表头往后找 if (i>=n) return -1; //未找到返回-1 else return i; //找到后返回其序号i } 简单比较方法 13/64
设置一个哨兵//顺序查找算法2public intSeqSearch2(intk)1/添加哨兵R[n]=newRecType(k);int i=o;while (R[i].key!=k)i++;从表头往后找if(i==n)return-1;//未找到返回-1//找到后返回其序号ielse return i;说明由于查找算法主要考虑关键字之间的比较，两个算法的效率差不多14/64
public int SeqSearch2(int k) //顺序查找算法2 { R[n]=new RecType(k); //添加哨兵 int i=0; while (R[i].key!=k) i++; //从表头往后找 if (i==n) return -1; //未找到返回-1 else return i; //找到后返回其序号i } 设置一个哨兵 说明 由于查找算法主要考虑关键字之间的比较，两个算法的效率差不多 14/64
2.顺序查找算法分析1）仅考虑查找成功的情况第1个元素即R[0].key=k，1次关键字比较。第2个元素即R[1].key=k，2次关键字比较。Ci=i+1以此类推，第n个元素即R[n-1].key=k，n次关键字比较共有n种查找成功的情况，在等概率时，P=1/n。n-1n-11n(n + 1)n+11(i + 1) =ASLXPiCi=成功22nni=0i=015/64
2. 顺序查找算法分析 1）仅考虑查找成功的情况 第1个元素即R[0].key=k，1次关键字比较。 第2个元素即R[1].key=k，2次关键字比较。 以此类推，第n个元素即R[n-1].key=k，n次关键字比较 ci=i+1 共有n种查找成功的情况，在等概率时，pi=1/n。 15/64