2019-11-30:Java集合相关数据结构

1.待补充知识

数组结构

数组特点:

长度固定，内存连续，类型必须一致.
优点:支持随机访问，查询速度O(1).
缺点:中间位置增加、删除O(N).
4.数组实现代码

package array;

import org.junit.Test;

import java.util.Arrays;

public class Array {
    //默认容量大小
    private final static int DEFAULT_SIZE = 10;
    //创建默认容量数组
    private Object[] objects =new Object[DEFAULT_SIZE];
    //设置默认扩容率
    private final static float ENLARGE_RATE=0.75f;
    //记录元素的实际数量
    private int size;
    private void enlarge(){
        //如果条件满足，执行扩容.
        if((size+1)==objects.length){
            //保存旧的容量大小.
            int oldSize=size;
            //每次在之前容量+0.75%的容量.
            int newSize=size+(int)(size*ENLARGE_RATE);
            //创建扩容后的空数组
            Object[] temp=new Object[newSize];
            //把原来数组中的元素复制到新数组
            System.arraycopy(objects,0,temp,0,oldSize+1);
            //提升垃圾回收效率
            for (int i = 0; i <objects.length ; i++) {
                objects[i]=null;
            }
            //把旧的数组引用替换成新的数组.
            objects = temp;
        }
    }

    public void add(Object o){
        //1.调用扩容方法
        enlarge();
        //2.把元素存放到当前size+1的位置
        objects[size++]=o;
    }

    /**
     * 向后添加的实现
     * @param index
     * @param o
     */
    public void addAfter(int index,Object o){
        //1.调用扩容方法
        enlarge();
        //2.找到索引位置的元素
        if(objects[index]!=null) {
            //3.不为null
            //4.后续元素都后移一位
            int offset = index+1;
            for (int i =size-1; i >=offset; i--) {
                    objects[i+1]=objects[i];
            }
            objects[offset]=o;
            size++;
            return;
        }
        //3.如果为null
        //4.直接放进去
        objects[index]=o;
        size++;

    }

    public void del(int index){
        //1.调用整理算法
        int offset = index+1;
        for (int i =offset; i <size; i++) {
            objects[i-1]=objects[i];
        }
        objects[size-1]=null;
    }

    public int length(){
        return objects.length;
    }

    public int getSize() {
        return size;
    }

    public Object get(int index){
        return objects[index];
    }

    public void info(){
        System.out.println(Arrays.toString(objects));
    }


    @Test
    public void test(){

        Array array = new Array();
        System.out.println("扩容前:"+array.length());
        for (int i = 0; i <50 ; i++) {
            array.add(i);
        }
        array.addAfter(3,666);
        array.addAfter(8,8888);
       // array.del(4);
        //array.del(1);
        System.out.println("扩容后:"+array.length());
        array.info();
    }
}

链表结构

链表特点:

无大小限制,内存不连续，支持多种类型.
优点:增加、删除快O(1)
缺点:查询O(N)|根据索引判断前半段或后半段O(N/2)
参考:LinkedList
链表实现代码

package linked;

import org.junit.Test;

public class SingleLinked {
   private Node first;
   private Node last;
   private int size;

    class Node {
        String element;
        Node next;

        private Node(String element) {
            this.element = element;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element='" + element + '\'' +
                    ", next=" + next +
                    '}';
        }
    }


    public void addLeft(String o) {
        //1.构建Node对象
        Node node = new Node(o);
        //2.是否是第一个
        if (first == null) {
            //3.如果是那么就把first=当前Node.
            first = node;
            last = node;
        } else {
            //3.把first保存到临时变量
            Node f = first;
            //4.把新节点当做首节点
            first = node;
            //5.建立节点关联
            first.next = f;
        }
        size++;
    }

    public void addRight(String o) {
        //1.构建Node对象
        Node node = new Node(o);
        //2.是否是第一个
        if (last == null) {
            //3.如果是那么就把first=当前Node.
            last = node;
            first = node;
        } else {
            //3.建立节点关联
            last.next = node;
            last = node;
        }
        size++;
    }

    public void addMiddle(Node index, String o) {
        //1.构建Node对象
        Node node = new Node(o);
        //2.建立节点关联
        Node l = index.next;
        index.next = node;
        node.next = l;
        size++;
    }

    public Node get(int index) {
        Node t = first;
        for (int i = 0; i < index; i++) {
            t = t.next;
        }
        return t;
    }

    public Node getFirst() {
        return first;
    }

    public Node getLast() {
        return last;
    }

    public int getSize() {
        return size;
    }

    public void info() {
        Node t = first;
        for (int i = 0; i < size; i++) {
            System.out.println(t);
            t = t.next;
        }
    }


    @Test
    public void test() {
        SingleLinked linked = new SingleLinked();
        linked.addRight("1");
        linked.addRight("2");
        linked.addRight("3");
        SingleLinked.Node index = linked.get(1);
        linked.addMiddle(index, "9");
        linked.info();

    }
}

树结构

基础概念

术语	中文	描述
Root	根节点	The top node in a tree.
Child	子节点	A node directly connected to another node when moving away from the Root.
Leaf	叶子节点	A node with no children
Edge	边	The connection between one node and another.
Path	路径	A sequence of nodes and edges connecting a node with a descendant.
Height	节点高度	The height of a node is the number of edges on the longest path between that node and a leaf.
Depth	深度	The depth of a node is the number of edges from the tree’s root node to the node.
Level	层级	The level of a node is defined by 1 + (the number of connections between the node and the root).
Degree	度	The number of subtrees of a node.

