C++数据结构与算法 第4版PDF|Epub|txt|kindle电子书版本网盘下载

C++数据结构与算法 第4版PDF格式电子书版下载

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

第1章 C＋＋面向对象程序设计1

1.1 抽象数据类型1

1.2 封装1

1.3 继承5

1.4 指针7

1.4.1 指针与数组10

1.4.2 指针与复制构造函数12

1.4.3 指针与析构函数14

1.4.4 指针和引用变量14

1.4.5 函数指针17

1.5 多态性18

1.6 C＋＋和面向对象程序设计20

1.7 标准模板库20

1.7.1 容器21

1.7.2 迭代器21

1.7.3 算法21

1.7.4 函数对象22

1.8 标准模板库中的向量24

1.9 数据结构与面向对象编程29

1.10 案例分析：随机访问文件30

1.11 习题38

1.12 编程练习40

参考书目42

第2章 复杂度分析43

2.1 计算复杂度以及渐近复杂度43

2.2 大O表示法44

2.3 大O表示法的性质46

2.4 Ω表示法与？表示法47

2.5 可能存在的问题48

2.6 复杂度示例49

2.7 确定渐近复杂度示例50

2.8 最好、平均和最坏情况51

2.9 摊销复杂度（amortized complexity）54

2.10 NP完整性57

2.11 习题59

参考书目61

第3章 链表63

3.1 单向链表63

3.1.1 插入68

3.1.2 删除70

3.1.3 查找74

3.2 双向链表74

3.3 循环链表78

3.4 跳跃链表（skip list）79

3.5 自组织链表83

3.6 稀疏表87

3.7 标准模板库中的链表89

3.8 小结92

3.9 案例分析：图书馆93

3.10 习题101

3.11 编程练习102

参考书目105

第4章 栈与队列107

4.1 栈107

4.2 队列113

4.3 优先队列119

4.4 标准模板库中的栈119

4.5 标准模板库中的队列120

4.6 标准模板库中的优先队列121

4.7 标准模版库中的双端队列123

4.8 案例分析：迷宫问题127

4.9 习题131

4.10 编程练习133

参考书目134

第5章 递归135

5.1 递归定义135

5.2 函数调用与递归实现137

5.3 分析递归调用139

5.4 尾递归142

5.5 非尾递归142

5.6 间接递归147

5.7 嵌套递归148

5.8 不合理递归149

5.9 回溯152

5.10 小结157

5.11 案例分析：递归下降解释器158

5.12 习题165

5.13 编程练习167

参考书目169

第6章 二叉树171

6.1 树、二叉树和二叉查找树171

6.2 二叉树的实现174

6.3 二叉查找树的查找176

6.4 树的遍历179

6.4.1 广度优先遍历179

6.4.2 深度优先遍历180

6.4.3 不使用栈的深度优先遍历186

6.5 插入191

6.6 删除193

6.6.1 合并删除194

6.6.2 复制删除196

6.7 树的平衡198

6.7.1 DSW算法200

6.7.2 AVL树202

6.8 自适应树（self-adjusting tree）207

6.8.1 自重新构造树（self-restructuring tree）207

6.8.2 “张开”策略（splaying）208

6.9 堆212

6.9.1 将堆作为优先队列213

6.9.2 用数组实现堆215

6.10 treap树218

6.11 k-d树221

6.12 波兰表示法和表达式树225

6.13 案例分析：计算单词出现的频率229

6.14 习题235

6.15 编程练习239

参考书目242

第7章 多叉树245

7.1 B树家族245

7.1.1 B树247

7.1.2 B＊树254

7.1.3 B＋树255

7.1.4 前缀B＋树257

7.1.5 k-d B树259

7.1.6 位树264

7.1.7 R树265

7.1.8 2-4树267

7.1.9 标准模板库中的集合（set）以及多重集合（multiset）278

7.1.10 标准模板库中的映射（map）和多映射（multimap）282

