数据结构图解

1.初学者友好：专为在校学生、应届毕业生及新手程序员打造，避开复杂数学，轻松入门数据结构。
2.内容循序渐进：覆盖初级到部分中级数据结构，从基础概念到实际应用，逐步深入讲解。
3.实践导向：每种数据结构均配 Python 实现示例，边学边练，快速掌握实践技能。
4.性能分析透彻：考虑数据结构操作的时间和内存需求，助力编写代码。
5.知识体系完整：介绍数组、链表、栈、树、图等多种数据结构，构建系统知识架构。

本书旨在向读者介绍最重要且广泛使用的数据结构，帮助他们理解这些数据结构的应用案例以及如何在编程中充分发挥它们的作用。书中不仅介绍了基本的数组、链表、栈和优先队列的实现，以及更高级的数据结构，比如散列表和散列函数的使用，用于加速搜索，还探讨了与其相关的风险。此外，读者还将学习如何使用树和二叉查找树（BST）来组织数据，以及如何使用图来建模和处理复杂的数据。书中的内容旨在引导初学者，无须具备高深的数学知识，只需掌握高中水平的数学即可开始学习。每种数据结构都配有Python实现示例，使读者能够立即开始实践所学的知识。此外，本书还考虑了数据结构操作的时间和内存需求，以帮助读者在编写代码时选择最佳的数据结构解决方案。最终，读者将了解数据结构的权衡取舍以及如何避免潜在的问题，以便利用数据结构的强大功能来编写更高效的代码。

马尔切洛·拉·罗卡（Marcello La Rocca），一名研究科学家和全栈工程师，为Twitter、Microsoft和Apple创建大规模Web应用程序和机器学习基础设施做出了贡献，详见https://www.linkedin.com/in/marcellolarocca/。

