Data Structures and Problem Solving Using C++:2nd

第一部分 对象和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 附加的构造函数语法和

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 顺序统计 526

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