Java数据结构之查找

发布于 2020-11-22|标签java
复制链接
本文主要介绍了Java数据结构中查找的相关知识。具有很好的参考价值。下面跟着小妖一起来看下吧
前言:查找是开发中用的非常多的一项,比如mysql中的查找,下面主要简单介绍一下查找。1:线性表查找线性表查找主要分为顺序查找和链式查找,顺序表查找都是从一端到另一端进行遍历。比如下面代码 ```java public int indexOf(T x){ if (x!=null){ for (int i=0;i第二种是链式查找也非常简单 ```java public T search(T key) { if (key==null){ return null; } Node 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在前面。 ```java public static int binarySearch(Comparable[] values,int begin,int end,T key) { if (key != null) { while (begin 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 key) { end = mid - 1; } } return -1; } ``` 3:分块索引查找我们都知道查字典,首先要查询是字的拼音,然后定位到字页数的一个位置,比如查找张这个字,我们先查询z,然后看哪些页是z,然后在这一块进行查找。ok我们做个简单的例子现在我们已知一个数组里面存放的是Java的关键字,那么我们给出一个关键字来判断是否在这个数组中。首先我们看下关键字的数组 ```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个字母存起来,然后记录每个字母的位置。 ```java private static class IndexItem implements Comparable{ String frist; int start; public IndexItem(String frist,int start){ this.frist=frist; this.start=start; } ``` 其中frist是字母,二start是字母的索引,比如abstract是a0,那么assert就是a1了以此类推 ```java 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 我们创建一个静态块,在类被加载的时候运行。最后我们利用2次2分查找第一找到索引,然后通过索引匹配到值 ```java 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。 ```java public class HashSet { private SingleLinkedList[] table; public HashSet(int size) { this.table = new SingleLinkedList[Math.abs(size)]; for (int i = 0; i ();//制造单链表 } } 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); } } ``` 原文地址: http://www.cnblogs.com/LipeiNet/p/6511634.html
冀ICP备17029012号-4 | 版权所有©鲍亚龙 |免责声明  | GIF图库  | NUXT版