数据结构学习，集合（Set）和映射（Map）（java语言）

1.集合（Set）

集合中不包含重复的元素，所以我们经常利用集合来去重
首先给集合定义以下接口

public interface Set<E> {
    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

1.1基于二分搜索树的集合

基于二分搜索树的集合底层是一个二分搜索树的数据结构，对于新增操作和删除操作，都直接调用二分搜索树中对应的方法即可，由于二分搜索树中的元素需要排序，所以泛型E要继承Comparable接口

public class BSTSet<E extends Comparable<E>> implements Set<E> {

    private BST<E> bst;
    public BSTSet(){
        bst = new BST<>();
    }

    @Override
    public int getSize(){
        return bst.size();
    }

    @Override
    public boolean isEmpty(){
        return bst.isEmpty();
    }

    @Override
    public void add(E e){
        bst.add(e);
    }

    @Override
    public void remove(E e){
        bst.remove(e);
    }

    @Override
    public boolean contains(E e){
        return bst.contains(e);
    }

    public void Order(){
        bst.inOrder();
    }
}

1.2基于链表的集合

基于链表的集合本身底层使用一个链表实现，但是链表本身可以存储重复的元素，所以我们在添加元素之前要判断集合中是否有此元素，有就不用添加了

public class LinkedListSet<E> implements Set<E> {

    private LinkedList<E> list;
    public LinkedListSet(){
        list = new LinkedList<>();
    }

    @Override
    public int getSize(){
        return list.getSize();
    }

    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }

    @Override
    public boolean contains(E e){
        return list.contains(e);
    }

    @Override
    public void add(E e){
        if(!list.contains(e)){
            list.addFirst(e);
        }
    }

    @Override
    public void remove(E e){
        list.removeElement(e);
    }
}

2.映射（Map）

映射就像一个英文字典一样，给定一个词，就有对应的英文解释，且一本字典不会存相同的词。这样就组成了一个键值对的结构<key,value>。
以下是Map的接口

public interface Map<K,V> {
    void add(K key,V value);
    V remove(K key);
    V get(K key);
    boolean contains(K key);
    void set(K key , V value);
    int getSize();
    boolean isEmpty();
}

2.1基于链表的映射

由于一个节点储存的数据不只是一个元素e了，所以我们要对链表的结构进行修改。

    private class Node{
        public K key;
        public V value;
        public Node next;

        public Node(K key,V value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key){
            this(key,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString(){
            return key.toString()+" : "+value.toString();
        }

    }

然后为了方便我们之后的操作，首先声明一个获取key所对应的节点的方法

    private Node getNode(K key){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

之后的操作就很容易了，我们要判断Map是否为空就可以调用上面的方法

    public boolean contains(K key){
        return getNode(key)==null;
    }

要获取一个节点的value也可以通过调用getNode方法

    public V get(K key){
        Node node = getNode(key);
        return node==null?null:node.value;
    }

添加操作由于是链表，所以我们使用头插法比较省时

    public void add(K key,V value){
        Node node = getNode(key);
        if(node == null){
            dummyHead.next = new Node(key,value,dummyHead.next);
            size ++;
        }else{
            node.value = value;
        }
    }

修改操作就通过getNode将节点获取，然后修改对应的值即可

    public void set(K key,V value){
        Node node = getNode(key);
        if(node == null){
            throw new IllegalArgumentException(key + " doesn't exist!");
        }
        node.value = value;
    }

删除操作与链表的删除操作相同

    public V remove(K key){
        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.key == key){
                break;
            }
            prev = prev.next;
        }

        if(prev.next == null){
            return null;
        }
            Node delNode = prev.next;
            prev.next = delNode.next;
            size --;
            delNode.next = null;

        return delNode.value;
    }

这样我们就将链表实现的映射方法给写完了

2.2基于二分搜索树的映射

同样，我们要先将节点的结构进行修改

    private class Node{
        public K key;
        public V value;
        public Node left;
        public Node right;
        public Node(K key , V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

新增操作同样使用了递归，与二分搜索树的新增操作差不多

    public void add(K key , V value){
        root = add(root,key,value);
    }

    public Node add(Node node ,K key ,V value){
        if(node == null){
            size ++;
            return new Node(key,value);
        }

        if(key.compareTo(node.key)<0){
            node.left = add(node.left,key,value);
        }
        if(key.compareTo(node.key)>0){
            node.right = add(node.right,key,value);
        }else{
            node.value = value;
        }
        return node;
    }

然后我们同样的，定义一个获取节点的方法get（）

    public Node get(Node node,K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key)==0){
            return node;
        }else if(key.compareTo(node.key)<0){
            return get(node.left,key);
        }else{
            return get(node.right,key);
        }
    }

这样，根据key获取节点的value就变得十分容易了，只需调用一下get节点的方法

    public V get(K key){
        Node node = get(root,key);
        return node==null?null:node.value;
    }

查询映射中是否包含key也十分容易

   public boolean contains(K key){
        return get(root,key)!=null;
    }

更新key所对应的value也一样

    public void set(K key,V value){
        Node node = get(root,key);
        if(node == null){
            throw new IllegalArgumentException("not found the key");
        }
        node.value = value;
    }

删除操作与二分搜索树的操作也基本相同

    public V remove(K key){
        Node node = get(root,key);
        if(node!=null) {
            root = remove(root, key);
            return node.value;
        }else{
            return null;
        }
    }

    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }


    public Node remove(Node node, K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key)<0){
            node.left = remove(node.left,key);
            return node;
        }else if(key.compareTo(node.key)>0){
            node.right = remove(node.right,key);
            return node;
        }else{
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            Node successor = minimum(node.right);
            successor.left = node.left;
            successor.right = remove(node.right,minimum(node.right).key);
            node.left = node.right = null;
            return successor;
        }
    }

这样，我们就将Map 的结构也写完了

3.总结

• 集合根据其不能存放重复元素的特性，主要可以用来去重
• 映射中由于key的唯一性，我们可以通过value储存元素出现的次数，用来统计频率