Java数据结构之查找
前言:查找是开发中用的非常多的一项,比如mysql中的查找,下面主要简单介绍一下查找。
1:线性表查找
线性表查找主要分为顺序查找和链式查找,顺序表查找都是从一端到另一端进行遍历。比如下面代码
publicintindexOf(Tx){ if(x!=null){ for(inti=0;i第二种是链式查找也非常简单
publicTsearch(Tkey){ if(key==null){ returnnull; } Nodep=this.head.next; while(p!=null){ if(p.data.equals(key)){ returnp.data; } p=p.next; } returnnull; } 2:基于有序顺序表的二分查找
这个用的比较多,因为查询效率比较高,但是有限制条件,1是顺序存储,2必须有序,所以每次只需要和中间值进行比对,如果大于中间值,说明在key值在后面,如果小于中间值,说明key在前面。
publicstaticintbinarySearch(Comparable []values,intbegin,intend,Tkey){ if(key!=null){ while(begin<=end){ intmid=(begin+end)/2; if(values[mid].compareTo(key)==0){ returnmid; } if(values[mid].compareTo(key)<0){ begin=mid+1; } if(values[mid].compareTo(key)>0){ end=mid-1; } } } return-1; } publicstaticintbinarySearch(int[]arrays,intkey){ if(arrays==null||arrays.length==0){ return-1; } intstart=0,end=arrays.length-1; while(start<=end){ intmid=(start+end)/2; if(arrays[mid]==key){ returnmid; } if(arrays[mid] key){ end=mid-1; } } return-1; } 3:分块索引查找
我们都知道查字典,首先要查询是字的拼音,然后定位到字页数的一个位置,比如查找张这个字,我们先查询z,然后看哪些页是z,然后在这一块进行查找。ok我们做个简单的例子
现在我们已知一个数组里面存放的是Java的关键字,那么我们给出一个关键字来判断是否在这个数组中。首先我们看下关键字的数组
privatestaticString[]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个字母存起来,然后记录每个字母的位置。
privatestaticclassIndexItemimplementsComparable{ Stringfrist; intstart; publicIndexItem(Stringfrist,intstart){ this.frist=frist; this.start=start; } 其中frist是字母,二start是字母的索引,比如abstract是a0,那么assert就是a1了以此类推
publicintcompareTo(IndexItemo){ returnthis.frist.compareTo(o.frist); } privatestaticIndexItem[]index;索引表 static{ index=newIndexItem[26]; inti=0,j=0,size=0; for(i=0;j我们创建一个静态块,在类被加载的时候运行。最后我们利用2次2分查找第一找到索引,然后通过索引匹配到值
publicstaticbooleanisKeyWord(Stringstr){ IndexItemindexItem=newIndexItem(str.substring(0,1),-1); intpos=BSArry.binarySearch(index,indexItem); intbegin=index[pos].start; intend; if(pos==index.length-1){ end=keyWords.length-1; }else{ end=index[pos+1].start-1; } returnBSArry.binarySearch(keyWords,begin,end,str)>=0; }4:散列表的查找
散列的查找非常高效,但是我们必须要完成2项工作,一个是散列函数,另一个是解决冲突。下面看一下如何利用单链表简单的实现hash。
publicclassHashSet{ privateSingleLinkedList []table; publicHashSet(intsize){ this.table=newSingleLinkedList[Math.abs(size)]; for(inti=0;i ();//制造单链表 } } publicHashSet(){ this(97); } privateinthash(Tx){//利用hashCode解决 intkey=Math.abs(x.hashCode()); returnkey%table.length; } publicvoidinsert(Tx){ this.table[hash(x)].insert(0,x); } publicvoidremove(Tx){ this.table[hash(x)].remove(x); } publicTsearch(Tkey){ returntable[hash(key)].search(key); } } 以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持毛票票!