Java数据结构之查找

网友投稿 223 2023-06-03


Java数据结构之查找

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

1:线性表查找

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

public int indexOf(T x){

if (x!=null){

for (int i=0;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 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在前面。

pvPyszZAPublic static int binarySearch(Comparable[] 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{

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) {http://

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 {

private SingleLinkedList[] table;

public HashSet(int size) {

this.table = new SingleLinkedList[Math.abs(size)];

for (int i = 0; i < table.length; i++) {

table[i] = new SingleLinkedList();//制造单链表

}

}

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

}

}

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 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在前面。

pvPyszZAPublic static int binarySearch(Comparable[] 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{

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) {http://

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 {

private SingleLinkedList[] table;

public HashSet(int size) {

this.table = new SingleLinkedList[Math.abs(size)];

for (int i = 0; i < table.length; i++) {

table[i] = new SingleLinkedList();//制造单链表

}

}

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

}

}


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:基于Bootstrap框架实现图片切换
下一篇:BootStrap注意事项小结(五)表单
相关文章

 发表评论

暂时没有评论,来抢沙发吧~