书籍详情
数据结构与问题求解（C++版）
作者：（美）Mark Allen Weiss著；张丽萍译
出版社：清华大学出版社
出版时间：2005-01-01
ISBN：9787302111665
定价：¥86.00
购买这本书可以去
内容简介
本书从抽象思想、问题解决以及C编程语言使用的观点介绍了数据结构和算法。本书中包含了C的最新特性，任何地方都可以完全使用标准模板库（STL）。C允许程序员分开编写接口和实现，将它们保存在单独编译的文件中，并隐藏实现的具体细节。本书深入了一层：数据结构的接口和实现在本书的不同部分讨论。第一部分（对象和C）、第二部分（算法和构建块）、第三部分（应用程序）打基础，专门讨论各种基本概念并提供实践中的一些例子。第四部分（实现）介绍数据结构的实现。接口与实现的这种分离促进了抽象思想。将类接口放在实现之前编写与使用，这就迫使读者去思考各种数据结构的功能性和潜能（例如，在实现优先队列之前就使用它了）。特色：加入了C最新的发展，包含一个有关模型的新章节，并且从头到尾都使用了vector类。包含在恰当时使用了STL的修订材料。介绍高级使用C较重要的细节的同时，介绍了类和继承（这两者简化了最初的表示法）的一些新内容。阐述了数据结构的STL接口，并提供了STL实现，同时也提供了不使用STL的简化过的接口，这使得理解数据结构的基础知识更加简单，没有了STL的复杂性。包含大量的代码。这些都已被全面重写并测试过，可兼容当前各种各样的编译器。本书前言序言本书是为计算机科学专业的第2学期的课程而编写的，从典型的《数据结构》（CS-2，即计算机科学专业第2学期）开始直到高级的数据结构和算法分析。CS-2课程的内容经历过一段时间的演变。尽管多数人都同意这样的主题安排，但在具体的细节上还是有较大的分歧。获得一致认可的主题是软件开发的原则，最突出的是封装和信息隐藏的概念。理论上，所有的CS-2课程都倾向于包含运行时分析、递归、基本的排序方法和初等数据结构。许多大学还开设了高级课程，主题涉及到高级的数据结构、算法、运行时分析。本书中的材料设计同时考虑到这两种级别，因此读者不必再另外购买其他教科书。尽管如此，争论最激烈的还是CS-2中编程语言的选择以及其他几项必要的基本选择，包括：是否这么早就介绍面向对象的设计或基于对象的设计。对数学水平的要求。在实现数据结构及其使用之间达到恰当的平衡点，以及与所选语言相关的编程细节。笔者写本书的目的是，从抽象思维和问题求解的角度来介绍数据结构和算法。笔者试图覆盖所有与数据结构、分析及其C实现有关的重要内容，同时对那些理论上似乎很有意义但实际上很少使用的数据结构，则是避而远之。几乎不可能有哪本书能像本书一样在一门课程里讲述所有不同的数据结构，包括数据结构的使用。因此，笔者设计了本教材，以便让教师能够灵活地选择主题。教师需要在实践和理论之间寻求平衡，然后选择最适合课程需要的主题。正如此序言后面所讨论的那样，笔者对课本进行了细致的组织，尽可能地降低了各章之间的依赖性。统一的方法笔者的基本假设是基于任何语言的软件开发工具都有一个庞大的库，许多数据结构就是这些库的一部分。笔者预感到数据结构教学的重心将从实现转向使用。在本书中，笔者采用了一套独特的方法，将数据结构分成规范和实现，并充分利用已有的数据结构库，即标准模板库（StandardTemplateLibrary，STL）。在第二部分将会有一章（第7章）单独讲述适合大多数应用程序的STL子集。第二部分还讲述了基本的分析技术、递归和排序。第三部分介绍使用STL数据结构的应用程序。直到第四部分已经使用数据结构之后，才开始介绍STL的实现。因为STL是C的一部分（较早的编译器则使用本教材中的STL代码，请参阅稍后的"代码可用性"部分），学生可以使用现有的软件组件来设计大型项目。尽管本书中大量使用了STL，但本书并非针对STL的专著，也不是专门讲述STL实现的入门读物。本书的重点在于数据结构和基本的问题求解技术。当然，数据结构设计中使用的技术大都适用于STL的实现，因此在第四部分有几章介绍了STL的实现。然而，教师可以选择第四部分中较简单的实现，而不必讨论STL协议。第7章介绍了STL，这对理解第三部分的代码很有必要。笔者只是使用了一些基本的STL。许多教师更喜欢定义、实现，然后使用每个数据结构的传统方法。由于第三部分和第四部分中的材料之间并不存在依赖关系，因此可以利用本书轻松地教授传统方法。预备技能阅读本书的学生应该了解一门面向对象或面向过程的编程语言。必须了解编程语言的基本特征，包括基元数据类型、运算符、控制结构、函数（方法）、输入和输出（但并不需要了解数组和类）。已初步接触过C或Java的学生可能会觉得前两章的某些内容很简单。但其他部分所讲的C技术细节则相对比较深奥，在入门课程中可能不会讲到这些知识。学习了其他语言课程的学生应该从第1章开始学习，并且应该仔细研读。还应该查阅附录A，因为附录A中讨论了某些专属于C的语言问题。如果喜欢同时参阅一本C参考书，可以参考第1章中给出的推荐书目。离散数学方面的知识对学习本书很有帮助，但并非绝对必要。本书给出了几个数学证明，但对于更复杂的证明，则提示读者复习有关的数学知识。第8章以及第19～24章需要具备一定程度的数学技能。教师可以轻松地选择跳过数学证明，而只介绍证明结果。本书中所有的数学证明都被清晰地标出来了，并与本书正文部分分开。
作者简介
暂缺《数据结构与问题求解（C++版）》作者简介
目录
第一部分 对象和C++
第1章 数组、指针和结构 1
1.1 什么是指针、数组和结构 1
1.2 数组和字符串 2
1.2.1 头等对象与次等对象的对比 2
1.2.2 使用Vector 3
1.2.3 调整Vector大小 5
1.2.4 push_back大小与容量 7
1.2.5 参数传递机制 7
1.2.6 常量基元数组 9
1.2.7 多维数组 9
1.2.8 标准库类型string 9
1.3 C++中的指针语法 10
1.4 动态内存管理 14
1.4.1 new运算符 15
1.4.2 垃圾收集与delete 15
1.4.3 过期指针、双重删除及其他 16
1.5 引用变量 17
1.6 结构 19
1.6.1 指向结构的指针 21
1.6.2 外部数据与内部数据、深复制与浅复制 21
1.6.3 非邻接链表：链表 23
小结 24
学习目标 24
常见错误 25
网上资源 26
练习 26
简答题 26
实践题 28
编程项目 28
参考文献 28
第2章 对象和类 30
2.1 什么是面向对象编程 30
2.2 类的基本语法 31
2.2.1 类成员 31
2.2.2 附加的构造函数语法和访问函数 33
2.2.3 接口和实现的分离 35
2.2.4 析构函数、复制构造函数和赋值运算符（=） 38
2.2.5 默认的构造函数 43
2.3 附加的C++类特性 43
2.3.1 调整后的构造函数中的初始化与赋值 47
2.3.2 类型转换 48
2.3.3 运算符重载 49
2.3.4 输入、输出和友元 52
2.4 一些常用术语 54
2.4.1 避免使用友元 54
2.4.2 静态类成员 55
2.4.3 整型类常量的陷阱 55
2.5 异常 56
2.6 String类 57
2.7 要点重述：进行了哪些调用？
哪些采用了默认行为 65
2.8 组合 66
小结 67
学习目标 68
常见错误 69
Internet资源 70
练习 70
简答题 70
理论题 71
编程项目 72
参考文献 75
第3章 模板 76
3.1 模板的概念 76
3.2 函数模板 76
3.3 排序函数模板 78
3.4 类模板 81
3.4.1 MemoryCell模板 81
3.4.2 实现vector类模板 85
3.5 模板的模板：matrix类 87
3.5.1 数据成员、构造函数和基本附件 88
3.5.2 operator [ ] 89
3.5.3 析构函数、复制赋值和复制构造函数 89
3.6 Fancy模板 89
3.6.1 多平台参数 89
3.6.2 默认的模板参数 90
3.6.3 保留字typename 90
3.7 与模板有关的bug 90
3.7.1 错误消息和改变的规则 91
3.7.2 模板匹配算法 91
3.7.3 模板中的嵌套类 91
3.7.4 类模板中的静态成员 91
小结 91
学习目标 91
常见错误 92
Internet资源 92
练习 93
简答题 93
实践题 93
编程项目 93
第4章 继承 94
4.1 什么是继承 94
4.2 继承的基本知识 97
4.2.1 可视性规则 98
4.2.2 构造函数和基类初始化 98
4.2.3 添加成员 99
4.2.4 覆盖方法 101
4.2.5 静态绑定和动态绑定 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.2 默认参数 114
4.4.3 派生类方法隐藏基类方法 114
4.4.4 覆盖方法的兼容返回类型 115
4.4.5 私有继承 116
4.4.6 友元 116
4.4.7 值调用与多态并不混淆 117
4.5 多重继承 117
小结 118
学习目标 119
常见错误 119
Internet资源 120
练习 120
简答题 120
实践题 122
编程项目 122
参考文献 122
第5章 设计模式 123
5.1 模式的概念 123
5.2 Functor（函数对象） 124
5.3 适配器和包装器 129
5.3.1 指针包装器 129
5.3.2 常数引用包装器 134
5.3.3 适配器更改接口 135
5.4 迭代器 136
5.4.1 迭代器设计1 137
5.4.2 迭代器设计2 139
5.4.3 基于继承的迭代器和
factory 139
5.5 合成（对） 144
5.6 观察者 144
小结 148
学习目标 148
常见错误 149
Internet资源 149
练习 150
简答题 150
理论题 150
实践题 150
编程项目 152
参考文献 152
第二部分 算法和构建代码块
第6章 算法分析 153
6.1 什么是算法分析 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 静态查找问题 169
6.6.1 顺序查找 169
6.6.2 折半查找 169
6.6.3 插值查找 172
6.7 算法分析的检验 173
6.8 Big-Oh分析的限制 174
小结 174
学习目标 174
常见错误 175
Internet资源 175
练习 176
简答题 176
理论题 177
实践题 179
编程项目 179
参考文献 180
第7章 标准模板库 182
7.1 简介 182
7.2 堆栈和队列 183
7.2.1 堆栈 184
7.2.2 堆栈和计算机语言 185
7.2.3 队列 186
7.3 容器和迭代器 187
7.3.1 容器 187
7.3.2 迭代器 188
7.4 STL算法 189
7.4.1 STL函数对象 189
7.4.2 二分查找法 191
7.4.3 排序 193
7.5 实现带有迭代器的vector 193
7.6 顺序表和链表 195
7.6.1 list类 195
7.6.2 堆栈和队列 196
7.7 集合 197
7.8 映射 199
7.9 优先队列 200
小结 203
学习目标 204
常见错误 204
Internet资源 205
练习 205
简答题 205
理论题 205
实践题 206
编程项目 206
参考文献 208
第8章 递归 209
8.1 递归的概念 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 数值应用 223
8.4.1 模运算 223
8.4.2 模幂运算 224
8.4.3 最大公约数和乘法逆元素 225
8.4.4 RSA密码系统 228
8.5 分治算法 230
8.5.1 最大邻近子序列和问题 230
8.5.2 基本分治递归分析 233
8.5.3 分治法运行时间的一般上限 235
8.6 动态规划 237
8.7 回溯法 241
小结 244
学习目标 244
常见错误 245
Internet资源 245
练习 246
简答题 246
理论题 246
实践题 247
编程项目 248
参考文献 249
第9章 排序算法 250
9.1 排序为何重要 250
9.2 预备知识 251
9.3 插入排序和其他简单排序的分析 252
9.4 希尔排序 254
9.5 归并排序 257
9.5.1 排过序的数组的线性时间合并 257
9.5.2 归并排序算法 259
9.6 快速排序 261
9.6.1 快速排序算法 261
9.6.2 快速排序的分析 263
9.6.3 支点的选择 265
9.6.4 分组策略 267
9.6.5 同支点相等的键 268
9.6.6 中值划分 269
9.6.7 小数组 270
9.6.8 C++快速排序例程 270
9.7 排序选择 272
9.8 排序的下限 274
9.9 间接排序 275
9.9.1 使用指针将Comparable
副本数减少为2N 275
9.9.2 避免附加数组 276
小结 278
学习目标 279
常见错误 279
Internet资源 279
练习 280
简答题 280
理论题 280
实践题 281
编程项目 282
参考文献 283
第10章 随机 285
10.1 为什么我们需要随机数 285
10.2 随机数生成器 286
10.3 非均匀随机数 290
10.4 生成随机排列 291
10.5 随机算法 293
10.6 随机素数测试 295
小结 298
学习目标 298
常见错误 298
Internet资源 299
练习 299
简答题 299
理论题 299
实践题 300
编程项目 300
参考文献 301
第三部分 应用程序
第11章 娱乐与游戏 302
11.1 单词查找拼图 302
11.1.1 理论 303
11.1.2 C++实现 304
11.2 Tic-Tac-Toe游戏 309
11.2.1 a- b修剪 309
11.2.2 变换表 312
11.2.3 计算机国际象棋 316
小结 316
学习目标 317
常见错误 317
Internet资源 317
练习 317
简答题 317
理论题 317
实践题 318
编程项目 318
参考文献 319
第12章 堆栈和编译器 320
12.1 对称符号检查器 320
12.1.1 基本算法 320
12.1.2 实现 321
12.2 简单计算器 330
12.2.1 后缀自动机 330
12.2.2 中缀到后缀的转换 332
12.2.3 实现 333
12.2.4 表达式树 341
小结 343
学习目标 343
常见错误 343
Internet资源 343
练习 344
简答题 344
理论题 344
实践题 344
编程项目 345
参考文献 345
第13章 实用工具 346
13.1 文件压缩 346
13.1.1 前缀码 347
13.1.2 霍夫曼算法 348
13.1.3 实现 350
13.2 交叉引用生成程序 366
13.2.1 基本概念 366
13.2.2 C++实现 366
小结 370
学习目标 370
常见错误 371
Internet资源 371
练习 371
简答题 371
理论题 371
实践题 372
编程项目 372
参考文献 373
第14章 仿真 375
14.1 Josephus问题 375
14.1.1 简单的解决方案 376
14.1.2 一个更有效的算法 376
14.2 事件驱动仿真 380
14.2.1 基本思想 380
14.2.2 实例：调制解调器
库仿真 381
小结 388
学习目标 388
常见错误 389
Internet资源 389
练习 389
简答题 389
理论题 389
实践题 390
编程项目 390
第15章 图和路径 391
15.1 定义 391
15.2 无权最短路径问题 403
15.2.1 理论 403
15.2.2 C++实现 406
15.3 正的有权最短路径问题 407
15.3.1 理论：迪杰斯特拉算法 407
15.3.2 C++实现 410
15.4 负的有权最短路径问题 412
15.4.1 理论 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
Internet资源 423
练习 423
简答题 423
理论证明 423
实践题 424
编程项目 425
参考文献 426
第四部分 实现
第16章 堆栈和队列 427
16.1 动态数组实现 427
16.1.1 堆栈 427
16.1.2 队列 431
16.2 链表实现 436
16.2.1 堆栈 436
16.2.2 队列 441
16.3 两种方法的比较 444
16.4 STL堆栈和队列适配器 445
16.5 双头队列 446
小结 447
学习目标 447
常见错误 448
Internet资源 448
练习 448
简答题 448
实践题 449
编程项目 449
第17章 链表 450
17.1 基本概念 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
学习目标 480
常见错误 480
Internet资源 480
练习 481
简答题 481
理论题 481
实践题 482
编程项目 483
第18章 树 485
18.1 一般树 485
18.1.1 定义 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
常见错误 512
Internet资源 512
练习 513
简答题 513
理论题 514
实践题 514
编程项目 514
第19章 二叉查找树 516
19.1 基本概念 516
19.1.1 操作 517
19.1.2 C++实现 518
19.2 顺序统计C++实现 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 红-黑树 541
19.5.1 自底向上插入 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
Internet资源 582
练习 582
简答题 582
理论题 583
实践题 583
编程项目 584
参考文献 584
第20章 散列表 587
20.1 基本概念 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.4.2 二次探测法分析 603
20.5 分离链接法 603
20.6 散列表与二叉查找树 604
20.7 散列化应用程序 604
小结 605
学习目标 605
常见错误 606
Internet资源 606
练习 606
简答题 606
实践题 607
编程项目 608
参考文献 608
第21章 优先级队列：二叉堆 610
21.1 基本思想 610
21.1.1 结构属性 611
21.1.2 堆顺序属性 612
21.1.3 允许的操作 613
21.2 基本操作的实现 615
21.2.1 insert操作 615
21.2.2 deleteMin操作 616
21.3 buildHeap操作：线性时间的堆构造函数 619
21.4 STL priority_queue实现 622
21.5 高级操作：decreaseKey和merge 625
21.6 内部排序：堆排序 625
21.7 外部排序 628
21.7.1 我们为什么需要新的算法 628
21.7.2 外部排序模型 628
21.7.3 简单的算法 629
21.7.4 多路归并 630
21.7.5 多相归并 631
21.7.6 置换选择 632
小结 634
学习目标 634
常见错误 635
Internet资源 635
练习 635
简答题 635
理论题 635
实践题 637
编程项目 637
参考文献 638
第五部分 高级数据结构
第22章 伸展树 639
22.1 自我调整和摊销分析 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
Internet资源 659
练习 659
简答题 659
理论题 659
实践题 660
编程项目 660
参考文献 660
第23章 合并优先级队列 661
23.1 偏斜堆 661
23.1.1 合并是基础 661
23.1.2 简化的堆排序树合并 662
23.1.3 偏斜堆：简单修改 662
23.1.4 偏斜堆分析 663
23.2 对偶堆 665
23.2.1 对偶堆的操作 666
23.2.2 对偶堆的实现 668
23.2.3 应用：Dijkstra最短加权
路径算法 674
小结 676
学习目标 676
常见错误 676
Internet资源 677
练习 677
简答题 677
理论题 677
实践题 678
编程项目 678
参考文献 678
第24章 不相交集类 680
24.1 等价关系 680
24.2 动态等价和两个应用 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
Internet资源 702
练习 702
简答题 702
理论题 703
实践题 703
编程项目 703
参考文献 704
附 录
附录A C++相关信息 706
A.1 没有编译器实现该标准 706
A.2 不常见的C++运算符 706
A.2.1 自增运算符与自减运算符 706
A.2.2 类型转换 707
A.2.3 按位运算符 708
A.2.4 条件运算符 710
A.3 命令参数 710
A.4 输入和输出 710
A.4.1 基本的流操作 711
A.4.2 顺序文件 714
A.4.3 字符串流 714
A.5 名字空间 716
A.6 C++新特性 717
常见错误 717
附录B 运算符 719
附录C 某些库例程 720
C.1 <ctype.h>和<cctype>中声明的例程 720
C.2 <limits.h>和<climits>中声明的常量 720
C.3 <math.h>和<cmath>中声明的例程 721
C.4 <stdlib.h>和<cstdlib>中声明的例程 721
附录D C++中的基元数组 723
D.1 基元数组 723
D.1.1 C++实现：数组名称是一个指针 723
D.1.2 多维数组 726
D.1.3 char * 类型、const指针和常量字符串 726
D.2 动态数组分配：new [ ]和delete [ ] 729
D.3 指针算术运算、指针跳和基本迭代 733
D.3.1 *、&和[ ]优先级的含意 734
D.3.2 指针算术的含意 734
D.3.3 指针跳例子 736
D.3.4 使用指针跳的意义 737
常见错误 738
Internet资源 738
第1章 数组、指针和结构 1
1.1 什么是指针、数组和结构 1
1.2 数组和字符串 2
1.2.1 头等对象与次等对象的对比 2
1.2.2 使用Vector 3
1.2.3 调整Vector大小 5
1.2.4 push_back大小与容量 7
1.2.5 参数传递机制 7
1.2.6 常量基元数组 9
1.2.7 多维数组 9
1.2.8 标准库类型string 9
1.3 C++中的指针语法 10
1.4 动态内存管理 14
1.4.1 new运算符 15
1.4.2 垃圾收集与delete 15
1.4.3 过期指针、双重删除及其他 16
1.5 引用变量 17
1.6 结构 19
1.6.1 指向结构的指针 21
1.6.2 外部数据与内部数据、深复制与浅复制 21
1.6.3 非邻接链表：链表 23
小结 24
学习目标 24
常见错误 25
网上资源 26
练习 26
简答题 26
实践题 28
编程项目 28
参考文献 28
第2章 对象和类 30
2.1 什么是面向对象编程 30
2.2 类的基本语法 31
2.2.1 类成员 31
2.2.2 附加的构造函数语法和访问函数 33
2.2.3 接口和实现的分离 35
2.2.4 析构函数、复制构造函数和赋值运算符（=） 38
2.2.5 默认的构造函数 43
2.3 附加的C++类特性 43
2.3.1 调整后的构造函数中的初始化与赋值 47
2.3.2 类型转换 48
2.3.3 运算符重载 49
2.3.4 输入、输出和友元 52
2.4 一些常用术语 54
2.4.1 避免使用友元 54
2.4.2 静态类成员 55
2.4.3 整型类常量的陷阱 55
2.5 异常 56
2.6 String类 57
2.7 要点重述：进行了哪些调用？
哪些采用了默认行为 65
2.8 组合 66
小结 67
学习目标 68
常见错误 69
Internet资源 70
练习 70
简答题 70
理论题 71
编程项目 72
参考文献 75
第3章 模板 76
3.1 模板的概念 76
3.2 函数模板 76
3.3 排序函数模板 78
3.4 类模板 81
3.4.1 MemoryCell模板 81
3.4.2 实现vector类模板 85
3.5 模板的模板：matrix类 87
3.5.1 数据成员、构造函数和基本附件 88
3.5.2 operator [ ] 89
3.5.3 析构函数、复制赋值和复制构造函数 89
3.6 Fancy模板 89
3.6.1 多平台参数 89
3.6.2 默认的模板参数 90
3.6.3 保留字typename 90
3.7 与模板有关的bug 90
3.7.1 错误消息和改变的规则 91
3.7.2 模板匹配算法 91
3.7.3 模板中的嵌套类 91
3.7.4 类模板中的静态成员 91
小结 91
学习目标 91
常见错误 92
Internet资源 92
练习 93
简答题 93
实践题 93
编程项目 93
第4章 继承 94
4.1 什么是继承 94
4.2 继承的基本知识 97
4.2.1 可视性规则 98
4.2.2 构造函数和基类初始化 98
4.2.3 添加成员 99
4.2.4 覆盖方法 101
4.2.5 静态绑定和动态绑定 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.2 默认参数 114
4.4.3 派生类方法隐藏基类方法 114
4.4.4 覆盖方法的兼容返回类型 115
4.4.5 私有继承 116
4.4.6 友元 116
4.4.7 值调用与多态并不混淆 117
4.5 多重继承 117
小结 118
学习目标 119
常见错误 119
Internet资源 120
练习 120
简答题 120
实践题 122
编程项目 122
参考文献 122
第5章 设计模式 123
5.1 模式的概念 123
5.2 Functor（函数对象） 124
5.3 适配器和包装器 129
5.3.1 指针包装器 129
5.3.2 常数引用包装器 134
5.3.3 适配器更改接口 135
5.4 迭代器 136
5.4.1 迭代器设计1 137
5.4.2 迭代器设计2 139
5.4.3 基于继承的迭代器和
factory 139
5.5 合成（对） 144
5.6 观察者 144
小结 148
学习目标 148
常见错误 149
Internet资源 149
练习 150
简答题 150
理论题 150
实践题 150
编程项目 152
参考文献 152
第二部分 算法和构建代码块
第6章 算法分析 153
6.1 什么是算法分析 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 静态查找问题 169
6.6.1 顺序查找 169
6.6.2 折半查找 169
6.6.3 插值查找 172
6.7 算法分析的检验 173
6.8 Big-Oh分析的限制 174
小结 174
学习目标 174
常见错误 175
Internet资源 175
练习 176
简答题 176
理论题 177
实践题 179
编程项目 179
参考文献 180
第7章 标准模板库 182
7.1 简介 182
7.2 堆栈和队列 183
7.2.1 堆栈 184
7.2.2 堆栈和计算机语言 185
7.2.3 队列 186
7.3 容器和迭代器 187
7.3.1 容器 187
7.3.2 迭代器 188
7.4 STL算法 189
7.4.1 STL函数对象 189
7.4.2 二分查找法 191
7.4.3 排序 193
7.5 实现带有迭代器的vector 193
7.6 顺序表和链表 195
7.6.1 list类 195
7.6.2 堆栈和队列 196
7.7 集合 197
7.8 映射 199
7.9 优先队列 200
小结 203
学习目标 204
常见错误 204
Internet资源 205
练习 205
简答题 205
理论题 205
实践题 206
编程项目 206
参考文献 208
第8章 递归 209
8.1 递归的概念 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 数值应用 223
8.4.1 模运算 223
8.4.2 模幂运算 224
8.4.3 最大公约数和乘法逆元素 225
8.4.4 RSA密码系统 228
8.5 分治算法 230
8.5.1 最大邻近子序列和问题 230
8.5.2 基本分治递归分析 233
8.5.3 分治法运行时间的一般上限 235
8.6 动态规划 237
8.7 回溯法 241
小结 244
学习目标 244
常见错误 245
Internet资源 245
练习 246
简答题 246
理论题 246
实践题 247
编程项目 248
参考文献 249
第9章 排序算法 250
9.1 排序为何重要 250
9.2 预备知识 251
9.3 插入排序和其他简单排序的分析 252
9.4 希尔排序 254
9.5 归并排序 257
9.5.1 排过序的数组的线性时间合并 257
9.5.2 归并排序算法 259
9.6 快速排序 261
9.6.1 快速排序算法 261
9.6.2 快速排序的分析 263
9.6.3 支点的选择 265
9.6.4 分组策略 267
9.6.5 同支点相等的键 268
9.6.6 中值划分 269
9.6.7 小数组 270
9.6.8 C++快速排序例程 270
9.7 排序选择 272
9.8 排序的下限 274
9.9 间接排序 275
9.9.1 使用指针将Comparable
副本数减少为2N 275
9.9.2 避免附加数组 276
小结 278
学习目标 279
常见错误 279
Internet资源 279
练习 280
简答题 280
理论题 280
实践题 281
编程项目 282
参考文献 283
第10章 随机 285
10.1 为什么我们需要随机数 285
10.2 随机数生成器 286
10.3 非均匀随机数 290
10.4 生成随机排列 291
10.5 随机算法 293
10.6 随机素数测试 295
小结 298
学习目标 298
常见错误 298
Internet资源 299
练习 299
简答题 299
理论题 299
实践题 300
编程项目 300
参考文献 301
第三部分 应用程序
第11章 娱乐与游戏 302
11.1 单词查找拼图 302
11.1.1 理论 303
11.1.2 C++实现 304
11.2 Tic-Tac-Toe游戏 309
11.2.1 a- b修剪 309
11.2.2 变换表 312
11.2.3 计算机国际象棋 316
小结 316
学习目标 317
常见错误 317
Internet资源 317
练习 317
简答题 317
理论题 317
实践题 318
编程项目 318
参考文献 319
第12章 堆栈和编译器 320
12.1 对称符号检查器 320
12.1.1 基本算法 320
12.1.2 实现 321
12.2 简单计算器 330
12.2.1 后缀自动机 330
12.2.2 中缀到后缀的转换 332
12.2.3 实现 333
12.2.4 表达式树 341
小结 343
学习目标 343
常见错误 343
Internet资源 343
练习 344
简答题 344
理论题 344
实践题 344
编程项目 345
参考文献 345
第13章 实用工具 346
13.1 文件压缩 346
13.1.1 前缀码 347
13.1.2 霍夫曼算法 348
13.1.3 实现 350
13.2 交叉引用生成程序 366
13.2.1 基本概念 366
13.2.2 C++实现 366
小结 370
学习目标 370
常见错误 371
Internet资源 371
练习 371
简答题 371
理论题 371
实践题 372
编程项目 372
参考文献 373
第14章 仿真 375
14.1 Josephus问题 375
14.1.1 简单的解决方案 376
14.1.2 一个更有效的算法 376
14.2 事件驱动仿真 380
14.2.1 基本思想 380
14.2.2 实例：调制解调器
库仿真 381
小结 388
学习目标 388
常见错误 389
Internet资源 389
练习 389
简答题 389
理论题 389
实践题 390
编程项目 390
第15章 图和路径 391
15.1 定义 391
15.2 无权最短路径问题 403
15.2.1 理论 403
15.2.2 C++实现 406
15.3 正的有权最短路径问题 407
15.3.1 理论：迪杰斯特拉算法 407
15.3.2 C++实现 410
15.4 负的有权最短路径问题 412
15.4.1 理论 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
Internet资源 423
练习 423
简答题 423
理论证明 423
实践题 424
编程项目 425
参考文献 426
第四部分 实现
第16章 堆栈和队列 427
16.1 动态数组实现 427
16.1.1 堆栈 427
16.1.2 队列 431
16.2 链表实现 436
16.2.1 堆栈 436
16.2.2 队列 441
16.3 两种方法的比较 444
16.4 STL堆栈和队列适配器 445
16.5 双头队列 446
小结 447
学习目标 447
常见错误 448
Internet资源 448
练习 448
简答题 448
实践题 449
编程项目 449
第17章 链表 450
17.1 基本概念 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
学习目标 480
常见错误 480
Internet资源 480
练习 481
简答题 481
理论题 481
实践题 482
编程项目 483
第18章 树 485
18.1 一般树 485
18.1.1 定义 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
常见错误 512
Internet资源 512
练习 513
简答题 513
理论题 514
实践题 514
编程项目 514
第19章 二叉查找树 516
19.1 基本概念 516
19.1.1 操作 517
19.1.2 C++实现 518
19.2 顺序统计C++实现 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 红-黑树 541
19.5.1 自底向上插入 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
Internet资源 582
练习 582
简答题 582
理论题 583
实践题 583
编程项目 584
参考文献 584
第20章 散列表 587
20.1 基本概念 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.4.2 二次探测法分析 603
20.5 分离链接法 603
20.6 散列表与二叉查找树 604
20.7 散列化应用程序 604
小结 605
学习目标 605
常见错误 606
Internet资源 606
练习 606
简答题 606
实践题 607
编程项目 608
参考文献 608
第21章 优先级队列：二叉堆 610
21.1 基本思想 610
21.1.1 结构属性 611
21.1.2 堆顺序属性 612
21.1.3 允许的操作 613
21.2 基本操作的实现 615
21.2.1 insert操作 615
21.2.2 deleteMin操作 616
21.3 buildHeap操作：线性时间的堆构造函数 619
21.4 STL priority_queue实现 622
21.5 高级操作：decreaseKey和merge 625
21.6 内部排序：堆排序 625
21.7 外部排序 628
21.7.1 我们为什么需要新的算法 628
21.7.2 外部排序模型 628
21.7.3 简单的算法 629
21.7.4 多路归并 630
21.7.5 多相归并 631
21.7.6 置换选择 632
小结 634
学习目标 634
常见错误 635
Internet资源 635
练习 635
简答题 635
理论题 635
实践题 637
编程项目 637
参考文献 638
第五部分 高级数据结构
第22章 伸展树 639
22.1 自我调整和摊销分析 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
Internet资源 659
练习 659
简答题 659
理论题 659
实践题 660
编程项目 660
参考文献 660
第23章 合并优先级队列 661
23.1 偏斜堆 661
23.1.1 合并是基础 661
23.1.2 简化的堆排序树合并 662
23.1.3 偏斜堆：简单修改 662
23.1.4 偏斜堆分析 663
23.2 对偶堆 665
23.2.1 对偶堆的操作 666
23.2.2 对偶堆的实现 668
23.2.3 应用：Dijkstra最短加权
路径算法 674
小结 676
学习目标 676
常见错误 676
Internet资源 677
练习 677
简答题 677
理论题 677
实践题 678
编程项目 678
参考文献 678
第24章 不相交集类 680
24.1 等价关系 680
24.2 动态等价和两个应用 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
Internet资源 702
练习 702
简答题 702
理论题 703
实践题 703
编程项目 703
参考文献 704
附 录
附录A C++相关信息 706
A.1 没有编译器实现该标准 706
A.2 不常见的C++运算符 706
A.2.1 自增运算符与自减运算符 706
A.2.2 类型转换 707
A.2.3 按位运算符 708
A.2.4 条件运算符 710
A.3 命令参数 710
A.4 输入和输出 710
A.4.1 基本的流操作 711
A.4.2 顺序文件 714
A.4.3 字符串流 714
A.5 名字空间 716
A.6 C++新特性 717
常见错误 717
附录B 运算符 719
附录C 某些库例程 720
C.1 <ctype.h>和<cctype>中声明的例程 720
C.2 <limits.h>和<climits>中声明的常量 720
C.3 <math.h>和<cmath>中声明的例程 721
C.4 <stdlib.h>和<cstdlib>中声明的例程 721
附录D C++中的基元数组 723
D.1 基元数组 723
D.1.1 C++实现：数组名称是一个指针 723
D.1.2 多维数组 726
D.1.3 char * 类型、const指针和常量字符串 726
D.2 动态数组分配：new [ ]和delete [ ] 729
D.3 指针算术运算、指针跳和基本迭代 733
D.3.1 *、&和[ ]优先级的含意 734
D.3.2 指针算术的含意 734
D.3.3 指针跳例子 736
D.3.4 使用指针跳的意义 737
常见错误 738
Internet资源 738
猜您喜欢
