数据结构与问题求解 C++版PDF电子书下载

第1章　数组、指针和结构 1

1.1　什么是指针、数组和结构 1

目录 1

第一部分　对象和C++ 1

1.2.1　头等对象与次等对象的对比 2

1.2　数组和字符串 2

1.2.2　使用Vector 3

1.2.3 调整Vector大小 5

1.2.5　参数传递机制 7

1.2.4　push back大小与容量 7

1.2.8　标准库类型string 9

1.2.7　多维数组 9

1.2.6　常量基元数组 9

1.3　C++中的指针语法 10

1.4　动态内存管理 14

1.4.2　垃圾收集与delete 15

1.4.1　new运算符 15

1.4.3　过期指针、双重删除及其他 16

1.5　引用变量 17

1.6　结构 19

1.6.2　外部数据与内部数据、深复制与浅复制 21

1.6.1　指向结构的指针 21

1.6.3　非邻接链表：链表 23

学习目标 24

小结 24

常见错误 25

简答题 26

练习 26

网上资源 26

参考文献 28

编程项目 28

实践题 28

2.1　什么是面向对象编程 30

第2章　对象和类 30

2.2.1 类成员 31

2.2　类的基本语法 31

2.2.2　附加的构造函数语法和访问函数 33

2.2.3　接口和实现的分离 35

2.2.4　析构函数、复制构造函数和赋值运算符（＝） 38

2.3　附加的C++类特性 43

2.2.5　默认的构造函数 43

2.3.1　调整后的构造函数中的初始化与赋值 47

2.3.2　类型转换 48

2.3.3　运算符重载 49

2.3.4　输入、输出和友元 52

2.4.1　避免使用友元 54

2.4　一些常用术语 54

2.4.3　整型类常量的陷阱 55

2.4.2　静态类成员 55

2.5　异常 56

2.6　String类 57

2.7　要点重述：进行了哪些调用？哪些采用了默认行为 65

2.8　组合 66

小结 67

学习目标 68

常见错误 69

简答题 70

练习 70

Internet资源 70

理论题 71

编程项目 72

参考文献 75

3.2　函数模板 76

3.1　模板的概念 76

第3章　模板 76

3.3　排序函数模板 78

3.4.1　MemoryCell模板 81

3.4　类模板 81

3.4.2　实现vector类模板 85

3.5　模板的模板：matrix类 87

3.5.1　数据成员、构造函数和基本附件 88

3.6.1 多平台参数 89

3.6　Fancy模板 89

3.5.2　operator［］ 89

3.5.3　析构函数、复制赋值和复制构造函数 89

3.7 模板有关的bug 90

3.6.3　保留字typename 90

3.6.2　默认的模板参数 90

学习目标 91

小结 91

3.7.1　错误消息和改变的规则 91

3.7.2　模板匹配算法 91

3.7.3　模板中的嵌套类 91

3.7.4　类模板中的静态成员 91

Internet资源 92

常见错误 92

编程项目 93

实践题 93

练习 93

简答题 93

4.1　什么是继承 94

第4章 继承 94

4.2　继承的基本知识 97

4.2.2　构造函数和基类初始化 98

4.2.1 视性规则 98

4.2.3　添加成员 99

4.2.5　静态绑定和动态绑定 101

4.2.4　覆盖方法 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.3　派生类方法隐藏基类方法 114

4.4.2　默认参数 114

4.4.4　覆盖方法的兼容返回类型 115

4.4.6　友元 116

4.4.5　私有继承 116

4.5　多重继承 117

4.4.7　值调用与多态并不混淆 117

小结 118

常见错误 119

学习目标 119

简答题 120

练习 120

Internet资源 120

参考文献 122

编程项目 122

实践题 122

5.1　模式的概念 123

第5章　设计模式 123

5.2　Functor（函数对象） 124

5.3.1　指针包装器 129

5.3　适配器和包装器 129

5.3.2　常数引用包装器 134

5.3.3　适配器更改接口 135

5.4　迭代器 136

5.4.1 迭代器设计1 137

5.4.3　基于继承的迭代器和factory 139

5.4.2 迭代器设计2 139

5.6　观察者 144

5.5　合成（对） 144

学习目标 148

小结 148

Internet资源 149

常见错误 149

实践题 150

理论题 150

练习 150

简答题 150

参考文献 152

编程项目 152

6.1　什么是算法分析 153

第6章　算法分析 153

第二部分　算法和构建代码块 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.2　折半查找 169

6.6.1 顺序查找 169

6.6　静态查找问题 169

6.6.3　插值查找 172

6.7　算法分析的检验 173

学习目标 174

小结 174

6.8　Big-Oh分析的限制 174

Internet资源 175

常见错误 175

简答题 176

练习 176

理论题 177

编程项目 179

实践题 179

参考文献 180

7.1　简介 182

第7章　标准模板库 182

7.2　堆栈和队列 183

