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);
}
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！