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

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

前　　言
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版本（互动式数字教材）的授权，因此大量视频和动画内容无法通过纸质版本有效呈现。我们在书中提供了互动内容的访问地址，读者可通过以下二维码获得完整的互动内容链接列表。

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

目　　录
Introduction to C++ Programming and Data Structures, Fifth Edition
第17章　递归　1
17.1　简介　1
17.2　案例研究：计算阶乘　2
17.3　案例研究：斐波那契数　8
17.4　使用递归解决问题　12
17.5　递归辅助函数　16
17.5.1　选择排序　18
17.5.2　二分查找　20
17.6　汉诺塔　22
17.7　八皇后问题　26
17.8　递归与迭代　30
17.9　尾递归　31
关键术语　34
章节总结　35
编程练习　35
第18章　开发高效算法　46
18.1　简介　47
18.2　使用大O表示法衡量算法效率　47
18.3　示例：确定大O　50
18.4　分析算法时间复杂度　56
18.4.1　分析二分查找　56
18.4.2　分析选择排序　57
18.4.3　分析汉诺塔问题　58
18.4.4　常见的递归关系　59
18.4.5　比较常见的增长函数　59
18.5　使用动态规划求斐波那契数　63
18.6　使用欧几里得算法求最大
公约数　66
18.7　寻找质数的高效算法　72
18.8　使用分治法寻找最近点对　81
18.9　使用回溯法解决八皇后问题　84

18.10　案例研究：寻找凸包　88
18.10.1　礼品包装算法　89
18.10.2　Graham算法　90
18.11　字符串匹配　92
18.11.1　Boyer-Moore算法　95
18.11.2　Knuth-Morris-Pratt算法　98
关键术语　102
章节总结　103
编程练习　104
第19章　排序　111
19.1　简介　111
19.2　插入排序　112
19.3　冒泡排序　115
19.4　归并排序　117
19.5　快速排序　123
19.6　堆排序　127
19.6.1　存储堆　129
19.6.2　添加新节点　130
19.6.3　删除根　131
19.6.4　Heap类　134
19.6.5　使用Heap类进行排序　137
19.6.6　堆排序的时间复杂度　139
19.7　桶排序和基数排序　140
19.8　外部排序　143
19.8.1　实现第一阶段　145
19.8.2　实现第二阶段　146
19.8.3　合成两个阶段　149
19.8.4　外部排序复杂度　150
关键术语　151
章节总结　151
编程练习　151
第20章　链表、队列和优先级队列　154
20.1　简介　154
20.2　节点　155
20.3　LinkedList类　159
20.4　实现LinkedList　163
20.4.1　实现addFirst
(T element)　164
20.4.2　实现addLast
(T element)　165
20.4.3　实现add(int index,
T element)　166
20.4.4　实现removeFirst()　168
20.4.5　实现removeLast()　170
20.4.6　实现removeAt
(int index)　171
20.4.7　LinkedList的源代码　173
20.4.8　LinkedList的时间
复杂度　175
20.5　迭代器　179
20.6　C++11 foreach循环　184
20.7　链表的变体　186
20.8　队列　189
20.9　优先级队列　192
关键术语　196
章节总结　196
编程练习　197
第21章　二叉查找树　200
21.1　简介　200
21.2　二叉查找树基础知识　201
21.3　表示二叉查找树　202
21.4　访问二叉查找树中的节点　204
21.5　查找元素　204
21.6　将元素插入二叉查找树　206
21.7　树的遍历　208
21.8　BST类　210
21.9　删除二叉查找树中的元素　216
21.10　BST的迭代器　224
21.11　案例研究：数据压缩　227
关键术语　232
章节总结　233
编程练习　233
第22章　STL容器　236
22.1　简介　236
22.2　STL基础　237
22.3　STL迭代器　243
22.3.1　迭代器的类型　245
22.3.2　迭代器运算符　246
22.3.3　预定义迭代器　248
22.3.4　istream_iterator和ostream_iterator　250
22.4　C++11自动类型推断　252
22.5　序列容器　253
22.5.1　序列容器：vector　254
22.5.2　序列容器：deque　257
22.5.3　序列容器：list　259
22.6　关联容器　263
22.6.1　关联容器：set和
multiset　263
22.6.2　关联容器：map和
multimap　265
22.7　容器适配器　269
22.7.1　容器适配器：stack　269
22.7.2　容器适配器：queue　270
22.7.3　容器适配器：priority_
queue　272
关键术语　274
章节总结　275
编程练习　276
第23章　STL算法　280
23.1　简介　281
23.2　算法类型　282
23.3　copy函数　284
23.4　fill和fill_n　287
23.5　将函数作为参数传递　289
23.6　generate和generate_n　293
23.7　remove、remove_if、
remove_copy和
remove_copy_if　295
23.8　replace、replace_if、replace_copy和
replace_copy_if　299
23.9　find、find_if、find_end和
find_first_of　303
23.10　search和search_n　309<