C++程序设计 基础、编程抽象与算法策略PDF电子书下载

第1章 C＋＋概述 1

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

1.2 C＋＋的历史 2

1.2.1 面向对象范型 2

1.2.2 C＋＋的演化 3

1.3 编译过程 3

1.4 C＋＋程序结构 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.3 if语句 24

1.8.4 switch语句 25

1.8.5 while语句 27

1.8.6 for语句 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.9 Stanford类库介绍 73

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

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

本章小结 77

复习题 78

习题 79

第3章 字符串类string 85

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.7 strlib.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.5 simpio.h和filelib.h库 127

本章小结 128

复习题 128

习题 129

第5章 集合类 133

5.1 Vector类 134

5.1.1 指定Vector的基类型 134

5.1.2 声明Vector对象 135

5.1.3 Vector的操作 135

5.1.4 从Vector对象中选择元素 136

5.1.5 作为参数传递Vector对象 137

5.1.6 创建预先定义大小的Vector 138

5.1.7 Vector类的构造函数 141

5.1.8 Vector中的操作符 142

5.1.9 表示二维结构 143

5.1.10 Stanford类库中的Grid类 143

5.2 Stack类 144

5.2.1 Stack类结构 145

5.2.2 栈和小型计算器 145

5.3 Queue类 148

5.3.1 仿真和模型 149

5.3.2 排队模型 149

5.3.3 离散时间 150

5.3.4 仿真时间中的事件 150

5.3.5 实现仿真 151

5.4 Map类 154

5.4.1 Map类的结构 154

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

5.4.3 Map类作为关联数组 157

5.5 Set类 158

5.5.1 实现＜cctype＞库 159

5.5.2 创建单词列表 160

5.5.3 Stanford类库中的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.4 token扫描器类的设计 198

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

6.4.2 tokenscanner.h接口 200

6.4.3 实现TokenScanner类 202

6.5 将程序封装成类 205

本章小结 207

复习题 207

习题 208

第7章 递归简介 215

7.1 一个简单的递归例子 215

7.2 阶乘函数 217

7.2.1 fact的递归公式 217

7.2.2 追踪递归过程 218

7.2.3 递归的稳步跳跃 221

7.3 斐波那契函数 222

7.3.1 计算斐波那契数列项 222

7.3.2 在递归实现中获得自信 223

7.3.3 递归实现的效率 224

7.3.4 递归不应被指责 225

7.4 检测回文 226

7.5 二分查找算法 228

7.6 间接递归 229

7.7 递归地思考 230

7.7.1 保持全局的观点 230

7.7.2 避免常见的错误 231

本章小结 232

复习题 233

习题 234

第8章 递归策略 237

8.1 汉诺塔 237

8.1.1 问题框架 238

8.1.2 找到一种递归策略 238

8.1.3 验证这个策略 240

8.1.4 编码方案 241

8.1.5 跟踪递归过程 242

8.2 子集求和问题 245

8.2.1 寻找一个递归解决方案 246

8.2.2 包含／排除模式 246

8.3 字符排列 247

8.4 图的递归 249

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

8.4.2 分形 252

本章小结 254

复习题 255

习题 255

第9章 回溯算法 264

9.1 迷宫的递归回溯 264

9.1.1 右手法则 264

9.1.2 寻找一种递归方法 265

9.1.3 确定简单情况 266

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

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

9.2 回溯与游戏 271

9.2.1 拿子游戏 272

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

9.3 最小最大算法 277

9.3.1 游戏树 278

9.3.2 评价位置和走法 278

9.3.3 限制递归搜索的深度 280

9.3.4 实现最小最大算法 280

本章小结 282

复习题 282

习题 283

第10章 算法分析 291

10.1 排序问题 291

10.1.1 选择排序算法 291

10.1.2 性能的经验评估 292

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

10.2 时间复杂度 294

10.2.1 大O符号 295

10.2.2 大O的标准简化 295

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

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

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

10.2.6 大O符号的正式定义 298

10.3 递归的终止 300

10.3.1 分治策略的作用 300

10.3.2 合并两个矢量 301

10.3.3 归并排序算法 301

10.3.4 归并排序的计算复杂度 302

10.3.5 比较N2与Nlog2N的性能 304

10.4 标准的算法复杂度类别 304

