数据结构与问题求解 C++版PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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

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

目录1

第一部分　对象和C++1

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

1.2　数组和字符串2

1.2.2　使用Vector3

1.2.3 调整Vector大小5

1.2.5　参数传递机制7

1.2.4　push back大小与容量7

1.2.8　标准库类型string9

1.2.7　多维数组9

1.2.6　常量基元数组9

1.3　C++中的指针语法10

1.4　动态内存管理14

1.4.2　垃圾收集与delete15

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 模板有关的bug90

3.6.3　保留字typename90

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或非virtual104

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 迭代器设计1137

5.4.3　基于继承的迭代器和factory139

5.4.2 迭代器设计2139

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　实现带有迭代器的vector193

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副本数减少为2N275

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和merge625

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