本书首先介绍了软件开发的各个阶段和C++面向对象程序设计，然后系统阐述了指针和动态数组、链表、模板、迭代器、堆栈、队列、递归、树和图，尤其对排序与查找的相关算法进行了深入剖析。在附录中详细介绍了大O复杂度分析、兼容性问题、C++的输入输出、标准模板类及异常输出等内容，这方面的内容是提供给学生进行课程同步阅读的。在每章中提供了相应的实例分析和程序设计作业。
本书适合于作为计算机软件专业或者其他相关专业的教科书。对于需要参加计算机考试，或者希望自学计算机软件开发的人也有非常大的帮助。
第1章 软件开发阶段 1
1.1 规范说明、设计和实现 2
1.1.1 概念设计：问题分解 3
1.1.2 前置条件和后置条件 4
1.1.3 使用其他程序员提供的函数 6
1.1.4 有关ANSI/ISO C++
标准的实现问题 7
1.1.5 自测习题 12
1.2 运行时间分析 13
1.2.1 台阶计数问题 13
1.2.2 大O表示法 17
1.2.3 C++函数的时间分析 18
1.2.4 最坏情况、平均情况和
最好情况下的时间分析 20
1.2.5 自测习题 20
1.3 测试和调试 21
1.3.1 选择测试数据 21
1.3.2 边界值 22
1.3.3 完全代码测试 22
1.3.4 调试 23
1.3.5 自测习题 23
1.4 本章小结 24
1.5 自测习题答案 24
第2章 抽象数据类型和C++类 27
2.1 类和成员 28
2.1.1 编程示例：节流阀类 28
2.1.2 使用类 31
2.1.3 节流阀类的示范程序 33
2.1.4 实现成员函数 34
2.1.5 自测习题 37
2.2 构造函数 37
2.2.1 节流阀类的构造函数 38
2.2.2 修改节流阀类的成员函数 40
2.2.3 内联成员函数 41
2.2.4 自测习题 42
2.3 使用命名空间、头文件和
实现文件 42
2.3.1 创建命名空间 42
2.3.2 头文件 43
2.3.3 实现文件 47
2.3.4 使用命名空间中的数据项 49
2.3.5 自测习题 51
2.4 类和参数 52
2.4.1 编程示例：point类 52
2.4.2 默认参数 55
2.4.3 参数 57
2.4.4 当函数返回值的类型是类时 62
2.4.5 自测习题 63
2.5 操作符重载 64
2.5.1 重载二元比较操作符 64
2.5.2 重载二元算术操作符 65
2.5.3 重载输出和输入操作符 66
2.5.4 友元函数 69
2.5.5 Point类—— 内容汇总 70
2.5.6 操作符重载的总结 72
2.5.7 自测习题 73
2.6 本章小结 73
2.7 自测习题答案 74
2.8 编程项目 77
第3章 容器类 85
3.1 包类 85
3.1.1 包类—— 规范说明 86
3.1.2 包类—— 文档说明 92
3.1.3 包类—— 示范程序 93
3.1.4 包类——设计 95
3.1.5 类的不变式 96
3.1.6 包类——实现 97
3.1.7 包类——内容汇总 103
3.1.8 包类——测试 106
3.1.9 包类——分析 107
3.1.10 自测习题 108
3.2 编程项目：序列类 109
3.2.1 序列类——规范说明 109
3.2.2 序列类——文档说明 112
3.2.3 序列类——设计 114
3.2.4 序列类——实现的伪代码 115
3.2.5 自测习题 117
3.3 交互式测试程序 117
3.4 本章小结 122
3.5 自测习题答案 123
3.6 编程项目 125
第4章 指针和动态数组 131
4.1 指针和动态内存 131
4.1.1 指针变量 132
4.1.2 使用指针的赋值操作符 134
4.1.3 动态变量和new操作符 135
4.1.4 使用new分配动态数组 136
4.1.5 堆和bad_alloc异常 138
4.1.6 操作符delete 139
4.1.7 自测习题 140
4.2 指针和数组作为参数 141
4.2.1 指针作为值参数 141
4.2.2 数组参数 143
4.2.3 指针或数组作为常量参数 144
4.2.4 指针作为引用参数 145
4.2.5 自测习题 147
4.3 用动态数组实现的包类 149
4.3.1 指针成员变量 150
4.3.2 成员函数按需分配
动态内存 151
4.3.3 值语义 154
4.3.4 析构函数 156
4.3.5 修改后的包类—— 类定义 157
4.3.6 修改后的包类—— 实现 159
4.3.7 修改后的包类——
内容汇总 163
4.3.8 自测习题 165
4.4 有关动态类的规定 166
4.4.1 4条规则 166
4.4.2 复制构造函数的
特殊重要性 166
4.4.3 自测习题 167
4.5 编程项目：字符串类 167
4.5.1 以null终结的字符串 167
4.5.2 初始化字符串变量 168
4.5.3 空字符串 168
4.5.4 读写字符串变量 169
4.5.5 函数strcpy 169
4.5.6 函数strcat 170
4.5.7 函数strlen 170
4.5.8 函数strcmp 171
4.5.9 字符串类—— 规范说明 171
4.5.10 字符串类—— 设计 175
4.5.11 字符串类—— 实现 175
4.5.12 字符串类的示范程序 177
4.5.13 串接输出操作符 178
4.5.14 声明常量对象 179
4.5.15 产生构造函数的转换 179
4.5.16 在表达式中使用重载
的操作符 180
4.5.17 本文的字符串类与C++
库中的字符串类 180
4.5.18 自测习题 180
4.6 编程项目：多项式 180
4.7 本章小结 184
4.8 自测习题答案 184
4.9 编程项目 186
第5章 链表 189
5.1 链表的基本节点类 189
5.1.1 为节点声明类 190
5.1.2 在链表节点中使用
typedef语句 191
5.1.3 头指针和尾指针 191
5.1.4 空指针 192
5.1.5 头指针或尾指针为NULL
时的含义 193
5.1.6 节点构造函数 193
5.1.7 节点成员函数 194
5.1.8 成员选择操作符 195
5.1.9 自测习题 198
5.2 链表工具包 199
5.2.1 链表工具包—— 头文件 199
5.2.2 计算链表的长度 200
5.2.3 链表的参数 203
5.2.4 在链表头插入一个新节点 204
5.2.5 在非头节点处插入一个
新节点 206
5.2.6 在链表中查找数据项 210
5.2.7 在链表中根据节点的
位置寻找节点 211
5.2.8 复制链表 212
5.2.9 从链表头删除节点 215
5.2.10 删除链表中不在头部
的节点 216
5.2.11 清除链表 217
5.2.12 链表工具包—— 内容汇总 218
5.2.13 使用链表工具包 222
5.2.14 自测习题 222
5.3 用链表实现的包类 223
5.3.1 第三个包—— 规范说明 223
5.3.2 第三个包—— 类定义 223
5.3.3 如何匹配包的value_type
和节点的value_type 226
5.3.4 在类中使用动态内存
应当遵循的规则 227
5.3.5 第三个包类—— 实现 227
5.3.6 第三个包类—— 内容汇总 234
5.3.7 自测习题 236
5.4 编程项目：用链表实现
的序列类 237
5.4.1 修改的序列类
—— 设计建议 237
5.4.2 修改后的序列类
—— 值语义 238
5.4.3 自测习题 239
5.5 动态数组、链表和双向链表 239
5.5.1 做出抉择 241
5.5.2 自测习题 241
5.6 本章小结 241
5.7 自测习题答案 242
5.8 编程项目 246
第6章 利用模板、迭代器和STL
进行软件开发 251
6.1 模板函数 251
6.1.1 模板函数的语法 253
6.1.2 使用模板函数 253
6.1.3 模板函数—— 交换两个值 255
6.1.4 模板函数的参数匹配 256
6.1.5 模板函数—— 在数组中
寻找最大项 257
6.1.6 模板函数—— 在排序数组
中插入一个数据项 258
6.1.7 自测习题 260
6.2 模板类 260
6.2.1 模板类的语法 260
6.2.2 关于模板实现文件的
其他内容 262
6.2.3 模板类成员函数的
参数匹配 267
6.2.4 使用模板类 267
6.2.5 编故事程序的细节 270
6.2.6 自测习题 270
6.3 标准模板类及其迭代器 271
6.3.1 多集模板类 271
6.3.2 多集成员 272
6.3.3 迭代器和[…)模式 272
6.3.4 测试迭代器的等同性 274
6.3.5 其他多集操作 274
6.3.6 集合算法 275
6.3.7 无效的迭代器 276
6.3.8 迭代器的标准类别 277
6.3.9 数组的迭代器 278
6.3.10 标准模板库列表类 279
6.3.11 自测习题 280
6.4 节点模板类 280
6.4.1 返回引用类型的函数 281
6.4.2 将引用返回值复制到别处
时发生的情况 283
6.4.3 成员函数data目前需要
两个版本 283
6.4.4 新节点的头文件和
实现文件 283
6.4.5 自测习题 290
6.5 链表的迭代器 291
6.5.1 节点迭代器 291
6.5.2 节点迭代器源自
std::iterator 293
6.5.3 节点迭代器的私有
成员变量 293
6.5.4 节点迭代器—— 构造函数 293
6.5.5 节点迭代器—— *操作符 293
6.5.6 节点迭代器—— 操作符++
的两个版本 294
6.5.7 节点迭代器—— 相等和
不相等的比较 295
6.5.8 常量集合的迭代器 296
6.5.9 自测习题 297
6.6 含有迭代器的包模板类
的链表版本 298
6.6.1 如何为容器类提供迭代器 298
6.6.2 包迭代器 299
6.6.3 将迭代器定义在包中
的原因 299
6.6.4 自测习题 306
6.7 本章小结和5个包的总结 306
6.8 自测习题答案 307
6.9 编程项目 311
第7章 堆栈 313
7.1 堆栈和STL堆栈的简介 313
7.1.1 标准库的堆栈类 315
7.1.2 编程示例：翻转单词 316
7.1.3 自测习题 316
7.2 堆栈的应用 317
7.2.1 编程示例：括号的平衡 317
7.2.2 编程示例：
算术表达式求值 319
7.2.3 算术表达式求值
——规范说明 319
7.2.4 算术表达式求值—— 设计 319
7.2.5 算术表达式求值—— 实现 325
7.2.6 计算器程序使用的函数 325
7.2.7 算术表达式求值——
测试与分析 325
7.2.8 算术表达式求值—— 改进 326
7.2.9 自测习题 326
7.3 堆栈类的实现 327
7.3.1 堆栈的数组实现 327
7.3.2 堆栈的链表实现 330
7.3.3 Koenig查找 333
7.3.4 自测习题 333
7.4 更复杂的堆栈应用 334
7.4.1 后缀表达式求值 334
7.4.2 将中缀表示法转换成
后缀表示法 336
7.4.3 在中缀表达式中使用
优先级规则 338
7.4.4 中缀转换为后缀的正确性 340
7.4.5 自测习题 341
7.5 本章小结 342
7.6 自测习题答案 342
7.7 编程项目 344
第8章 队列 349
8.1 队列和STL队列的简介 349
8.1.1 标准库的队列类 350
8.1.2 队列的使用 350
8.1.3 自测习题 352
8.2 队列的应用 352
8.2.1 编程示例：识别回文 352
8.2.2 自测习题 355
8.2.3 编程示例：洗车模拟 355
8.2.4 洗车模拟—— 规范说明 355
8.2.5 洗车模拟—— 设计 355
8.2.6 洗车模拟—— 实现洗车类 358
8.2.7 洗车模拟——
实现模拟函数 363
8.2.8 自测习题 365
8.3 队列类的实现 365
8.3.1 队列的数组实现 365
8.3.2 有关队列中循环数组
实现的讨论 369
8.3.3 队列的链表实现 371
8.3.4 实现细节 372
8.3.5 自测习题 377
8.4 优先队列 377
8.4.1 如何指定优先级 378
8.4.2 标准库的优先队列类 378
8.4.3 优先队列类——实现思想 379
8.4.4 自测习题 379
8.5 堆栈、队列和优先队列
类的引用返回值 379
8.6 本章小结 380
8.7 自测习题答案 380
8.8 编程项目 381
第9章 递归思想 385
9.1 递归函数 385
9.1.1 递归思想的第一个例子 385
9.1.2 跟踪递归调用 387
9.1.3 编程示例：write_vertical
的一个扩展 388
9.1.4 深入分析递归 389
9.1.5 成功递归函数的一般形式 392
9.1.6 自测习题 392
9.2 递归的研究：分形和迷宫 393
9.2.1 编程示例：产生随机分形 393
9.2.2 用于产生随机分形的函数
—— 规范说明 395
9.2.3 分形函数的设计和实现 396
9.2.4 如何显示随机分形 398
9.2.5 编程示例：穿越迷宫 399
9.2.6 穿越迷宫—— 规范说明 399
9.2.7 穿越迷宫—— 设计 401
9.2.8 穿越迷宫—— 实现 401
9.2.9 运用回溯穷举搜索的
递归模式 403
9.2.10 编程示例：玩具熊游戏 404
9.2.11 自测习题 406
9.3 推导递归 406
9.3.1 如何确保没有无限递归 408
9.3.2 归纳推导递归函数
的正确性 410
9.3.3 自测习题 411
9.4 本章小结 411
9.5 自测习题答案 412
9.6 编程项目 414
第10章 树 419
10.1 树的简介 419
10.1.1 二叉树 419
10.1.2 二叉分类树 422
10.1.3 一般树 422
10.1.4 自测习题 423
10.2 树的表示法 424
10.2.1 完全二叉树的数组
表示法 424
10.2.2 使用节点类表示二叉树 427
10.2.3 自测习题 428
10.3 二叉树节点类 429
10.3.1 编程示例：猜动物 432
10.3.2 动物猜测程序——
设计和实现 434
10.3.3 动物猜测程序—— 改进 438
10.3.4 自测习题 441
10.4 树的遍历 441
10.4.1 二叉树的遍历 441
10.4.2 从树的节点中输出数据 445
10.4.3 遍历中的问题 446
10.4.4 函数作为参数 447
10.4.5 apply函数的一个
模板版本 448
10.4.6 使apply模板函数更
具有通用性 449
10.4.7 树遍历的模板函数 450
10.4.8 自测习题 451
10.5 二叉搜索树 458
10.5.1 二叉搜索树存储机制 458
10.5.2 第6个包—— 类定义 462
10.5.3 第6个包——
某些简单函数的实现 462
10.5.4 计算某个元素在二叉
搜索树中出现的次数 462
10.5.5 添加一个新元素到
二叉搜索树中 463
10.5.6 从二叉搜索树中移除
某个元素 464
10.5.7 二叉搜索树的
组合操作符 467
10.5.8 时间分析和迭代器 469
10.5.9 自测习题 469
10.6 本章小结 469
10.7 自测习题答案 470
10.8 编程项目 473
第11章 树项目 479
11.1 堆 479
11.1.1 堆的存储规则 479
11.1.2 使用堆结构实现的
优先队列ADT 480
11.1.3 插入新项 480
11.1.4 删除项 482
11.1.5 自测习题 484
11.2 B树 484
11.2.1 非平衡树的问题 484
11.2.2 B树的规则 485
11.2.3 B树的一个示例 486
11.2.4 B树实现的集合ADT 487
11.2.5 在B树中查找项 491
11.2.6 在B树中插入项 493
11.2.7 B树的松散插入操作 493
11.2.8 修正子节点多余项的
私有成员函数 495
11.2.9 回到成员函数Insert 496
11.2.10 采用自顶向下
方法设计 497
11.2.11 从B树中删除项 498
11.2.12 B树的松散删除操作 499
11.2.13 解决子节点项短缺
问题的私有成员函数 501
11.2.14 从B树中删除最大的项 503
11.2.15 外部B树 505
11.2.16 自测习题 505
11.3 树、日志和时间分析 506
11.3.1 二叉搜索树的时间分析 506
11.3.2 堆的时间分析 507
11.3.3 对数运算 508
11.3.4 对数级算法 509
11.3.5 自测习题 510
11.4 本章小结 510
11.5 自测习题答案 510
11.6 编程项目 513
第12章 查找 515
12.1 顺序查找和二分查找 515
12.1.1 顺序查找 515
12.1.2 顺序查找—— 分析 516
12.1.3 二分查找 517
12.1.4 二分查找—— 设计 518
12.1.5 二分查找—— 分析 520
12.1.6 标准库查找函数 523
12.1.7 用于有序域的函数 523
12.1.8 用于无序域的函数 525
12.1.9 STL查找函数 526
12.1.10 自测习题 526
12.2 开地址散列 526
12.2.1 散列简介 526
12.2.2 表类—— 声明 529
12.2.3 表类—— 设计 530
12.2.4 表ADT—— 实现 533
12.2.5 选择散列函数来
减少冲突 538
12.2.6 再散列减少聚类 538
12.2.7 自测习题 540
12.3 链式散列 540
12.3.1 链式散列 540
12.3.2 自测习题 542
12.4 散列的时间分析 542
12.4.1 散列表的装填因子 542
12.4.2 自测习题 545
12.5 程序设计：使用STL
向量的表类 545
12.5.1 新表类 545
12.5.2 在新表类中使用向量 545
12.5.3 常量模板参数 545
12.5.4 函数模板参数 546
12.5.5 实现新表类 546
12.5.6 自测习题 547
12.6 STL中的匹配和多重匹配 547
12.7 本章小结 548
12.8 自测习题答案 549
12.9 编程项目 552
第13章 排序 555
13.1 二次排序算法 555
13.1.1 选择排序—— 规范说明 555
13.1.2 选择排序—— 设计 556
13.1.3 选择排序—— 实现 558
13.1.4 选择排序—— 分析 560
13.1.5 插入排序 561
13.1.6 插入排序—— 分析 564
13.1.7 自测习题 566
13.2 递归排序算法 567
13.2.1 使用递归的分治法 567
13.2.2 合并排序 569
13.2.3 合并函数 571
13.2.4 动态内存在合并排序
中的应用 575
13.2.5 合并排序——分析 575
13.2.6 文件的合并排序 577
13.2.7 快速排序 577
13.2.8 partition函数 579
13.2.9 快速排序—— 分析 581
13.2.10 快速排序—— 选择一个
好的基准元素 583
13.2.11 自测习题 583
13.3 使用堆的O(n log n)算法 584
13.3.1 堆排序 584
13.3.2 构建堆 589
13.3.3 向下重排 590
13.3.4 堆排序—— 分析 591
13.3.5 自测习题 592
13.4 使用库函数排序和随机
访问迭代器 592
13.4.1 原始C qusort 函数 592
13.4.2 STL排序函数 593
13.4.3 使用迭代器编写一个
排序函数 593
13.5 本章小结 594
13.6 自测习题答案 595
13.7 编程项目 597
第14章 派生类和继承 601
14.1 派生类 601
14.1.1 如何声明派生类 603
14.1.2 派生类的自动构造函数 604
14.1.3 使用派生类 605
14.1.4 派生类的自动赋值
操作符 606
14.1.5 派生类的自动析构函数 607
14.1.6 覆盖继承的成员函数 607
14.1.7 自测习题 608
14.2 仿真生态系统 608
14.2.1 实现部分生物对象层次 609
14.2.2 organism类 609
14.2.3 animal类：具有新私有
成员变量的派生类 612
14.2.4 如何为派生类提供新
的构造函数 612
14.2.5 animal类的其他
成员函数 614
14.2.6 自测习题 617
14.2.7 Herbivore类 618
14.2.8 池塘生活仿真程序 620
14.2.9 池塘生活——实现细节 623
14.2.10 使用池塘模型 624
14.2.11 动态内存的使用 625
14.2.12 自测习题 625
14.3 虚拟成员函数和game类 625
14.3.1 game类简介 626
14.3.2 受保护的成员 629
14.3.3 虚拟成员函数 629
14.3.4 虚拟析构函数 630
14.3.5 游戏类的受保护虚拟
成员函数 630
14.3.6 玩Connect Four游戏
的派生类 631
14.3.7 Connect Four游戏类
的私有成员变量 631
14.3.8 Connect Four的构造
函数和重启函数 633
14.3.9 三个处理游戏状态
的Connect Four函数 633
14.3.10 三个处理移动的
Connect Four函数 634
14.3.11 Clone函数 634
14.3.12 编写派生自
game类的游戏 635
14.3.13 使用minimax的游戏
类的play算法 635
14.3.14 自测习题 638
14.4 本章小结 638
14.5 进阶阅读 639
14.6 自测习题答案 639
14.7 编程项目 643
第15章 图 645
15.1 图的定义 645
15.1.1 无向图 645
15.1.2 有向图 648
15.1.3 图的更多术语 649
15.1.4 航线的例子 650
15.1.5 自测习题 650
15.2 图的实现 651
15.2.1 使用邻接矩阵表示图 651
15.2.2 使用二维数组存储
邻接矩阵 652
15.2.3 使用边列表表示图 652
15.2.4 使用边集表示图 653
15.2.5 哪种表示方法最好 653
15.2.6 编程示例：标签图类 654
15.2.7 用于增加顶点和边的
成员函数 655
15.2.8 标签图类—— 重载
下标操作符 655
15.2.9 下标操作符的常量版本 656
15.2.10 标签图类——
函数neighbors 657
15.2.11 标签图类——实现 657
15.2.12 自测习题 657
15.3 图的遍历 662
15.3.1 深度优先搜索 663
15.3.2 宽度优先搜索 666
15.3.3 深度优先搜索—— 实现 668
15.3.4 宽度优先搜索—— 实现 669
15.3.5 自测习题 669
15.4 路径算法 671
15.4.1 判断某条路径是否存在 671
15.4.2 具有加权边的图 672
15.4.3 最短距离算法 672
15.4.4 最短路径算法 680
15.4.5 自测习题 681
15.5 本章小结 681
15.6 自测习题答案 681
15.7 编程项目 683
附录A ASCII字符集类 687
附录B 大O表达式 689
附录C 操作符的优先顺序 693
附录D 命令行编译和链接 695
附录E 使用旧式编译器 699
附录F C++的输入和输出 703
附录G 选择库函数 711
附录H 标准模板类简介 715
附录I useful函数的工具箱 725
附录J 基本格式指南 729
附录K 下载GNU编译器和软件 731
附录L 异常处理 733
本书是为计算机科学专业二级课程编写的，在美国许多大学称之为CS 2课程。本书将授课重点放在规范说明、设计、实现以及基本数据类型的使用上，其中有关使用的内容通常在第二学期的课程中讲授。此外，本书涵盖了重要的编程技术，并提供各自独立的抽象技术、面向对象编程、大O时间分析算法和排序等内容。
我们假设学生已经完成了《计算机科学导论》和《程序设计》等课程的学习，但本书还是包含了一些基础课程中没有完全涵盖到的主题(例如递归和指针)。在本书中，所有的代码均采用C++语言编写，但有关C++类的内容比较浅显，因此本书仍旧适合那些以C语言而不是C++语言作为程序设计语言入门的学生。根据以往的经验，这些学生需要对C++输入与输出技术(参见附录F)有所了解，此外还需要学习有关C++参数类型(参见第2章)的内容。当C程序员克服了有关输入/输出和参数的障碍后，他们将能够领略类和其他C++面向对象的特征。需要说明的是，根据学生不同的知识背景，本书可以有多种不同的学习方案，尤其是对那些具有较强应用背景的学生来说，可以有选择地学习本书的内容。
01 第3版：新增内容和附加的Web支持
在第3版中，每种数据类型的讲授顺序和主题概要均与第1版相同。对于那些已经采用较早版本进行授课的教师来说，仍旧可以利用本书继续教学，只是需要做一些改变。这些改变是由于C++标准模板库容器类不断增长的内容而引发的，特别是：
● 第1章和附录L新增有关异常处理的内容。
● 第5章扩展有关常量指针的正确用法。
● 第6章扩展有关标准模板库迭代器、集合、多集的内容。
● 第9章新增递归示例。
● 第12章新增一个利用vectors容器实现散列表的项目。此外，通过利用标准模板库容器作为基本数据结构可以成功地实现其他项目，例如B树。
● 第12章和附录H扩展有关列表、映射、多重映射类的内容。
在本书的课程中，仍旧着重要求学生必须理解所有层次的数据结构，包括：规范说明、设计、实现、测试和分析。然而，从长远来看，将要在计算机科学领域继续深造的学生将会对标准模板库(Standard Template Library，STL，已经规范为1998标准的一部分)的数据类型有更进一步的应用，例如利用STL类来成功实现诸如B树等复杂的数据结构。
从本书中，读者也会发现以下内容：
● 许多新的自测习题
● 新的编程项目
访问我们的项目网站www.cs.colorado.edu/~main/dsoc.html可以获取我们新开发的项目。
02 每种数据类型的5个步骤
总体来说，第3版保留了最经典的数据类型：集合、包(或多集)、序列、有序列表(利用“小于”操作符排序)、堆栈、队列、表和图。此外，还额外补充了一些数据类型，例如优先队列。上述每种数据类型都将会按照下列固定的模式进行介绍。
第1步：抽象地理解数据类型。在这一层次，学生可从概念和图形的层次上获取有关数据类型及其操作的理解。例如，学生可以采用可视化的方法理解堆栈及其元素的入栈和出栈操作。学生可以理解简单的应用程序，并手动加以实现，例如利用堆栈翻转一个单词的字母次序。
第2步：将数据类型的规范说明编写为C++类。在这一步中，学生将学会如何为实现数据类型的C++类编写规范说明。规范说明包含构造函数、公有成员函数的原型和其他公有属性(例如一个用于决定堆栈最大尺寸的基本常量)。每个成员函数的原型随同用于完整描述函数行为的前置条件/后置条件一起发布。在这一层次中，规范说明与任何选定的特定实现技术是无关的，让学生意识到这一点非常重要。事实上，可以为同一数据类型的几种不同实现使用相同的规范说明。
第3步：使用数据类型。在理解规范说明之后，学生可以编写一些小的应用程序或者演示程序来展示数据类型的使用。这些应用程序只是基于数据类型的规范说明，因为我们还没有完成数据类型的实现。
第4步：选择适当的数据结构，继续设计和实现数据类型。在对数据类型有了很好的抽象理解之后，我们就可以选择适当的数据结构了，例如定长数组、动态数组、节点的链表或节点构成的二叉树。对于许多数据类型，我们最初的设计和实现将会选择较简单的方法，例如采用定长数组。随后，我们会使用更加复杂的基本结构来重新设计和实现相同的数据类型。
由于使用的是C++类，数据类型的实现将选定的数据结构(数组、指针等)作为类的私有成员变量。对于每个已经实现的类，本书强调需要清楚地理解将私有成员变量和数据类型的抽象概念相关联的规则。我们要求每个学生能用简洁的英文句子写出这些规则，并且称这些规则为抽象数据类型的不变式。一旦不变式编写完毕，学生就可以继续实现各种成员函数。不变式有助于编写正确的函数，这是因为：(a)当函数开始执行时，每个函数(除了构造函数)均知道不变式为真；(b)当函数结束时，每个函数(除了析构函数)都负责确保不变式再次为真。
第5步：分析实现。每个实现的分析包括：正确性、灵活性(例如采用固定尺寸还是动态尺寸)和操作的时间分析(利用大O表示法)。当利用多种方法实现相同的数据类型之后，学生就会有牢固的基础来进行这些分析。
03 在课程结束时，学生将会学到什么
在本课程结束时，学生将能够彻底地理解数据类型。他们将学会如何使用数据类型；如何通过多种方式实现这些数据类型；明确不同实现的实际效果。学生能够利用大O分析探究效率，通过参考类的不变式验证实现的正确性。
本课程的重要持久影响之一是对规范说明、设计和实现方面的体验，以及程序推理能力的提高。但最重要的也许是展示了能够简单地应用于多种情况的类。学生无需每次都从头开始编写所有的一切。我们告诉学生，将来某一天，当他们正在思考某个问题的时候，可能会突然发现大量的工作原本可以用包、堆栈、队列等方法来完成，并且这些工作根本不需要真正动手去实现，而是可以不加修改地直接利用本学期编写的包、堆栈、队列等来完成。或者，更有可能的是，他们将可以利用标准数据类型库中各种熟悉的数据类型，例如C++标准模板库。实际上，本书介绍的数据类型只是标准模板库的精简版本，因此当学生开始进一步学习真正的STL时，他们将会有一个较为熟悉的基础。在此基础上加以实现时，学生将会知道哪种数据类型正是他或她所需要的，此时学生将会成为一名真正的程序员。
04 其他基础知识
贯穿本课程，除了讲授基本的数据结构之外，还将为“真实程序设计”的其他方面打下基础，并涵盖以下基础知识：
面向对象编程 通过让学生深入理解C++类来为面向对象编程(Object-Oriented Programming，OOP)打下基础。在课程的早期将会介绍有关类的重要内容：成员函数的概念、私有和公有成员的区别、构造函数的用途和操作符重载等。这些内容足以令学生顺利而兴奋地进入类的学习。
有关类的主要方面将会在学生第一次使用动态内存时(第4章)进一步介绍。在第4章中，我们将对复制构造函数、重载赋值操作符以及析构函数这3个额外元素的需求加以解释。通过第一次使用动态内存来讲授这些OOP方面的知识，能够给学生一个有关动态内存的具体影像，即动态内存是一种能够被使用但是必须在最后被回收的资源。
从概念上来讲，OOP最大的革新在于通过继承实现了软件重用。当然，也可以在数据结构这门课程一开始就介绍继承的概念(例如实现一个集合类作为包类的子类)。然而，过早介绍这些概念也会带来一定的麻烦，学生一下子受困于过多的新概念，会弱化对数据结构基础的理解。因此，将继承放在本课程的最后介绍。但继承的概念也可以在理解了复制构造函数之后(14.1节和14.2节)就开始学习。出于这种想法，有些教师可能希望在堆栈和队列之前讲解第14章。
另一种替代方法是将那些已经了解类的基本知识的学生分离出来，让他们完成继承项目(例如14.2节中的生态系统或14.3节中的游戏引擎)，而其他的学生则要先学习类。
模板 模板函数和模板类是标准模板库的一个重要部分，它们便于程序员随意更改容器类中基本数据项的类型。模板类也允许在一个简单的程序中使用多个不同的实例。同样，我们也认为在堆栈(第7章)之前学习并使用模板(第6章)非常重要，这是因为表达式求值是使用堆栈的一个重要应用，它采用了两种类型的堆栈。
迭代器 迭代器是标准模板库的另一个重要部分，它便于程序员遍历容器对象中的数据项(例如集合或包中的元素)。这种迭代器可以是内部的(与容器类成员函数一起实现)或外部的(由容器类的一个独立友元类实现)。我们在讲述第一个容器类时(3.2节的序列)介绍内部迭代器。在第6章中，将会根据需要向包类添加一个内部迭代器。同时，也将会讨论更复杂的外部迭代器，学生应当意识到外部迭代器的优点。总之，迭代器为许多编程项目提供了一个很好的机会，例如实现一个外部包迭代器(第6章)，或者利用堆栈实现二叉搜索树的内部迭代器(第10章)。
递归 第一学期的课程不时地向学生介绍递归，但是第一学期的许多例子都是尾递归(tail recursion)，尾递归中函数的最后一步就是递归调用，这也许会误导学生错误地认为递归只不过是一个循环。正因为如此，我们在第二学期的课程中尽可能避免过早地使用尾递归。例如，链表遍历和其他链表的操作都可以利用尾递归来实现，但其影响可能会增强对递归的错误印象(当学生在操作含有成千上万个数据项的链表时，应当忘记尾递归链表的操作，以避免遇到潜在的运行时栈溢出)。
因此，在第二学期的课程中，我们将强调除尾递归之外的更多的递归解决方案。第9章“递归思想”中提供了遵循此理念的3个例子。学生将会对其中的两个例子——产生随机分形和穿越迷宫非常感兴趣。在本课程中，我们将在树(第10章)之前讲授递归
无封面
第二书店&China-pub战略联盟提供专业服务
第二书店联系方式 010-64348411 webmaster@dearbook.com