第1章 软件开发 1
1.1 问题分析和需求规格说明 3
1.2 设计 5
1.2.1 自顶向下设计 5
1.2.2 面向对象设计 7
1.2.3 小规模设计 9
1.3 编码 15
1.4 测试、运行和调试 27
1.5 维护 34
1.6 本章小结 36
第2章 抽象数据类型入门 40
2.1 对ADT及其实现的第一瞥 40
2.2 C++的简单数据类型 41
2.2.1 整型数据 42
2.2.2 实型数据 46
2.2.3 字符数据 49
2.4.4 布尔数据 50
2.3 程序员定义的数据类型 53
2.3.1 Typedefs 53
2.3.2 枚举 53
2.3.3 类 55
2.4 指针 56
2.4.1 声明和初始化指针 57
2.4.2 基本指针操作 60
2.4.3 动态内存分配——new操作 64
2.4.4 关于引用形参的注释 65
2.5 本章小结 68
第3章 数据结构和抽象数据类型 73
3.1 数据结构，抽象数据类型和实现 73
3.2 静态数组 77
3.2.1 一维静态数组 78
3.2.2 下标运算 81
3.2.3 数组作为形参 82
3.2.4 越界错误 83
3.2.5 数组的问题 86
3.3 多维数组 88
3.3.1 二维数组 88
3.3.2 高维数组 89
3.3.3 数组的数组声明 91
3.3.4 多维数组作函数参数 95
3.4 动态数组 97
3.4.1 new操作——动态数组 98
3.4.2 指针的其他用法 110
3.5 C风格结构（可选） 112
指向结构的指针 116
3.6 过程式编程 117
过程式编程的例子 118
3.7 本章小结 123
第4章 OOP和ADT进阶——类 129
4.1 过程式编程vs.面向对象编程 129
4.2 类 130
4.2.1 “传统的”（C）结构和OOP
（C++）结构以及类之间的
区别 131
4.2.2 类声明 131
4.3 例子：用户定义的Time类的
第一个版本 135
4.3.1 为什么不使所有成员都
公有化 137
4.3.2 实现一个类 138
4.3.3 一些现象 141
4.4 类构造函数 142
4.5 其他类操作 150
4.5.1 复制操作——初始化和
赋值 150
4.5.2 访问函数和更动函数 151
4.5.3 重载运算符 153
4.5.4 重载输入/输出运算符 154
4.5.5 其他操作：前进和关系
操作 161
4.5.6 总结以及其他一些细节 163
4.5.7 指向类对象的指针 167
4.5.8 this指针 168
4.6 本章小结 171
第5章 标准C++输入/输出和字
符串类 176
5.1 C++标准I/O类 177
5.1.1 istream类 178
5.1.2 ostream类 182
5.1.3 文件I/O：ifstream和
ofstream类 186
5.1.4 I/O类层次 188
5.2 C++ String类型 192
5.2.1 C风格的字符串 193
5.2.2 一个字符串类 195
5.2.3 C++ String类 196
5.2.4 String流 204
5.3 案例学习：文本编辑 208
5.4 模式匹配介绍（可选） 216
5.5 数据加密介绍（可选） 219
5.5.1 数据加密标准（Data Encryption
Standard） 222
5.5.2 公共密钥加密（Public-Key
Encryption） 222
5.6 本章小结 224
第6章 列表 228
6.1 作为ADT的列表 229
设计和创建一个列表类 230
6.2 基于数组的列表实现 231
6.2.1 选择存储结构 231
6.2.2 实现操作 232
6.2.3 一个使用静态数组存储的
列表类 234
6.3 使用动态分配的基于数组实现的
列表 242
6.3.1 类中的动态分配——析构函数、复制构造函数和赋值运算符 246
6.3.2 最后一点 253
6.4 对链表的介绍 257
6.4.1 它们是什么 257
6.4.2 实现基本列表操作 258
6.4.3 小结 262
6.5 在C++中基于指针来实现链表 264
6.5.1 节点结构 264
6.5.2 链表实现中的数据成员 266
6.5.3 链表实现中的函数成员 267
6.6 基于数组的链表实现 271
6.6.1 节点结构 272
6.6.2 存储池管理 274
6.7 本章小结 276
第7章 栈 280
7.1 栈的介绍 281
7.2 设计和创建一个Stack类——
基于数组 285
7.2.1 选择存储结构 285
7.2.2 实现操作 288
7.2.3 实现pop操作的算法 290
7.2.4 完整的Stack类 290
7.2.5 使用动态数组存储栈元素296
7.2.6 前瞻 309
7.3 链式栈 312
7.3.1 选择存储结构 313
7.3.2 实现操作 314
7.3.3 完整的Stack类：链表
版本 317
7.4 栈在函数调用中的使用 324
7.5 案例学习：后缀（RPN）表示329
7.5.1 计算后缀表达式 330
7.5.2 将中缀表达式转换成后缀
表达式 331
7.6 本章小节 341
第8章 队列 345
8.1 队列入门 345
8.2 设计和创建一个Queue类——
基于数组 353
8.2.1 使用静态数组存储队列
元素 356
8.2.2 使用动态数组存储队列
元素 361
8.3 链式队列 365
8.3.1 一种自然的链表实现 365
8.3.2 使用循环链表 374
8.4 队列的应用：缓冲区和调度376
8.5 案例学习：信息中心仿真 379
8.5.1 问题分析和需求规格说明380
8.5.2 创建一个Simulation类 380
8.5.3 Time类和Call类 389
8.6 本章小结 390
第9章 ADT实现：模板和标准容器393
9.1 介绍：可重用性和通用性的发展394
9.1.1 从算法到算法 394
9.1.2 从数据到容器 396
9.2 函数通用性——重载和模板396
9.2.1 重载 397
9.2.2 函数模板 399
9.2.3 另一个例子：显示一个
数组 403
9.3 类通用性——模板 404
9.3.1 Typedef有什么错 404
9.3.2 类模板 405
9.3.3 Stack类模板的另一个版本417
9.3.4 对标准C++容器类模板的
快速一瞥 418
9.4 vector容器 420
9.4.1 定义vector对象 421
9.4.2 一些vector操作 423
9.4.3 内部实现一瞥——增加
容量 427
9.4.4 对迭代器的第一次探讨 430
9.4.5 一些牵涉到迭代器的vector
函数成员 433
9.4.6 综合比较：vector对数组434
9.5 案例学习：计算机系统登录统计438
9.6 多维vector（可选） 443
9.6.1 二维vector对象 443
9.6.2 二维vector操作 444
9.7 其他标准容器——deque、stack以及queue 447
9.7.1 STL的deque类模板 447
9.7.2 我们的stack类模板的一个
新（但是非必须的）版本 450
9.7.3 STL的stack适配器 452
9.7.4 STL的queue适配器 453
9.8 Bitset和Valarray（可选）454
9.8.1 Bitset 454
9.8.2 Valarray 456
9.8.3 Slics、Mask、以及间接
数组 458
9.9 本章小结 459
第10章 ADT实现--递归、算法分析
以及标准算法 464
10.1 递归 464
10.1.1 递归的例子 465
10.1.2 递归函数的编码 466
10.1.3 糟糕递归的例子：Fibonacci
数字 468
10.1.4 例子：折半查找 470
10.1.5 例子：回文检查程序 473
10.2 递归的例子：Hanoi塔；分析478
10.2.1 Hanoi塔 478
10.2.2 分析 481
10.3 实现递归 485
10.4 算法效率 489
10.5 C++中的标准算法 500
10.5.1 例：STL的sort算法 500
10.5.2 STL算法的例子 505
10.5.3 <numeric>库中的算法 506
10.5.4 例：花样滑冰评判 507
10.6 算法正确性证明(可选) 508
10.6.1 例：计算平均值 509
10.6.2 例：递归求幂函数 510
10.6.3 总结 511
10.7 本章小节 513
第11章 其他链表结构 519
11.1 单向链表的某些变种 519
11.1.1 带头节点的链表 519
11.1.2 循环链表 522
11.2 稀疏多项式的链式实现 526
11.3 双向链表和标准C++list 534
11.3.1 双向链表 534
11.3.2 标准list类模板 536
11.3.3 例：互联网地址 542
11.3.4 对C++中list的内部一瞥546
11.4 案例学习：长整数运算 551
11.4.1 问题 551
11.4.2 设计 551
11.4.3 实现 553
11.5 其他链列表 560
11.5.1 多序列表 560
11.5.2 稀疏矩阵 561
11.5.3 广义表 563
11.6 本章小结 566
第12章 二叉树和散列表 571
12.1 线性查找和折半查找的复习571
12.1.1 线性查找 572
12.1.2 折半查找 573
12.2 二叉树的介绍 576
12.2.1 树的定义 577
12.2.2 二叉树的一些例子 578
12.2.3 二叉树的数组表示 579
12.2.4 二叉树的链表表示 581
12.3 作为递归数据结构的二叉树583
12.4 二叉查找树 589
12.4.1 BST的实现 590
12.4.2 遍历BST 592
12.4.3 BST的查找 596
12.4.4 BST中的插入操作 599
12.4.5 从BST中删除一个节点 602
12.4.6 不平衡（Lopsidedness）
问题 612
12.5 案例学习：计算机登录验证616
12.5.1 问题 616
12.5.2 设计 616
12.5.3 编码 617
12.6 线索化二叉查找树（可选）620
12.7 散列表 624
12.7.1 散列函数 625
12.7.2 冲突处理策略 626
12.7.3 改进 627
12.8 本章小结 631
第13章 排序 636
13.1 某些计算时间为O(n2)的排序
方法 637
13.1.1 选择排序 637
13.1.2 交换排序 639
13.1.3 插入排序 641
13.1.4 排序算法的性能比较 643
13.1.5 间接排序 644
13.2 堆、堆排序和优先队列 647
13.2.1 堆 648
13.2.2 堆的基本操作 649
13.2.3 堆排序 652
13.2.4 STL中的堆算法 655
13.2.5 堆和优先队列 658
13.3 快速排序 662
13.3.1 拆分操作 663
13.3.2 快速排序 665
13.3.3 改进 668
13.4 归并排序 670
13.4.1 归并列表 670
13.4.2 折半归并排序 672
13.4.3 自然归并排序 674
13.5 基数排序（Radix Sort）677
13.6 本章小结 680
第14章 OOP和ADT 684
14.1 OOP和ADT的简要历史和概览684
14.1.1 封装性 685
14.1.2 继承性 686
14.1.3 多态性和动态联编 687
14.2 继承和面向对象设计 688
14.2.1 第1个例子：许可证 689
14.2.2 公有、私有和保护域 693
14.2.3 派生类的形式 693
14.2.4 类之间的Is-a、Has-a和
Uses-a关系 694
14.3 创建派生类 696
14.3.1 派生类构造函数 697
14.3.2 访问继承的数据成员 697
14.3.3 复用操作 698
14.3.4 例子：栈和有限栈 700
14.4 案例学习：工资 703
14.4.1 问题 703
14.4.2 设计 703
14.5 多态性、虚函数和ADT 711
14.5.1 为什么需要多态性：联编
问题 711
14.5.2 虚函数和动态联编 713
14.5.3 例1：使用句柄 716
14.5.4 例2：栈和有限栈 717
14.5.5 纯虚函数和抽象类 720
14.6 案例学习：异构数据结构722
14.6.1 虚函数的必要性 723
14.7 本章小结 726
第15章 树 729
15.1 案例学习：哈夫曼编码 729
15.1.1 变长码 730
15.1.2 立刻可解码性 730
15.1.3 哈夫曼编码 731
15.2 平衡树：AVL树 735
15.2.1 例子：州简称的BST 735
15.2.2 基本的重新平衡旋转
操作 743
15.3 2-3-4树、红-黑树、B-树和
其他树 748
15.3.1 2-3-4树 750
15.3.2 红-黑树 756
15.3.3 B-树 760
15.3.4 用二叉树来表示树和
森林 761
15.4 STL中的关联容器——
map（可选） 765
15.5 本章小结 771
第16章 图和有向图 773
16.1 有向图 773
16.1.1 邻接矩阵表示（Adjacency-
Matrix Representation） 775
16.1.2 邻接表表示（Adjacency-
List Representation） 776
16.2 搜索和遍历有向图 781
16.2.1 深度优先搜索 782
16.2.2 广度优先搜索 783
16.2.3 遍历和最短路经问题 785
16.2.4 NP完全性问题 794
16.3 图 796
16.3.1 邻接矩阵和邻接表表示797
16.3.2 边列表表示 798
16.3.3 连通性 799
16.4 本章小结 810
附录A ASCII字符集 812
附录B 小测验答案 814
鄂公网安备 42010302001612号 