第1章 算法——程序的灵魂 1
1.1了解算法 2
1.1.1算法的特征和发展由来 2
1.1.2为什么是程序的灵魂 2
1.1.3何谓算法 3
1.1.4算法的特性 4
1.2算法的表示方法——流程图 4
1.3算法的另一种表示方法——N-S流程图表示法 6
1.4用计算机语言表示算法 6
1.5算法在编程中的应用 6
1.6总结 8
职场点拨——职场的“算法” 8
第2章9种算法思想 10
2.1枚举算法思想 11
2.1.1枚举算法的特点 11
2.1.2算法思路 11
2.1.3应用实例 11
2.1.4总结 14
2.2递推算法思想 15
2.2.1递推算法的思路 15
2.2.2顺推法实例 15
2.2.3逆推法实例 16
2.3递归算法思想 17
2.3.1递归算法的特点 18
2.3.2递归算法实例 18
2.4分治算法思想 22
2.4.1分治算法的思路 22
2.4.2看一个经典问题——找出假币 23
2.4.3应用实例——大数相乘 23
2.4.4应用实例——世界杯比赛日程安排 27
2.5贪心算法思想 29
2.5.1贪心算法的思路 29
2.5.2应用实例——装箱问题 30
2.5.3应用实例——找零方案 33
2.6试探法算法思想 34
2.6.1试探法算法的思路 35
2.6.2应用实例——八皇后问题 35
2.6.3应用实例——彩票组合 37
2.7动态规划算法 38
2.7.1动态规划算法的思路 39
2.7.2应用实例 39
2.8迭代算法思想 41
2.8.1迭代算法的思路 42
2.8.2应用实例 42
2.9模拟算法思想 43
2.9.1模拟算法的思路 43
2.9.2应用实例——猜数游戏 44
2.9.3应用实例——掷骰子游戏 45
2.10最后做一个评价 46
2.10.1算法优劣标准 46
2.10.2算法效率的衡量方法 47
职场点拨——程序员面试面面观 48
第3章 最简单的线性结构 50
3.1线性表 50
3.1.1线性表的特性 51
3.1.2顺序表的基本操作实现 52
3.1.3链表基本操作实现 59
3.2先进先出的结构——队列 65
3.2.1队列简介 65
3.2.2队列的抽象数据类型定义 66
3.2.3链队列和循环队列 67
3.2.4队列的基本操作 67
3.2.5队列的链式存储 68
3.2.6应用实例——电信排号程序 73
3.3后进先出的结构——栈 75
3.3.1什么是栈 75
3.3.2栈的基本操作 76
3.3.3应用实例 79
职场点拨——同事相处之道 82
第4章 层次关系结构——树 84
4.1基本概念 84
4.1.1树的定义 85
4.1.2树的相关术语 85
4.1.3树的基本操作概况 86
4.2二叉树 87
4.2.1二叉树的定义 87
4.2.2二叉树的性质 88
4.3二叉树的存储 88
4.3.1顺序存储结构 88
4.3.2链式存储结构 90
4.3.3二叉树操作 91
4.3.4二叉树遍历 94
4.3.5使用二叉树 98
4.4线索二叉树 101
4.4.1线索二叉树的表示 101
4.4.2线索二叉树的操作 104
4.5最优二叉树——赫夫曼树 109
4.5.1几个相关概念 109
4.5.2构造赫夫曼树的过程 110
4.5.3赫夫曼编码 111
职场点拨——谈职业素养 117
第5章 网状关系结构——图 118
5.1图的定义 118
5.2图的几个概念 119
5.3图的存储结构 123
5.3.1邻接矩阵 123
5.3.2邻接表 124
5.3.3十字链表 127
5.3.4创建图 128
5.4图的遍历 133
5.4.1深度优先搜索 133
5.4.2广度优先搜索 136
5.4.3遍历算法的常见应用 140
5.4.4测试图遍历实例 142
5.5图的连通性问题 143
5.5.1无向图的连通分量 143
5.5.2最小生成树 143
5.5.3关键路径 147
5.6最短路径 152
5.6.1求某一顶点到其他各顶点的最短路径 152
5.6.2求任意一对顶点间的最短路径 156
职场点拨——和领导相处 158
第6章 常用算法——查找 160
6.1查找的基本概念 160
6.2基于线性表的查找法 161
6.2.1顺序查找法 161
6.2.2折半查找法 165
6.2.3分块查找法 167
6.3基于树的查找法 168
6.3.1二叉排序树 168
6.3.2平衡二叉排序树 180
6.4计算式查找法——散列法 186
6.4.1散列函数的构造方法 187
6.4.2处理冲突的方法 188
6.4.3散列表的查找过程 190
6.4.4散列法性能分析 191
6.5索引查找 195
6.5.1索引查找基础 195
6.5.2索引查找算法的应用 195
职场点拨——寻兼职 199
第7章 常用算法——内部排序 200
7.1排序基础 200
7.2插入类排序 202
7.2.1直接插入排序 202
7.2.2折半插入排序 205
7.2.3表插入排序 206
7.2.4希尔排序 206
7.3交换类排序法 209
7.3.1冒泡排序（相邻比序法） 209
7.3.2快速排序 213
7.4选择类排序法 217
7.4.1直接选择排序（Straight Selection Sort） 217
7.4.2树形选择排序 219
7.4.3堆排序 220
7.5归并排序 225
7.5.1归并排序思想 225
7.5.2二路归并算法 226
7.5.3归并排序的实现方法 228
7.6各种排序方法的综合比较 231
职场点拨——兼职可靠吗？ 232
第8章 外部排序和文件 234
8.1外存信息的特性 235
8.1.1磁带存储器 235
8.1.2磁盘存储器 236
8.2外排序的基本方法 237
8.2.1磁盘排序 237
8.2.2磁带排序 241
8.3文件的基本概念 243
8.3.1文件中的常用基本概念 244
8.3.2文件的有关操作 244
8.4文件的组织方式 245
8.4.1顺序文件 245
8.4.2索引文件 245
8.4.3 ISAM文件 246
8.4.4 VSAM文件 248
8.4.5散列文件 249
8.4.6多关键字文件 250
职场点拨——换工作的注意事项 250
第9章 算法在数学领域中的应用 252
9.1求两个数的最大公约数和最小公倍数 252
9.2哥德巴赫猜想的近似证明 254
9.3三色球问题 257
9.4百钱买百鸡问题 258
9.5完全数 260
9.6亲密数 262
9.7水仙花数 264
9.8自守数 264
9.9素数 266
9.9.1求素数 266
9.9.2回文素数 268
9.9.3平方回文数 269
9.10阶乘 270
9.10.1递归计算阶乘 270
9.10.2大数的阶乘 272
9.11新郎和新娘的问题 281
9.12年龄几何 283
9.13三色球问题 284
9.14马克思手稿中的数学题 285
9.15正整数分解质因数 286
9.16方程求解 287
9.16.1求解线性方程组介绍 287
9.16.2求解非线性方程组介绍 288
9.16.3高斯消元法求解线性方程组 288
9.16.4二分法解非线性方程 293
9.16.5牛顿迭代法解非线性方程 295
9.17矩阵运算 297
9.18孪生素数 301
9.18.1孪生素数介绍 301
9.18.2求解孪生素数 302
9.19一元多项式运算 303
9.19.1编程实现一元多项式的加法运算 303
9.19.2编程实现一元多项式的减法运算 308
职场点拨——谈学习方法 318
第10章 数据结构问题 319
10.1约瑟夫环 320
10.2大整数运算 323
10.2.1用数组实现大整数运算 323
10.2.2用链表实现大整数运算 333
10.3计算机进制转换 339
10.4中序表达式转换为后序表达式 344
职场点拨——团队成员的素质 349
第11章 算法的经典问题 350
11.1存钱利息最大化 351
11.2歌星大奖赛 354
11.3借书方案知多少 355
11.4打鱼还是晒网 356
11.5捕鱼和分鱼 357
11.6出售金鱼 358
11.7平分七筐鱼 359
11.8绳子的长度和井深 361
11.9鸡兔同笼 362
11.10汉诺塔 363
11.10.1递归法 364
11.10.2非递归法 365
11.11背包问题 368
11.11.1动态规划法 368
11.11.2递归法 375
11.12马踏棋盘 378
11.12.1循环查找 378
11.12.2递归法实现 382
11.12.3栈实现 384
11.13八皇后问题 388
11.13.1递归法 389
11.13.2循环法 391
11.14农夫过河 394
11.15 青蛙过河 397
11.16三色旗 401
11.17取石子 403
11.18生命游戏 407
11.19黑白棋问题 412
11.20停车场管理 422
11.21约瑟夫生者死者游戏 432
11.22骑士迷宫问题 435
职场点拨——谈升职 444