一、前言
在计算机科学中，数据结构是程序设计的重要基础，也是学习算法、操作系统、数据库、计算机网络以及其他技术领域的必备知识。
在上一篇文章中，我们介绍了数据、数据元素、数据对象、数据结构等基本概念。理解这些概念之后，接下来需要进一步学习：数据在计算机中是如何组织和存储的？不同的数据结构适合解决什么问题？如何根据实际需求选择合适的数据结构？
例如：
如何快速查找大量数据？
如何实现先进先出的任务队列？
如何管理具有层级关系的数据？
如何表示网络中的设备和连接关系？
如何高效地插入、删除和访问数据？
这些问题都与数据结构密切相关。
本文将从数据结构的分类入手，逐步介绍线性表、栈、队列、树、图、哈希表等常见数据结构，并结合代码示例分析它们的特点和适用场景。
二、什么是数据结构？
数据结构是指数据元素之间的组织方式，以及数据元素在计算机中的存储方式。
简单来说，数据结构研究的是数据如何组织、如何存储，以及如何高效地操作数据。
例如，要存储一个班级中所有学生的信息，可以使用数组保存学生编号，也可以使用链表动态管理学生记录，还可以使用哈希表根据学生编号快速查找学生。
虽然它们存储的数据可能完全相同，但组织方式不同，因此在查询、插入、删除等操作上的效率也有所不同。
2.1 数据结构的组成
从逻辑和实现两个角度来看，数据结构通常涉及以下内容。
1. 逻辑结构
逻辑结构描述数据元素之间的关系，关注数据本身的组织形式，而不关心具体如何存储。
例如：
线性关系：元素之间存在前后顺序。
树形关系：元素之间存在层级关系。
网状关系：元素之间存在多对多的连接关系。
2. 存储结构
存储结构也称为物理结构，描述数据元素及其关系在计算机内存中的具体表示方式。
常见的存储方式包括：
顺序存储：将元素存放在连续的存储空间中。
链式存储：通过指针或引用连接不同的存储节点。
散列存储：通过散列函数确定元素的存储位置。
索引存储：建立索引来辅助定位数据。
3. 数据运算
数据运算是指在数据结构上执行的操作，例如：
查找
插入
删除
修改
排序
遍历
不同数据结构支持的操作及其效率不同，因此需要根据实际应用场景进行选择。
三、数据结构的分类
从逻辑结构的角度来看，常见的数据结构可以分为线性结构和非线性结构。
3.1 线性结构
线性结构中的数据元素具有一对一的逻辑关系。除首元素和尾元素外，每个元素通常都有唯一的直接前驱和直接后继。
常见的线性结构包括：
数组
链表
栈
队列
例如，一个任务列表可以按照任务进入的先后顺序排列，每个任务都处于明确的位置。
3.2 非线性结构
非线性结构中的元素不再局限于简单的前后关系，可以形成层级关系或复杂的网络关系。
常见的非线性结构包括：
树
图
堆
哈希表（从逻辑组织方式上看，通常不属于传统的线性结构）
例如，文件系统中的目录具有层级关系，适合使用树形结构表示；网络中的路由器及其链路可以使用图结构表示。
3.3 常见数据结构对比
| 数据结构 | 主要特点 | 常见应用 |
|---|---|---|
| 数组 | 连续存储，支持按下标访问 | 固定大小的数据集合 |
| 链表 | 节点通过指针连接 | 动态插入和删除 |
| 栈 | 后进先出 | 函数调用、撤销操作 |
| 队列 | 先进先出 | 任务调度、消息处理 |
| 树 | 层级关系 | 文件系统、搜索树 |
| 堆 | 满足特定优先级关系 | 优先队列、任务调度 |
| 图 | 表示复杂连接关系 | 网络拓扑、路径搜索 |
| 哈希表 | 通过哈希函数定位数据 | 字典、缓存、快速查找 |
四、数组（Array）
4.1 数组的基本概念
数组是一种将多个相同类型或相同类别的数据元素按照一定顺序组织起来的数据结构。
在许多编程语言中，数组元素存储在连续的内存空间中，因此可以通过下标快速访问指定位置的元素。
例如：
int arr[5] = {10, 20, 30, 40, 50};数组中的元素可以通过下标访问：
printf("%d", arr[2]); // 输出 30这里需要注意，C 语言数组的下标从 0 开始。
4.2 数组的特点
支持通过下标进行随机访问。
连续存储有利于提高缓存局部性。
数组的容量通常需要预先确定，动态数组则可以通过扩容机制调整容量。
在数组中间插入或删除元素时，通常需要移动其他元素。
4.3 数组的时间复杂度
| 操作 | 典型时间复杂度 |
|---|---|
| 按下标访问 | O(1) |
| 查找无序数组中的元素 | O(n) |
| 在末尾追加元素 | 固定容量数组为 O(1)，动态数组均摊 O(1) |
| 在中间插入元素 | O(n) |
| 删除中间元素 | O(n) |
数组适合需要频繁随机访问、元素数量相对稳定的场景。
五、链表（Linked List）
5.1 链表的基本概念
链表由多个节点组成，每个节点通常包含数据域和指针域。
与数组不同，链表的节点不要求存储在连续的内存空间中，而是通过指针建立节点之间的连接关系。
一个单链表节点可以表示为：
typedef struct Node { int data; struct Node *next; } Node;其中：
data：保存节点的数据。next：指向下一个节点。NULL：表示链表结束，没有后继节点。
5.2 链表的类型
单链表：每个节点只保存指向下一个节点的指针。
双向链表：每个节点同时保存前驱和后继指针。
循环链表：尾节点可以连接到头节点，形成环形结构。
5.3 链表的特点
节点可以分散存储在内存中。
在已知插入位置的节点或其前驱时，插入和删除操作可以在 O(1) 时间内完成。
访问指定位置的元素通常需要从头节点开始遍历。
相比数组，链表需要额外的指针存储空间。
需要注意：如果要先查找插入位置，查找过程仍然可能需要 O(n) 时间。因此，链表并不意味着所有插入和删除操作都很快。
5.4 数组与链表的区别
| 对比项目 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 通常连续存储 | 节点可以分散存储 |
| 随机访问 | O(1) | O(n) |
| 中间插入 | 通常需要移动元素 | 已知位置时可为 O(1) |
| 内存开销 | 通常较小 | 需要额外指针空间 |
| 缓存局部性 | 通常较好 | 通常较差 |
六、栈（Stack）
6.1 栈的基本概念
栈是一种特殊的线性数据结构，遵循后进先出（LIFO，Last In First Out）的原则。
也就是说，最后进入栈的元素最先被取出。
可以将栈理解为一摞盘子：最后放上去的盘子，通常最先被拿走。
6.2 栈的基本操作
push：入栈，将元素放入栈顶。pop：出栈，移除栈顶元素。peek或top：查看栈顶元素，但不删除。isEmpty：判断栈是否为空。
在常见的数组栈或链式栈实现中，这些基本操作通常可以在 O(1) 时间内完成。
6.3 栈的应用场景
函数调用和递归执行。
浏览器中的后退操作。
文本编辑器中的撤销操作。
括号匹配。
表达式求值。
深度优先搜索。
栈适合处理需要逆序回退、保存执行状态或按照后进先出规则处理的数据。
七、队列（Queue）
7.1 队列的基本概念
队列是一种遵循先进先出（FIFO，First In First Out）原则的线性数据结构。
先进入队列的元素先被取出，类似于排队办理业务。
7.2 队列的基本操作
enqueue：入队，在队尾添加元素。dequeue：出队，从队头移除元素。front：查看队头元素。isEmpty：判断队列是否为空。
使用循环数组或链表实现队列时，入队和出队操作通常都可以达到 O(1) 时间复杂度。
7.3 队列的常见类型
普通队列：按先进先出的顺序处理元素。
循环队列：通过循环使用数组空间，减少数组队列中的空间浪费。
双端队列：允许在队头和队尾进行插入或删除操作。
优先队列：按照优先级处理元素，而不是严格按照进入顺序处理。优先队列通常使用堆实现。
7.4 队列的应用场景
操作系统任务调度。
网络数据包排队。
消息队列。
广度优先搜索。
请求缓冲与流量管理。
例如，在网络设备中，数据包可能进入不同的队列，并按照调度策略被发送。实际网络设备的队列机制还会涉及优先级、拥塞管理和流量调度等内容。
八、树（Tree）
8.1 树的基本概念
树是一种非线性数据结构，用于表示元素之间的层级关系。
树通常由一个根节点和若干子树组成，节点之间通过边连接。
常见术语包括：
根节点：树的起始节点。
父节点：具有子节点的上层节点。
子节点：由某个节点直接连接的下层节点。
叶子节点：没有子节点的节点。
深度：节点从根节点到该节点所经过的边数。
高度：节点到最深叶子节点的最长路径所经过的边数。
8.2 二叉树
二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树的遍历方式包括：
前序遍历：根节点 → 左子树 → 右子树。
中序遍历：左子树 → 根节点 → 右子树。
后序遍历：左子树 → 右子树 → 根节点。
层序遍历：按照从上到下、从左到右的层级顺序访问节点。
8.3 二叉搜索树
二叉搜索树（BST）通常满足以下性质：
左子树中的所有键小于当前节点的键。
右子树中的所有键大于当前节点的键。
左右子树本身也满足二叉搜索树性质。
在树高度为 h 的情况下，查找、插入和删除操作通常需要 O(h) 时间。
如果树比较平衡，时间复杂度通常为 O(log n)；如果树严重倾斜，最坏情况下会退化到 O(n)。
8.4 树的应用场景
文件系统目录管理。
数据库索引。
语法分析和表达式解析。
组织架构表示。
分类检索和层级数据管理。
需要注意，二叉搜索树、平衡树、B 树和 B+ 树具有不同的性质与应用场景，不能简单地认为所有树结构的查找效率都相同。
九、堆（Heap）
9.1 堆的基本概念
堆是一种满足特定堆序性质的完全二叉树，通常通过数组实现。
常见的堆包括：
大顶堆：每个父节点的值都不小于其子节点的值。
小顶堆：每个父节点的值都不大于其子节点的值。
堆只保证父子节点之间满足堆序性质，并不保证整个数组有序。
9.2 堆的主要操作
对于通常使用数组实现的二叉堆：
| 操作 | 时间复杂度 |
|---|---|
| 查看堆顶元素 | O(1) |
| 插入元素 | O(log n) |
| 删除堆顶元素 | O(log n) |
| 建立堆 | O(n) |
9.3 堆的应用场景
优先队列。
任务优先级调度。
Top K 问题。
堆排序。
某些图算法中的最短路径计算。
当需要持续获取当前最大值或最小值时，堆通常是一种非常合适的数据结构。
十、图（Graph）
10.1 图的基本概念
图由顶点集合和边集合组成，可以表示元素之间复杂的连接关系。
图通常表示为：
G = (V, E)
其中：
V 表示顶点集合。
E 表示边集合。
根据边是否具有方向，可以分为有向图和无向图；根据边是否具有权值，可以分为带权图和无权图。
10.2 图的存储方式
邻接矩阵：
使用二维矩阵记录顶点之间是否存在边，或者记录边的权值。
优点是判断两个顶点之间是否存在边通常为 O(1)，缺点是在稀疏图中可能浪费大量空间。
邻接表：
为每个顶点维护一个邻居列表。
对于稀疏图，邻接表通常更加节省空间。使用邻接表遍历所有顶点及其邻接边的时间复杂度通常为 O(V + E)。
10.3 图的遍历
深度优先搜索（DFS）：尽可能沿着一条路径深入访问，无法继续时回溯。
广度优先搜索（BFS）：从起始顶点开始，按照距离起点的层级逐步访问邻居，通常使用队列实现。
10.4 图的应用场景
计算机网络拓扑。
路由与路径搜索。
社交网络关系分析。
地图导航。
依赖关系分析。
推荐系统中的关联关系建模。
例如，在计算机网络中，可以将路由器或交换机抽象为顶点，将设备之间的链路抽象为边，从而构建网络拓扑图，并进一步研究连通性、路径和故障影响。
十一、哈希表（Hash Table）
11.1 哈希表的基本概念
哈希表是一种利用哈希函数建立键与存储位置之间映射关系的数据结构。
例如，可以根据员工编号查找对应的员工信息，也可以根据用户名快速定位用户记录。
哈希表的核心思想是：通过哈希函数计算键对应的位置，尽量避免逐个遍历所有元素。
11.2 哈希函数
哈希函数将输入的键映射为一个哈希值，再根据表的容量等条件确定存储位置。
例如：
key = 12345 hash(key) = 某个哈希值 index = hash(key) % table_size以上只是一个简化的示意。实际实现可能使用更复杂的哈希函数和索引计算方式。
11.3 哈希冲突
不同的键可能映射到同一个存储位置，这种情况称为哈希冲突。
常见的解决方法包括：
链地址法：每个槽位维护一个链表或其他容器，存放映射到该位置的元素。
开放寻址法：当目标位置被占用时，按照特定探测规则寻找其他位置。
11.4 哈希表的特点
在哈希函数分布合理、负载因子得到控制的情况下，哈希表的查找、插入和删除操作平均时间复杂度通常为 O(1)。
但是，发生大量冲突或其他不利情况时，操作效率可能下降，最坏情况下可达到 O(n)。
11.5 哈希表的应用场景
字典和键值映射。
缓存系统。
数据去重。
统计元素出现次数。
编译器中的符号表。
用户信息与会话信息查询。
哈希表适合根据键快速定位数据，但不适合直接承担有序遍历或范围查询任务。
十二、时间复杂度与空间复杂度
学习数据结构时，不能只关注数据如何组织，还需要分析相关操作的效率。
算法复杂度通常用于描述算法执行所需的时间和额外空间如何随输入规模增长。
12.1 时间复杂度
时间复杂度描述算法执行步骤随输入规模 n 增长的变化趋势，通常使用大 O 表示法。
常见复杂度如下：
| 复杂度 | 名称 | 典型示例 |
|---|---|---|
| O(1) | 常数时间 | 数组按下标访问 |
| O(log n) | 对数时间 | 平衡搜索树查找 |
| O(n) | 线性时间 | 遍历数组 |
| O(n log n) | 线性对数时间 | 归并排序 |
| O(n²) | 平方时间 | 简单的双重循环排序 |
需要注意，大 O 表示法关注增长趋势，并不直接等于实际运行时间。常数开销、硬件环境、缓存行为和输入数据分布也会影响实际性能。
12.2 空间复杂度
空间复杂度描述算法所需空间随输入规模变化的趋势。
例如：
使用固定数量的辅助变量，额外空间通常为 O(1)。
创建一个与输入规模成正比的数组，额外空间通常为 O(n)。
递归算法的调用栈也可能占用额外空间。
在分析算法时，需要明确是否统计输入本身占用的空间，以及是否包含递归调用栈。
12.3 为什么需要关注复杂度？
假设有两个算法都能完成相同的查找任务：
算法 A：平均需要遍历一半的数据。
算法 B：利用合适的数据组织方式，将查找范围逐步缩小。
当数据量很小时，两者的差距可能不明显；当数据规模扩大到数百万条记录时，算法设计的差异可能显著影响系统性能。
因此，选择数据结构时，应综合考虑访问模式、数据规模、更新频率、内存开销和实现复杂度。
十三、如何选择合适的数据结构？
实际开发中，没有一种数据结构能够在所有场景下都表现最佳。选择时应首先分析业务需求，再确定数据组织方式。
| 需求场景 | 可以优先考虑 |
|---|---|
| 频繁通过下标访问 | 数组或动态数组 |
| 需要频繁在已知位置插入、删除 | 链表 |
| 需要后进先出 | 栈 |
| 需要先进先出 | 队列 |
| 需要按照优先级取出元素 | 堆或优先队列 |
| 需要层级组织数据 | 树 |
| 需要表示复杂连接关系 | 图 |
| 需要根据键快速查询 | 哈希表 |
| 需要有序查询或范围查询 | 平衡搜索树等有序结构 |
例如，如果需要保存大量用户信息，并且主要根据用户 ID 查询记录，可以考虑哈希表；如果需要按时间顺序处理任务，可以使用队列；如果需要持续获取优先级最高的任务，可以考虑优先队列。
实际系统还可能组合使用多种数据结构，以兼顾查询效率、更新效率和内存开销。
十四、数据结构在实际系统中的应用
数据结构并不只是算法题中的知识点，在实际软件系统中也有广泛应用。
14.1 操作系统
操作系统通过队列管理等待任务，通过栈支持函数调用，通过各种链表或树结构管理内核对象和资源。
14.2 数据库
数据库使用索引结构提高数据查询效率。例如，许多关系型数据库使用 B+ 树索引处理有序查找和范围查询，也可能使用哈希索引或其他索引结构。
14.3 计算机网络
网络设备和网络管理系统中也能找到数据结构的应用：
路由拓扑可以抽象为图。
路由查找可以使用专门的树形结构或其他高效索引。
报文缓冲与任务调度可能使用队列。
配置和状态查询可以使用哈希表。
网络设备中的实际转发和调度实现还会受到硬件架构、协议要求及资源限制的影响。
理解数据结构，有助于从底层机制理解系统为什么能够高效处理大量数据。
