数据结构与算法-基础(十六)集合集合类数据结构

bigegpt 2024-10-12 06:08 8 浏览

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

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

就是因为这个特点，它可以被用作序列中元素的去重处理，比如存放新增加的 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);
}

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

list.size

上一篇：一文搞懂LRU 一文搞懂伤寒论六经辨证
下一篇：第五十七天-树状问题树状图求概率题目及答案

数据结构与算法-基础(十六)集合集合类数据结构

相关推荐

无缓存不行?例行升级的入门级阿斯加特AN2 SSD装机点评

Ceph运维手册(基于P版本)

Docker 命令大全（docker命令大全记录表）

替代Docker build的Buildah简单介绍

Docker Desktop安装使用指南:零基础教程

Tensorflow分类loss函数总结 tensorflow绘制loss曲线

R语言学习笔记(七) -离散型数据的模型预测2

7 个对 Java 意义重大的性能指标，你知道几个?

服务器硬件RAID性能横评(2)（服务器常用raid技术）

Python教程:第9篇字符串基本操作

数据结构与算法-基础(十六)集合 集合类数据结构

相关推荐

无缓存不行?例行升级的入门级阿斯加特AN2 SSD装机点评

Ceph运维手册(基于P版本)

Docker 命令大全（docker命令大全记录表）

替代Docker build的Buildah简单介绍

Docker Desktop安装使用指南:零基础教程

Tensorflow分类loss函数总结 tensorflow绘制loss曲线

R语言学习笔记(七) -离散型数据的模型预测2

7 个对 Java 意义重大的性能指标，你知道几个?

服务器硬件RAID性能横评(2)（服务器常用raid技术）

Python教程:第9篇 字符串基本操作

数据结构与算法-基础(十六)集合集合类数据结构

Python教程:第9篇字符串基本操作