C++程序设计 基础、编程抽象与算法策略pdf

C++程序设计 基础、编程抽象与算法策略 内容简介

本书是一本关于C++语言的经典书籍，全书共计20章，主要介绍了C++的基本知识、函数和库、字符串、流、集合、类的设计、递归、递归策略、回溯算法、算法分析、指针与数组、动态内存管理、效率与表示、线性结构、映射、树、图、继承、迭代的策略等内容。本书重点图突出，全面讲解了C++语言的基本概念，深入剖析了具体的编程思路。同事，每章后面都有配套的的习题，有助于读者进一步理解和掌握晦涩的概念。本书适合作为计算机专业及相关专业学生的教材或教学参考书，也适合希望学习C++语言的初学者和中高级程序员使用。

C++程序设计 基础、编程抽象与算法策略 目录

出版者的话

译者序

前言

第1章C++概述1

1.1你的第一个C++程序1

1.2C++的历史2

1.2.1面向对象范型2

1.2.2C++的演化3

1.3编译过程3

1.4C++程序结构4

1.4.1注释5

1.4.2包含的库文件6

1.4.3函数原型6

1.4.4主程序7

1.4.5函数定义8

1.5变量9

1.5.1变量声明9

1.5.2命名规则10

1.5.3局部变量和全局变量11

1.5.4常量11

1.6数据类型12

1.6.1数据类型的概念12

1.6.2整数类型13

1.6.3浮点类型13

1.6.4布尔类型14

1.6.5字符14

1.6.6字符串15

1.6.7枚举类型16

1.6.8复合类型17

1.7表达式17

1.7.1优先级和结合律18

1.7.2表达式中的混合类型19

1.7.3整数除法和求余操作符19

1.7.4类型转换20

1.7.5赋值操作符20

1.7.6自增和自减操作符21

1.7.7布尔运算22

1.8语句24

1.8.1简单语句24

1.8.2块24

1.8.3if语句24

1.8.4switch语句25

1.8.5while语句27

1.8.6for语句29

本章小结31

复习题32

习题33

第2章函数与库37

2.1函数概念37

2.1.1数学中的函数37

2.1.2编程中的函数37

2.1.3使用函数的优点38

2.1.4函数和算法38

2.2库39

2.3在C++中定义函数41

2.3.1函数原型41

2.3.2重载42

2.3.3默认形参数42

2.4函数调用机制43

2.4.1函数调用步骤43

2.4.2组合函数44

2.4.3追踪组合函数执行过程46

2.5引用参数49

2.6接口与实现52

2.6.1定义error库53

2.6.2导出数据类型54

2.6.3导出常量定义56

2.7接口设计原则58

2.7.1统一主题的重要性58

2.7.2简单性与信息隐藏原理59

2.7.3满足用户需求60

2.7.4通用工具的优势60

2.7.5库稳定性的价值60

2.8随机数库的设计61

2.8.1随机数与伪随机数61

2.8.2标准库中的伪随机数62

2.8.3选择正确的函数集63

2.8.4构建用户程序65

2.8.5随机数库的实现65

2.8.6初始化随机数种子69

2.9Stanford类库介绍73

2.9.1简单的输入和输出类库73

2.9.2Stanford类库中的图形处理程序74

本章小结77

复习题78

习题79

第3章字符串类string85

3.1使用字符串作为抽象数据85

3.2字符串操作87

3.2.1操作符重载88

3.2.2从一个字符串中选取字符89

3.2.3字符串赋值90

3.2.4提取字符串中的子串90

3.2.5在一个字符串中进行搜索90

3.2.6循环遍历字符串中的所有字符91

3.2.7通过连接扩展字符串92

3.3＜cctype＞库93

3.4修改字符串中的内容94

3.5遗留的C风格字符串95

3.6编写字符串应用程序95

3.6.1回文识别96

3.6.2将英语翻译成儿童黑话96

3.7strlib.h库99

本章小结100

复习题100

习题101

第4章流类108

4.1格式化输出108

4.2格式化输入112

4.3数据文件113

4.3.1使用文件流114

4.3.2单个字符的输入／输出115

4.3.3面向行的输入／输出118

4.3.4格式化输入／输出119

4.3.5字符串流121

4.3.6一个用于控制台输入的更鲁棒的策略122

4.4类层次123

4.4.1生物层次123

4.4.2流类层次124

4.4.3在流层次中选择正确的层次126

4.5simpio.h和filelib.h库127

本章小结128

复习题128

习题129

第5章集合类133

5.1Vector类134

5.1.1指定Vector的基类型134

5.1.2声明Vector对象135

5.1.3Vector的操作135

5.1.4从Vector对象中选择元素136

5.1.5作为参数传递Vector对象137

5.1.6创建预先定义大小的Vector138

5.1.7Vector类的构造函数141

5.1.8Vector中的操作符142

5.1.9表示二维结构143

5.1.10Stanford类库中的Grid类143

5.2Stack类144

5.2.1Stack类结构145

5.2.2栈和小型计算器145

5.3Queue类148

5.3.1仿真和模型149

5.3.2排队模型149

5.3.3离散时间150

5.3.4仿真时间中的事件150

5.3.5实现仿真151

5.4Map类154

5.4.1Map类的结构154

5.4.2在一个应用中使用Map类156

