Java數(shù)據(jù)結(jié)構(gòu)之查找

更新時(shí)間：2017年03月10日 14:22:34 作者：朝向遠(yuǎn)方

本文主要介紹了Java數(shù)據(jù)結(jié)構(gòu)中查找的相關(guān)知識(shí)。具有很好的參考價(jià)值。下面跟著小編一起來看下吧

前言：查找是開發(fā)中用的非常多的一項(xiàng)，比如mysql中的查找，下面主要簡單介紹一下查找。

1：線性表查找

線性表查找主要分為順序查找和鏈?zhǔn)讲檎?，順序表查找都是從一端到另一端進(jìn)行遍歷。比如下面代碼

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)];
 }

第二種是鏈?zhǔn)讲檎乙卜浅：唵?/p>

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：基于有序順序表的二分查找

這個(gè)用的比較多，因?yàn)椴樵冃时容^高，但是有限制條件，1是順序存儲(chǔ)，2必須有序，所以每次只需要和中間值進(jìn)行比對(duì)，如果大于中間值，說明在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：分塊索引查找

我們都知道查字典，首先要查詢是字的拼音，然后定位到字頁數(shù)的一個(gè)位置，比如查找張這個(gè)字，我們先查詢z，然后看哪些頁是z，然后在這一塊進(jìn)行查找。ok我們做個(gè)簡單的例子

現(xiàn)在我們已知一個(gè)數(shù)組里面存放的是Java的關(guān)鍵字，那么我們給出一個(gè)關(guān)鍵字來判斷是否在這個(gè)數(shù)組中。首先我們看下關(guān)鍵字的數(shù)組

 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"};

然后我們思考一下建立索引，因?yàn)橛⑽膯卧~是26個(gè)字母組成，那么我們效仿字典，把26個(gè)字母存起來，然后記錄每個(gè)字母的位置。

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方法對(duì)數(shù)組進(jìn)行壓縮
   if (size < oldCount) {
    IndexItem[] items = index;
    index = new IndexItem[size];
    for (int m = 0; m < size; m++) {
     index[m] = items[m];
    }
   }
  }

我們創(chuàng)建一個(gè)靜態(tài)塊,在類被加載的時(shí)候運(yùn)行。最后我們利用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項(xiàng)工作，一個(gè)是散列函數(shù)，另一個(gè)是解決沖突。下面看一下如何利用單鏈表簡單的實(shí)現(xiàn)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);
 }
}

以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持腳本之家！

您可能感興趣的文章: