算法与数据结构

算法是每个计算机应用程序的核心。算法学是计算机科学的一个崭新、活跃的领域。每位计算机科学家和专业程序员都应该熟悉算法的基本工具包；即有效组织和检索数据的结构。常用的算法；用于建模、理解并求解算法问题的基本技术。
梅霍内、桑德斯编著的《算法与数据结构》内容精炼，强调了学生和专业人员必须熟悉的编程和基本数学语言，包括了数组与链表、散列表与关联数组、排序与选择、优先队列、有序序列、图的表示、图的遍历、最短路径、最小生成树和优化等章节。本书首先提出问题，然后进行分析说明，最后给出问题的解决方案，在讲解过程中，不仅给出清晰的定义，丰富的示例和练习，而且还采用插图和伪代码来解释算法，再用真正的编程语言(如C++和Java)高效实现算法。
《算法与数据结构》是作者多年的本科生和研究生算法课程的经验荟萃，非常适合作为算法与数据结构课程的教材。

第1章 开胃菜： 整数运算1
1.1 加法2
1.2 乘法： 学校方法2
1.3 结果检查5
1.4 递归版的学校方法6
1.5 Karatsuba乘法7
1.6 算法工程9
1.7 程序10
1.8 引理1.5和定理1.7的证明13
1.9 实现提示14
1.9.1 C++14
1.9.2 Java14
1.10 历史注释与进一步的读物15
第2章 概述16
2.1 渐近表示法16
2.2 机器模型19
2.2.1 外部存储器20
2.2.2 并行处理21
2.3 伪代码21
2.3.1 变量和基本数据类型21
2.3.2 语句23
2.3.3 过程与函数23
2.3.4 面向对象25
2.4 设计正确的算法和程序25
2.4.1 断言和不变量26
2.4.2 循环不变量26
2.4.3 数据结构不变量27
2.4.4 验证算法27
2.5 一个示例： 二分查找27
2.6 基本算法分析29
2.6.1 求和29
2.6.2 递推30
2.6.3 全局参数33
2.7 平均情况分析33
2.7.1 递增计数器33
2.7.2 从左到右的最大值34
2.7.3 线性搜索35
2.8 随机算法36
2.8.1 形式模型37
2.8.2 Las Vegas和Monte Carlo算法38
2.9 图39
2.9.1 第一个图算法41
2.9.2 树41
2.9.3 有序树42
2.10 P与NP43
2.11 实现提示45
2.11.1 C++45
2.11.2 Java46
2.12 历史注释与进一步的读物46
第3章 用数组与链表表示序列47
3.1 链表48
3.1.1 双链表48
3.1.2 单链表51
3.2 无界数组52
3.2.1 无界数组的平摊分析： 全局参数53
3.2.2 无界数组的平摊分析： 局部参数55
3.2.3 二进制计数器的平摊分析55
3.3？* 平摊分析56
3.3.1 平摊分析： 势能方法或银行账户方法57
3.3.2 势能方法的普遍性58
3.4 栈与队列58
3.5 链表与数组60
3.6 实现提示61
3.6.1 C++61
3.6.2 Java62
3.7 历史注释与进一步的读物62
第4章 散列表与关联数组64
4.1 链接法散列66
4.2 通用散列67
4.3 线性探测散列71
4.4 链接法与线性探测法72
4.5 ？*完全散列73
4.6 实现提示75
4.6.1 C++76
4.6.2 Java76
4.7 历史注释与进一步的读物76
第5章 排序与选择78
5.1 简单排序80
5.2 归并排序--O(nlogn)的排序算法81
5.3 下界83
5.4 快速排序85
5.4.1 分析85
5.4.2 细化87
5.5 选择89
5.6 打破下界91
5.7 外部排序93
5.7.1 多路归并94
5.7.2 采样排序94
5.8 实现提示96
5.8.1 C/C++97
5.8.2 Java97
5.9 历史注释与进一步的读物97
第6章 优先级队列99
6.1 二叉堆100
6.2 可寻址的优先级队列104
6.2.1 配对堆104
6.2.2 斐波那契堆106
6.3 外部存储器109
6.4 实现提示110
6.4.1 C++110
6.4.2 Java110
6.5 历史注释与进一步的读物111
第7章 有序序列112
7.1 二叉搜索树113
7.2 (a,b)-树与红黑树115
7.3 更多的操作121
7.3.1 连接121
7.3.2 拆分122
7.4 更新操作的平摊分析123
7.5 增强搜索树124
7.5.1 父指针125
7.5.2 子树大小125
7.6 实现提示126
7.6.1 C++127
7.6.2 Java127
7.7 历史注释与进一步的读物128
第8章 图的表示130
8.1 无序的边序列131
8.2 邻接数组--静态图132
8.3 邻接表--动态图132
8.4 邻接矩阵表示133
8.5 隐式表示134
8.6 实现提示134
8.6.1 C++135
8.6.2 Java135
8.7 历史注释与进一步的读物135
第9章 图的遍历137
9.1 广度优先搜索137
9.2 深度优先搜索139
9.2.1 DFS编号、完成时间和拓扑排序140
9.2.2 强连通分量142
9.3 实现提示147
9.3.1 C++147
9.3.2 Java148
9.4 历史注释与进一步的读物148
第10章 最短路径149
10.1 从基本概念到遗传算法150
10.2 有向无环图153
10.3 非负边代价(Dijkstra算法)153
10.4 ？*Dijkstra算法的平均情况分析156
10.5 单调整数优先级队列157
10.5.1 桶队列157
10.5.2 ？*基数堆158
10.6 任意边代价(Bellman-Ford算法)161
10.7 所有点对最短路径和节点的势162
10.8 最短路径查询163
10.8.1 目标定向搜索164
10.8.2 等级166
10.8.3 中转节点路线166
10.9 实现提示167
10.9.1 C++167
10.9.2 Java167
10.10 历史注释与进一步的读物168
第11章 最小生成树169
11.1 割和环的性质170
11.2 Jarník-Prim算法171
11.3 Kruskal算法172
11.4 并-查数据结构173
11.5 ？*外部存储器176
11.5.1 Semiexternal的Kruskal算法176
11.5.2 边收缩176
11.5.3 Sibeyn算法176
11.6 应用程序178
11.6.1 Steiner树问题178
11.6.2 旅行推销员之旅179
11.7 实现提示180
11.7.1 C++180
11.7.2 Java180
11.8 历史注释与进一步的读物180
第12章 遗传方法优化182
12.1 线性规划： 黑盒求解器183
12.1.1 整数线性规划185
12.2 贪婪算法： 永不回头186
12.3 动态规划： 子问题的构建189
12.4 系统搜索： 有疑问，用蛮力192
12.4.1 求解整数线性规划194
12.5 局部搜索： 全局思考，局部行动194
12.5.1 爬山195
12.5.2 模拟退火： 从自然中学习196
12.5.3 局部搜索的优化201
12.6 进化算法201
12.7 实现提示203
12.8 历史注释与进一步的读物204
附录A205
A.1 数学符号205
A.2 数学概念206
A.3 概率论基础207
A.4 有用的公式210
A.4.1 证明211
参考文献21