树的图解

Edge、Root、Leaf

image.png

Path

image.png

Height、Depth

image.png

从Height和Depth的对比，它们的方向刚好是相反的。
对于Height和Depth不用死记，我们可以把树倒过来看，也就是我们现实生活当中的树，求某个节点的Height那肯定是从根部往上的方向；
如果是求某个节点的深度，方向肯定是向下的。

Level

image.png

节点的Level是从1开始的，Level = Depth+1，根节点的Level=1
也有很多书籍上Level是从0开始的，这样的话Level就等于Depth，根节点的Level=0

树的分类

二叉树

完美二叉树（perfect binary tree)
特点:所有内部节点都有两个子节点，并且所有叶节点的深度相同。
2.完全二叉树(Complete Binary Tree)
特点:除了最后一层其他每一层都是完全填满的，而最后一层从左往右依次排列。
3.满二叉树（full binary tree）
特点:直接定义：除根节点以外的每个节点要么有0个要么2个节点，
平衡树(AVL)
待添加

二叉树的实现

必备知识:递归算法

添加叶子(完全树)

add

public void searchInsertPoint(Node<Double> parent,double value) {
        if(value<parent.getValue()){
            if(parent.getLeft()==null){
                addLeftLeaf(parent,value);
            }else {
                searchInsertPoint(parent.getLeft(),value);
            }
        }
        if(value>parent.getValue()){
            if(parent.getRight()==null){
                addRightLeaf(parent,value);
            }else {
                searchInsertPoint(parent.getRight(),value);
            }
        }

    }

遍历分类

深度遍历

前序遍历(pre-search)（根->左->右）

/**
     * 前序遍历
     * 根->左叶子->右叶子
     * @param parent
     */

    public void pre_foreach(Node parent) {
        if(parent==null)return;
        System.out.println(parent.getValue());
        pre_foreach(parent.getLeft());
        pre_foreach(parent.getRight());


    }

中序遍历(in-search)（左->根->右）

/**
     * 中序遍历
     * 左叶子->根->右叶子
     * @param parent
     */
    public void in_foreach(Node parent) {
        if(parent==null)return;
        in_foreach(parent.getLeft());
        System.out.println(parent.getValue());
        in_foreach(parent.getRight());

    }

后序遍历(post-search)（左->右->根）

/**
     * 后序遍历
     * 左叶子->右叶子->根
     * @param parent
     */
    public void post_foreach(Node parent) {
        if(parent==null)return;
        in_foreach(parent.getLeft());
        in_foreach(parent.getRight());
        System.out.println(parent.getValue());

    }

广度遍历(breadth first search)

使用先进先出的队列实现

public void breadthSearch(){
        while(!nodes.isEmpty()) {
            Node node = nodes.pop();
            System.out.println(node.getValue());
            if (Objects.nonNull(node.getLeft())) {
                nodes.push(node.getLeft());
            }
            if (Objects.nonNull(node.getRight())) {
                nodes.push(node.getRight());
            }
        }
    }

来源: https://blog.csdn.net/johnny901114/article/details/80574803

hash结构

hash特点
1.插入、删除
hash代码实现

image.png

package hash;

import org.junit.Test;

import java.util.Arrays;
import java.util.Map;


public class HashTable {
    private Node[] objects;



    public HashTable(){
        objects=new Node[10];
    }


    public int hash(Object o){
        int h=o.hashCode()%objects.length;
        System.out.println("随机数:"+o+",hash位置:"+h);
        return h;
    }

    private class Node implements Map.Entry<String,String>{

        private int hash;
        private String key;
        private String value;
        private Node next;

        public Node(int hash, String key, String value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public String getKey() {
            return key;
        }

        public String getValue() {
            return value;
        }

        public String setValue(String value) {
            String oldValue =value;
            this.value = value;
            return oldValue;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "hash=" + hash +
                    ", key='" + key + '\'' +
                    ", value='" + value + '\'' +
                    ", next=" + next +
                    '}';
        }
    }


    public void put(String key,String value){
        int hash = hash(key);
        Node node = new Node(hash,key,value,null);
        //没有发生hash冲突
        if(objects[hash]==null){
            objects[hash] = node;
            return;
        }
        //悲观看法
        //总是会发生冲突，一开始就存储链表结点
        //如果发生hash冲突
        Node temp = objects[hash];
        Node last=null;
        while(temp != null) {
            //判断链表上是否存在
            if(temp.getKey().equals(node.getKey()) && temp.getValue().equals(node.getValue())){
                //如果存在就覆盖.
                temp.setValue(value);
                return;
            }
            last = temp;
            temp  = temp.next;
        }
        //否则不存在相同结点，添加到链表后面
        last.next = new Node(hash,key,value,null);

    }

    public String get(String key){
       int hash = hash(key);
       Node temp = objects[hash]; 
       //直接去遍历链表
        while(temp != null) {
            if(temp.getKey().equals(key)){
                return temp.getValue();
            }
            temp  = temp.next;
        }
        //没有匹配返回null
        return null;
    }


    @Test
    public void test(){
        HashTable hashTable = new HashTable();

        for (int i = 0; i <10 ; i++) {
            int random =(int)(Math.random()*5);
            hashTable.put(Integer.toString(random),"test_v_"+i);
        }
        System.out.println(Arrays.toString(hashTable.objects));
        System.out.println(hashTable.get("0"));
    }
}