Skip to content

Latest commit

 

History

History
385 lines (333 loc) · 8.61 KB

6_集合和映射.md

File metadata and controls

385 lines (333 loc) · 8.61 KB
Raw

集合和映射

集合

集合的基本功能：

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

基于二分搜索树的集合实现

public class BSTSet<E extends Comparable<E>> implements Set<E>{
    private BST<E> bst;

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

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

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

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

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

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

基于链表的集合实现

public class LinkedListSet<E> implements Set<E>{
   private LinkedList<E> linkedList;

   public LinkedListSet(){
       linkedList=new LinkedList<>();
   }

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

    @Override
    public void remove(E e) {
        if(contains(e)){
            linkedList.removeElement(e);
        }
    }

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

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

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

时间复杂度分析

操作 LinkedListSet BSTSet
add O(n) 平均情况：O(log n)
最差情况：O(n)
contains O(n) 平均情况：O(log n)
最差情况：O(n)
remove O(n) 平均情况：O(log n)
最差情况：O(n)

映射

映射的基本功能：

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

基于二分搜索树的映射实现

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V>{
    private class Node{
        public K key;
        public V value;
        public Node left,right;
        public Node(K key,V value){
            this.key=key;
            this.value=value;
            this.left=null;
            this.right=null;
        }
    }

    private Node root;
    private int size;

    //返回以node为根节点的二分搜索树中，key所在的节点
    private Node getNode(Node node,K key){
        if(node==null){
            return null;
        }
        if(key.compareTo(node.key)<0){
            return getNode(node.left,key);
        }else if(key.compareTo(node.key)>0){
            return getNode(node.right,key);
        }else{ //key.compareTo(node.key)==0
            return node;
        }
    }

    @Override
    public void add(K key, V value) {
        root=add(root,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;
    }



    @Override
    public V remove(K key) {
        Node node=getNode(root,key);
        if(node!=null){
            root=del(root,key);
            size--;
        }
        return null;
    }

    //获取Map中的最小的key
    private Node min(Node node){
        if(node.left==null){
            return node;
        }
        return min(node.left);
    }

    //删除以node为根结点的Map中的key最小的元素
    private Node delMin(Node node){
        if(node.left==null){
            Node nodeRight=node.right;
            node.right=null;
            size--;
            return nodeRight;
        }
        node.left=delMin(node.left);
        return node;
    }

    //删除以node为根结点的Map中的键值为key的元素
    private Node del(Node node, K key){
        if(node==null){
            return null;
        }
        if(key.compareTo(node.key)<0){
            node.left=del(node.left,key);
            return node;
        }else if(key.compareTo(node.key)>0){
            node.right= del(node.right,key);
            return node;
        }else{
            //节点node就是要删除的节点
            //该节点只有右子树
            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 s=min(node.right);
            s.right=delMin(node.right);
            s.left=node.left;

            //删除node
            node.left=node.right=null;
            return s;
        }
    }

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

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

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

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

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

基于链表的映射实现

public class LinkedListMap<K,V> implements Map<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,V value){
            this(key,value,null);
        }
        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;
    }

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

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

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

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

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

    @Override
    public void set(K key, V newValue) {
        Node node=getNode(key);
        if(node==null){
            throw new IllegalArgumentException(key + "dose not exist");
        }
        node.value=newValue;
    }

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

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

时间复杂度分析

操作 LinkedListMap BSTMap
add O(n) 平均情况：O(log n)
最差情况：O(n)
remove O(n) 平均情况：O(log n)
最差情况：O(n)
set O(n) 平均情况：O(log n)
最差情况：O(n)
get O(n) 平均情况：O(log n)
最差情况：O(n)
contains O(n) 平均情况：O(log n)
最差情况：O(n)