第1章 数组、指针和结构 1
1.1 什么是指针、数组和结构 1
目录 1
第一部分 对象和C++ 1
1.2.1 头等对象与次等对象的对比 2
1.2 数组和字符串 2
1.2.2 使用Vector 3
1.2.3 调整Vector大小 5
1.2.5 参数传递机制 7
1.2.4 push back大小与容量 7
1.2.8 标准库类型string 9
1.2.7 多维数组 9
1.2.6 常量基元数组 9
1.3 C++中的指针语法 10
1.4 动态内存管理 14
1.4.2 垃圾收集与delete 15
1.4.1 new运算符 15
1.4.3 过期指针、双重删除及其他 16
1.5 引用变量 17
1.6 结构 19
1.6.2 外部数据与内部数据、深复制与浅复制 21
1.6.1 指向结构的指针 21
1.6.3 非邻接链表：链表 23
学习目标 24
小结 24
常见错误 25
简答题 26
练习 26
网上资源 26
参考文献 28
编程项目 28
实践题 28
2.1 什么是面向对象编程 30
第2章 对象和类 30
2.2.1 类成员 31
2.2 类的基本语法 31
2.2.2 附加的构造函数语法和访问函数 33
2.2.3 接口和实现的分离 35
2.2.4 析构函数、复制构造函数和赋值运算符（＝） 38
2.3 附加的C++类特性 43
2.2.5 默认的构造函数 43
2.3.1 调整后的构造函数中的初始化与赋值 47
2.3.2 类型转换 48
2.3.3 运算符重载 49
2.3.4 输入、输出和友元 52
2.4.1 避免使用友元 54
2.4 一些常用术语 54
2.4.3 整型类常量的陷阱 55
2.4.2 静态类成员 55
2.5 异常 56
2.6 String类 57
2.7 要点重述：进行了哪些调用？哪些采用了默认行为 65
2.8 组合 66
小结 67
学习目标 68
常见错误 69
简答题 70
练习 70
Internet资源 70
理论题 71
编程项目 72
参考文献 75
3.2 函数模板 76
3.1 模板的概念 76
第3章 模板 76
3.3 排序函数模板 78
3.4.1 MemoryCell模板 81
3.4 类模板 81
3.4.2 实现vector类模板 85
3.5 模板的模板：matrix类 87
3.5.1 数据成员、构造函数和基本附件 88
3.6.1 多平台参数 89
3.6 Fancy模板 89
3.5.2 operator［］ 89
3.5.3 析构函数、复制赋值和复制构造函数 89
3.7 模板有关的bug 90
3.6.3 保留字typename 90
3.6.2 默认的模板参数 90
学习目标 91
小结 91
3.7.1 错误消息和改变的规则 91
3.7.2 模板匹配算法 91
3.7.3 模板中的嵌套类 91
3.7.4 类模板中的静态成员 91
Internet资源 92
常见错误 92
编程项目 93
实践题 93
练习 93
简答题 93
4.1 什么是继承 94
第4章 继承 94
4.2 继承的基本知识 97
4.2.2 构造函数和基类初始化 98
4.2.1 视性规则 98
4.2.3 添加成员 99
4.2.5 静态绑定和动态绑定 101
4.2.4 覆盖方法 101
4.2.6 默认的构造函数、复制构造函数、复制赋值运算符和析构函数 103
4.2.7 构造函数和析构函数virtual或非virtual 104
4.2.8 抽象方法和抽象类 105
4.3 例子：扩展Shape类 108
4.4 微妙的C++细节 112
4.4.1 参数的静态绑定 113
4.4.3 派生类方法隐藏基类方法 114
4.4.2 默认参数 114
4.4.4 覆盖方法的兼容返回类型 115
4.4.6 友元 116
4.4.5 私有继承 116
4.5 多重继承 117
4.4.7 值调用与多态并不混淆 117
小结 118
常见错误 119
学习目标 119
简答题 120
练习 120
Internet资源 120
参考文献 122
编程项目 122
实践题 122
5.1 模式的概念 123
第5章 设计模式 123
5.2 Functor（函数对象） 124
5.3.1 指针包装器 129
5.3 适配器和包装器 129
5.3.2 常数引用包装器 134
5.3.3 适配器更改接口 135
5.4 迭代器 136
5.4.1 迭代器设计1 137
5.4.3 基于继承的迭代器和factory 139
5.4.2 迭代器设计2 139
5.6 观察者 144
5.5 合成（对） 144
学习目标 148
小结 148
Internet资源 149
常见错误 149
实践题 150
理论题 150
练习 150
简答题 150
参考文献 152
编程项目 152
6.1 什么是算法分析 153
第6章 算法分析 153
第二部分 算法和构建代码块 153
6.2 算法运行时间的例子 156
6.3 最大连续子数列和问题 157
6.3.1 直观的O（N3）算法 158
6.3.2 改进的O（N2）算法 160
6.3.3 线性算法 161
6.4 一般的Big-Oh规则 164
6.5 对数 167
6.6.2 折半查找 169
6.6.1 顺序查找 169
6.6 静态查找问题 169
6.6.3 插值查找 172
6.7 算法分析的检验 173
学习目标 174
小结 174
6.8 Big-Oh分析的限制 174
Internet资源 175
常见错误 175
简答题 176
练习 176
理论题 177
编程项目 179
实践题 179
参考文献 180
7.1 简介 182
第7章 标准模板库 182
7.2 堆栈和队列 183
7.2.1 堆栈 184
7.2.2 堆栈和计算机语言 185
7.2.3 队列 186
7.3.1 容器 187
7.3 容器和迭代器 187
7.3.2 迭代器 188
7.4.1 STL函数对象 189
7.4 STL算法 189
7.4.2 二分查找法 191
7.5 实现带有迭代器的vector 193
7.4.3 排序 193
7.6.1 list类 195
7.6 顺序表和链表 195
7.6.2 堆栈和队列 196
7.7 集合 197
7.8 映射 199
7.9 优先队列 200
小结 203
常见错误 204
学习目标 204
理论题 205
简答题 205
Internet资源 205
练习 205
编程项目 206
实践题 206
参考文献 208
8.1 递归的概念 209
第8章 递归 209
8.2 背景知识：数学归纳法 210
8.3 基本递归 212
8.3.1 以任意基数打印数字 213
8.3.2 递归算法有效的原因 215
8.3.3 递归算法的作用原理 216
8.3.4 递归不宜太多 217
8.3.5 树 218
8.3.6 附加例子 219
8.4.1 模运算 223
8.4 数值应用 223
8.4.2 模幂运算 224
8.4.3 最大公约数和乘法逆元素 225
8.4.4 RSA密码系统 228
8.5.1 最大邻近子序列和问题 230
8.5 分治算法 230
8.5.2 基本分治递归分析 233
8.5.3 分治法运行时间的一般上限 235
8.6 动态规划 237
8.7 回溯法 241
学习目标 244
小结 244
Internet资源 245
常见错误 245
理论题 246
简答题 246
练习 246
实践题 247
编程项目 248
参考文献 249
9.1 排序为何重要 250
第9章 排序算法 250
9.2 预备知识 251
9.3 插入排序和其他简单排序的分析 252
9.4 希尔排序 254
9.5 归并排序 257
9.5.1 排过序的数组的线性时间合并 257
9.5.2 归并排序算法 259
9.6.1 快速排序算法 261
9.6 快速排序 261
9.6.2 快速排序的分析 263
9.6.3 支点的选择 265
9.6.4 分组策略 267
9.6.5 同支点相等的键 268
9.6.6 中值划分 269
9.6.8 C++快速排序例程 270
9.6.7 小数组 270
9.7 排序选择 272
9.8 排序的下限 274
9.9.1 使用指针将Comparable副本数减少为2N 275
9.9 间接排序 275
9.9.2 避免附加数组 276
小结 278
Internet资源 279
常见错误 279
学习目标 279
理论题 280
简答题 280
练习 280
实践题 281
编程项目 282
参考文献 283
10.1 为什么我们需要随机数 285
第10章 随机 285
10.2 随机数生成器 286
10.3 非均匀随机数 290
10.4 生成随机排列 291
10.5 随机算法 293
10.6 随机素数测试 295
常见错误 298
学习目标 298
小结 298
理论题 299
简答题 299
Internet资源 299
练习 299
编程项目 300
实践题 300
参考文献 301
11.1 单词查找拼图 302
第11章 娱乐与游戏 302
第三部分 应用程序 302
11.1.1 理论 303
11.1.2 C++实现 304
11.2.1 α-β修剪 309
11.2 Tic-Tac-Toe游戏 309
11.2.2 变换表 312
小结 316
11.2.3 计算机国际象棋 316
理论题 317
简答题 317
学习目标 317
常见错误 317
Internet资源 317
练习 317
编程项目 318
实践题 318
参考文献 319
12.1.1 基本算法 320
12.1 对称符号检查器 320
第12章 堆栈和编译器 320
12.1.2 实现 321
12.2.1 后缀自动机 330
12.2 简单计算器 330
12.2.2 中缀到后缀的转换 332
12.2.3 实现 333
12.2.4 表达式树 341
Internet资源 343
常见错误 343
小结 343
学习目标 343
实践题 344
理论题 344
练习 344
简答题 344
参考文献 345
编程项目 345
13.1 文件压缩 346
第13章 实用工具 346
13.1.1 前缀码 347
13.1.2 霍夫曼算法 348
13.1.3 实现 350
13.2.2 C++实现 366
13.2.1 基本概念 366
13.2 交叉引用生成程序 366
学习目标 370
小结 370
理论题 371
简答题 371
常见错误 371
Internet资源 371
练习 371
编程项目 372
实践题 372
参考文献 373
14.1 Josephus问题 375
第14章 仿真 375
14.1.2 一个更有效的算法 376
14.1.1 简单的解决方案 376
14.2.1 基本思想 380
14.2 事件驱动仿真 380
14.2.2 实例：调制解调器库仿真 381
学习目标 388
小结 388
理论题 389
简答题 389
常见错误 389
Internet资源 389
练习 389
编程项目 390
实践题 390
15.1 定义 391
第15章 图和路径 391
15.2.1 理论 403
15.2 无权最短路径问题 403
15.2.2 C++实现 406
15.3.1 理论：迪杰斯特拉算法 407
15.3 正的有权最短路径问题 407
15.3.2 C++实现 410
15.4.1 理论 412
15.4 负的有权最短路径问题 412
15.4.2 C++实现 413
15.5 无环图的路径问题 414
15.5.1 拓扑排序 415
15.5.2 无环最短路径算法的理论 416
15.5.3 C++实现 417
15.5.4 应用：关键路径分析 419
小结 421
常见错误 422
学习目标 422
理论证明 423
简答题 423
Internet资源 423
练习 423
实践题 424
编程项目 425
参考文献 426
16.1.1 堆栈 427
16.1 动态数组实现 427
第四部分 实现 427
第16章 堆栈和队列 427
16.1.2 队列 431
16.2.1 堆栈 436
16.2 链表实现 436
16.2.2 队列 441
16.3 两种方法的比较 444
16.4 STL堆栈和队列适配器 445
16.5 双头队列 446
学习目标 447
小结 447
简答题 448
练习 448
常见错误 448
Internet资源 448
编程项目 449
实践题 449
17.1 基本概念 450
第17章 链表 450
17.1.1 header节点 452
17.1.2 迭代器类 453
17.2 C++实现 454
17.3 双链表和循环链表 462
17.4 排序链表 464
17.5 实现STL链表类 466
小结 479
Internet资源 480
常见错误 480
学习目标 480
理论题 481
简答题 481
练习 481
实践题 482
编程项目 483
18.1.1 定义 485
18.1 一般树 485
第18章 树 485
18.1.2 实现 486
18.1.3 应用：文件系统 487
18.2 二叉树 490
18.3 递归和树 496
18.4 树遍历：迭代器类 499
18.4.1 后序遍历 502
18.4.2 中序遍历 506
18.4.3 前序遍历 508
18.4.4 层序遍历 509
小结 511
常见错误 512
Internet资源 512
学习目标 512
简答题 513
练习 513
编程项目 514
实践题 514
理论题 514
19.1 基本概念 516
第19章 二叉查找树 516
19.1.1 操作 517
19.1.2 C++实现 518
C++实现 526
19.2 顺序统计 526
19.3 分析二叉查找树操作 530
19.4 AVL树 533
19.4.1 属性 534
19.4.2 单旋转 536
19.4.3 旋转 538
19.4.4 AVL插入总结 540
19.5.1 自底向上插入 541
19.5 红—黑树 541
19.5.2 自项向下红—黑树 543
19.5.3 C++实现 545
19.5.4 自顶往下删除 551
19.6 AA—树 553
19.6.1 插入 554
19.6.2 删除 556
19.6.3 C++实现 557
19.7 实现STL set类和map类 561
19.8 B树 575
小结 580
常见错误 581
学习目标 581
简答题 582
练习 582
Internet资源 582
实践题 583
理论题 583
参考文献 584
编程项目 584
20.1 基本概念 587
第20章 散列表 587
20.2 散列函数 588
20.3 线形探测法 590
20.3.1 线性探测法的简单分析（naive analysis） 591
20.3.2 实际情况：原始集聚 592
20.3.3 查找运算分析 593
20.4 二次探测法 594
20.4.1 C++实现 598
20.5 分离链接法 603
20.4.2 二次探测法分析 603
20.7 散列化应用程序 604
20.6 散列表与二叉查找树 604
学习目标 605
小结 605
简答题 606
练习 606
常见错误 606
Internet资源 606
实践题 607
参考文献 608
编程项目 608
21.1 基本思想 610
第21章 优先级队列：二叉堆 610
21.1.1 结构属性 611
21.1.2 堆顺序属性 612
21.1.3 允许的操作 613
21.2.1 insert操作 615
21.2 基本操作的实现 615
21.2.2 deleteMin操作 616
21.3 buildHeap操作：线性时间的堆构造函数 619
21.4 STL priority_queue实现 622
21.6 内部排序：堆排序 625
21.5 高级操作：decreaseKey和merge 625
21.7.2 外部排序模型 628
21.7.1 我们为什么需要新的算法 628
21.7 外部排序 628
21.7.3 简单的算法 629
21.7.4 多路归并 630
21.7.5 多相归并 631
21.7.6 置换选择 632
学习目标 634
小结 634
理论题 635
简答题 635
常见错误 635
Internet资源 635
练习 635
编程项目 637
实践题 637
参考文献 638
22.1 自我调整和摊销分析 639
第22章 伸展树 639
第五部分 高级数据结构 639
22.1.1 摊销时间限制 640
22.1.2 简单的自我调整策略 641
22.2 基本的自底往上伸展树 642
22.3 基本伸展树操作 644
22.4 自底往上伸展树分析 645
22.5 自顶往下伸展树 649
22.6 实现自项往下伸展树 652
22.7 伸展树与其他查找树的比较 657
常见错误 658
学习目标 658
小结 658
理论题 659
简答题 659
Internet资源 659
练习 659
参考文献 660
编程项目 660
实践题 660
23.1.1 合并是基础 661
23.1 偏斜堆 661
第23章 合并优先级队列 661
23.1.3 偏斜堆：简单修改 662
23.1.2 简化的堆排序树合并 662
23.1.4 偏斜堆分析 663
23.2 对偶堆 665
23.2.1 对偶堆的操作 666
23.2.2 对偶堆的实现 668
23.2.3 应用：Dijkstra最短加权路径算法 674
常见错误 676
学习目标 676
小结 676
理论题 677
简答题 677
Internet资源 677
练习 677
参考文献 678
编程项目 678
实践题 678
24.2 动态等价和两个应用 680
24.1 等价关系 680
第24章 不相交集类 680
24.2.1 应用：生成迷宫 681
24.2.2 应用：最小伸展树 684
24.2.3 应用：最近共同祖先问题 686
24.3 快速查找算法 689
24.4 快速合并算法 690
24.4.1 巧妙的合并算法 691
24.4.2 路径压缩 693
24.5 C++实现 694
24.6 针对按秩合并与路径压缩的最坏情形 695
合并／查找算法分析 696
学习目标 701
小结 701
简答题 702
练习 702
常见错误 702
Internet资源 702
编程项目 703
实践题 703
理论题 703
参考文献 704
A.2.1 自增运算符与自减运算符 706
A.2 不常见的C++运算符 706
附录 706
附录A C++相关信息 706
A.1 没有编译器实现该标准 706
A.2.2 类型转换 707
A.2.3 按位运算符 708
A.4 输入和输出 710
A.3 命令参数 710
A.2.4 条件运算符 710
A.4.1 基本的流操作 711
A.4.3 字符串流 714
A.4.2 顺序文件 714
A.5 名字空间 716
常见错误 717
A.6 C++新特性 717
附录B 运算符 719
C.2 〈limits.h〉和〈climits〉中声明的常量 720
C.1 〈ctype.h〉和〈cctype〉中声明的例程 720
附录C 某些库例程 720
C.4 〈stdlib.h〉和〈cstdlib〉中声明的例程 721
C.3 〈math.h〉和〈cmath〉中声明的例程 721
D.1.1 C++实现：数组名称是一个指针 723
D.1 基元数组 723
附录D C++中的基元数组 723
D.1.3 char＊类型、const指针和常量字符串 726
D.1.2 多维数组 726
D.2 动态数组分配：new［］和delete［］ 729
D.3 指针算术运算、指针跳和基本迭代 733
D.3.2 指针算术的含意 734
D.3.1 ＊、＆和［］优先级的含意 734
D.3.3 指针跳例子 736
D.3.4 使用指针跳的意义 737
Internet资源 738
常见错误 738