10.5 快速排序算法 306

10.5.1 划分矢量 308

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

10.6 数学归纳法 311

本章小结 313

复习题 314

习题 315

第11章 指针和数组 320

11.1 内存结构 320

11.1.1 位、字节和字 320

11.1.2 二进制和十六进制表示 321

11.1.3 表示其他数据类型 322

11.1.4 内存地址 323

11.1.5 为变量分配内存 325

11.2 指针 326

11.2.1 把地址当作数值 327

11.2.2 声明指针变量 327

11.2.3 基本的指针运算 328

11.2.4 指向结构和对象的指针 330

11.2.5 关键字this 331

11.2.6 特殊的指针NULL 331

11.2.7 指针和引用调用 332

11.3 数组 334

11.3.1 声明数组 334

11.3.2 数组元素的选择 335

11.3.3 数组的静态初始化 335

11.3.4 有效容量和分配容量 336

11.3.5 指针和数组的关系 336

11.4 指针运算 338

11.4.1 数组索引和内存地址 338

11.4.2 指针的自增自减运算 339

11.4.3 C风格字符串 339

11.4.4 指针运算和程序风格 341

本章小结 341

复习题 342

习题 344

第12章 动态内存管理 347

12.1 动态分配和堆 347

12.1.1 new操作符 348

12.1.2 动态数组 348

12.1.3 动态对象 349

12.2 链表 349

12.2.1 刚铎灯塔 349

12.2.2 链表内的迭代 352

12.2.3 递归和列表 352

12.3 释放内存 352

12.3.1 delete操作符 352

12.3.2 释放内存策略 353

12.3.3 析构函数 354

12.4 定义CharStack类 354

12.4.1 charstack.h接口 355

12.4.2 选择字符栈的表示 357

12.5 堆-栈图 361

12.6 单元测试 366

12.7 拷贝对象 368

12.7.1 深拷贝和浅拷贝 368

12.7.2 赋值和拷贝构造函数 369

12.8 关键字const的使用 371

12.8.1 常量定义 371

12.8.2 常量引用调用 372

12.8.3 const方法 372

12.9 CharStack类的效率 376

本章小结 377

复习题 378

习题 379

第13章 效率和表示 383

13.1 编辑文本的软件模式 383

13.2 设计简单的文本编辑器 384

13.2.1 编辑器命令 384

13.2.2 EditorBuffer类的公有接口 385

13.2.3 选择一种底层表示 387

13.2.4 编写编辑器应用代码 388

13.3 基于数组的类实现 389

13.3.1 定义私有数据结构 390

13.3.2 缓冲区操作的实现 390

13.3.3 基于数组的编辑器的时间复杂度 393

13.4 基于栈的类实现 394

13.4.1 定义私有数据结构 394

13.4.2 缓冲区操作的实现 395

13.4.3 时间复杂度的比较 397

13.5 基于列表的类实现 397

13.5.1 链表缓冲区的插入操作 400

13.5.2 链表缓冲区的删除操作 402

13.5.3 链表表示法中光标的移动 403

13.5.4 缓冲区实现的完善 405

13.5.5 基于链表的缓冲区的时间复杂度 407

13.5.6 双向链表 408

13.5.7 时空权衡 408

本章小结 409

复习题 409

习题 410

第14章 线性结构 414

14.1 模板 414

14.2 栈的实现 416

14.2.1 使用动态数组实现栈 416

14.2.2 使用链表实现栈 420

14.3 队列的实现 426

14.3.1 基于数组的队列实现 427

14.3.2 队列的链表表示 433

14.4 实现矢量类 437

14.5 集成原型和代码 442

本章小结 442

复习题 443

习题 444

第15章 映射 446

15.1 使用矢量实现映射 447

15.2 查找表 449

15.3 哈希 451

15.3.1 设计数据结构 451

15.3.2 为字符串定义哈希函数 452

15.3.3 实现哈希表 454

15.3.4 跟踪哈希表的实现 456

15.3.5 调整桶的数目 457

15.4 实现HashMap类 458

本章小结 459

复习题 460

习题 461

第16章 树 463

16.1 家谱 463

16.1.1 用来描述树的术语 463

16.1.2 树的递归特性 464

16.1.3 用C＋＋语言表示家谱 464