5.4.3Map类作为关联数组157

5.5Set类158

5.5.1实现＜cctype＞库159

5.5.2创建单词列表160

5.5.3Stanford类库中的Lexicon类161

5.6在集合上进行迭代162

5.6.1迭代顺序163

5.6.2再论儿童黑话164

5.6.3计算单词的频率165

本章小结167

复习题168

习题168

第6章类的设计178

6.1二维点的表示178

6.1.1将Point定义为结构类型178

6.1.2将Point定义为类179

6.1.3接口与实现的分离182

6.2操作符重载184

6.2.1重载插入操作符184

6.2.2判断两个点是否相等186

6.2.3为Direction类型增加操作符189

6.3有理数191

6.3.1定义新类的机制192

6.3.2采用用户的观点193

6.3.3确定Rational类的私有实例变量193

6.3.4为Rational类定义构造函数193

6.3.5为Rational类定义方法194

6.3.6实现Rational类196

6.4token扫描器类的设计198

6.4.1用户想从记号扫描器中得到什么199

6.4.2tokenscanner.h接口200

6.4.3实现TokenScanner类202

6.5将程序封装成类205

本章小结207

复习题207

习题208

第7章递归简介215

7.1一个简单的递归例子215

7.2阶乘函数217

7.2.1fact的递归公式217

7.2.2追踪递归过程218

7.2.3递归的稳步跳跃221

7.3斐波那契

7.3.1计算斐波那契数列项

7.3.2在递归实现中获得自信

7.3.3递归实现的效率

7.3.4递归不应被指责

7.4检测回文

7.5二分查找算法

7.6间接递归

7.7递归地思考

7.7.1保持全局的观点

7.7.2避免常见的错误

本章小结

复习题

习题

第8章递归策略

8.1汉诺塔

8.1.1问题框架

8.1.2找到一种递归策略

8.1.3验证这个策略

8.1.4编码方案

8.1.5跟踪递归过程

8.2子集求和问题

8.2.1寻找一个递归解决方案

8.2.2包含／排除模式

8.3字符排列

8.4图的递归

8.4.1一个来自计算机艺术的实例

8.4.2分形

本章小结

复习题

习题

第9章回溯算法

9.1迷宫的递归回溯

9.1.1右手法则

9.1.2寻找一种递归方法

9.1.3确定简单情况

9.1.4对迷宫问题的解决算法进行编码

9.1.5说服你自己那个方案可行

9.2回溯与游戏

9.2.1拿子游戏

9.2.2一个通用的双人游戏程序

9.3最小最大算法

9.3.1游戏树

9.3.2评价位置和走法

9.3.3限制递归搜索的深度

9.3.4实现最小最大算法

本章小结

复习题

习题

第10章算法分析

10.1排序问题

10.1.1选择排序算法

10.1.2性能的经验评估

10.1.3分析选择排序算法的性能

10.2时间复杂度

10.2.1大O符号

10.2.2大O的标准简化

10.2.3选择排序算法的时间复杂度

10.2.4从代码中降低时间复杂度

10.2.5最坏情况以及平均情况下的复杂度

10.2.6大O符号的正式定义

10.3递归的终止

10.3.1分治策略的作用

10.3.2合并两个矢量

10.3.3归并排序算法

10.3.4归并排序的计算复杂度

10.3.5比较N2与Nlog2N的性能

10.4标准的算法复杂度类别

10.5快速排序算法

10.5.1划分矢量

10.5.2快速排序算法的性能分析

10.6数学归纳法

本章小结

复习题

习题

第11章指针和数组

11.1内存结构

11.1.1位、字节和字

11.1.2二进制和十六进制表示

11.1.3表示其他数据类型

11.1.4内存地址

11.1.5为变量分配内存

11.2指针

11.2.1把地址当作数值

11.2.2声明指针变量

11.2.3基本的指针运算

11.2.4指向结构和对象的指针

11.2.5关键字this

11.2.6特殊的指针NULL

11.2.7指针和引用调用

11.3数组

11.3.1声明数组

11.3.2数组元素的选择

11.3.3数组的静态初始化

11.3.4有效容量和分配容量

11.3.5指针和数组的关系

11.4指针运算

11.4.1数组索引和内存地址

11.4.2指针的自增自减运算

11.4.3C风格字符串

11.4.4指针运算和程序风格

本章小结

复习题

习题

……

第12章动态内存管理

第13章效率和表示

第14章线性结构

第15章映射

第16章树

第17章集合

第18章图

第19章继承

第20章迭代策略

索引

C++程序设计 基础、编程抽象与算法策略 精彩文摘

1．2．2 C++的演化

像人类语言一样，程序设计语言也随着时间的推移发生着改变。多年来，c++已经逐步发展以满足用户不断变化的需求。国际标准化组织(ISO)一直在管理c++新版本的发布，它在1998年、2003年和2011年分别修订了c++语言中的若干重要问题。最新的修订版称为C++11，它引进了很多新特性，包括若干让C++更容易学习的特性。

尽管每个人在某一时刻会用到C++ll提供的很多特性，可是很多编译器还不支持C++11标准。在主要的编译器版本可以使用C+十11之前，你可能不得不遵循2003年出台的旧c++标准。本书会在合适的时候介绍c++11的特性，但是通常会概述用旧的编译器实现相同结果的策略。