1. 简介
在本教程中，我们将介绍几种常见的数据结构，包括：
- 数组（Arrays）
- 向量（Vectors）
- 链表（Linked Lists）
- 树（Trees）
- 图（Graphs）
- 栈（Stacks）
这些数据结构在编程中非常基础且实用。我们不会聚焦于某种特定的编程语言，而是从通用的角度进行讲解，帮助读者理解它们的用途和适用场景。
2. 数组（Arrays）
数组是计算机科学中最基础的数据结构之一，它是一组连续的内存区域，每个元素都有固定的大小。
我们可以为每个元素分配一个索引（从 0 开始），通过索引快速访问数组中的任意元素。数组的访问方式通常是基于偏移量计算的，例如要访问第 n 个元素，只需将 n 乘以单个元素的大小，再加上数组的起始地址即可。
下图展示了一个一维数组中访问第 4 个元素的过程：
在编程语言中，我们通常使用 V[4] 或 V(4) 的方式来访问数组中的第 4 个元素。
2.1. 矩阵（Matrices）
矩阵是数组的一种特殊形式，它表示一个二维的数据集合。我们可以将矩阵理解为“数组的数组”。
下图展示了矩阵的结构：
第一个维度用于访问“主数组”中的子数组，第二个维度用于访问子数组中的具体元素。
例如，如果我们有一个 2D 数组 M，其中每个子数组包含 5 个元素，我们可以通过 M[1][2] 来访问第一行第二列的元素：
在内存中，矩阵是按行优先或列优先的方式线性存储的。例如，访问 M[1][2] 实际上是通过以下方式计算偏移量的：
address = matrixStart + (rowSize * rowIndex + columnIndex) * elementSize
2.2. 数组与矩阵的用途
数组是编程中最基本的数据结构之一，几乎可以用来表示任何一组有序或无序的数据集合。例如：
✅ 一组数字、字符串、城市名、任务列表等都可以用数组表示
✅ 每个数组元素可以是一个基本类型，也可以是一个复杂对象（如员工信息）
✅ 表格数据（如 Excel 表格）本质上就是二维数组
✅ 机器学习中的数据集、图像像素、线性代数运算（如矩阵乘法）都依赖数组结构
3. 图（Graphs）
图是一种非常有用的数据结构，起源于图论。图由节点（Nodes）和边（Edges）组成，节点之间通过边连接。
图中的节点和边都可以拥有属性，这些属性在图论中被称为“颜色”（color）。边可以是有向的（directed）或无向的（undirected）。
下图展示了一个包含 4 个节点的图，其中两个节点有标签“Jill”和“Jack”，边的类型包括有向边、无向边以及双向边：
图可以用来表示很多现实世界的问题，例如：
✅ 网页之间的链接关系（有向图）
✅ 社交网络中的好友关系（无向图）
✅ 地图中的路径规划（带权图）
✅ AI 中的状态转移（搜索空间）
3.1. 树（Trees）
树是图的一种特殊形式，它是一个无环的连通图。也就是说，树中任意两个节点之间只有一条唯一的路径。
下图展示了同一个树结构的两种不同画法：
树中有一个特殊的节点叫做“根节点”（root），其余节点通过边连接到根节点，形成层次结构。每个节点可以有多个子节点，但只有一个父节点。
3.2. 图的表示方法
图可以用多种方式表示，常见的包括：
1. 基于节点的表示
每个节点包含其连接的边信息。例如：
节点 1 的信息：
- 颜色：1
- 边信息：
- 边 0：指向节点 2
- 边 1：指向节点 3
- 边 2：指向节点 4
2. 基于边的表示
每条边包含两个节点的引用，以及边的属性（如权重、方向）。
边 1 -> 2 的信息：
- 类型：有向边
- 颜色：无
- 节点 1 和节点 2 的引用
3. 邻接矩阵（Adjacency Matrix）
邻接矩阵是一个 n x n 的矩阵，用于表示图中节点之间的连接关系。其中：
A[i][j] = 0：表示节点 i 和节点 j 之间没有边A[i][j] = 非零值：表示存在一条从 i 到 j 的有向边A[i][j] = 非零值 且 A[j][i] = 非零值：表示节点 i 和 j 之间存在无向边
下图是一个图及其对应的邻接矩阵：
3.3. 树与图的用途
树和图在实际开发中应用广泛：
✅ 语义网（Semantic Web）中使用图来表示实体之间的关系（RDF）
✅ AI 中的搜索算法（如 BFS、DFS）使用图来表示状态空间
✅ 游戏 AI（如井字棋）中使用树来表示所有可能的走法
✅ 函数式编程中的表达式解析可以使用树结构
✅ 化学分子结构可以用图表示，节点为原子，边为化学键
例如，下图展示了一个简单的 RDF 图：
下图展示了一个井字棋游戏的状态树：
4. 链表（Linked Lists）
链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和一个指向下一个节点的指针。
链表的基本结构如下：
链表有三种常见形式：
- 单向链表（Singly Linked List）：每个节点只指向下一个节点
- 双向链表（Doubly Linked List）：每个节点同时指向前一个和后一个节点
- 循环链表（Circular Linked List）：最后一个节点指向第一个节点
4.1. 链表表示数组与树
链表非常灵活，可以用来表示数组和树结构：
例如，一个整数数组 [0, 1, 2, 3, 4, 5] 可以用链表表示如下：
同样，树结构也可以用链表来表示：
4.2. 链表的用途
链表在插入和删除操作上具有优势，因为不需要像数组那样移动大量元素：
✅ 插入操作的时间复杂度为 O(1)（已知插入位置）
✅ 删除操作的时间复杂度也为 O(1)
✅ 适合频繁插入/删除的场景（如缓存、LRU 算法）
例如，插入一个元素到数组和链表中的操作对比：
数组插入（O(n)）：
链表插入（O(1)）：
5. 栈与队列（Stacks and Queues）
栈和队列是用于控制数据进出顺序的结构。
5.1. 栈（Stack）
栈是一种后进先出（LIFO, Last In First Out）的数据结构。每次插入（push）元素都放在栈顶，每次弹出（pop）元素也从栈顶取出。
例如，压入 5 个元素后，最后一个压入的元素最先被弹出：
5.2. 队列（Queue）
队列是一种先进先出（FIFO, First In First Out）的数据结构。每次插入（enqueue）元素放在队尾，每次取出（dequeue）元素从队头取出。
例如，将 5 个球依次入队后，第一个入队的球最先出队：
5.3. 栈与队列的用途
栈的常见用途：
✅ 实现“撤销”功能（Undo）
✅ 递归调用中的上下文保存（调用栈）
队列的常见用途：
✅ 任务调度（如打印任务排队）
✅ 广度优先搜索（BFS）中的节点访问顺序
✅ 消息队列系统（如 RabbitMQ、Kafka）
例如，递归函数调用时，栈用于保存函数上下文：
6. 总结
本文介绍了几种常见的数据结构，包括数组、矩阵、图、树、链表、栈和队列。它们各有特点，适用于不同的场景：
| 数据结构 | 插入复杂度 | 查找复杂度 | 适用场景 |
|---|---|---|---|
| 数组 | O(n) | O(1) | 静态数据、快速访问 |
| 链表 | O(1) | O(n) | 频繁插入/删除 |
| 栈 | O(1) | O(1) | 撤销操作、递归 |
| 队列 | O(1) | O(1) | 任务调度、BFS |
| 图 | 视结构而定 | 视结构而定 | 状态空间、社交网络 |
| 树 | O(log n) | O(log n) | 文件系统、搜索算法 |
选择合适的数据结构对程序的性能和可维护性至关重要。在实际开发中，应根据具体需求选择合适的数据结构，并结合时间复杂度和空间复杂度进行权衡。