数据结构篇|集合(Set)

1.简介

Set是数据结构中的一种，它的特点是无序，唯一。在计算机界的应用十分广泛，可用于统计书中的单词数以及某日网站的访问人数

集合的实现会复用之前实现的数据结构，连接如下

基于二分搜索树：https://www.jianshu.com/p/f04a85439922
基于链表：https://www.jianshu.com/p/fdd0c76837a1

2.实现Set接口

public interface Set<E> {

    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

Set分别具有以上功能，所以就创建一个接口将对应的功能在接口中进行创建即可。

基于二分搜索树的实现

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

    private BST<E> bst;

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

因为是基于二分搜索树的实现，所以就起名为BSTSet，它是支持泛型的并具有比较大小的功能，所以要继承Comparable接口，然后再实现Set接口。首先在类中声明变量BST，再在BSTSet被初始化时将小的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 boolean contains(E e){
        return bst.contains(e);
    }

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

这些方法分别是获取元素个数，判断集合是否为空，向集合中添加元素，查看集合中是否包含某元素，从集合中删除元素的。它们的实现只需调用bst中已有的方法即可，因为上一节实现的二分搜索树就具有Set需要的功能。

基于链表的实现

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

    private LinkedList<E> linkedList;

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

链表的实现方式与二分搜索树的实现类似，都是首先声明成员变量，然后在调用构造方法时将成员变量进行初始化。但是这里不同的是不需要继承Comparable接口。因为线性数据结构不需要具有可比较性。

接口方法的实现

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

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

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

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

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

这里和基于二分搜索树实现也是类似的，唯一的不同就是在添加元素时，需要注意不能添加重复的元素，所以在add操作时要进行条件过滤，条件也很简单，只在链表中不包含元素e时再进行添加即可，因为链表从链表头进行添加的时间复杂度比较低，所以就调用addFirst()方法。