C++数据结构导引（国外经典教材计算机科学与技术）

第1章 软件开发 1
1.1 问题分析和需求规格说明 1
1.2 设计 3
1.2.1 对象 3
1.2.2 操作 4
1.2.3 算法 5
1.2.4 函数YearSum()的设计 5
1.2.5 函数DisplayTable()的设计 6
1.2.6 关于算法的一些最后说明 7
1.3 编码 10
1.4 测试、执行和调试 14
1.5 维护 18
1.5.1 小测验 18
1.5.2 练习 19
第2章 数据结构入门和抽象数据类型——C风格类型 21
2.1 数据结构、抽象数据类型和实现 21
2.2 简单数据类型 24
2.2.1 Boolean数据 24
2.2.2 Character数据 25
2.2.3 整型数据 26
2.2.4 实数数据 28
2.2.5 小结 30
2.2.6 小测验 31
2.2.7 练习 31
2.3 数组 32
2.3.1 一维数组 33
2.3.2 下标运算 35
2.3.3 数组作为形参 35
2.3.4 越界错误 37
2.3.5 数组的问题 37
2.3.6 多维数组 38
2.3.7 小测验 44
2.3.8 练习 45
2.4 结构 46
2.4.1 为什么需要结构 46
2.4.2 C风格结构 47
2.4.3 结构的运算 49
2.4.4 联合 50
2.4.5 内存中的结构 52
2.4.6 小测验 53
2.4.7 练习 53
2.5 过程式编程 55
2.5.1 例子：一个时间数据类型 55
2.5.2 PP对OOP 59
第3章 数据结构和抽象数据结构进阶——C++类型 64
3.1 类 64
3.1.1 “传统的”（C）结构，OOP（C++）结构以及类之间的区别 65
3.1.2 类声明 65
3.1.3 例子：C++标准I/O类 66
3.2 用户定义类型的例子：一个Time类67
3.2.1 实现一个类 68
3.2.2 一些现象 70
3.2.3 类构造函数 72
3.2.4 复制操作——初始化和赋值 76
3.2.5 访问函数 77
3.2.6 输入/输出——重载运算符——友元函数 78
3.2.7 其他操作：关系操作和前进 83
3.2.8 总结以及其他一些细节 85
3.2.9 小测验 87
3.2.10 练习 87
3.3 作为ADT的串 88
3.3.1 串的C风格实现 89
3.3.2 一个串类 90
3.3.3 练习 93
3.4 C++串类型 93
3.4.1 定义和构造函数 94
3.4.2 存储 94
3.4.3 输入/输出 94
3.4.4 string流 96
3.4.5 修改符 97
3.4.6 复制符 97
3.4.7 访问单独的字符 98
3.4.8 查找操作 98
3.4.9 比较 99
3.4.10 string和C风格串 100
3.4.11 小测验 100
3.4.12 练习 101
3.5 一个例子：文本编辑 101
3.5.1 对象 102
3.5.2 操作 102
3.5.3 文本编辑算法 102
3.6 数据加密（可选） 105
3.6.1 数据加密标准 107
3.6.2 公共密钥加密 110
3.6.3 练习 113
3.7 模式匹配（可选） 114
第4章 栈 128
4.1 栈的介绍 128
4.2 设计和创建一个Stack类 132
4.2.1 设计一个Stack类 132
4.2.2 实现一个栈类 132
4.2.3 选择数据成员 133
4.2.4 函数成员 135
4.2.5 前瞻 142
4.2.6 小测验 142
4.2.7 练习 143
4.3 栈的两个应用：函数调用，逆波兰表示 144
4.3.1 在函数调用中使用栈 144
4.3.2 逆波兰表示中栈的应用 145
4.3.3 小测验 153
4.3.4 练习 153
第5章 队列 158
5.1 队列入门 158
5.1.1 例子：训练和实践问题 159
5.1.2 调度队列的例子 163
5.2 基于数组的队列实现 165
5.2.1 小测验 168
5.2.2 练习 169
5.3 队列的应用：信息中心仿真 170
5.3.1 问题分析和需求规格说明 171
5.3.2 设计 171
5.3.3 编码和执行 174
第6章 改进ADT——第1部分： 模板和标准容器 181
6.1 介绍：可重用性和通用性的发展 181
6.1.1 从算法到算法 182
6.1.2 从数据到容器 183
6.2 函数通用性——重载和模板 183
6.2.1 重载 184
6.2.2 函数模板 186
6.2.3 例子：显示一个数组 189
6.3 类通用性——模板 190
6.3.1 Typedef有什么错 190
6.3.2 类模板 190
6.3.3 一个Stack类模板 192
6.3.4 Stack类模板的另一个版本 196
6.3.5 标准C++的容器类模板 197
6.3.6 小测验 198
6.3.7 练习 198
6.4 vector容器 198
6.4.1 定义vector对象 199
6.4.2 一些vector操作 200
6.4.3 例子：登录计数 204
6.4.4 内部实现一瞥——增加容量 207
6.4.5 对迭代器的第一次探讨 209
6.4.6 一些涉及到迭代器的vector函数成员 212
6.4.7 综合比较：vector对数组 212
6.4.8 小测验 213
6.4.9 练习 214
6.5 多维向量 215
6.5.1 二维vector对象 216
6.5.2 二维vector操作 216
6.5.3 练习 218
6.6 其他标准容器——deque、stack和queue 218
6.6.1 STL的deque类模板 219
6.6.2 Stack类模板的一个新（但是非必需的）版本 221
6.6.3 STL的stack适配器 222
6.6.4 STL的queue适配器 224
6.6.5 小测验 224
6.7 bitsets（可选） 224
6.7.1 bitset对象的声明 224
6.7.2 bitset操作 225
6.7.3 使用bitset实现集合 226
6.7.4 例子：使用埃拉托色尼（Eratoshenes）筛寻找素数 228
6.7.5 练习 230
6.8 valarrays（可选） 230
6.8.1 valarray对象的声明 231
6.8.2 valarray操作 231
6.8.3 slices、masks以及间接数组 232
6.8.4 练习 233
第7章 改进ADT——第2部分：递归，算法分析，以及标准算法 238
7.1 递归 238
7.1.1 例子：递归的求幂和求阶乘函数238
7.1.2 糟糕递归的例子：Fibonacci数字242
7.1.3 例子：折半搜索 245
7.1.4 例子：回文检查程序 246
7.1.5 小测验 248
7.1.6 练习 248
7.2 递归的例子：Hanoi塔；分析 251
7.2.1 Hanoi塔 251
7.2.2 分析 253
7.2.3 练习 258
7.3 实现递归 259
7.4 算法效率 261
7.4.1 小测验 271
7.4.2 练习 271
7.5 C++中的标准算法 272
7.5.1 例子：STL的sort算法 272
7.5.2 STL算法的例子 275
7.5.3 <numeric>库中的算法 276
7.5.4 例子：花样滑冰评判 277
7.5.5 小测验 278
7.6 算法正确性证明 278
7.6.1 例子：计算平均值 278
7.6.2 例子：递归求幂函数 280
7.6.3 总结 280
7.6.4 练习 281
第8章 列表 287
8.1 列表的顺序存储实现 287
8.1.1 存储结构 287
8.1.2 操作的实现 288
8.1.3 小测验 290
8.1.4 练习 290
8.2 对链表的介绍 290
8.2.1 它们是什么 291
8.2.2 实现基本列表操作 291
8.2.3 小结 294
8.2.4 小测验 295
8.2.5 练习 295
8.3 基于数组的链表实现 296
8.3.1 节点结构 296
8.3.2 存储池管理 298
8.3.3 练习 300
8.4 C++中的指针 301
8.4.1 指针 301
8.4.2 基本指针操作 303
8.4.3 指针的其他用法 309
8.4.4 小测验 310
8.4.5 练习 310
8.5 运行时分配和释放 311
8.5.1 New操作——运行时数组 312
8.5.2 delete操作 314
8.5.3 类中的运行时分配——析构函数、复制构造函数和赋值操作符 317
8.5.4 最后一点 325
8.5.5 小测验 327
8.5.6 练习 328
8.6 在C++中基于指针来实现链表 328
8.6.1 节点结构 329
8.6.2 LinkedList的数据成员 330
8.6.3 LinkedList的函数成员 330
8.6.4 练习 331
8.7 标准list类模板 334
8.7.1 List与其他容器类的比较 334
8.7.2 迭代器 334
8.7.3 基本list操作 334
8.7.4 例子：互联网地址 338
8.7.5 小测验 340
8.7.6 练习 340
第9章 其他链表结构 346
9.1 单向链表的某些变种 346
9.1.1 链式栈和链式队列 346
9.1.2 带头节点或尾节点的链表 347
9.1.3 循环链表 348
9.1.4 小测验 350
9.1.5 练习 350
9.2 稀疏矩阵的链式实现 351
练习 355
9.3 哈希表 356
9.3.1 哈希函数 356
9.3.2 冲突处理策略 356
9.3.3 改进 357
9.3.4 小测验 358
9.3.5 练习 359
9.4 双向链表和标准的C++链表 359
9.4.1 双向链表 359
9.4.2 对C++中列表的内部一瞥 360
9.4.3 应用：长整数运算 363
9.4.4 练习 367
9.5 其他多链列表 368
9.5.1 多序列表 368
9.5.2 稀疏矩阵 368
9.5.3 广义表 370
9.5.4 练习 372
第10章 二叉树 377
10.1 线性查找和折半查找的复习 377
10.1.1 线性查找 377
10.1.2 折半查找 378
10.1.3 练习 380
10.2 二叉树的介绍 381
10.2.1 树的定义和例子 381
10.2.2 二叉树的数组表示 382
10.2.3 二叉树的链表表示 383
10.3 二叉查找树 385
10.3.1 对BST的查找 385
10.3.2 在BST中插入项 386
10.3.3 例子：计算机登录验证 388
10.3.4 不平衡（Lopsidedness）问题391
10.3.5 小测验 392
10.3.6 练习 392
10.4 作为递归数据结构的二叉树 392
10.4.1 遍历 393
10.4.2 递归查找 396
10.4.3 递归插入 397
10.4.4 删除 397
10.4.5 小测验 402
10.4.6 练习 402
10.5 二叉树的应用：哈夫曼编码 404
10.5.1 变长码 404
10.5.2 立刻可解码性 405
10.5.3 哈夫曼编码 405
10.5.4 练习 412
第11章 排序 417
11.1 某些计算时间为O(n2)的排序方法 417
11.1.1 选择排序 417
11.1.2 交换排序 419
11.1.3 排序算法的性能比较 423
11.1.4 间接排序 424
11.1.5 小测验 424
11.1.6 练习 424
11.2 堆和堆排序 426
11.2.1 堆 426
11.2.2 堆的基本操作 427
11.2.3 STL中的堆算法 430
11.2.4 堆和优先级队列 432
11.2.5 小测验 434
11.2.6 练习 434
11.3 快速排序 436
11.3.1 拆分操作 436
11.3.2 快速排序 438
11.3.3 改进 441
11.3.4 小测验 441
11.3.5 练习 441
11.4 归并排序 442
11.4.1 归并列表 443
11.4.2 折半归并排序 444
11.4.3 自然归并排序 445
11.4.4 小测验 447
11.4.5 练习 448
第12章 OOP和ADT 452
12.1 OOP和ADTs的简要历史和概览 452
12.1.1 封装性 452
12.1.2 继承性 453
12.1.3 多态性和动态联编 453
12.1.4 小测验 454
12.2 继承和面向对象设计 454
12.2.1 从OCD到OOD 454
12.2.2 OOD的第1个例子：许可证455
12.2.3 类之间的is-a、has-a和uses-a关系 459
12.2.4 OOD的第2个例子：工资 461
12.2.5 派生类中的操作 463
12.2.6 派生类中的构造函数 463
12.2.7 OOD的第3个例子：有限栈 465
12.2.8 OOD的第4个例子：scrolls468
12.2.9 小测验 469
12.2.10 练习 469
12.3 多态性、虚拟函数和ADTs 470
12.3.1 联编问题 470
12.3.2 虚拟函数和动态联编 472
12.3.3 例子：栈、有限栈和Scroll 473
12.3.4 纯虚拟函数和抽象类 476
12.3.5 小测验 478
12.3.6 练习 478
12.4 异构数据结构 478
12.4.1 构建异构数据结构 479
12.4.2 虚拟函数的必要性 480
第13章 树 483
13.1 线索化二叉查找树 483
13.1.1 小测验 485
13.1.2 练习 486
13.2 平衡树：AVL树 486
13.2.1 例子：州简称的BST 487
13.2.2 基本的重新平衡旋转操作 491
13.2.3 小测验 493
13.2.4 练习 494
13.3 2-3-4树、红—黑树、B-树和其他树494
13.3.1 2-3-4树 495
13.3.2 红—黑树 498
13.3.3 B-树 501
13.3.4 用二叉树来表示树和森林 502
13.3.5 小测验 503
13.3.6 练习 503
13.4 STL中的关联容器——map（可选） 504
小测验 507
第14章 图和有向图 509
14.1 有向图 509
14.1.1 邻接矩阵表示 510
14.1.2 邻接表表示 511
14.1.3 小测验 512
14.1.4 练习 513
14.2 搜索和遍历有向图 515
14.2.1 深度优先搜索 516
14.2.2 广度优先搜索 516
14.2.3 遍历和最短路径问题 517
14.2.4 NP完全性问题 523
14.2.5 小测验 524
14.2.6 练习 524
14.3 图 525
14.3.1 邻接矩阵和邻接表表示 526
14.3.2 边列表表示 526
14.3.3 连通性 527
14.3.4 小测验 531
14.3.5 练习 532
附录A ASCII字符集 536
附录B 数制系统 538
练习 539
附录C 基本C++ 542
C1 C++程序结构 542
C2 编译器命令 542
C3 标准库 543
C4 注释 545
C5 标识符和关键字 545
C6 基本数据类型 547
C7 常量 548
C8 声明 548
C9 运算符和表达式 548
C10 控制结构 552
C11 函数 556
C12 对象的生命周期、作用域和名字空间 560
C13 文件 562
附录D 其他C++特性 566
D1 数组、结构和联合 566
D2 流操作 567
D3 串操作 570
D4 异常 575
D5 关于函数模板的更多信息 577
D6 指针的其他应用 578
附录E 小测验答案 583
索引 594