顺序查找改进算法

12年前

顺序查找，最简单的一种查找方法。其基本思想是：从线性表的一端开始，依次将每个记录的关键字与给定值进行比较。若某个记录的给定值等于给定值，则表示查找成功并返回记录序号；若将线性表中的记录查找完仍然没有找到关键字，则表示查找失败，返回一失败值。
传统的顺序查找针对的线性表中的元素不允许存在元素相同的情况，并且其查找方式：for(j = 0 ; j< source.length && source[j] != key; j++)中的这段代码： j< source.length && source[j] != key 每循环一次都要进行两次比较.如果线性表中的数据较多，则查找需要很长的时间，程序效率会显著降低。但是我们可以对以上两点进行改进。在线性表的末端为他增加一个空单元，用来保存查找的关键字。这样可以确保静态查找表中有一个与查找关键字相同的数据，就可以不再需要使用“j < source.length”进行判断了。针对如何判断查找失败，可以定义一个标记：flag。flag值不改变则代表查找失败。
针对的线性表中的元素不允许存在元素相同的情况，看代码。

public class SequentialSearch   {   /**    * 顺序查找基础算法    */   public void basicSeqSearcher(int [] source , int key)   {    int j;    for(j = 0 ; j< source.length && source[j] != key; j++)//循环查找关键字     ;    if(j < source.length) //查找成功    {     System.out.print("该元素为：" + source[j] + "；  所在位置：" + (j+1));    }    else  //查找失败     System.out.print("查找失败。不包含指定值：" + key);   }   /**    * 顺序查找改进算法    * @param source 数组列表    * @param key 查找的关键字    * @return    */   public void sequentialSearcher(int [] source , int key)   {    int flag = 0;//设定一个标记，用于表示数组列表中是否包括要查找的关键字Key    System.out.print("元数据：");    for(int i = 0 ; i < source.length ; i ++)    {     System.out.print(source[i]+",");    }    System.out.print("\n");        //数组替换    int [] newSource  = new int[(source.length + 1)];     for(int a = 0 ; a < source.length ; a ++)    {     newSource[a] = source[a];    }    newSource[source.length] = key;      int j;    for(j = 0 ; j < newSource.length ; j ++)    {     if(newSource[j] == key)     {      if(j != source.length)//因为数组最后一个元素是开始故意插入的，与Key相等，所以这里不输出      {       flag = 1;//如果包含key则flag标记为1       System.out.println("该元素为：" + newSource[j] + "；  所在位置：" + (j+1));      }     }    }    if(flag == 0)     System.out.println("查找失败。不包含指定值：" + key);   }      public static void main(String[] args)    {    int [] s = {69,65,90,3,27,6,4,4,92,6,28,88,66,6,55,54};    int key = 6;     SequentialSearch ss = new SequentialSearch();    ss.sequentialSearcher(s, key);    System.out.println("基础算法查找：");    ss.basicSeqSearcher(s, key);   }    }

输出如下：
情况1，查找成功