集合和映射

集合(Set)

• 每个元素不重复
• 实现

# 基于BST(二叉搜索树)实现
public class BSTSet<E extends Comparable>{

    private BST<E> bst;

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

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

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

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

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

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

# 基于LinkedList(链表)实现
public class LinkedListSet<E>{
    
    private LinkedList<E> list;

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

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

    public isEmpty(){
        return list.isEmpty();
    }

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

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

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

集合应用(唯一摩尔斯密码)

映射(Map)

• 存储(键,值)数据对的数据结构
• 根据key寻找值
• 实现

# 基于LinkedList实现
public class LinkedListMap<K,V>{
    
    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);
        }
    }

    private Node dummyHead;

    private int size;

    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

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

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

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

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

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

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

        return null;
    }
}

# 基于二分搜索树实现
public class BSTMap(){

    private class Node{
        pubic 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;
        }
    }

    private Node root;
    private int size;

    public BSTMap(){
        root = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

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

    private 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);
        }else if(key.compareTo(node.key)>0){
            node.right=add(node.right,key,value);
        }else{
            node.value=value;
        }
        return node;
    }

    private Node getNode(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 getNode(node.left,key);
        }else{
            return getNode(node.right,key);
        }
    }

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

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

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

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

    private Node removeMin(Node node){
        if(node.left==null){
            Node rightNode = node.right;
            node.right=null;
            size--;
            return rightNode;
        }

        node.left=removeMin(node.left);
        return node;
    }

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

        return null;
    }

    private Node remove(Node node,K key){
        if(node==null){
            return null;
        }
        if(key.compareTo(node.key)<0){
            node.left=remove(node.left,key);
        }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.right=removeMin(node.right);
            successor.left=node.left;
            node.left=node.right=null;
            return successor;
        }
    }
}