查找【数据结构与算法java】

2025-03-27 10:12:02 阅读次数：8

查找

基于线性表的查找

顺序查找

package search1;

/**
 * @author CSDN@日星月云
 * @date 2022/10/31 09:58
 */
public class SeqSearch {
    public static void main(String[] args) {
        int[] nums={-1,1,2,3,4,5,0,9,8,7,6};//0号不存储有效数值
        int k=0;
        //顺序查找
        System.out.println(new SeqSearch().seqSearch(nums, k));
        //加“监视哨”的顺序查找
        System.out.println(new SeqSearch().seqSearchPlus(nums, k));

    }
    //顺序查找
    public int seqSearch(int[] nums,int k){
        int i=nums.length-1;
        while (i>=1&&nums[i]!=k){i--;}
        return i;
    }

    //加“监视哨”的顺序查找
    public int seqSearchPlus(int[] nums,int k){
        nums[0]=k;//监视哨
        int i=nums.length-1;
        while (nums[i]!=k){i--;}
        return i;
    }
    //最不频繁使用法（LFU）,计数法
    //最进最少使用法（LRU），移至前端法
    //转置方法，调换方法




}

折半查找

package search1;

/**
 * @author CSDN@日星月云
 * @date 2022/10/31 10:06
 */
public class BinSrch {
    public static void main(String[] args) {
        //折半查找必须有序
        int[] nums={-1,12,19,25,33,46,58,64,80};//0号不存储有效数值
        int k=80;
        //折半查找非递归实现
        System.out.println(new BinSrch().binSrchN(nums, k));
        //折半查找递归实现
        System.out.println(new BinSrch().binSrch(nums, k,1, nums.length-1));
    }
    public int binSrchN(int[] nums,int k){
        int low=1,high= nums.length-1,mid;
        while (low<=high){
            mid=(low+high)/2;
            if(k==nums[mid]) return mid;
            else if(k<nums[mid]) high=mid-1;
            else low=mid+1;
        }
        return 0;
    }

    public int binSrch(int[] nums,int k,int low,int high){
        int mid=(low+high)/2;
        if(k==nums[mid]) return mid;
        else if(k<nums[mid]) return binSrch(nums,k,low,mid-1);
        else return binSrch(nums,k,mid+1,high);
    }


}

基于树的查找

二叉排序树

package search1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author CSDN@日星月云
 * @date 2022/10/31 10:20
 */
class BSTNode {
    int key;
    BSTNode lChild;
    BSTNode rChild;

    public BSTNode() {
    }

    public BSTNode(int key) {
        this.key = key;
    }

    public BSTNode(int key, BSTNode lChild, BSTNode rChild) {
        this.key = key;
        this.lChild = lChild;
        this.rChild = rChild;
    }

    @Override
    public String toString() {
        return "BSTNode{" +
                "key=" + key +
                ", lChild=" + lChild +
                ", rChild=" + rChild +
                '}';
    }
}


class BsTree {
    BSTNode root;
    BsTree(){
        root=null;
    }

    //用扩展先序遍历序列创建二叉链表
    //依靠队列，当队首元素分配了左右孩子就出队
    public BSTNode setTree(Integer[] data)//data为传入的形参数组，如Integer[] nums = {1,2,null,4,null,5}
    {
        root = new BSTNode(data[1]);
        Queue<BSTNode> queue = new LinkedList<>();//先入先出，构造子树
        queue.offer(root);
        int i = 2;//从第二个元素开始入列
        while(i<data.length)
        {
            BSTNode node = queue.poll();//弹出队列中的树节点
            if(data[i] != null)//当实参的元素不为null时，添加左节点
            {
                node.lChild = new BSTNode(data[i]);
                queue.offer(node.lChild);
            }
            i++;//不管实参(传入Integer[] data的Integer数组)的元素是不是null，均需要后移一位
            if(data[i] != null)//当实参的元素不为null时，添加右节点
            {
                node.rChild = new BSTNode(data[i]);
                queue.offer(node.rChild);
            }
            i++;
        }
        return root;//返回根节点
    }


    //访问
    void visit(int n){
        System.out.print(n+" ");
    }

    // 递归 中序
    void inOrder(BSTNode root){
        if (root!=null){
            inOrder(root.lChild);
            visit(root.key);
            inOrder(root.rChild);
        }
    }

    //基于二叉排序树查找的非递归实现
    BSTNode searchBSTN(BSTNode root, int k){
        BSTNode q;
        q=root;
        while (q!=null){
            if(q.key==k){
                return q;
            }
            if (k<q.key){
                q=q.lChild;
            }else{
                q=q.rChild;
            }
        }
        return null;
    }

    //基于二叉排序树查找的递归实现
    BSTNode searchBST(BSTNode root, int k){
        if (root==null) return null;
        else if(root.key==k) return root;
        else if(k<root.key) return searchBST(root.lChild, root.key);
        else return searchBST(root.rChild, k);
    }


