欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java数据结构之查找

程序员文章站 2024-03-05 14:22:03
前言:查找是开发中用的非常多的一项,比如mysql中的查找,下面主要简单介绍一下查找。 1:线性表查找 线性表查找主要分为顺序查找和链式查找,顺序表查找都是从一端到另一...

前言:查找是开发中用的非常多的一项,比如mysql中的查找,下面主要简单介绍一下查找。

1:线性表查找

线性表查找主要分为顺序查找和链式查找,顺序表查找都是从一端到另一端进行遍历。比如下面代码

public int indexof(t x){
  if (x!=null){
   for (int i=0;i<this.len;i++){
    if (this.element[i].equals(x)){
     return i;
    }
   }
  }
  return -1;
 }
 public t search(t key) {
  return indexof(key)==-1?null:(t) this.element[indexof(key)];
 }

第二种是链式查找也非常简单

public t search(t key) {
  if (key==null){
   return null;
  }
  node<t> p=this.head.next;
  while (p!=null){
   if (p.data.equals(key)){
    return p.data;
   }
   p=p.next;
  }
  return null;
 }

2:基于有序顺序表的二分查找

这个用的比较多,因为查询效率比较高,但是有限制条件,1是顺序存储,2必须有序,所以每次只需要和中间值进行比对,如果大于中间值,说明在key值在后面,如果小于中间值,说明key在前面。

public static<t> int binarysearch(comparable<t>[] values,int begin,int end,t key) {
  if (key != null) {
   while (begin <= end) {
    int mid = (begin + end) / 2;
    if (values[mid].compareto(key) == 0) {
     return mid;
    }
    if (values[mid].compareto(key) < 0) {
     begin = mid + 1;
    }
    if (values[mid].compareto(key) > 0) {
     end = mid - 1;
    }
   }
  }
  return -1;
 }
 public static int binarysearch(int[] arrays, int key) {
  if (arrays == null || arrays.length == 0) {
   return -1;
  }
  int start=0,end=arrays.length-1;
  while (start <=end) {
   int mid = (start + end) / 2;
   if (arrays[mid] == key) {
    return mid;
   }
   if (arrays[mid] < key) {
    start = mid + 1;
   }
   if (arrays[mid] > key) {
    end = mid - 1;
   }
  }
  return -1;
 }

3:分块索引查找

我们都知道查字典,首先要查询是字的拼音,然后定位到字页数的一个位置,比如查找张这个字,我们先查询z,然后看哪些页是z,然后在这一块进行查找。ok我们做个简单的例子

现在我们已知一个数组里面存放的是java的关键字,那么我们给出一个关键字来判断是否在这个数组中。首先我们看下关键字的数组

 private static string[] keywords={"abstract","assert","boolean","break","byte","case",
   "catch","char","continue","default","do","double","else","extend","false","final",
 "finally","float","for","if","implements","import","instaceof","in","interface",
 "long","native","new","null","package","private","protectd","public","return","short",
 "static","super","switch","synchronized","this","throw","transient","true","try","void","volatile","while"};

然后我们思考一下建立索引,因为英文单词是26个字母组成,那么我们效仿字典,把26个字母存起来,然后记录每个字母的位置。

private static class indexitem implements comparable<indexitem>{
  string frist;
  int start;
  public indexitem(string frist,int start){
   this.frist=frist;
   this.start=start;
  }

其中frist是字母,二start是字母的索引,比如abstract是a0,那么assert就是a1了以此类推

public int compareto(indexitem o) {
   return this.frist.compareto(o.frist);
  }
private static indexitem[] index;索引表
  static {
   index = new indexitem[26];
   int i = 0, j = 0, size = 0;
   for (i = 0; j < keywords.length && i < index.length; i++) {
    char ch = keywords[j].charat(0);
    indexitem item = new indexitem(ch + "", j);
    if (item != null) {
     index[i] = item;
     size++;
    }
    j++;
    while (j < keywords.length && keywords[j].charat(0) == ch) {
     j++;
    }
   }
   int oldcount = index.length;利用trimtosize方法对数组进行压缩
   if (size < oldcount) {
    indexitem[] items = index;
    index = new indexitem[size];
    for (int m = 0; m < size; m++) {
     index[m] = items[m];
    }
   }
  }

我们创建一个静态块,在类被加载的时候运行。最后我们利用2次2分查找第一找到索引,然后通过索引匹配到值

public static boolean iskeyword(string str){
   indexitem indexitem=new indexitem(str.substring(0,1),-1);
   int pos=bsarry.binarysearch(index,indexitem);
   int begin=index[pos].start;
   int end;
   if (pos==index.length-1){
    end=keywords.length-1;
   }else {
     end=index[pos+1].start-1;
   }
   return bsarry.binarysearch(keywords,begin,end,str)>=0;
  }

4:散列表的查找

散列的查找非常高效,但是我们必须要完成2项工作,一个是散列函数,另一个是解决冲突。下面看一下如何利用单链表简单的实现hash。

public class hashset<t> {
 private singlelinkedlist<t>[] table;
 public hashset(int size) {
  this.table = new singlelinkedlist[math.abs(size)];
  for (int i = 0; i < table.length; i++) {
   table[i] = new singlelinkedlist<t>();//制造单链表
  }
 }
 public hashset() {
  this(97);
 }
 private int hash(t x) {//利用hashcode解决
  int key = math.abs(x.hashcode());
  return key % table.length;
 }
 public void insert(t x) {
  this.table[hash(x)].insert(0, x);
 }
 public void remove(t x) {
  this.table[hash(x)].remove(x);
 }
 public t search(t key) {
  return table[hash(key)].search(key);
 }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!