欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

}