C++语言程序设计（进阶篇）（原书第5版） [美]梁勇

·在设计自定义类之前介绍基本的编程概念和技术，同时侧重于解决问题，使用了数学、科学、商业、金融、游戏等许多不同领域的示例。 ·CodeAnimation和LiveExample引导读者逐行阅读代码，通过填写缺失的代码，读者能够在实时编码环境中得到实时反馈，有助于在实践中巩固所学。 ·算法动画、交互式流程图和UML图向读者展示算法的每个步骤，以可视化和交互方式展示算法如何工作。 ·新版反映了近期的编程趋势，比如云存储和触摸屏，而且所有的代码都兼容C++17。 

本书是关于C++程序设计的经典教材，中文版分为基础篇和进阶篇，主要介绍程序设计基础、面向对象程序设计和数据结构。本书采用“基础优先，问题驱动”的教学方式，在设计自定义类之前介绍基本的编程概念和技术，同时侧重于解决问题而非语法，通过不同领域的示例说明相关概念。本书引导读者循序渐进地学习，从基本的编程技术到面向对象编程，从简单的数据类型到经典的结构。本书可作为高等院校计算机相关专业程序设计课程的教材，也可作为C++语言及编程爱好者的参考书。

梁勇（Y. Daniel Liang） 佐治亚南方大学计算机科学荣休教授。之前曾是普渡大学计算机科学系副教授，并曾两次获得普渡大学卓越研究奖。他撰写了30多本著作，其中程序设计类教材在世界各地得到广泛使用。

目　　录
Introduction to C++ Programming and Data Structures, Fifth Edition
译者序
前言
作者简介
第17章　递归　1
17.1　简介　1
17.2　案例研究：计算阶乘　2
17.3　案例研究：斐波那契数　5
17.4　使用递归解决问题　7
17.5　递归辅助函数　9
17.5.1　选择排序　10
17.5.2　二分查找　12
17.6　汉诺塔　13
17.7　八皇后问题　16
17.8　递归与迭代　19
17.9　尾递归　19
关键术语　21
章节总结　21
编程练习　21
第18章　开发高效算法　30
18.1　简介　30
18.2　使用大O表示法衡量算法效率　30
18.3　示例：确定大O　32
18.4　分析算法时间复杂度　34
18.4.1　分析二分查找　35
18.4.2　分析选择排序　35
18.4.3　分析汉诺塔问题　35
18.4.4　常见的递归关系　36
18.4.5　比较常见的增长函数　36
18.5　使用动态规划求斐波那契数　37
18.6　使用欧几里得算法求最大
公约数　39
18.7　寻找质数的高效算法　43
18.8　使用分治法寻找最近点对　51
18.9　使用回溯法解决八皇后问题　53
18.10　案例研究：寻找凸包　56
18.10.1　礼品包装算法　57
18.10.2　Graham算法　58
18.11　字符串匹配　59
18.11.1　Boyer-Moore算法　61
18.11.2　Knuth-Morris-Pratt算法　64
关键术语　67
章节总结　68
编程练习　68
第19章　排序　74
19.1　简介　74
19.2　插入排序　74
19.3　冒泡排序　77
19.4　归并排序　79
19.5　快速排序　82
19.6　堆排序　86
19.6.1　存储堆　86
19.6.2　添加新节点　87
19.6.3　删除根　89
19.6.4　Heap类　92
19.6.5　使用Heap类进行排序　94
19.6.6　堆排序的时间复杂度　95
19.7　桶排序和基数排序　96
19.8　外部排序　97
19.8.1　实现第一阶段　99
19.8.2　实现第二阶段　100
19.8.3　合成两个阶段　102
19.8.4　外部排序复杂度　107
关键术语　107
章节总结　107
编程练习　107
第20章　链表、队列和优先级队列　109
20.1　简介　109
20.2　节点　109
20.3　LinkedList类　112
20.4　实现LinkedList　114
20.4.1　实现addFirst
(T element)　115
20.4.2　实现addLast
(T element)　116
20.4.3　实现add(int index,
T element)　118
20.4.4　实现removeFirst()　119
20.4.5　实现removeLast()　120
20.4.6　实现removeAt
(int index)　122
20.4.7　LinkedList的源代码　123
20.4.8　LinkedList的时间
复杂度　129
20.5　迭代器　130
20.6　C++11 foreach循环　133
20.7　链表的变体　135
20.8　队列　135
20.9　优先级队列　138
关键术语　141
章节总结　141
编程练习　141
第21章　二叉查找树　144
21.1　简介　144
21.2　二叉查找树基础知识　144
21.3　表示二叉查找树　145
21.4　访问二叉查找树中的节点　146
21.5　查找元素　146
21.6　将元素插入二叉查找树　146
21.7　树的遍历　148
21.8　BST类　150
21.9　删除二叉查找树中的元素　160
21.10　BST的迭代器　165
21.11　案例研究：数据压缩　167
关键术语　172
章节总结　172
编程练习　173
第22章　STL容器　174
22.1　简介　174
22.2　STL基础　174
22.3　STL迭代器　179
22.3.1　迭代器的类型　181
22.3.2　迭代器运算符　182
22.3.3　预定义迭代器　184
22.3.4　istream_iterator和ostream_iterator　185
22.4　C++11自动类型推断　187
22.5　序列容器　187
22.5.1　序列容器：vector　188
22.5.2　序列容器：deque　189
22.5.3　序列容器：list　191
22.6　关联容器　194
22.6.1　关联容器：set和
multiset　195
22.6.2　关联容器：map和
multimap　196
22.7　容器适配器　198
22.7.1　容器适配器：stack　198
22.7.2　容器适配器：queue　200
22.7.3　容器适配器：priority_
queue　201
关键术语　202
章节总结　203
编程练习　203
第23章　STL算法　207
23.1　简介　207
23.2　算法类型　208
23.3　copy函数　209
23.4　fill和fill_n　211
23.5　将函数作为参数传递　212
23.6　generate和generate_n　215
23.7　remove、remove_if、remove_copy和remove_copy_if　216
23.8　replace、replace_if、replace_
copy和replace_copy_if　220
23.9　find、find_if、find_end和
find_first_of　223
23.10　search和search_n　227

