第1章 C＋＋概述 1
1.1 你的第一个C＋＋程序 1
1.2 C＋＋的历史 2
1.2.1 面向对象范型 2
1.2.2 C＋＋的演化 3
1.3 编译过程 3
1.4 C＋＋程序结构 4
1.4.1 注释 5
1.4.2 包含的库文件 6
1.4.3 函数原型 6
1.4.4 主程序 7
1.4.5 函数定义 8
1.5 变量 9
1.5.1 变量声明 9
1.5.2 命名规则 10
1.5.3 局部变量和全局变量 11
1.5.4 常量 11
1.6 数据类型 12
1.6.1 数据类型的概念 12
1.6.2 整数类型 13
1.6.3 浮点类型 13
1.6.4 布尔类型 14
1.6.5 字符 14
1.6.6 字符串 15
1.6.7 枚举类型 16
1.6.8 复合类型 17
1.7 表达式 17
1.7.1 优先级和结合律 18
1.7.2 表达式中的混合类型 19
1.7.3 整数除法和求余操作符 19
1.7.4 类型转换 20
1.7.5 赋值操作符 20
1.7.6 自增和自减操作符 21
1.7.7 布尔运算 22
1.8 语句 24
1.8.1 简单语句 24
1.8.2 块 24
1.8.3 if语句 24
1.8.4 switch语句 25
1.8.5 while语句 27
1.8.6 for语句 29
本章小结 31
复习题 32
习题 33
第2章 函数与库 37
2.1 函数概念 37
2.1.1 数学中的函数 37
2.1.2 编程中的函数 37
2.1.3 使用函数的优点 38
2.1.4 函数和算法 38
2.2 库 39
2.3 在C＋＋中定义函数 41
2.3.1 函数原型 41
2.3.2 重载 42
2.3.3 默认形参数 42
2.4 函数调用机制 43
2.4.1 函数调用步骤 43
2.4.2 组合函数 44
2.4.3 追踪组合函数执行过程 46
2.5 引用参数 49
2.6 接口与实现 52
2.6.1 定义error库 53
2.6.2 导出数据类型 54
2.6.3 导出常量定义 56
2.7 接口设计原则 58
2.7.1 统一主题的重要性 58
2.7.2 简单性与信息隐藏原理 59
2.7.3 满足用户需求 60
2.7.4 通用工具的优势 60
2.7.5 库稳定性的价值 60
2.8 随机数库的设计 61
2.8.1 随机数与伪随机数 61
2.8.2 标准库中的伪随机数 62
2.8.3 选择正确的函数集 63
2.8.4 构建用户程序 65
2.8.5 随机数库的实现 65
2.8.6 初始化随机数种子 69
2.9 Stanford类库介绍 73
2.9.1 简单的输入和输出类库 73
2.9.2 Stanford类库中的图形处理程序 74
本章小结 77
复习题 78
习题 79
第3章 字符串类string 85
3.1 使用字符串作为抽象数据 85
3.2 字符串操作 87
3.2.1 操作符重载 88
3.2.2 从一个字符串中选取字符 89
3.2.3 字符串赋值 90
3.2.4 提取字符串中的子串 90
3.2.5 在一个字符串中进行搜索 90
3.2.6 循环遍历字符串中的所有字符 91
3.2.7 通过连接扩展字符串 92
3.3 ＜cctype＞库 93
3.4 修改字符串中的内容 94
3.5 遗留的C风格字符串 95
3.6 编写字符串应用程序 95
3.6.1 回文识别 96
3.6.2 将英语翻译成儿童黑话 96
3.7 strlib.h库 99
本章小结 100
复习题 100
习题 101
第4章 流类 108
4.1 格式化输出 108
4.2 格式化输入 112
4.3 数据文件 113
4.3.1 使用文件流 114
4.3.2 单个字符的输入／输出 115
4.3.3 面向行的输入／输出 118
4.3.4 格式化输入／输出 119
4.3.5 字符串流 121
4.3.6 一个用于控制台输入的更鲁棒的策略 122
4.4 类层次 123
4.4.1 生物层次 123
4.4.2 流类层次 124
4.4.3 在流层次中选择正确的层次 126
4.5 simpio.h和filelib.h库 127
本章小结 128
复习题 128
习题 129
第5章 集合类 133
5.1 Vector类 134
5.1.1 指定Vector的基类型 134
5.1.2 声明Vector对象 135
5.1.3 Vector的操作 135
5.1.4 从Vector对象中选择元素 136
5.1.5 作为参数传递Vector对象 137
5.1.6 创建预先定义大小的Vector 138
5.1.7 Vector类的构造函数 141
5.1.8 Vector中的操作符 142
5.1.9 表示二维结构 143
5.1.10 Stanford类库中的Grid类 143
5.2 Stack类 144
5.2.1 Stack类结构 145
5.2.2 栈和小型计算器 145
5.3 Queue类 148
5.3.1 仿真和模型 149
5.3.2 排队模型 149
5.3.3 离散时间 150
5.3.4 仿真时间中的事件 150
5.3.5 实现仿真 151
5.4 Map类 154
5.4.1 Map类的结构 154
5.4.2 在一个应用中使用Map类 156
5.4.3 Map类作为关联数组 157
5.5 Set类 158
5.5.1 实现＜cctype＞库 159
5.5.2 创建单词列表 160
5.5.3 Stanford类库中的Lexicon类 161
5.6 在集合上进行迭代 162
5.6.1 迭代顺序 163
5.6.2 再论儿童黑话 164
5.6.3 计算单词的频率 165
本章小结 167
复习题 168
习题 168
第6章 类的设计 178
6.1 二维点的表示 178
6.1.1 将Point定义为结构类型 178
6.1.2 将Point定义为类 179
6.1.3 接口与实现的分离 182
6.2 操作符重载 184
6.2.1 重载插入操作符 184
6.2.2 判断两个点是否相等 186
6.2.3 为Direction类型增加操作符 189
6.3 有理数 191
6.3.1 定义新类的机制 192
6.3.2 采用用户的观点 193
6.3.3 确定Rational类的私有实例变量 193
6.3.4 为Rational类定义构造函数 193
6.3.5 为Rational类定义方法 194
6.3.6 实现Rational类 196
6.4 token扫描器类的设计 198
6.4.1 用户想从记号扫描器中得到什么 199
6.4.2 tokenscanner.h接口 200
6.4.3 实现TokenScanner类 202
6.5 将程序封装成类 205
本章小结 207
复习题 207
习题 208
第7章 递归简介 215
7.1 一个简单的递归例子 215
7.2 阶乘函数 217
7.2.1 fact的递归公式 217
7.2.2 追踪递归过程 218
7.2.3 递归的稳步跳跃 221
7.3 斐波那契函数 222
7.3.1 计算斐波那契数列项 222
7.3.2 在递归实现中获得自信 223
7.3.3 递归实现的效率 224
7.3.4 递归不应被指责 225
7.4 检测回文 226
7.5 二分查找算法 228
7.6 间接递归 229
7.7 递归地思考 230
7.7.1 保持全局的观点 230
7.7.2 避免常见的错误 231
本章小结 232
复习题 233
习题 234
第8章 递归策略 237
8.1 汉诺塔 237
8.1.1 问题框架 238
8.1.2 找到一种递归策略 238
8.1.3 验证这个策略 240
8.1.4 编码方案 241
8.1.5 跟踪递归过程 242
8.2 子集求和问题 245
8.2.1 寻找一个递归解决方案 246
8.2.2 包含／排除模式 246
8.3 字符排列 247
8.4 图的递归 249
8.4.1 一个来自计算机艺术的实例 250
8.4.2 分形 252
本章小结 254
复习题 255
习题 255
第9章 回溯算法 264
9.1 迷宫的递归回溯 264
9.1.1 右手法则 264
9.1.2 寻找一种递归方法 265
9.1.3 确定简单情况 266
9.1.4 对迷宫问题的解决算法进行编码 267
9.1.5 说服你自己那个方案可行 269
9.2 回溯与游戏 271
9.2.1 拿子游戏 272
9.2.2 一个通用的双人游戏程序 276
9.3 最小最大算法 277
9.3.1 游戏树 278
9.3.2 评价位置和走法 278
9.3.3 限制递归搜索的深度 280
9.3.4 实现最小最大算法 280
本章小结 282
复习题 282
习题 283
第10章 算法分析 291
10.1 排序问题 291
10.1.1 选择排序算法 291
10.1.2 性能的经验评估 292
10.1.3 分析选择排序算法的性能 293
10.2 时间复杂度 294
10.2.1 大O符号 295
10.2.2 大O的标准简化 295
10.2.3 选择排序算法的时间复杂度 295
10.2.4 从代码中降低时间复杂度 296
10.2.5 最坏情况以及平均情况下的复杂度 297
10.2.6 大O符号的正式定义 298
10.3 递归的终止 300
10.3.1 分治策略的作用 300
10.3.2 合并两个矢量 301
10.3.3 归并排序算法 301
10.3.4 归并排序的计算复杂度 302
10.3.5 比较N2与Nlog2N的性能 304
10.4 标准的算法复杂度类别 304
10.5 快速排序算法 306
10.5.1 划分矢量 308
10.5.2 快速排序算法的性能分析 310
10.6 数学归纳法 311
本章小结 313
复习题 314
习题 315
第11章 指针和数组 320
11.1 内存结构 320
11.1.1 位、字节和字 320
11.1.2 二进制和十六进制表示 321
11.1.3 表示其他数据类型 322
11.1.4 内存地址 323
11.1.5 为变量分配内存 325
11.2 指针 326
11.2.1 把地址当作数值 327
11.2.2 声明指针变量 327
11.2.3 基本的指针运算 328
11.2.4 指向结构和对象的指针 330
11.2.5 关键字this 331
11.2.6 特殊的指针NULL 331
11.2.7 指针和引用调用 332
11.3 数组 334
11.3.1 声明数组 334
11.3.2 数组元素的选择 335
11.3.3 数组的静态初始化 335
11.3.4 有效容量和分配容量 336
11.3.5 指针和数组的关系 336
11.4 指针运算 338
11.4.1 数组索引和内存地址 338
11.4.2 指针的自增自减运算 339
11.4.3 C风格字符串 339
11.4.4 指针运算和程序风格 341
本章小结 341
复习题 342
习题 344
第12章 动态内存管理 347
12.1 动态分配和堆 347
12.1.1 new操作符 348
12.1.2 动态数组 348
12.1.3 动态对象 349
12.2 链表 349
12.2.1 刚铎灯塔 349
12.2.2 链表内的迭代 352
12.2.3 递归和列表 352
12.3 释放内存 352
12.3.1 delete操作符 352
12.3.2 释放内存策略 353
12.3.3 析构函数 354
12.4 定义CharStack类 354
12.4.1 charstack.h接口 355
12.4.2 选择字符栈的表示 357
12.5 堆-栈图 361
12.6 单元测试 366
12.7 拷贝对象 368
12.7.1 深拷贝和浅拷贝 368
12.7.2 赋值和拷贝构造函数 369
12.8 关键字const的使用 371
12.8.1 常量定义 371
12.8.2 常量引用调用 372
12.8.3 const方法 372
12.9 CharStack类的效率 376
本章小结 377
复习题 378
习题 379
第13章 效率和表示 383
13.1 编辑文本的软件模式 383
13.2 设计简单的文本编辑器 384
13.2.1 编辑器命令 384
13.2.2 EditorBuffer类的公有接口 385
13.2.3 选择一种底层表示 387
13.2.4 编写编辑器应用代码 388
13.3 基于数组的类实现 389
13.3.1 定义私有数据结构 390
13.3.2 缓冲区操作的实现 390
13.3.3 基于数组的编辑器的时间复杂度 393
13.4 基于栈的类实现 394
13.4.1 定义私有数据结构 394
13.4.2 缓冲区操作的实现 395
13.4.3 时间复杂度的比较 397
13.5 基于列表的类实现 397
13.5.1 链表缓冲区的插入操作 400
13.5.2 链表缓冲区的删除操作 402
13.5.3 链表表示法中光标的移动 403
13.5.4 缓冲区实现的完善 405
13.5.5 基于链表的缓冲区的时间复杂度 407
13.5.6 双向链表 408
13.5.7 时空权衡 408
本章小结 409
复习题 409
习题 410
第14章 线性结构 414
14.1 模板 414
14.2 栈的实现 416
14.2.1 使用动态数组实现栈 416
14.2.2 使用链表实现栈 420
14.3 队列的实现 426
14.3.1 基于数组的队列实现 427
14.3.2 队列的链表表示 433
14.4 实现矢量类 437
14.5 集成原型和代码 442
本章小结 442
复习题 443
习题 444
第15章 映射 446
15.1 使用矢量实现映射 447
15.2 查找表 449
15.3 哈希 451
15.3.1 设计数据结构 451
15.3.2 为字符串定义哈希函数 452
15.3.3 实现哈希表 454
15.3.4 跟踪哈希表的实现 456
15.3.5 调整桶的数目 457
15.4 实现HashMap类 458
本章小结 459
复习题 460
习题 461
第16章 树 463
16.1 家谱 463
16.1.1 用来描述树的术语 463
16.1.2 树的递归特性 464
16.1.3 用C＋＋语言表示家谱 464
16.2 二叉搜索树 465
16.2.1 使用二叉搜索树的动机 466
16.2.2 在二叉搜索树中寻找节点 467
16.2.3 在二叉搜索树中插入一个新节点 468
16.2.4 删除节点 471
16.2.5 树的遍历 472
16.3 平衡树 473
16.3.1 平衡树策略 474
16.3.2 可视化AVL算法 475
16.3.3 单旋转 476
16.3.4 双旋转 478
16.3.5 实现AVL算法 478
16.4 使用BST实现映射 482
16.5 偏序数 482
本章小结 485
复习题 485
习题 487
第17章 集合 494
17.1 集合作为一种数学抽象 494
17.1.1 隶属关系 494
17.1.2 集合运算 495
17.1.3 集合恒等式 496
17.2 集合接口的扩展 497
17.3 集合的实现策略 500
17.4 优化小整数的集合 504
17.4.1 特征向量 504
17.4.2 压缩的位数组 505
17.4.3 位操作符 506
17.4.4 实现特征向量 507
17.4.5 实现高级集合运算 509
17.4.6 模板特化 509
17.4.7 使用一种混合的实现 509
本章小结 510
复习题 511
习题 512
第18章 图 514
18.1 图的结构 514
18.1.1 有向图和无向图 515
18.1.2 路径和回路 516
18.1.3 连通性 516
18.2 表示策略 517
18.2.1 用邻接表表示连接关系 517
18.2.2 用邻接矩阵表示连接关系 518
18.2.3 用弧集合表示关系 519
18.3 一种低层的图抽象 520
18.4 图的遍历 524
18.4.1 深度优先搜索 524
18.4.2 广度优先搜索 527
18.5 定义图类 528
18.5.1 用类表示图、节点和弧 528
18.5.2 用参数化的类实现图 529
18.6 寻找最短路径 538
18.7 搜索网页的算法 542
18.7.1 谷歌的网页排名算法 542
18.7.2 网页排名算法的一个简例 543
本章小结 544
复习题 545
习题 546
第19章 继承 551
19.1 简单的继承 551
19.1.1 指定模板类中的类型 551
19.1.2 定义Employee类 552
19.1.3 C＋＋中子类的局限性 554
19.2 图形对象的继承层次 556
19.2.1 调用父类的构造函数 561
19.2.2 将GObject类指针存储在矢量中 563
19.3 表达式的类层次 563
19.3.1 异常处理 565
19.3.2 表达式结构 566
19.3.3 表达式的递归定义 566
19.3.4 二义性 567
19.3.5 表达式树 568
19.3.6 exp.h接口 570
19.3.7 Expression子类的表示 573
19.3.8 表达式图解 573
19.3.9 方法的实现 574
19.4 解析表达式 577
19.4.1 语句解析和语法 577
19.4.2 考虑运算的优先级 578
19.4.3 递归下降语法分析器 579
19.5 多重继承 584
19.5.1 stream类库中的多重继承 584
19.5.2 在GObject继承层次中添加GFillable类 585
19.5.3 多重继承的危险性 586
本章小结 586
复习题 587
习题 589
第20章 迭代策略 595
20.1 使用迭代器 595
20.1.1 简单的迭代器例子 595
20.1.2 迭代器的层次结构 597
20.2 使用函数作为数据值 598
20.2.1 函数指针 598
20.2.2 简单的画图应用 598
20.2.3 声明函数指针 600
20.2.4 实现plot函数 600
20.2.5 映射函数 601
20.2.6 实现映射函数 603
20.2.7 回调函数的限制 603
20.3 用函数封装数据 604
20.3.1 使用对象模拟闭包 604
20.3.2 函数对象的简单例子 605
20.3.3 向映射函数传递函数对象 606
20.3.4 编写以函数作为参数的函数 607
20.4 STL算法库 607
20.5 C＋＋的函数式编程 609
20.5.1 STL库＜functional＞的接口 610
20.5.2 比较函数 612
20.6 迭代器的实现 612
20.6.1 为矢量类实现迭代器 612
20.6.2 将指针作为迭代器 616
20.6.3 typedef关键字 617
20.6.4 为其他集合类实现迭代器 618
本章小结 618
复习题 619
习题 619
索引 624