第1章　算法之美 1
1．1　打开算法之门 2
1．2　妙不可言—算法复杂性 2
1．3　美不胜收—魔鬼序列 9
1．4　灵魂之交—马克思手稿中的数学题 16
1．5　算法学习瓶颈 21
1．6　你怕什么 22
第2章　贪心算法 24
2．1　人之初，性本贪 25
2．1．1 贪心本质 25
2．1．2 贪亦有道 26
2．1．3 贪心算法秘籍 26
2．2　加勒比海盗船—最优装载问题 27
2．2．1 问题分析 27
2．2．2 算法设计 28
2．2．3 完美图解 28
2．2．4 伪代码详解 29
2．2．5 实战演练 30
2．2．6 算法解析及优化拓展 31
2．3　阿里巴巴与四十大盗—背包问题 32
2．3．1 问题分析 32
2．3．2 算法设计 33
2．3．3 完美图解 33
2．3．4 伪代码详解 34
2．3．5 实战演练 35
2．3．6 算法解析及优化拓展 36
2．4　高级钟点秘书—会议安排 37
2．4．1 问题分析 38
2．4．2 算法设计 39
2．4．3 完美图解 40
2．4．4 伪代码详解 41
2．4．5 实战演练 42
2．4．6 算法解析及优化拓展 45
2．5　一场说走就走的旅行—最短路径 45
2．5．1 问题分析 46
2．5．2 算法设计 46
2．5．3 完美图解 47
2．5．4 伪代码详解 51
2．5．5 实战演练 52
2．5．6 算法解析及优化拓展 55
2．6　神秘电报密码—哈夫曼编码 59
2．6．1 问题分析 60
2．6．2 算法设计 62
2．6．3 完美图解 63
2．6．4 伪代码详解 65
2．6．5 实战演练 74
2．6．6 算法解析及优化拓展 77
2．7　沟通无限校园网—最小生成树 77
2．7．1 问题分析 78
2．7．2 算法设计 79
2．7．3 完美图解 80
2．7．4 伪代码详解 87
2．7．5 实战演练 88
2．7．6 算法解析 90
2．7．7 算法优化拓展 90
第3章　分治法 99
3．1　山高皇帝远 100
3．1．1 治众如治寡—分而治之 100
3．1．2 天时地利人和—分治算法要素 100
3．1．3 分治算法秘籍 101
3．2　猜数游戏—二分搜索技术 101
3．2．1 问题分析 101
3．2．2 算法设计 102
3．2．3 完美图解 102
3．2．4 伪代码详解 103
3．2．5 实战演练 104
3．2．6 算法解析与拓展 105
3．3　合久必分，分久必合—合并排序 107
3．3．1 问题分析 108
3．3．2 算法设计 108
3．3．3 完美图解 108
3．3．4 伪代码详解 108
3．3．5 实战演练 111
3．3．6 算法解析与拓展 112
3．4　兵贵神速—快速排序 113
3．4．1 问题分析 114
3．4．2 算法设计 115
3．4．3 完美图解 116
3．4．4 伪代码详解 117
3．4．5 实战演练 118
3．4．6 算法解析与拓展 120
3．5　效率至上—大整数乘法 124
3．5．1 问题分析 124
3．5．2 算法设计 125
3．5．3 完美图解 126
3．5．4 伪代码详解 128
3．5．5 实战演练 132
3．5．6 算法解析与拓展 135
3．6　分治算法复杂度求解秘籍 137
第4章　动态规划 141
4．1　神奇的兔子序列 142
4．2　动态规划基础 143
4．2．1　算法思想 143
4．2．2　算法要素 143
4．2．3　解题秘籍 143
4．3　孩子有多像爸爸—最长的公共子序列 145
4．3．1　问题分析 145
4．3．2　算法设计 147
4．3．3　完美图解 148
4．3．4　伪代码详解 152
4．3．5　实战演练 153
4．3．6　算法解析及优化拓展 155
4．4　DNA基因鉴定—编辑距离 156
4．4．1　问题分析 156
4．4．2　算法设计 158
4．4．3　完美图解 159
4．4．4　伪代码详解 161
4．4．5　实战演练 162
4．4．6　算法解析及优化拓展 163
4．5　长江一日游—游艇租赁 164
4．5．1　问题分析 164
4．5．2　算法设计 166
4．5．3　完美图解 166
4．5．4　伪代码详解 170
4．5．5　实战演练 171
4．5．6　算法解析及优化拓展 172
4．6　快速计算—矩阵连乘 172
4．6．1　问题分析 173
4．6．2　算法设计 176
4．6．3　完美图解 176
4．6．4　伪代码详解 180
4．6．5　实战演练 181
4．6．6　算法解析及优化拓展 182
4．7　切呀切披萨—最优三角剖分 183
4．7．1　问题分析 183
4．7．2　算法设计 186
4．7．3　完美图解 187
4．7．4　伪代码详解 191
4．7．5　实战演练 192
4．7．6　算法解析及优化拓展 194
4．8　小石子游戏—石子合并 194
4．8．1　问题分析 195
4．8．2　算法设计 197
4．8．3　完美图解 198
4．8．4　伪代码详解 203
4．8．5　实战演练 205
4．8．6　算法解析及优化拓展 206
4．9　大卖场购物车1—0-1背包问题 209
4．9．1　问题分析 210
4．9．2　算法设计 211
4．9．3　完美图解 212
4．9．4　伪代码详解 216
4．9．5　实战演练 217
4．9．6　算法解析及优化拓展 218
4．10　快速定位—最优二叉搜索树 220
4．10．1　问题分析 221
4．10．2　算法设计 225
4．10．3　完美图解 226
4．10．4　伪代码详解 239
4．10．5　实战演练 241
4．10．6　算法解析及优化拓展 243
4．11　动态规划算法秘籍 246
第5章　回溯法 248
5．1　回溯法基础 249
5．1．1　算法思想 249
5．1．2　算法要素 249
5．1．3　解题秘籍 251
5．2　大卖场购物车2—0-1背包问题 252
5．2．1　问题分析 252
5．2．2　算法设计 253
5．2．3　完美图解 255
5．2．4　伪代码详解 258
5．2．5　实战演练 259
5．2．6　算法解析 262
5．2．7　算法优化拓展 262
5．3　部落护卫队—最大团 265
5．3．1　问题分析 266
5．3．2　算法设计 267
5．3．3　完美图解 269
5．3．4　伪代码详解 274
5．3．5　实战演练 275
5．3．6　算法解析及优化拓展 277
5．4　地图调色板—地图着色 278
5．4．1　问题分析 278
5．4．2　算法设计 279
5．4．3　完美图解 280
5．4．4　伪代码详解 285
5．4．5　实战演练 286
5．4．6　算法解析及优化拓展 288
5．5　一山不容二虎—n皇后问题 289
5．5．1　问题分析 290
5．5．2　算法设计 291
5．5．3　完美图解 292
5．5．4　伪代码详解 300
5．5．5　实战演练 301
5．5．6　算法解析及优化拓展 303
5．6　机器零件加工—最优加工顺序 305
5．6．1　问题分析 305
5．6．2　算法设计 308
5．6．3　完美图解 308
5．6．4　伪代码详解 313
5．6．5　实战演练 314
5．6．6　算法解析 316
5．6．7　算法优化拓展 316
5．7　奇妙之旅1—旅行商问题 319
5．7．1　问题分析 319
5．7．2　算法设计 320
5．7．3　完美图解 321
5．7．4　伪代码详解 330
5．7．5　实战演练 331
5．7．6　算法解析及优化拓展 333
5．8　回溯法算法秘籍 336
第6章　分支限界法 338
6．1　横行天下—广度优先 339
6．1．1　算法思想 340
6．1．2　算法步骤 340
6．1．3　解题秘籍 341
6．2　大卖场购物车3—0-1背包问题 341
6．2．1　问题分析 342
6．2．2　算法设计 343
6．2．3　完美图解 345
6．2．4　伪代码详解 350
6．2．5　实战演练 352
6．2．6　算法解析 355
6．2．7　算法优化拓展—优先队列式分支限界法 356
6．3　奇妙之旅2—旅行商问题 366
6．3．1　问题分析 366
6．3．2　算法设计 367
6．3．3　完美图解 368
6．3．4　伪代码详解 371
6．3．5　实战演练 373
6．3．6　算法解析 376
6．3．7　算法优化拓展 377
6．4　铺设电缆—最优工程布线 385
6．4．1　问题分析 386
6．4．2　算法设计 386
6．4．3　完美图解 387
6．4．4　伪代码详解 399
6．4．5　实战演练 400
6．4．6　算法解析及优化拓展 403
6．5　回溯法与分支限界法的异同 404
第7章　线性规划网络流 405
7．1　线性规划问题 406
7．1．1 线性规划标准型 408
7．1．2 单纯形算法图解 409
7．1．3 解题秘籍 413
7．1．4 练习 413
7．2　工厂最大效益—单纯形算法 414
7．2．1 问题分析 414
7．2．2 完美图解 415
7．2．3 伪代码详解 418
7．2．4 实战演练 420
7．2．5 算法解析及优化拓展 423
7．3　最大网络流—最短增广路算法 424
7．3．1 问题分析 424
7．3．2 增广路算法 427
7．3．3 完美图解 431
7．3．4 伪代码详解 437
7．3．5 实战演练 439
7．3．6 算法解析 441
7．3．7 算法优化拓展—重贴标签算法ISAP 442
7．4　最小费用最大流—最小费用路算法 455
7．4．1 问题分析 456
7．4．2 算法设计 456
7．4．3 完美图解 457
7．4．4 伪代码详解 459
7．4．5 实战演练 461
7．4．6 算法解析 465
7．4．7 算法优化拓展—消圈算法 466
7．5　精明的老板—配对方案问题 468
7．5．1 问题分析 468
7．5．2 算法设计 469
7．5．3 完美图解 469
7．5．4 伪代码详解 470
7．5．5 实战演练 471
7．5．6 算法解析 475
7．5．7 算法优化拓展—匈牙利算法 475
7．6　国际会议交流—圆桌问题 480
7．6．1 问题分析 481
7．6．2 算法设计 482
7．6．3 完美图解 482
7．6．4 伪代码详解 484
7．6．5 实战演练 485
7．6．6 算法解析及优化拓展 489
7．7　要考试啦—试题库问题 489
7．7．1 问题分析 490
7．7．2 算法设计 490
7．7．3 完美图解 491
7．7．4 伪代码详解 493
7．7．5 实战演练 494
7．7．6 算法解析及优化拓展 498
7．8　太空实验计划—最大收益问题 499
7．8．1 问题分析 499
7．8．2 算法设计 500
7．8．3 完美图解 502
7．8．4 伪代码详解 505
7．8．5 实战演练 506
7．8．6 算法解析及优化拓展 510
7．9　央视娱乐节目购物街—方格取数问题 511
7．9．1 问题分析 511
7．9．2 算法设计 512
7．9．3 完美图解 513
7．9．4 伪代码详解 514
7．9．5 实战演练 516
7．9．6 算法解析及优化拓展 520
7．10　走着走着，就走到了西藏—旅游路线问题 521
7．10．1 问题分析 521
7．10．2 算法设计 523
7．10．3 完美图解 523
7．10．4 伪代码详解 525
7．10．5 实战演练 528
7．10．6 算法解析及优化拓展 532
7．11　网络流问题解题秘籍 533
附录A　特征方程和通项公式 534
附录B　sort函数 537
附录C　优先队列 541
附录D　邻接表 549
附录E　并查集 555
附录F　四边不等式 561
附录G　排列树 565
附录H　贝尔曼规则 579
附录I　增广路中称为关键边的次数 582
附录J　最大流最小割定理 585

