java中查找算法
程序员文章站
2024-03-01 13:17:22
...
1.顺序查找(无序链表)
package chazao;
import javax.xml.soap.Node;
//顺序查找(无序链表)
public class Shunxu {
private Node first;
private Node last;
private class Node{
int key;
int val;
Node next;
public Node(int key, int val, Node next){
this.key=key;
this.val=val;
this.next=next;
}
}
//查找给定的键值 返回相关联的值
public int get(int key){
for(Node x=first;x!=null;x=x.next){
if(key==x.key){
return x.val;
}
}
return -1;
}
//查找给定的键值 找到则更新值 否则在表中新建节点
public void put(int key,int val){
for(Node x=first;x!=null;x=x.next){
if(key==x.key){
x.val=val;
return ;
}
}
first=new Node(key,val,first);
}
//链表长度
public int size(){
int num=0;
for(Node x=first;x!=null;x=x.next){
num++;
}
return num;
}
//删除指定节点
public void del(int key){
for(Node x=first;x!=null;x=x.next){
if(key==x.next.key){
x.next=x.next.next;
}
}
}
}
2 二分查找(基于有序数组的实现)
package chazao;
public class ErFen {
public static int sort(int[] a,int key,int low,int high){
if(low<=high){
int mid=(low+high)/2;
if(a[mid]==key){
return mid+1;
}
else if(a[mid]>key){
return sort(a,key,low,mid-1);
}
else{
return sort(a,key,high,mid+1);
}
}
return -1;
}
public static void main(String[] args){
int[] a={1,3,4,6,8,9};
System.out.println( sort(a,3,0,5));
}
}
3.二叉树
package chazao.shu;
public class ClassTree {
Node root;
private class Node {
int key;
int value;
Node left;
Node right;
public Node(int key,int value){
this.key=key;
this.value=value;
}
}
//插入
public Node insert(int key,int value,Node root){
if(root==null){
return new Node(key,value);
}
if(value<root.value){
root.left=insert(key,value,root.left);
}
else{
root.right=insert(key,value,root.right);
}
return root;
}
//查询
public int cha(int value,Node root){
if(root==null){
return -1;
}
else if(value==root.value){
return root.key;
}
else if(value<root.value){
return cha(value,root.left);
}
else{
return cha(value,root.right);
}
}
//打印
public void printTree(Node t)
{
if(t!=null)
{
printTree(t.left);
System.out.print(t.value+" ");
printTree(t.right);
}
}
//查找集合中最小值
public Node minFin(Node root){
if(root==null){
return null;
}else if(root.left==null){
return root;
}else{
return minFin(root.left);
}
}
//查找集合中最大值
public Node maxFin(Node root){
if(root==null){
return null;
}
else if(root.right==null){
return root;
}
else{
return minFin(root.right);
}
}
//删除节点
public Node remove(int value,Node root){
if(root==null){
return null;
}
if(value<root.value){
root.left=remove(value,root.left);
}else if(value>root.value){
root.right=remove(value,root.right);
}else if(root.left!=null&&root.right!=null){
//如果被删除节点有两个儿子
//1.当前节点值被其右子树的最小值代替
root.value=minFin(root.right).value;
//将右子树的最小值删除
root.right=remove(root.value,root.right);
}else{
//如果被删除节点是一个叶子
if(root.left!=null){
root=root.left;
}else{
root=root.right;
}
}
return root;
}
public void Insert(int key,int value){
root=insert(key,value,root);
}
public void PrintTree()
{
printTree(root);
}
public int Min(){
return minFin(root).value;
}
public int Max(){
return maxFin(root).value;
}
public int Cha(int value){
return cha(value,root);
}
public void Remove(int value){
remove(value,root);
}
public static void main(String args[]){
ClassTree classTree=new ClassTree();
classTree.Insert(1,7);
classTree.Insert(2,6);
classTree.Insert(3,9);
classTree.Insert(4,4);
classTree.Insert(5,8);
classTree.Insert(6,10);
classTree.PrintTree();
System.out.println("查询:"+classTree.Cha(3));
System.out.println(classTree.Min());
System.out.println(classTree.Max());
classTree.Remove(7);
classTree.PrintTree();
}
}