    //二叉排序树的插入
    void insertBST(BSTNode root,int k){
        BSTNode s;
        if (root==null){
            s=new BSTNode(k);
            root=s;//值传递机制赋值失败
        }
        else if(k<root.key) {insertBST(root.lChild,k);}
        else if(k>root.key) {insertBST(root.rChild,k);}
    }

    //二叉排序树的插入
    public void insert(int k){
        BSTNode newNode=new BSTNode(k);
        if (root==null){
            root=newNode;
        }
        else{
            BSTNode current = root; // start at root
            BSTNode parent;
            while (true) {//(exits internally)
                parent = current;
                if (k < current.key) {// go left?
                    current = current.lChild;
                    if (current == null) {// if end of the line,
                        // insert on left
                        parent.lChild = newNode;
                        return;
                    }
                }// end if go left
                else {// or go right?
                    current = current.rChild;
                    if (current == null) {// if end of the line
                        // insert on right
                        parent.rChild = newNode;
                        return;
                    }
                } // end else go right
            } // end while
        }
    }

    //二叉排序树的创建
    public void create(int []nums){
        for (int i = 0; i < nums.length; i++) {
            insert(nums[i]);
        }
    }


    public boolean delete(int key) {        //delete node with given key
        // (assumes non-empty list)
        BSTNode current = root;
        BSTNode parent = root;
        boolean isLeftChild = true;
        while (current.key != key) {// search for node
            parent = current;
            if (key < current.key) { // go left?
                isLeftChild = true;
                current = current.lChild;
            } else {
                // or go right?
                isLeftChild = false;
                current = current.rChild;
            }
            if (current == null)// end of the line,
                return false; // didn't find it
        } // end while
        // found node to delete
        // if no children, simply delete it
        if (current.lChild == null && current.rChild == null) {
            if (current == root)// if root,
                root = null;// tree is empty
            else if (isLeftChild)
                parent.lChild = null;// disconnect
            else// from parent
                parent.rChild = null;
        }
        // if no right child, replace with left subtree
        else if (current.rChild == null) {
            if (current == root) root = current.lChild;
            else if (isLeftChild)
                parent.lChild = current.lChild;
            else
                parent.rChild = current.lChild;
        }

        // if no left child, replace with right subtree
        else if (current.lChild == null) {
            if (current == root)
                root = current.rChild;
            else if (isLeftChild) parent.lChild = current.rChild;
            else
                parent.rChild = current.rChild;
        } else {// two children, so replace with inorder successor
            // get successor of node to delete (current)
            BSTNode successor = getSuccessor(current);

            // connect parent of current to successor instead
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.lChild = successor;
            else
                parent.rChild = successor;

            // connect successor to current's left child
            successor.lChild = current.lChild;
            // end else two children// (successor cannot have a left child)
        }
        return true; // success
    }// end delete()
    // returns node with next-highest value after delNode

    // goes to right child, then right child's left descendents
    private BSTNode getSuccessor(BSTNode delNode) {
        BSTNode successorParent = delNode;
        BSTNode successor = delNode;
        BSTNode current = delNode.rChild;// go to right child
        while (current != null) {// until no more
            // left children,
            successorParent = successor;
            successor = current;// go to left child
            current = current.lChild;
        }
        // if successor not
        if (successor != delNode.rChild) {// right child,
            // make connections
            successorParent.lChild = successor.rChild;
            successor.rChild = delNode.rChild;
        }
        return successor;
    }


}
public class SearchBSt {

    public static void main(String[] args) {
        //用扩展先序遍历序列创建二叉链表，手动创建二叉搜索数
        Integer[] nums={null,44,21,65,14,32,58,72,null,null,null,null,null,null,null,80};
        BsTree bsTree = new BsTree();
        bsTree.setTree(nums);
        bsTree.inOrder(bsTree.root);//14 21 32 44 58 65 72 80
        System.out.println();

        //测试基于二叉排序树查找的非递归实现
        System.out.println(bsTree.searchBSTN(bsTree.root, 80));//BSTNode{key=80, lChild=null, rChild=null}
        //测试基于二叉排序树查找的递归实现
        System.out.println(bsTree.searchBST(bsTree.root, 80));//BSTNode{key=80, lChild=null, rChild=null}


          //测试二叉排序树的插入
//        new SearchBSt().insertBST(bsTree.root, 69);
//        bsTree.inOrder(bsTree.root);//14 21 32 44 58 65 72 80

        //测试二叉排序树的插入
        bsTree.insert(69);
        bsTree.inOrder(bsTree.root);//14 21 32 44 58 65 69 72 80
        System.out.println();

        //测试二叉排序树的建立
        BsTree bst=new BsTree();
        int[] numbers={44,21,65,14,32,58,72,80};
        bst.create(numbers);
        bst.inOrder(bst.root);//14 21 32 44 58 65 72 80
        System.out.println();

        //测试二叉排序树的删除
//        bst.delete(14);
//        bst.inOrder(bst.root);//14 21 32 44 58 65 72 80
//        System.out.println();//21 32 44 58 65 72 80

//        bst.delete(80);
//        bst.inOrder(bst.root);//14 21 32 44 58 65 72 80
//        System.out.println();//14 21 32 44 58 65 72

//        bst.delete(21);
//        bst.inOrder(bst.root);//14 21 32 44 58 65 72 80
//        System.out.println();//14 32 44 58 65 72 80

//        bst.delete(72);
//        bst.inOrder(bst.root);//14 21 32 44 58 65 72 80
//        System.out.println();//14 21 32 44 58 65 80

        bst.delete(32);
        bst.inOrder(bst.root);//14 21 32 44 58 65 72 80
        System.out.println();//14 21 44 58 65 72 80
    }








}