第1 章 数据结构简介：为什么要学
数据结构 ............................................. 1
1.1 欢迎阅读本书 ........................................... 1
1.1.1 数据结构无处不在 ........................ 2
1.1.2 人人可学数据结构 ........................ 2
1.2 什么是数据结构 ....................................... 2
1.3 为什么应该关注数据结构 ........................ 4
1.3.1 什么时候需要数据结构 ................ 5
1.3.2 我将来需要编写代码来实现这
些数据结构吗 ............................... 7
1.3.3 到底应该怎样选择数据结构 ......... 7
1.4 在实际项目中应该如何使用数据结构 ..... 8
1.4.1 以心智模型教你用数据结构 ......... 8
1.4.2 数据结构的应用实例 ................... 10
1.5 要点回顾 .................................................. 13
第2 章 静态数组：创建你的第一个
数据结构 ............................................ 14
2.1 什么是数组 .............................................. 14
2.1.1 什么时候需要使用数组 ............... 15
2.1.2 定义：尺寸固定型与尺寸可变
型 ................................................. 16
2.1.3 值及其索引 .................................. 18
2.1.4 初始化 .......................................... 18
2.2 Python 中的数组 ...................................... 19
2.2.1 Python 中的list 类与
array.array 类 ......................... 20
2.2.2 索引设定 ...................................... 21
2.3 数组中的操作 ...................................... 21
2.3.1 无序数组类 .................................. 22
2.3.2 添加新元素 .................................. 23
2.3.3 删除某个元素 .............................. 24
2.3.4 查找某个值 .................................. 25
2.3.5 遍历.............................................. 25
2.4 数组的实际应用 ...................................... 26
2.4.1 数据统计 ...................................... 26
2.4.2 （藏品）集合 .............................. 28
2.4.3 多维数组 ...................................... 29
2.5 要点回顾 .................................................. 29
第3 章 有序数组：查找更快，但需
付出代价 ............................................ 30
3.1 有序数组的意义何在 .............................. 30
3.2 实现有序数组 .......................................... 31
3.2.1 插入.............................................. 32
3.2.2 删除.............................................. 34
3.2.3 线性查找 ...................................... 35
3.2.4 二分查找 ...................................... 36
3.3 要点回顾 .................................................. 38
第4 章 大O 记号：衡量算法性能的
准则体系 ............................................ 39
4.1 如何选择最佳方案 .................................. 39
4.1.1 剖面分析 ...................................... 40
4.1.2 渐近分析 ...................................... 41
4.1.3 应该选择哪种方案 ....................... 41
4.2 大O 记号 ................................................. 41
4.2.1 随机存取机（RAM）模型 .......... 41
4.2.2 增长速率 ...................................... 42
4.2.3 常见的函数量级 .......................... 44
4.2.4 真实世界里的增长速率 ............... 45
4.2.5 大O 算术 ..................................... 47
4.2.6 最坏情况分析、平均情况分析
及分摊分析 .................................. 49
4.2.7 资源衡量 ...................................... 50
4.3 渐近分析实例 .......................................... 51
4.3.1 线性查找 ...................................... 51
4.3.2 二分查找 ...................................... 52
4.4 要点回顾 ................................................. 54
第5 章 动态数组：处理尺寸可变的
数据集合 ............................................ 55
5.1 静态数组的局限性 .................................. 55
5.1.1 尺寸固定 ...................................... 56
5.1.2 权衡利弊 ...................................... 57
5.2 如何增加数组长度 .................................. 58
5.3 获奖作品展示柜 ...................................... 58
5.3.1 策略1：每次增加1 个单元 ........ 59
5.3.2 策略2：按固定量增加单元数 .... 60
5.3.3 策略3：容量加倍 ....................... 60
5.3.4 策略对比 ...................................... 61
5.3.5 将各种增加策略用于数组 ........... 62
5.4 数组需要进行缩减吗 .............................. 63
5.4.1 删除后减半 .................................. 64
5.4.2 更明智的缩减 .............................. 65
5.5 实现动态数组 .......................................... 65
5.5.1 DynamicArray 类 ......................... 66
5.5.2 插入 ............................................. 66
5.5.3 查找 ............................................. 68
5.5.4 删除 ............................................. 69
5.6 要点回顾 ................................................. 70
第6 章 链表：易于变通的动态集合 .......... 71
6.1 链表与数组 .............................................. 71
6.1.1 链表的底层机制 .......................... 72
6.1.2 对比数组与链表 .......................... 72
6.2 单链表 ..................................................... 73
6.2.1 订单管理 ...................................... 74
6.2.2 实现单链表 .................................. 75
6.2.3 插入 ............................................. 76
6.2.4 查找 ............................................. 78
6.2.5 删除 ............................................. 80
6.2.6 从表首删除元素 .......................... 81
6.3 有序链表 ................................................. 82
6.3.1 在链表里面插入 .......................... 82
6.3.2 能否改进查找操作的性能 ........... 83
6.4 双链表 ..................................................... 83
6.4.1 链接双倍，乐趣翻倍 ................... 84
6.4.2 折返的重要性 .............................. 85
6.4.3 插入 ............................................. 86
6.4.4 查找与遍历 .................................. 88
6.4.5 删除 ............................................. 88
6.4.6 拼接两个链表 .............................. 89
6.5 循环链表 ................................................. 90
6.5.1 循环链表实例 .............................. 90
6.5.2 实现技巧 ...................................... 92
6.6 要点回顾 ................................................. 93
第7 章 抽象数据类型：设计最简单的
容器——袋 ....................................... 94
7.1 抽象数据类型与数据结构 ....................... 94
7.1.1 定义 ............................................. 95
7.1.2 数组与链表：抽象数据类型
还是数据结构 .............................. 96
7.1.3 又一个实例：照明开关 ............... 97
7.2 容器 ......................................................... 99
7.2.1 什么是容器 .................................. 99
7.2.2 什么不是容器 ............................ 100
7.2.3 容器的主要特征 ........................ 100
7.3 最简单的容器：袋 ................................ 101
7.3.1 袋的定义 .................................... 101
7.3.2 袋的应用实例 ............................ 102
7.3.3 袋的实现 .................................... 104
7.4 要点回顾 ................................................ 106
第8 章 栈：处理数据之前先将其
叠放起来 .......................................... 108
8.1 栈作为抽象数据类型 ............................. 108
8.1.1 栈与后进先出策略 ..................... 109
8.1.2 栈的操作 .................................... 109
8.1.3 栈的应用实例 ............................ 110
8.2 栈作为数据结构 .................................... 111
8.2.1 以静态数组存储栈的数据 ......... 112
8.2.2 以动态数组存储栈的数据 ......... 112
8.2.3 链表与栈 .................................... 113
8.3 栈的链表实现 ........................................ 114
8.3.1 入栈 ............................................ 115
8.3.2 出栈 ............................................ 115
8.3.3 查看 ............................................ 116
8.4 理论与现实 ............................................ 117
8.5 栈的更多应用 ........................................ 119
8.5.1 调用栈 ........................................ 120
8.5.2 表达式求值 ................................ 121
8.5.3 撤销/重做 ................................... 122
8.5.4 折返 ............................................ 122
8.6 要点回顾 ................................................ 123
第9 章 队列：按抵达次序留存信息 ........ 124
9.1 队列作为抽象数据类型 ......................... 124
9.1.1 先进先出策略 ............................ 124
9.1.2 队列的操作 ................................ 125
9.1.3 队列的应用实例 ......................... 126
9.2 队列作为数据结构 ................................ 128
9.2.1 以链表实现队列 ......................... 129
9.2.2 以静态数组实现队列 ................. 130
9.2.3 实现方案对比 ............................ 133
9.3 队列的实现 ............................................ 133
9.3.1 底层静态数组 ............................ 134
9.3.2 入队............................................ 136
9.3.3 出队............................................ 138
9.4 用动态数组会如何 ............................. 140
9.5 队列的更多应用 .................................... 141
9.5.1 消息传送系统 ............................ 142
9.5.2 Web 服务器 ................................ 142
9.5.3 操作系统 .................................... 142
9.6 要点回顾 ................................................ 143
第10 章 优先级队列和堆：根据优先级
处理数据 ........................................ 144
10.1 引入优先级来拓展队列 ....................... 144
10.1.1 处理漏洞（以改进方式） ..... 145
10.1.2 优先级队列的抽象数据
类型 ........................................ 146
10.2 优先级队列作为数据结构 ................... 147
10.2.1 有序链表和有序数组 ............. 147
10.2.2 无序链表和无序数组 ............. 148
10.2.3 性能概览 ................................ 148
10.2.4 偏序 ........................................ 149
10.3 堆 ......................................................... 149
10.3.1 特殊的树结构 ........................ 150
10.3.2 堆的其他性质 ........................ 151
10.3.3 堆的性能 ................................ 152
10.3.4 最大堆和最小堆 ..................... 152
10.4 实现堆 ................................................. 153
10.4.1 如何存储堆 ............................ 153
10.4.2 构造函数、优先级及辅助
方法 ........................................ 154
10.4.3 插入 ........................................ 155
10.4.4 取顶 ........................................ 158
10.4.5 堆化 ........................................ 161
10.5 优先级队列的应用实例 ....................... 163
10.6 要点回顾 .............................................. 165
第11 章 二叉查找树：寻求平衡的
容器 ................................................ 166
11.1 树的构成要素 ...................................... 166
11.1.1 树的定义 ................................ 167
11.1.2 从链表到树 ............................ 168
11.1.3 二叉树 .................................... 169
11.1.4 树的若干应用 ........................ 169
11.2 二叉查找树 .......................................... 170
11.2.1 次序很重要 ............................ 170
11.2.2 类定义和构造函数 ................. 171
11.2.3 查找 ........................................ 171
11.2.4 寻找最大值和最小值 ............. 173
11.2.5 插入 ........................................ 174
11.2.6 删除 ........................................ 176
11.2.7 所有情况的整合 ..................... 179
11.2.8 遍历 ........................................ 180
11.2.9 前邻与后邻 ............................ 180
11.3 平衡树 ................................................. 182
11.3.1 二叉查找树的应用实例 ......... 182
11.3.2 敌手型插入序列 ..................... 183
11.3.3 删除操作会使树失衡 ............. 184
11.3.4 调整树的平衡 ........................ 184
11.4 要点回顾 .............................................. 185
第12 章 字典与散列表：如何构建和
使用关联式数组 ........................... 186
12.1 字典问题 .............................................. 186
12.1.1 删除重复项 ............................ 187
12.1.2 字典抽象数据类型 ................. 188
12.2 实现字典的数据结构 .......................... 189
12.2.1 数组 ........................................ 189
12.2.2 链表 ........................................ 189
12.2.3 平衡二叉查找树 ..................... 190
12.2.4 对比总结 ................................ 190
12.3 散列表 ................................................. 190
12.3.1 新的索引方案 ........................ 191
12.3.2 索引操作的开销 .................... 192
12.3.3 理想模型的问题 .................... 192
12.4 散列 ..................................................... 193
12.4.1 散列函数 ................................ 194
12.4.2 除余法 .................................... 195
12.4.3 乘截法 .................................... 195
12.5 解决冲突 ............................................. 196
12.5.1 结链 ....................................... 197
12.5.2 开放式定址 ............................ 199
12.5.3 开放式定址存在的问题 ......... 200
12.5.4 使用散列会带来的风险 ......... 201
12.6 要点回顾 ............................................. 202
第13 章 图：学会如何对数据中的
复杂关系进行建模....................... 204
13.1 什么是图 ............................................. 204
13.1.1 图的定义 ................................ 205
13.1.2 好友图 .................................... 206
13.1.3 有向图与无向图 .................... 206
13.1.4 有环图与无环图 .................... 207
13.1.5 连通图和连通分量 ................ 208
13.1.6 作为图的树 ............................ 210
13.2 图的实现 ............................................. 210
13.2.1 邻接表 .................................... 210
13.2.2 邻接矩阵 ................................ 213
13.3 图搜索 ................................................. 214
13.3.1 寻找好友 ................................ 214
13.3.2 广度优先搜索 ........................ 215
13.3.3 深度优先搜索 ........................ 218
13.4 未来可期 ............................................. 220
13.5 要点回顾 ............................................. 221