前　　言
Introduction to C++ Programming and Data Structures, Fifth Edition
教学特色
每章的开头列出学习目标，明确学生应该从这一章中学到什么。这份简洁的列表有助于学生在完成学习后，判断自己是否达到了学习目标。
要点提示强调了每节中所涵盖的重要概念。
CodeAnimation模拟程序的执行，它引导学生逐行浏览代码、要求学生提供输入并立即展示这些输入对程序产生的影响。
LiveExample让学生能够在类似于IDE的环境中练习编码。给学生提供填写缺失代码的机会要求他们编译和运行程序，提交内容后能立即获得反馈。LiveExample引导学生逐步接近正确答案，帮助他们坚持下去，并保持不断尝试的动力。
交互式流程图、算法动画和UML图可以提升解决问题和逻辑思维能力，有助于理解操作流程，并在学生开始编码之前帮助他们可视化程序中正在发生的事情。
本版新增内容
本版在细节上进行了全面修订，旨在改善清晰度、呈现方式、内容、示例和练习。主要的改进包括：
更新1.2节，包括云存储和触摸屏的内容。
更新4.8.4节，讨论基于元组的输入与基于行的输入。
在C++17中不再支持异常说明符。因此，在第５版中删除了第４版的16.8节。对所有使用异常说明符的代码都进行了修订。
18.11节是全新的。它介绍了三种字符串匹配算法：暴力法、Boyer-Moore算法和KMP算法。
21.11节也是全新的。它介绍了使用霍夫曼编码进行数据压缩的方法。
附录I是全新的。它给出了大O、大Omega和大Theta表示法的精确数学定义。
灵活的章节顺序
可采用灵活的章节顺序阅读本版，如下图所示。
补充说明
由于中文版未获得英文版Revel版本（互动式数字教材）的授权，因此大量视频和动画内容无法通过纸质版本有效呈现。我们在书中提供了部分互动内容的访问地址，包括CodeAnimation、LiveExample和编程练习等。读者可通过以下二维码获得完整的互动内容链接列表。