平衡二叉树

B树和B+树

伸展树

红黑树

散列

哈希函数的构造方法

处理冲突的方法

哈希表的查找

package search1;

import java.util.Arrays;

/**
 * @author CSDN@日星月云
 * @date 2022/10/31 12:09
 */
class HashTable {
    public final int HASHSIZE=11;
    Integer[] nums;//存储
    int [] times;//比较次数

    //采用除留余数法构造哈希函数
    int hashFunc(int key){
        return key % HASHSIZE;
    }

    //采用线性探测再散列处理冲突
    int collision(int di){
        return (di+1)%HASHSIZE;
    }

    //哈希表的查找
    int hashSearch(Integer x){
        int address;
        address=hashFunc(x);//计算散列地址
        while (nums[address]!=null&&!x.equals(nums[address])){
            address=collision(address);//没找到处理冲突
        }
        if(x.equals(nums[address])){
            return address;//查找成功
        }else {
            return -1;
        }

    }

    //哈希表的插入
    int hashInsert(int x){
        int address;
        //有就不用插入
        address=hashSearch(x);
        if(address>=0) return 0;

        //没有
        int time=1;
        address= hashFunc(x);//计算散列地址
        while(nums[address]!=null){
            address=collision(address);//没找到,处理冲突
            time++;
        }
        nums[address]=x;
        times[address]=time;
        return 1;

    }

    //哈希表的创建
    void createHt(int[] numbers){
        nums=new Integer[HASHSIZE];
        times=new int[HASHSIZE];
        for (int i = 0; i < numbers.length; i++) {
            hashInsert(numbers[i]);
        }
    }

    //哈希表的删除
    int hashDel(int x){
        int address;
        address=hashFunc(x);
        if (address>=0){
            nums[address]=null;
            return 1;
        }
        return 0;
    }

}


public class HashSearch{
    public static void main(String[] args) {
        HashTable ht=new HashTable();
        int[] numbers={19,1,23,14,55,68,11,82,36};
        //测试创建
        ht.createHt(numbers);
        System.out.println(Arrays.toString(ht.nums));
        //[55, 1, 23, 14, 68, 11, 82, 36, 19, null, null]
        //测试查找
        System.out.println(ht.hashSearch(14));
        //测试删除
        System.out.println(ht.hashDel(14));
        System.out.println(ht.hashSearch(14));

    }
}

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

查找【数据结构与算法java】

查找【数据结构与算法java】

查找

基于线性表的查找

顺序查找

折半查找

基于树的查找

二叉排序树

平衡二叉树

B树和B+树

伸展树

红黑树

散列

哈希函数的构造方法

处理冲突的方法

哈希表的查找

相关文章

顺序查找法

二叉树经典OJ练习

《剑指Offer》按之字形顺序打印二叉树——最容易理解的思路，两分钟学会~

《剑指Offer》二叉搜索树的第k个节点——真没你想象中那么难，一招教你秒杀它~

Redis Hash哈希

超级好用的C++实用库之sha256算法

30天拿下Rust之HashMap

SQL Server 执行计划3--关联查询

SQL Server 执行计划1--数据查询

SQL Server 执行计划2--函数计算

作者介绍

最新文章

《剑指Offer》按之字形顺序打印二叉树——最容易理解的思路，两分钟学会~

《剑指Offer》二叉搜索树的第k个节点——真没你想象中那么难，一招教你秒杀它~

SQL Server 执行计划3--关联查询

数据结构与算法学习路径

算法&数据结构 - 栈相关基础概念

数据结构线性表——顺序表

热门文章

【数据结构】二叉树基础OJ题

【数据结构】二叉树与堆

数据结构之二叉搜索树（BST）

redis-哈希数据类型

Redis中哈希hash数据类型

每日学习一个数据结构-AVL树

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

Redis中哈希hash数据类型

线性表技巧之Note002-寻找第 k 个节点

考研数据结构之树（6.10）——练习题之求表达式的值（C表示）

关于二叉树，你应该了解这些。（二叉树的理论基础）

利用完全二叉树的性质，如何创建一个大根堆和一个小根堆？

​数据结构之初始二叉树-相同的树

数据结构之初始二叉树-相同的树