第1章 绪论
　　本章阐述本书的目的和目标，并简要介绍学习本书所需要的数学知识，我们将要学习到：
　　数据结构的内容
　　学习数据结构的意义
　　本书其余部分所需要的基本的数学知识
　　1.1 几个实际问题
　　1.1.1 学生成绩表管理
　　学生的成绩数据如表1.1所示。
　　表1.1 学生成绩表(单位：分)
　　我们把表1.1称为一个数据结构（线性表），表中的每一行是一个节点（或记录），它由学号、姓名、各科成绩及平均成绩等数据项组成。
　　接下来的问题是如何快速根据成绩确定其中第 k 名是谁。我们将之称为选择问题(selection problem)。大多数学习过一两门程序设计课程的学生写一个解决这种问题的程序不会有什么困难，因为显而易见的解决方法就有很多。
　　该问题的一种解法就是将这 n 个元素读进一个数组中，通过某种简单的算法，如冒泡排序法，以递减顺序将数组排序，然后返回位置 k 上的元素。
　　稍好一点的算法可以先把前 k 个元素读入数组（以递减的顺序）并对其进行排序。然后，将剩下的元素再逐个读入，当新元素被读到时，如果它小于数组中的第 k 个元素则忽略，否则将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组。当算法终止时，位于第 k 个位置上的元素作为答案返回。
　　这两种算法编码都很简单，建议读者进行尝试。此时自然要问：哪种算法更好？哪种算法更重要？还是两种算法都足够好？使用含有100万个元素的随机文件，在 k =50000的条件下进行模拟，可以发现，两种算法都不能在合理的时间内结束；两种算法都需要计算机处理若干天才能算出（虽然*后还是给出了正确的答案）。在第7章中将讨论另外一种算法，该算法将在1s 左右给出问题的解。因此，虽然前面提到的两种算法都能计算出结果，但是不能认为它们是好的算法，要想在合理的时间内完成大量输入数据的处理，用这两种算法是不切实际的。
　　1.1.2 人机对弈
　　计算机之所以能和人对弈是因为有人事先已将对弈的策略存入计算机。由于对弈的过程是在一定规则下随机进行的，所以为使计算机能灵活对弈，必须将对弈过程中所有可能发生的情况以及相应的对策都考虑周全，并且一个好的棋手，在对弈时不仅要看棋盘当时的状态，还要能预测棋局发展的趋势，甚至是*后的结局。在对弈问题中，计算机的操作对象是对弈过程中可能出现的棋盘状态——格局，格局之间的关系是由对弈规则决定的。
　　以井字棋(tic-tac-toe)为例，井字棋是一种在3×3格子上进行的连珠游戏，和五子棋类似，由于棋盘一般不画边框，格线排成井字故得名。游戏规则是：由分别代表 O 和×的两个游戏者轮流在格子里留下标记（一般来说先手者为×），任意三个相同标记形成一条直线，则为获胜。图1.1是井字棋的一个格局，从当前格局可以派生出五个格局，这种格局之间的关系可以用树的数据结构来描述。如果将对弈开始到结束的过程中可能出现的格局都画在一张图上，则可得到一棵倒长的树。树根是对弈开始之前的棋盘格局，而所有的叶子就是可能出现的结局，对弈的过程就是从树根沿树杈到某个叶子的过程。树可以是某些非数值计算问题的数学模型，它也是一种数据结构。
　　图1.1 一个井字棋游戏中的格局
　　1.1.3 路径导航
　　在交通网络中经常会遇到这样的问题：两地之间是否有公路可通？在有多条公路可通的情况下，哪一条路径是*短的？
　　图1.2是广州城市的简化图，假如某人从新城东出发，前往机场，如果各点之间的距离已知，找到一条*短的路径显然是*佳策略。要做到这一点，就需要用到图的数据结构和*短路径算法。除了路径导航问题，在供暖、供气、供电、供水管道的设计和公路建设中，为了节省费用也需要用到这种算法。
　　图1.2 广州城市的简化图
　　在许多问题当中，一个重要的观念是：写出一个可以工作的程序并不够，如果这个程序在巨大的数据集上运行，那么运行效率就变成了重要的问题。读者将在本书中看到对于大量的输入如何估计程序的运行时间，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。读者还将学到提升程序速度以及确定程序瓶颈的方法。这些方法将使读者能够找到需要大力优化的代码段。
　　1.2 本书主要讨论内容
　　1.2.1 数据结构的主要内容
　　数据结构定义：数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。精心选择的数据结构可以带来更高的运行或者存储效率，因此，数据结构往往与高效的检索算法和索引技术有关。数据结构在计算机科学界至今没有标准的定义，个人根据各自的理解的不同而有不同的表述方法。
　　Sahni 在他的《数据结构、算法与应用——C++语言描述》一书中称：数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。Shaffer 在《数据结构与算法分析（C++版）》一书中的定义是：数据结构是抽象数据类型（abstract data type，ADT）的物理实现。
　　1.2.2 学习数据结构的意义
　　有人说：如果对编程思想不理解，哪怕会一千种语言，也写不出好的程序。数据结构和算法讲授的是编程的思想，学习它的意义可以从两个方面来讲。
　　1.技术层面
　　数据结构是编程*重要的基本功之一。“数据结构”课程并不涵盖编程的语法，而是提供解决问题的思路，这些思路是众多科学家智慧的结晶，适用于所有编程语言，在编程遇到运行效率上的瓶颈时，或是在接到一个任务，需要评估这个任务能否实现时，这些前人的方案就可以提供参考。例如，拧螺母时，可以用扳手，也可以用钳子，学习数据结构可以了解已有哪些工具、这些工具各有什么利弊、应用于什么场景，知道究竟该用扳手还是钳子。
　　例如，涉及后进先出的问题有很多，函数递归就是个栈模型，Android 的屏幕跳转就用到栈。对于很多类似的问题，学了栈之后，就会第一时间想到可以用栈实现这些功能。
　　例如，有多个网络下载任务，该怎么去调度它们去获得网络资源呢？再如，对于操作系统的进程（线程）调度，该怎么去分配资源[如中央处理器（centralprocessing unit，CPU）]给多个任务呢？肯定不能全部同时拥有，资源只有一个，那就要排队。对于先进先出要排队的问题，学了队列之后，就会想到要用队列。那么怎么排队呢？对于那些优先级高的线程怎么办？这时就会想到优先队列。
　　以后实践的过程中会发现这些基础的工具也存在一些缺陷，在不满足于这些工具后，就会开始在这些数据结构的基础上加以改造，这就称为自定义数据结构，以后还可以造出很多其他应用于实际场景的数据结构。
　　2.抽象层面
　　学习数据结构和算法会扩展视野，比如，平时编程中用到数组，如果不懂数据结构和算法，就只能认识到数组只是存储一系列有序元素的集合，但是学习了数据结构就会对数组的认识更加深刻。
　　学习数据结构和算法能够指导如何将数据组织起来。例如，若想把家谱管理起来，就需要对家谱数据进行抽象，将数据分解成树状结构的节点，但是计算机无法理解人的抽象，计算机中只有0和1，某个节点和其他节点的关系如何互相得到，这是程序员要做的，也是数据结构要介绍的。因此，了解数据结构，对选择程序结构、选择方案、提出解决方法都有很大帮助。
　　学习数据结构能够帮助提高解决问题的能力。学习数据结构也是学习如何将物理世界里的信息变成计算机世界里的数据，并且是高效存储、快速检索数据的过程，是一个树立计算思维的过程。计算思维是指运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。当必须求解一个特定的问题时，首先会问：解决这个问题有多困难？怎样才是*佳的解决方法？数据结构就是准确地回答这些问题的理论基础。
　　1.3 数学知识复习
　　本节列出一些需要记住或者能够推导出的基本公式，复习基本的证明方法。
　　1.3.1 指数
　　具体公式如下：
　　1.3.2 对数
　　在计算机科学中，除非有特别的声明，所有的对数都是以2为底的。
　　定义1.1 XA = B，当且仅当 logX B = A。
　　由该定义可以得到几个方便的等式。
　　定理1.1
　　证明：
　　令，以及。此时由对数的定义得：CX = B，CY = A 以及 AZ = B。联合这三个等式则产生(CY )Z = B = CX。此时 X = Y Z，这意味着 Z =XY，定理1.1得证。
　　定理1.2 logAB = logA + logB
　　证明：令 X = log A， Y = logB，以及 Z = logAB。此时由于假设默认的底数为2，2X = A，2Y = B 及2Z = AB。联合后面的三个等式则有。因此 X + Y = Z，这就证明了该定理。
　　其他一些有用的公式如下，它们都能够用类似的方法推导：
　　1.3.3 级数
　　*容易记忆的公式是
　　在第二个公式中，如果0< A <1，则

