顺序查找改进算法

11年前
   

    顺序查找,最简单的一种查找方法。其基本思想是:从线性表的一端开始,依次将每个记录的关键字与给定值进行比较。若某个记录的给定值等于给定值,则表示查找成功并返回记录序号;若将线性表中的记录查找完仍然没有找到关键字,则表示查找失败,返回一失败值。

    传统的顺序查找针对的线性表中的元素不允许存在元素相同的情况,并且其查找方式: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,查找成功

                情况2,查找失败