趣学数据结构
第 1章　数据结构入门 1
1.1　数据结构基础知识　2
1.2　算法复杂度　10
1.3　一棋盘麦子　17
1.4　神奇魔鬼序列　18
1.5　本章要点　23
第　2章 线性表　24
2.1　顺序表　25
2.1.1　静态分配　25
2.1.2　动态分配　26
2.1.3　顺序表的基本操作　28
2.2　单链表　35
2.2.1　单链表的存储方式　35
2.2.2　单链表的基本操作　37
2.3　双向链表　48
2.3.1　双向链表的存储方式　48
2.3.2　双向链表的基本操作　48
2.4　循环链表　54
2.5　线性表的应用　55
2.5.1　合并有序顺序表　55
2.5.2　合并有序链表　60
2.5.3　就地逆置单链表　64
2.5.4　查找链表的中间节点　68
2.5.5　删除链表中的重复元素　71
2.6　线性表学习秘籍　75
第3章　栈和队列　78
3.1　顺序栈　79
3.2　链栈　83
3.3　顺序队列　87
3.3.1　顺序队列的定义　88
3.3.2　循环队列的定义　92
3.3.3　循环队列的基本操作　96
3.4　链队列　98
3.5　栈和队列的应用　102
3.5.1　数制的转换　102
3.5.2　回文判定　104
3.5.3　双端队列　106
3.6　栈和队列学习秘籍　116
第4章　字符串　121
4.1　字符串　122
4.2　模式匹配BF算法　124
4.3　模式匹配KMP算法　128
4.4　改进的KMP算法　133
4.5　字符串的应用——病毒检测　135
4.6　字符串学习秘籍　137
第5章　数组与广义表　139
5.1　数组的顺序存储　140
5.2　特殊矩阵的压缩存储　143
5.2.1　对称矩阵　143
5.2.2　三角矩阵　145
5.2.3　对角矩阵　146
5.2.4　稀疏矩阵　150
5.3　广义表　151
5.4　好玩贪吃蛇——数字矩阵　151
5.5　数组与广义表学习秘籍　156
第6章　树　158
6.1　树　159
6.1.1　树的定义　159
6.1.2　树的存储结构　162
6.1.3　树、森林与二叉树的转换　165
6.2　二叉树　167
6.2.1　二叉树的性质　168
6.2.2　二叉树的存储结构　173
6.2.3　二叉树的创建　175
6.3　二叉树的遍历　183
6.3.1　先序遍历　183
6.3.2　中序遍历　186
6.3.3　后序遍历　188
6.3.4　层次遍历　192
6.4　线索二叉树　196
6.4.1　线索二叉树存储结构　196
6.4.2　构造线索二叉树　197
6.4.3　遍历线索二叉树　201
6.5　树和森林的遍历　204
6.5.1　树的遍历　204
6.5.2　森林的遍历　209
6.6　树的应用　212
6.6.1　二叉树的深度　212
6.6.2　二叉树的叶子数　213
6.6.3　三元组创建二叉树　214
6.6.4　遍历序列还原树　218
6.6.5　哈夫曼树　223
6.7　树学习秘籍　239
第7章　图　241
7.1　图的基本术语　242
7.2　图的存储结构　249
7.2.1　邻接矩阵　250
7.2.2　邻接表　256
7.2.3　十字链表　266
7.2.4　邻接多重表　268
7.3　图的遍历　270
7.3.1　广度优先搜索　270
7.3.2　深度优先搜索　275
7.4　图的应用　279
7.4.1　单源最短路径——Dijkstra　279
7.4.2　各顶点之间最短路径——Floyd　287
7.4.3　最小生成树——prim　293
7.4.4　最小生成树——kruskal　305
7.4.5　拓扑排序　308
7.4.6　关键路径　316
7.5　图学习秘籍　324
第8章　查找　327
8.1　线性表查找　328
8.1.1　顺序查找　328
8.1.2　折半查找　330
8.2　树表查找　335
8.2.1　二叉查找树　335
8.2.2　平衡二叉查找树　346
8.3　散列表的查找　361
8.3.1　散列函数　361
8.3.2　处理冲突的方法　364
8.3.3　散列查找及性能分析　376
8.4　查找学习秘籍　378
第9章　排序　379
9.1　插入排序　381
9.1.1　直接插入排序　381
9.1.2　希尔排序　387
9.2　交换排序　389
9.2.1　冒泡排序　389
9.2.2　快速排序　392
9.3　选择排序　401
9.3.1　简单选择排序　401
9.3.2　堆排序　403
9.4　合并排序　412
9.5　分配排序　417
9.5.1　桶排序　417
9.5.2　基数排序　418
9.6　排序学习秘籍　421
第　10章 高级数据结构　425
10.1　并查集　426
10.2　优先队列　430
10.2.1　出队　431
10.2.2　入队　433
10.2.3　构建初始堆　435
10.3　B-树　437
10.3.1　树高与性能　439
10.3.2　查找　440
10.3.3　插入　441
10.3.4　删除　444
10.4　B+树　449
10.4.1　查找　450
10.4.2　插入　451
10.4.3　删除　454
10.5　红黑树　457
10.5.1　红黑树的定义　457
10.5.2　树高与性能　458
10.5.3　红黑树与4阶B树　459
10.5.4　查找　460
10.5.5　插入　460
10.5.6　删除　466
10.6　高级数据结构学习秘籍　476