16.2 二叉搜索树 465

16.2.1 使用二叉搜索树的动机 466

16.2.2 在二叉搜索树中寻找节点 467

16.2.3 在二叉搜索树中插入一个新节点 468

16.2.4 删除节点 471

16.2.5 树的遍历 472

16.3 平衡树 473

16.3.1 平衡树策略 474

16.3.2 可视化AVL算法 475

16.3.3 单旋转 476

16.3.4 双旋转 478

16.3.5 实现AVL算法 478

16.4 使用BST实现映射 482

16.5 偏序数 482

本章小结 485

复习题 485

习题 487

第17章 集合 494

17.1 集合作为一种数学抽象 494

17.1.1 隶属关系 494

17.1.2 集合运算 495

17.1.3 集合恒等式 496

17.2 集合接口的扩展 497

17.3 集合的实现策略 500

17.4 优化小整数的集合 504

17.4.1 特征向量 504

17.4.2 压缩的位数组 505

17.4.3 位操作符 506

17.4.4 实现特征向量 507

17.4.5 实现高级集合运算 509

17.4.6 模板特化 509

17.4.7 使用一种混合的实现 509

本章小结 510

复习题 511

习题 512

第18章 图 514

18.1 图的结构 514

18.1.1 有向图和无向图 515

18.1.2 路径和回路 516

18.1.3 连通性 516

18.2 表示策略 517

18.2.1 用邻接表表示连接关系 517

18.2.2 用邻接矩阵表示连接关系 518

18.2.3 用弧集合表示关系 519

18.3 一种低层的图抽象 520

18.4 图的遍历 524

18.4.1 深度优先搜索 524

18.4.2 广度优先搜索 527

18.5 定义图类 528

18.5.1 用类表示图、节点和弧 528

18.5.2 用参数化的类实现图 529

18.6 寻找最短路径 538

18.7 搜索网页的算法 542

18.7.1 谷歌的网页排名算法 542

18.7.2 网页排名算法的一个简例 543

本章小结 544

复习题 545

习题 546

第19章 继承 551

19.1 简单的继承 551

19.1.1 指定模板类中的类型 551

19.1.2 定义Employee类 552

19.1.3 C＋＋中子类的局限性 554

19.2 图形对象的继承层次 556

19.2.1 调用父类的构造函数 561

19.2.2 将GObject类指针存储在矢量中 563

19.3 表达式的类层次 563

19.3.1 异常处理 565

19.3.2 表达式结构 566

19.3.3 表达式的递归定义 566

19.3.4 二义性 567

19.3.5 表达式树 568

19.3.6 exp.h接口 570

19.3.7 Expression子类的表示 573

19.3.8 表达式图解 573

19.3.9 方法的实现 574

19.4 解析表达式 577

19.4.1 语句解析和语法 577

19.4.2 考虑运算的优先级 578

19.4.3 递归下降语法分析器 579

19.5 多重继承 584

19.5.1 stream类库中的多重继承 584

19.5.2 在GObject继承层次中添加GFillable类 585

19.5.3 多重继承的危险性 586

本章小结 586

复习题 587

习题 589

第20章 迭代策略 595

20.1 使用迭代器 595

20.1.1 简单的迭代器例子 595

20.1.2 迭代器的层次结构 597

20.2 使用函数作为数据值 598

20.2.1 函数指针 598

20.2.2 简单的画图应用 598

20.2.3 声明函数指针 600

20.2.4 实现plot函数 600

20.2.5 映射函数 601

20.2.6 实现映射函数 603

20.2.7 回调函数的限制 603

20.3 用函数封装数据 604

20.3.1 使用对象模拟闭包 604

20.3.2 函数对象的简单例子 605

20.3.3 向映射函数传递函数对象 606

20.3.4 编写以函数作为参数的函数 607

20.4 STL算法库 607

20.5 C＋＋的函数式编程 609

20.5.1 STL库＜functional＞的接口 610

20.5.2 比较函数 612

20.6 迭代器的实现 612

20.6.1 为矢量类实现迭代器 612

20.6.2 将指针作为迭代器 616

20.6.3 typedef关键字 617

20.6.4 为其他集合类实现迭代器 618

本章小结 618

复习题 619

习题 619

索引 624