7.2.1 堆栈 184

7.2.2　堆栈和计算机语言 185

7.2.3 队列 186

7.3.1 容器 187

7.3　容器和迭代器 187

7.3.2　迭代器 188

7.4.1 STL函数对象 189

7.4　STL算法 189

7.4.2　二分查找法 191

7.5　实现带有迭代器的vector 193

7.4.3　排序 193

7.6.1　list类 195

7.6　顺序表和链表 195

7.6.2　堆栈和队列 196

7.7　集合 197

7.8　映射 199

7.9　优先队列 200

小结 203

常见错误 204

学习目标 204

理论题 205

简答题 205

Internet资源 205

练习 205

编程项目 206

实践题 206

参考文献 208

8.1　递归的概念 209

第8章　递归 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.1　模运算 223

8.4　数值应用 223

8.4.2　模幂运算 224

8.4.3　最大公约数和乘法逆元素 225

8.4.4　RSA密码系统 228

8.5.1　最大邻近子序列和问题 230

8.5　分治算法 230

8.5.2　基本分治递归分析 233

8.5.3　分治法运行时间的一般上限 235

8.6　动态规划 237

8.7　回溯法 241

学习目标 244

小结 244

Internet资源 245

常见错误 245

理论题 246

简答题 246

练习 246

实践题 247

编程项目 248

参考文献 249

9.1　排序为何重要 250

第9章　排序算法 250

9.2　预备知识 251

9.3　插入排序和其他简单排序的分析 252

9.4　希尔排序 254

9.5　归并排序 257

9.5.1　排过序的数组的线性时间合并 257

9.5.2　归并排序算法 259

9.6.1　快速排序算法 261

9.6　快速排序 261

9.6.2　快速排序的分析 263

9.6.3　支点的选择 265

9.6.4　分组策略 267

9.6.5　同支点相等的键 268

9.6.6 中值划分 269

9.6.8　C++快速排序例程 270

9.6.7　小数组 270

9.7　排序选择 272

9.8　排序的下限 274

9.9.1　使用指针将Comparable副本数减少为2N 275

9.9　间接排序 275

9.9.2　避免附加数组 276

小结 278

Internet资源 279

常见错误 279

学习目标 279

理论题 280

简答题 280

练习 280

实践题 281

编程项目 282

参考文献 283

10.1　为什么我们需要随机数 285

第10章　随机 285

10.2　随机数生成器 286

10.3　非均匀随机数 290

10.4　生成随机排列 291

10.5　随机算法 293

10.6　随机素数测试 295

常见错误 298

学习目标 298

小结 298

理论题 299

简答题 299

Internet资源 299

练习 299

编程项目 300

实践题 300

参考文献 301

11.1　单词查找拼图 302

第11章　娱乐与游戏 302

第三部分　应用程序 302

11.1.1　理论 303

11.1.2　C++实现 304

11.2.1　α-β修剪 309

11.2　Tic-Tac-Toe游戏 309

11.2.2　变换表 312

小结 316

11.2.3　计算机国际象棋 316

理论题 317

简答题 317

学习目标 317

常见错误 317

Internet资源 317

练习 317

编程项目 318

实践题 318

参考文献 319

12.1.1　基本算法 320

12.1 对称符号检查器 320

第12章　堆栈和编译器 320

12.1.2　实现 321

12.2.1　后缀自动机 330

12.2　简单计算器 330

12.2.2　中缀到后缀的转换 332

12.2.3　实现 333

12.2.4　表达式树 341

Internet资源 343

常见错误 343

小结 343

学习目标 343

实践题 344

理论题 344

练习 344

简答题 344

参考文献 345

编程项目 345

13.1　文件压缩 346

第13章　实用工具 346

13.1.1　前缀码 347

13.1.2　霍夫曼算法 348

13.1.3　实现 350

13.2.2 C++实现 366

13.2.1　基本概念 366

13.2　交叉引用生成程序 366

学习目标 370

小结 370

理论题 371

简答题 371

常见错误 371

Internet资源 371

练习 371

编程项目 372

实践题 372

参考文献 373

14.1　Josephus问题 375

第14章　仿真 375

14.1.2　一个更有效的算法 376

14.1.1　简单的解决方案 376

14.2.1 基本思想 380

14.2　事件驱动仿真 380

14.2.2　实例：调制解调器库仿真 381

学习目标 388

小结 388

理论题 389

简答题 389

常见错误 389

Internet资源 389

练习 389

编程项目 390

实践题 390

15.1　定义 391

第15章　图和路径 391

15.2.1 理论 403

15.2　无权最短路径问题 403

15.2.2　C++实现 406

15.3.1　理论：迪杰斯特拉算法 407

15.3　正的有权最短路径问题 407

15.3.2　C++实现 410

15.4.1 理论 412

15.4　负的有权最短路径问题 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

理论证明 423

简答题 423

Internet资源 423

练习 423

实践题 424

