15、数据结构与算法基础:集合

摘要

集合最重要的特点就是它里面的元素是不会存在重复的,所以集合的内部实现中,添加元素函数是需要先判断是否已经存在这个元素,是代码实现的核心部分。

集合是一个存储数据的序列,序列中的元素不会存在重复,这个就是集合最重要的特点。

就是因为这个特点,它可以被用作序列中元素的去重处理,比如存放新增加的 IP,统计新增的 IP 数量,存放词汇或者统计词汇量等。

集合的内部实现可以直接利用之前学过的数据结构来实现,比如动态数组链表AVL 树或者红黑树(属于二叉搜索树)

这里先用动态数组来实现集合。首先创建一个动态数组的对象来存放元素。

private List<E> list = new LinkedList<>();

集合中的其他函数,比如集合中的元素数量集合是否为空清除集合中的所有元素集合中是否包含某个元素这4个函数可以直接调用 list 的函数来处理,比如实现集合中的元素数量:

// 集合中的元素数量
public int size() {
   
     
  return list.size();
}

移除集合中的元素函数需要先在 list 中找到元素的 index,然后再移除 list 中的 index 位置元素。

// ELEMENT_NOT_FOUND:集合空元素标识符,常量为 -1
public void remove(E element) {
   
     
  int index = list.indexOf(element);
  if (index != List.ELEMENT_NOT_FOUND) {
   
     
    list.remove(index);
  }
}

最后就是实现集合的主要函数,即添加元素函数。因为集合要满足元素不可以重复的要求,所以在添加元素的时候需要先判断集合中是否已经存在该元素:

public void add(E element) {
   
     
  int index = list.indexOf(element);
  if (index != List.ELEMENT_NOT_FOUND) {
   
     
    // 存在,则替换
    list.set(index, element);
  } else {
   
     
    // 不存在,则直接添加
    list.add(element);
  }
}

如果用AVL树或者红黑树,那么添加元素的逻辑就更简单。因为这两种树中的元素都是不会有重复的,所以使用这两种树来实现,就直接调用树的添加函数就可以实现。

public void add(E element) {
   
     
  tree.add(element);
}

集合中的其他函数,就可以直接使用树已经有的函数来直接调用,和套用动态数组的方式是一样的。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: