数据结构与集合源码

我是南城余！阿里云开发者平台专家博士证书获得者！

欢迎关注我的博客！一同成长！

一名从事运维开发的worker，记录分享学习。

专注于AI，运维开发，windows Linux 系统领域的分享！

本章节对应知识库

数据结构与集合源码 (yuque.com)

---

【拓展】尚硅谷_宋红康_数据结构概述-Java版.xmind

计算机基础概念

数据结构

数据结构，就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度、减少内存占用的空间。

数据间的关系

逻辑关系

• 集合结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系。集合元素之间没有逻辑关系。
• 线性结构：数据结构中的元素存在一对一的相互关系。比如：排队。结构中必须存在唯一的首元素和唯一的尾元素。体现为：一维数组、链表、栈、队列
• 树形结构：数据结构中的元素存在一对多的相互关系。比如：家谱、文件系统、组织架构
• 图形结构：数据结构中的元素存在多对多的相互关系。比如：全国铁路网、地铁图

存储关系（物理结构）

顺序结构

• 顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素。
• 优点： 只需要申请存放数据本身的内存空间即可，支持下标访问，也可以实现随机访问。
• 缺点： 必须静态分配连续空间，内存空间的利用率比较低。插入或删除可能需要移动大量元素，效率比较低

开发中，我们更习惯如下的方式理解存储结构：

》线性表（一对一关系）：一维数组、单向链表、双向链表、栈、消息队列

》树（一对多关系）：各种树，比如：二叉树、B+树

》图（多对多关系）

》哈希表：比如：HashMap、HashSet

链式结构

• 不使用连续的存储空间存放结构的元素，而是为每一个元素构造一个节点。节点中除了存放数据本身以外，还需要存放指向下一个节点的指针。
• 优点：不采用连续的存储空间导致内存空间利用率比较高，克服顺序存储结构中预知元素个数的缺点。插入或删除元素时，不需要移动大量的元素。
• 缺点：需要额外的空间来表达数据之间的逻辑关系，不支持下标访问和随机访问。

  

  索引结构
• 除建立存储节点信息外，还建立附加的索引表来记录每个元素节点的地址。索引表由若干索引项组成。索引项的一般形式是：（关键字，地址）。
• 优点：用节点的索引号来确定结点存储地址，检索速度快。
• 缺点： 增加了附加的索引表，会占用较多的存储空间。在增加和删除数据时要修改索引表，因而会花费较多的时间。

  

  散列结构
• 根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。
• 优点：检索、增加和删除结点的操作都很快。
• 缺点：不支持排序，一般比用线性表存储需要更多的空间，并且记录的关键字不能重复。

  

运算结构

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

- 分配资源，建立结构，释放资源

- 插入和删除

- 获取和遍历

- 修改和排序