目录
前言
第1章 绪论 1
1.1 几个实际问题 1
1.1.1 学生成绩表管理 1
1.1.2 人机对弈 2
1.1.3 路径导航 3
1.2 本书主要讨论内容 3
1.2.1 数据结构的主要内容 3
1.2.2 学习数据结构的意义 4
1.3 数学知识复习 5
1.3.1 指数 5
1.3.2 对数 5
1.3.3 级数 6
1.3.4 模运算 8
1.3.5 证明方法 8
1.4 总结 11
第2章 算法分析 12
2.1 数学基础 12
2.2 模型 15
2.3 要分析的问题 15
2.4 算法的运行时间计算 19
2.4.1 一个简单的例子 19
2.4.2 一般法则 20
2.4.3 *大子序列和问题的解 23
2.4.4 运行时间中的对数 28
2.4.5 检验结果 32
2.4.6 分析结果的准确性 33
2.4.7 算法的存储空间计算 34
2.5 总结 34
第3章 线性表 35
3.1 抽象数据类型 35
3.2 线性表的逻辑特性 36
3.2.1 定义 36
3.2.2 特征 36
3.2.3 运算 36
3.3 顺序表及其实现 37
3.3.1 顺序表 37
3.3.2 表的简单数组实现 38
3.3.3 ArrayList的实现 38
3.4 链表及其实现 42
3.4.1 链表的思想 42
3.4.2 单向链表 43
3.4.3 单向链表ADT 44
3.4.4 常见的错误 48
3.4.5 模块化设计 48
3.4.6 双向链表 49
3.4.7 循环链表 51
3.5 链表应用实例 54
3.5.1 一元多项式 54
3.5.2 音乐播放列表排序 59
3.5.3 多重表 62
3.6 总结 63
第4章 栈和队列 64
4.1 栈 64
4.1.1 栈的定义 64
4.1.2 栈ADT 65
4.1.3 栈的顺序表示 65
4.1.4 栈的链接表示 67
4.2 表达式计算 68
4.2.1 表达式 68
4.2.2 计算后缀表达式的值 69
4.2.3 中缀表达式转换为后缀表达式 71
4.2.4 利用两个栈计算表达式 72
4.3 递归 76
4.3.1 递归的概念 76
4.3.2 递归的实现 81
4.4 队列 83
4.4.1 队列ADT 83
4.4.2 队列的数组实现 84
4.4.3 队列数组实现的改进 86
4.4.4 循环队列 87
4.4.5 循环队列的应用 90
4.4.6 队列的链接表示 90
4.4.7 舞伴问题 92
4.5 总结 93
第5章 矩阵 95
5.1 矩阵的二维数组存储 95
5.2 特殊矩阵的压缩存储 97
5.2.1 稠密矩阵和稀疏矩阵 97
5.2.2 对称矩阵 97
5.2.3 三角矩阵 98
5.2.4 带状矩阵 100
5.3 稀疏矩阵的压缩存储 101
5.3.1 三元组顺序表存储 102
5.3.2 行逻辑链接的顺序存储 107
5.3.3 十字链表 112
5.3.4 稀疏矩阵的并行运算 120
5.4 总结 121
第6章 查找和散列表 122
6.1 查找方法 122
6.1.1 顺序表的查找 122
6.1.2 有序表的查找 125
6.1.3 索引顺序表的查找 129
6.1.4 散列表的查找 130
6.2 散列表 131
6.2.1 基本思想 131
6.2.2 构造散列函数的原则 131
6.3 常见散列函数 132
6.3.1 直接定址法 132
6.3.2 数字分析法 132
6.3.3 平方取中法 133
6.3.4 折叠法 133
6.3.5 除留余数法 134
6.4 解决散列函数冲突的方法 134
6.4.1 拉链法 135
6.4.2 开放地址法 135
6.4.3 装填因子 139
6.4.4 再散列 139
6.5 散列表的查找 141
6.5.1 散列表的实现 141
6.5.2 性能分析 146
6.6 总结 147
第7章 排序 148
7.1 基本概念 148
7.2 插入排序 149
7.2.1 直接插入排序 149
7.2.2 对直接插入排序的分析 151
7.2.3 希尔排序 152
7.2.4 对希尔排序的分析 154
7.3 交换排序 154
7.3.1 冒泡排序 154
7.3.2 对冒泡排序的分析 156
7.3.3 快速排序 156
7.3.4 实际的快速排序程序 158
7.3.5 对快速排序的分析 160
7.4 选择排序 160
7.4.1 算法实现 161
7.4.2 效率分析 161
7.5 归并排序 162
7.5.1 二路归并排序 162
7.5.2 对归并排序的分析 164
7.6 基数排序 165
7.6.1 多关键字的排序 165
7.6.2 链式基数排序 166
7.6.3 对基数排序的分析 168
7.7 外部排序 171
7.7.1 外部排序的概念 171
7.7.2 简单算法 171
7.7.3 多路合并 172
7.7.4 多相合并 173
7.7.5 替换选择 175
7.8 ArrayList与LinkedList中的排序方法 176
7.8.1 ArrayList中的排序方法 176
7.8.2 LinkedList中的排序方法 176
7.9 总结 178
第8章 树 180
8.1 树的基础知识 180
8.1.1 基本术语 180
8.1.2 树的ADT 182
8.1.3 树的表示 184
8.1.4 树的实现 184
8.2 树的遍历 185
8.2.1 前序遍历 186
8.2.2 后序遍历 188
8.3 二叉树 190
8.3.1 二叉树基本概念 190
8.3.2 二叉树的性质 194
8.3.3 二叉树的实现 196
8.3.4 二叉树的遍历方法以及非递归实现 198
8.3.5 表达式树 205
8.3.6 哈夫曼树 212
8.3.7 决策树 220
8.4 二叉查找树 223
8.4.1 二叉查找树的概念 223
8.4.2 查找操作 225
8.4.3 插入操作 227
8.4.4 删除操作 228
8.4.5 性能分析 231
8.5 二叉平衡树 233
8.5.1 二叉平衡树的概念 233
8.5.2 平衡化策略 235
8.5.3 平衡树的实现 242
8.6 其他一些树 248
8.6.1 伸展树 248
8.6.2 B-树 249
8.6.3 红黑树的概念 254
8.6.4 红黑树的实现 256
8.7 总结 263
第9章 优先队列（堆） 265
9.1 基本概念和简单实现 265
9.2 二叉堆 266
9.2.1 堆ADT 268
9.2.2 基本的堆操作 268
9.3 d-堆 273
9.4 左式堆 274
9.4.1 左式堆的性质 274
9.4.2 左式堆的操作 275
9.5 斜堆 280
9.6 二项队列 282
9.6.1 二项队列的结构 282
9.6.2 二项队列的操作 283
9.6.3 二项队列的实现 286
9.7 优先队列的应用 291
9.7.1 堆排序 291
9.7.2 选择问题 293
9.7.3 事件模拟 294
9.8 总结 295
第10章 图论算法 296
10.1 图的基本概念 296
10.1.1 定义与术语 297
10.1.2 图ADT 300
10.2 图的存储 300
10.2.1 矩阵表示法 300
10.2.2 邻接矩阵表示法的实现 303
10.2.3 邻接表表示法 305
10.2.4 邻接表表示法的实现 306
10.3 图的遍历 308
10.3.1 广度优先遍历 308
10.3.2 深度优先遍历 311
10.3.3 图的连通性 314
10.4 拓扑排序 316
10.4.1 AOV网络 316
10.4.2 拓扑排序的概念 317
10.4.3 拓扑排序算法及其实现 318
10.5 关键路径 320
10.5.1 AOE网络 320
10.5.2 关键路径的概念 321
10.5.3 关键路径算法及其实现 323
10.6 *小代价生成树 325
10.6.1 *小代价生成树的概念 325
10.6.2 Prim算法 326
10.6.3 Kruskal算法 329
10.7 *短路径问题 333
10.7.1 问题描述 333
10.7.2 Dijkstra算法 334
10.7.3 Floyd算法 338
10.8 总结 341
参考文献 342
附录 343