编程项目 425

参考文献 426

16.1.1　堆栈 427

16.1　动态数组实现 427

第四部分　实现 427

第16章　堆栈和队列 427

16.1.2　队列 431

16.2.1　堆栈 436

16.2　链表实现 436

16.2.2　队列 441

16.3　两种方法的比较 444

16.4　STL堆栈和队列适配器 445

16.5 双头队列 446

学习目标 447

小结 447

简答题 448

练习 448

常见错误 448

Internet资源 448

编程项目 449

实践题 449

17.1　基本概念 450

第17章　链表 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

Internet资源 480

常见错误 480

学习目标 480

理论题 481

简答题 481

练习 481

实践题 482

编程项目 483

18.1.1 定义 485

18.1　一般树 485

第18章　树 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

Internet资源 512

学习目标 512

简答题 513

练习 513

编程项目 514

实践题 514

理论题 514

19.1　基本概念 516

第19章　二叉查找树 516

19.1.1　操作 517

19.1.2　C++实现 518

C++实现 526

19.2　顺序统计 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.1 自底向上插入 541

19.5　红—黑树 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

简答题 582

练习 582

Internet资源 582

实践题 583

理论题 583

参考文献 584

编程项目 584

20.1 基本概念 587

第20章　散列表 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.5　分离链接法 603

20.4.2　二次探测法分析 603

20.7　散列化应用程序 604

20.6　散列表与二叉查找树 604

学习目标 605

小结 605

简答题 606

练习 606

常见错误 606

Internet资源 606

实践题 607

参考文献 608

编程项目 608

21.1　基本思想 610

第21章　优先级队列：二叉堆 610

21.1.1　结构属性 611

21.1.2 堆顺序属性 612

21.1.3　允许的操作 613

21.2.1　insert操作 615

21.2　基本操作的实现 615

21.2.2　deleteMin操作 616

21.3　buildHeap操作：线性时间的堆构造函数 619

21.4　STL priority_queue实现 622

21.6　内部排序：堆排序 625

21.5 高级操作：decreaseKey和merge 625

21.7.2　外部排序模型 628

21.7.1　我们为什么需要新的算法 628

21.7　外部排序 628

21.7.3　简单的算法 629

21.7.4　多路归并 630

21.7.5　多相归并 631

21.7.6　置换选择 632

学习目标 634

小结 634

理论题 635

简答题 635

常见错误 635

Internet资源 635

练习 635

编程项目 637

实践题 637

参考文献 638

22.1 自我调整和摊销分析 639

第22章　伸展树 639

第五部分 高级数据结构 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

理论题 659

简答题 659

Internet资源 659

练习 659

参考文献 660

编程项目 660

实践题 660

23.1.1　合并是基础 661

23.1　偏斜堆 661

第23章　合并优先级队列 661

23.1.3　偏斜堆：简单修改 662

23.1.2　简化的堆排序树合并 662

23.1.4　偏斜堆分析 663

23.2 对偶堆 665

23.2.1 对偶堆的操作 666

23.2.2 对偶堆的实现 668

23.2.3 应用：Dijkstra最短加权路径算法 674

常见错误 676

学习目标 676

小结 676

理论题 677

简答题 677

Internet资源 677

练习 677

参考文献 678

编程项目 678

实践题 678

24.2　动态等价和两个应用 680

24.1　等价关系 680

第24章　不相交集类 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

练习 702

常见错误 702

Internet资源 702

编程项目 703

实践题 703

理论题 703

参考文献 704

A.2.1 自增运算符与自减运算符 706

A.2　不常见的C++运算符 706

附录 706

附录A　C++相关信息 706

A.1 没有编译器实现该标准 706

A.2.2　类型转换 707

A.2.3　按位运算符 708

A.4　输入和输出 710

A.3　命令参数 710

A.2.4　条件运算符 710

A.4.1　基本的流操作 711

A.4.3　字符串流 714

A.4.2　顺序文件 714

A.5　名字空间 716

常见错误 717

A.6　C++新特性 717

附录B　运算符 719

C.2 〈limits.h〉和〈climits〉中声明的常量 720

C.1 〈ctype.h〉和〈cctype〉中声明的例程 720

附录C　某些库例程 720

C.4 〈stdlib.h〉和〈cstdlib〉中声明的例程 721

C.3 〈math.h〉和〈cmath〉中声明的例程 721

D.1.1 C++实现：数组名称是一个指针 723

D.1　基元数组 723

附录D　C++中的基元数组 723

D.1.3　char＊类型、const指针和常量字符串 726

D.1.2　多维数组 726

D.2　动态数组分配：new［］和delete［］ 729

D.3　指针算术运算、指针跳和基本迭代 733

D.3.2　指针算术的含意 734

D.3.1　＊、＆和［］优先级的含意 734

D.3.3　指针跳例子 736

D.3.4　使用指针跳的意义 737

Internet资源 738

常见错误 738