（七）数据结构之集合

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 625 | 阅读时长 ≈ 1 分钟
  此文待重构

简介

  在计算机科学中，集合是一组可变数量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同（若使用的语言支持继承 “继承 (计算机科学)”)）。列表（或数组）通常不被认为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。

集合的分类

  集合的分类很多。

  集合根据底层使用的数据不同，可以进行不同划分。

  集合根据存储数据是否具有唯一性，可以分为：

  • 重复集合：相同元素的数据可以重复存储
  • 不重复集合：相同元素的数据只会存储一次

  集合根据存储数据是否具有顺序，可以分为：

  • 有序集合：其中的数据具有顺序性（常常基于搜索树实现）
  • 无序集合：其中的数据没有顺序性（常常基于哈希表实现）

实现步骤图示

代码实现

链表实现集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class LinkedListSet<E extends Comparable<E>> implements Set<E> {

    private LinkedList<E> list;

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

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

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

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

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

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

二叉树实现集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class BinarySearchTreeSet<E extends Comparable<E>> implements Set<E> {
    private BinarySearchTreeSet<E> bst ;

    public BinarySearchTreeSet(){
        this.bst = new BinarySearchTreeSet();
    }

    @Override
    public int size() {
        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 void contains(E e) {
        bst.contains(e);
    }
}

时间复杂度

操作 LinkedListSet BSTset 平均 最差
add O(n) O(h) O(log n) O(n)
contains O(n) O(h) O(log n) O(n)
remove O(n) O(h) O(log n) O(n)

文章信息

时间 说明
2018-12-09 初稿
0%