7.2 trie286

7.3 小结292

7.4 案例分析：拼写检查器292

7.5 习题300

7.6 编程练习301

参考书目304

第8章 图307

8.1 图的表示法308

8.2 图的遍历309

8.3 最短路径312

8.4 环的检测319

8.5 生成树322

8.6 连通性324

8.6.1 无向图中的连通性324

8.6.2 有向图中的连通性326

8.7 拓扑排序328

8.8 网络329

8.8.1 最大流329

8.8.2 成本最低的最大流337

8.9 匹配340

8.9.1 稳定匹配问题344

8.9.2 分配问题346

8.9.3 非二分图中的匹配集合348

8.10 欧拉（Eulerian）图与汉密尔顿（Hamiltonian）图349

8.10.1 欧拉图349

8.10.2 汉密尔顿图352

8.11 图的上色问题356

8.12 图论中的NP完整性问题359

8.12.1 派系问题359

8.12.2 三色问题360

8.12.3 顶点覆盖问题361

8.12.4 汉密尔顿环问题361

8.13 案例分析：唯一代表363

8.14 习题372

8.15 编程练习376

参考书目377

第9章 排序381

9.1 基本的排序算法382

9.1.1 插入排序382

9.1.2 选择排序384

9.1.3 冒泡排序386

9.1.4 梳排序388

9.2 决策树389

9.3 高效排序算法392

9.3.1 希尔排序392

9.3.2 堆排序395

9.3.3 快速排序397

9.3.4 归并排序402

9.3.5 基数排序405

9.3.6 计数排序408

9.4 标准模板库中的排序410

9.5 小结414

9.6 案例分析：多项式相加414

9.7 习题420

9.8 编程练习422

参考书目423

第10章 散列427

10.1 散列函数427

10.1.1 除余法428

10.1.2 折叠法428

10.1.3 平方取中法429

10.1.4 提取法429

10.1.5 基数转换法429

10.1.6 全域散列法429

10.2 冲突解决方法430

10.2.1 开放定址法430

10.2.2 链接法435

10.2.3 桶定址436

10.3 删除437

10.4 理想散列函数438

10.4.1 Cichelli方法438

10.4.2 FHCD算法440

10.5 再散列442

10.6 可扩展文件的散列函数444

10.6.1 可扩展散列445

10.6.2 线性散列446

10.7 案例分析：使用桶的散列449

10.8 习题456

10.9 编程练习457

参考书目458

第11章 数据压缩461

11.1 数据压缩的条件461

11.2 Huffman编码463

11.3 Run-Length编码方式473

11.4 Ziv-Lempel编码方式474

11.5 案例分析：Huffman方法和Run-Length编码方式476

11.6 习题485

11.7 编程练习486

参考书目487

第12章 内存管理489

12.1 sequential-fit方法490

12.2 nonsequential-fit方法491

12.3 垃圾回收497

12.3.1 标记和清除498

12.3.2 复制方法504

12.3.3 递增的垃圾回收505

12.3.4 分代垃圾回收510

12.4 小结513

12.5 案例分析514

12.6 习题521

12.7 编程练习522

参考书目524

第13章 字符串匹配527

13.1 字符串的精确匹配527

13.1.1 简单的算法527

13.1.2 Knuth-Morris-Pratt算法530

13.1.3 Boyer-Moore算法536

13.1.4 多次搜索545

13.1.5 面向位的方法546

13.1.6 单词集合的匹配550

13.1.7 正则表达式的匹配555

13.1.8 后缀trie和树558

13.1.9 后缀数组563

13.2 字符串的模糊匹配564

13.2.1 字符串的近似性565

13.2.2 有k个错误的字符串匹配570

13.3 案例分析：最长的共有子字符串573

13.4 习题580

13.5 编程练习581

参考书目582

附录A 计算大O585

附录B 标准模板库中的算法591

附录C NP完整性599