[数据结构与算法]DS-Set

定义接口

public interface SelfSet<T> {
    void add(T t);

    void remove(T t);

    boolean isContains(T t);

    int size();

    boolean isEmpty();

    /**
     * 将set元素放入list中
     */
    List<T> dataList();
}

数组实现

底层使用数组作为容器： DS-数组

/**
 * 以数组为set底层数据结构
 *
 * @author Deevan
 */
public class ArraySet<T> implements SelfSet<T> {

    /**
     * 声明数据容器
     */
    MySelfArray<T> data;

    public ArraySet() {
        data = new MySelfArray<>();
    }

    @Override
    public void add(T t) {
        if (data.isContains(t) == -1) {
            data.addTail(t);
        }
    }

    @Override
    public void remove(T t) {
        data.removeEle(t);
    }

    @Override
    public boolean isContains(T t) {
        return data.isContains(t) != -1;
    }

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

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

    /**
     * 将set元素放入list中
     *
     * @return list
     */
    @Override
    public List<T> dataList() {
        List<T> list = new ArrayList<>();
        T[] result = data.getData();
        list = Arrays.stream(result).collect(Collectors.toList());
        return list;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        T[] result = data.getData();
        for (int i = 0; i < data.getSize(); i++) {
            sb.append(result[i]);
            if (i != data.getSize() - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

链表实现

底层使用链表作为容器： DS-链表

/**
 * 底层为链表
 *
 * @author Deevan
 */
public class LinkedSet<T> implements SelfSet<T> {

    /**
     * 声明底层容器
     */
    MyLink<T> data;

    public LinkedSet() {
        data = new MyLink<>();
    }

    @Override
    public void add(T t) {
        if (!data.isContains(t)) {
            data.addTail(t);
        }
    }

    @Override
    public void remove(T t) {
        data.removeByVal(t);
    }

    @Override
    public boolean isContains(T t) {
        return data.isContains(t);
    }

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

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

    @Override
    public List<T> dataList() {
        List<T> list = new ArrayList<>();
        for (int i = 0; i < data.getSize(); i++) {
            list.add(data.get(i));
        }
        return list;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < data.getSize(); i++) {
            sb.append(data.get(i)).append(",");
        }
        sb.replace(sb.length() - 1, sb.length(), "]");
        return sb.toString();
    }
}

二分搜索树实现

底层使用二分搜索树作为容器： DS-二分搜索树

元素必须具有可比性

输出采用中序遍历（递增）

/**
 * 二分搜索树实现set
 *
 * @author Deevan
 */
public class STreeSet<T extends Comparable<T>> implements SelfSet<T> {
    BinarySearch<T> data;

    public STreeSet() {
        data = new BinarySearch<>();
    }

    @Override
    public void add(T t) {
        if (data.contains(t) == null) {
            data.add(t);
        }
    }

    @Override
    public void remove(T t) {
        data.removeNode(t);
    }

    @Override
    public boolean isContains(T t) {
        return data.contains(t) != null;
    }

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

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

    @Override
    public List<T> dataList() {
        return data.middleOrder();
    }

    /**
     * 使用二分搜索树的中序遍历
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (T t : data.middleOrder()) {
            sb.append(t).append(",");
        }
        sb.replace(sb.length() - 1, sb.length(), "]");
        return sb.toString();
    }
}