剑眉星目

深浅模式

数据结构 ​

更新: 2025/2/24 字数: 0 字 时长: 0 分钟

数据结构分类 ​

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，它们可以从“逻辑结构”和“物理结构”两个维度进行分类。

逻辑结构 ​

逻辑结构揭示了数据元素之间的逻辑关系。如下图所示，逻辑结构可分为“线性”和“非线性”两大类。

  • 线性结构比较直观，指数据在逻辑关系上呈线性排列；非线性结构则相反，呈非线性排列。

    • 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系。
    • 非线性数据结构：树、堆、图、哈希表。

  • 非线性数据结构可以进一步划分为树形结构和网状结构。

    • 树形结构：树、堆、哈希表，元素之间是一对多的关系。
    • 网状结构：图，元素之间是多对多的关系。

线性数据结构与非线性数据结构

物理结构 ​

当算法程序运行时，正在处理的数据主要存储在内存中。下图展示了一个计算机内存条，其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格，其中每个单元格都可以存储一定大小的数据，而且系统可以通过内存地址来访问目标位置的数据。如下图所示，计算机根据特定规则为表格中的每个单元格分配编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数据。

内存条、内存空间、内存地址

建议

值得说明的是，将内存比作 Excel 表格是一个简化的类比，实际内存的工作机制比较复杂，涉及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。

时间空间 ​

内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。比如，算法所占用的内存峰值不应超过系统剩余空闲内存；如果缺少连续大块的内存空间，那么所选用的数据结构必须能够存储在分散的内存空间内。如下图所示，物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（例如数组）和分散空间存储（例如链表）。物理结构从底层决定了数据的访问、更新、增删等操作方法，两种物理结构在时间效率和空间效率方面呈现出互补的特点。

连续空间存储与分散空间存储

值得说明的是，所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

  • 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度 ≥3 的数组）等。
  • 基于链表可实现：栈、队列、哈希表、树、堆、图等。

链表在初始化后，仍可以在程序运行过程中对其长度进行调整，因此也称“动态数据结构”。数组在初始化后长度不可变，因此也称“静态数据结构”。值得注意的是，数组可通过重新分配内存实现长度变化，从而具备一定的“动态性”。

基本数据类型 ​

当谈及计算机中的数据时，我们会想到文本、图片、视频、语音、3D 模型等各种形式。尽管这些数据的组织形式各异，但它们都由各种基本数据类型构成。

常用类型 ​

基本数据类型是 CPU 可以直接进行运算的类型，在算法中直接被使用，主要包括以下几种：

  • 整数类型 byte、short、int、long 。
  • 浮点数类型 float、double ，用于表示小数。
  • 字符类型 char ，用于表示各种语言的字母、标点符号甚至表情符号等。
  • 布尔类型 bool ，用于表示“是”与“否”判断。

基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 11 比特。在绝大多数现代操作系统中，11 字节（byte）由 88 比特（bit）组成。在 Python 中，整数类型 int 可以是任意大小，只受限于可用内存；浮点数 float 是双精度 64 位；没有 char 类型，单个字符实际上是长度为 1 的字符串 str 。即使表示布尔量仅需 11 位（00 或 11），它在内存中通常也存储为 11 字节。这是因为现代计算机 CPU 通常将 11 字节作为最小寻址内存单元。

关联关系 ​

有人会问，基本数据类型与数据结构之间有什么联系呢？

我们知道，数据结构是在计算机中组织与存储数据的方式。这句话的主语是“结构”而非“数据”。如果想表示“一排数字”，我们自然会想到使用数组。这是因为数组的线性结构可以表示数字的相邻关系和顺序关系，但至于存储的内容是整数 int、小数 float 还是字符 char ，则与“数据结构”无关。换句话说，基本数据类型提供了数据的“内容类型”，而数据结构提供了数据的“组织方式”。例如以下代码，我们用相同的数据结构（数组）来存储与表示不同的基本数据类型，包括 int、float、char、bool 等。

python
# 使用多种基本数据类型来初始化数组
numbers: list[int] = [0] * 5
decimals: list[float] = [0.0] * 5
# Python 的字符实际上是长度为 1 的字符串
characters: list[str] = ['0'] * 5
bools: list[bool] = [False] * 5
# Python 的列表可以自由存储各种基本数据类型和对象引用
data = [0, 0.0, 'a', False, ListNode(0)]

结构选择考量 ​

我们所写的程序都是由数据结构和算法结合得到的一个产物（数据结构 + 算法 = 程序），数据结构为算法提供服务，算法围绕数据结构操作。像平常我们都是使用框架和库开发项目，也不太可能去修改框架和库的内部代码，这时我们就可以对程序的数据结构和算法进行优化。

在优化的过程中我们会发现，选择数据结构和优化算法一样，都是一个充满权衡的过程，如果想在某方面取得提升，往往需要在另一方面作出妥协。例如，链表相较于数组，在数据添加和删除操作上更加便捷，但牺牲了数据访问速度。图相较于链表，提供了更丰富的逻辑信息，但需要占用更大的内存空间，选择哪种思路取决于我们更看重哪个方面。