第一篇 算法与数据结构基础 1
第1章 基础算法思想 1
1.1编程的灵魂：数据结构＋算法 1
1.2算法的作用 2
1.2.1概述 2
1.2.2实例：看商品猜价格 2
1.3递推算法思想 5
1.3.1算法思路 5
1.3.2顺推实例：斐波那契数列 5
1.3.3逆推实例：该存多少钱 7
1.4枚举算法思想 8
1.4.1算法思路 9
1.4.2实例：填数游戏 9
1.4.3实例：填运算符 10
1.5递归算法思想 13
1.5.1算法思路 13
1.5.2实例：求阶乘 14
1.5.3实例：数制转换 16
1.6分治算法思想 17
1.6.1算法思路 17
1.6.2实例：乒乓球比赛赛程安排 18
1.7贪婪算法思想 21
1.7.1算法思路 22
1.7.2实例：换零钱 22
1.8试探法算法思想 24
1.8.1算法思路 24
1.8.2实例：生成彩票号码组合 25
1.9模拟算法 27
1.9.1算法思路 28
1.9.2实例：猜数游戏 28
1.9.3实例：模拟掷骰子游戏 29
1.10算法的评价 30
1.10.1算法评价原则 30
1.10.2算法的效率 30
第2章 简单数据结构 32
2.1最简单的结构：线性表 32
2.1.1什么叫线性表 32
2.1.2操作顺序表 33
2.1.3操作链表 40
2.1.4实例：用链表制作通信录 49
2.2先进先出结构：队列 53
2.2.1什么是队列 53
2.2.2操作队列 53
2.2.3循环队列的操作 56
2.2.4实例：银行排号程序 59
2.3后进先出结构：栈 61
2.3.1什么是栈 61
2.3.2操作栈 62
2.3.3实例：算术表达式求值 66
第3章 复杂数据结构 74
3.1层次关系结构：树 74
3.1.1树的概念 74
3.1.2二叉树的概念 75
3.1.3二叉树的存储 77
3.1.4操作二叉树 79
3.1.5遍历二叉树 82
3.1.6测试二叉树 86
3.1.7线索二叉树 89
3.1.8最优二叉树（赫夫曼树） 96
3.2网状关系：图 105
3.2.1图的定义和基本术语 106
3.2.2图的存储 109
3.2.3创建图 112
3.2.4图的遍历 117
3.2.5最小生成树 121
3.2.6最短路径 126
第4章 常用算法——排序 131
4.1排序概述 131
4.1.1排序算法分类 131
4.1.2数据准备 132
4.2冒泡排序法 133
4.2.1算法描述 133
4.2.2改进的冒泡排序法 135
4.3快速排序法 137
4.3.1算法描述 137
4.3.2算法实现 138
4.4简单选择排序法 140
4.5堆排序法 141
4.5.1算法描述 141
4.5.2算法实现 143
4.6直接插入排序法 146
4.6.1算法描述 146
4.6.2算法实现 147
4.7希尔排序法 148
4.7.1算法描述 148
4.7.2算法实现 149
4.8合并排序法 150
4.8.1算法描述 151
4.8.2算法实现 152
4.9排序算法的选择 155
4.9.1选择基准 155
4.9.2各种排序算法的优缺点 156
第5章 常用算法——查找 157
5.1查找的基本概念 157
5.2简单查找 158
5.2.1顺序查找 158
5.2.2折半查找 160
5.3二叉排序树 163
5.3.1二叉排序树的定义 163
5.3.2插入结点 163
5.3.3查找结点 166
5.3.4删除结点 167
5.4索引查找 171
5.4.1索引的概念 171
5.4.2索引查找算法 173
5.5散列表 177
5.5.1散列表概述 177
5.5.2构造散列函数 178
5.5.3处理冲突 180
5.5.4创建和查找散列表 181
第二篇 用数据结构解决实际问题 185
第6章 数学问题 185
6.1有趣的整数 185
6.1.1完数 185
6.1.2亲密数 187
6.1.3水仙花数 189
6.1.4自守数 190
6.1.5最大公约数和最小公倍数 191
6.2素数 194
6.2.1求素数 194
6.2.2回文素数 197
6.2.3哥德巴赫猜想 200
6.3阶乘 203
6.3.1用递归计算阶乘 204
6.3.2大数阶乘 204
6.4求π的近似值 208
6.4.1概率法 209
6.4.2割圆法 210
6.4.3公式法 211
6.4.4计算任意位数的π 213
6.5方程求解 216
6.5.1高斯消元法解线性方程组 216
6.5.2二分法解非线性方程 221
6.5.3牛顿迭代法解非线性方程 222
6.6矩阵的运算 224
6.6.1矩阵加法和乘法运算 225
6.6.2多维矩阵转一维矩阵 227
6.6.3逆矩阵 229
6.6.4稀疏矩阵 233
6.7一元多项式的运算 235
6.7.1多项式加法 236
6.7.2多项式减法 240
第7章 数据结构问题 245
7.1约瑟夫环 245
7.2大整数四则运算 247
7.2.1使用数组进行大整数运算 247
7.2.2使用链表进行大整数运算 260
7.3进制转换 267
7.3.1进制转换的分析 267
7.3.2进制转换实现代码 268
7.4括号匹配 272
7.5中序表达式转后序表达式 275
7.5.1后序表达式 275
7.5.2算法实现 276
7.5.3后序表达式求值 279
7.6停车场管理 282
7.6.1问题分析 282
7.6.2算法实现 282
7.7迷宫求解 292
7.7.1迷宫问题 292
7.7.2算法实现 293
7.7.3求迷宫所有路径 300
7.8 LZW压缩的实现 304
7.8.1 LZW的相关概念 304
7.8.2 LZW压缩过程 304
7.8.3 LZW压缩的实现 306
7.8.4 LZW解压缩过程 310
7.8.5解压缩函数 311
7.8.6集成压缩和解压缩功能 314
第8章 算法经典问题 316
8.1不定方程问题 316
8.1.1百钱买百鸡 316
8.1.2存钱利息最大化 318
8.1.3求阶梯数 321
8.1.4五家共井 322
8.1.5鸡兔同笼 323
8.2推算问题 324
8.2.1猴子吃桃 324
8.2.2舍罕王的赏赐 325
8.3魔术方阵 327
8.3.1简捷连续填数法 327
8.3.2双向翻转法 330
8.3.3井字调整法 332
8.4智力趣题 336
8.4.1汉诺塔 336
8.4.2背包问题 340
8.4.3马踏棋盘 347
8.4.4八皇后问题 357
8.4.5青蛙过河 362
8.4.6三色旗 365
8.5趣味游戏 368
8.5.1取石子游戏 368
8.5.2生命游戏 371
8.5.3洗扑克牌 376
8.5.4黑白棋 379
8.5.5凑24点游戏 388
8.5.6 10点半游戏 394
第9章 信息学奥赛试题精解 399
9.1 NOIP普及组试题精解 399
9.1.1求级数之和 399
9.1.2求素数组合 402
9.1.3计算卒的路线 405
9.1.4检查校验码 407
9.1.5排座位 409
9.1.6击鼓传花 413
9.1.7绘制模拟立体图 414
9.1.8公路上的树 419
9.1.9采药 420
9.1.10求等价表达式 422
9.1.11不开心的龙龙 426
9.1.12孙悟空摘桃 428
9.1.13 FBI树 431
9.1.14外星人的语言 433
9.2 NOIP提高组试题精解 438
9.2.1砝码称重 438
9.2.2阿明的零花钱 439
9.2.3购买年货 442
9.2.4调整队形 445
9.2.5均分纸牌 448
9.2.6最小矩形面积 450
9.2.7低价买股票 458
9.2.8数字金字塔 461
9.2.9方格取数 463
9.2.10导弹防御系统 467
附录 Dev-C＋＋开发环境的使用 470