数据结构与算法分析 C++描述 第3版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

数据结构与算法分析 C++描述 第3版PDF格式电子书版下载

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

第1章 引论1

1.1　本书讨论的内容1

1.2　数学知识复习2

1.2.1　指数2

1.2.2 对数2

1.2.3 级数3

1.2.4　模运算4

1.2.5　证明方法4

1.3　递归的简单介绍6

1.4　C++类9

1.4.1 基本class语法9

1.4.2　特别的构造函数语法与访问函数10

1.4.3　接口与实现的分离11

1.4.4　vector和string13

1.5 C++细节14

1.5.1 指针14

1.5.2　参数传递15

1.5.3 返回值传递16

1.5.4 引用变量16

1.5.5　三大函数：析构函数、复制构造函数和operator=17

1.5.6　C风格的数组和字符串20

1.6　模板21

1.6.1 函数模板22

1.6.2　类模板22

1.6.3　Object、Comparable和例子24

1.6.4 函数对象25

1.6.5　类模板的分离编译26

1.7　使用矩阵27

1.7.1　数据成员、构造函数和基本访问函数27

1.7.2 operator[]28

1.7.3　析构函数、复制赋值和复制构造函数29

小结29

练习29

参考文献30

第2章 算法分析32

2.1 数学基础32

2.2　模型34

2.3　要分析的问题34

2.4　运行时间计算36

2.4.1　一个简单的例子37

2.4.2　一般法则37

2.4.3　最大子序列和问题的解39

2.4.4　运行时间中的对数44

2.4.5　检验你的分析46

2.4.6　分析结果的准确性47

小结48

练习48

参考文献52

第3章 表、栈和队列53

3.1 抽象数据类型（ADT）53

3.2 表ADT53

3.2.1　表的简单数组实现54

3.2.2　简单链表54

3.3　STL中的向量和表55

3.3.1　迭代器56

3.3.2 示例：对表使用erase57

3.3.3 const_iterator58

3.4　向量的实现59

3.5　表的实现63

3.6　栈ADT71

3.6.1　栈模型71

3.6.2　栈的实现72

3.6.3 应用72

3.7 队列ADT78

3.7.1 队列模型78

3.7.2　队列的数组实现78

3.7.3 队列的应用80

小结81

练习81

第4章 树85

4.1　预备知识85

4.1.1　树的实现86

4.1.2　树的遍历及应用87

4.2　二叉树90

4.2.1 实现90

4.2.2　一个例子——表达式树91

4.3　查找树ADT——二叉查找树93

4.3.1 contains94

4.3.2 findMin和findMax96

4.3.3 insert97

4.3.4 remove98

4.3.5　析构函数和复制赋值操作符99

4.3.6　平均情况分析99

4.4　AVL树102

4.4.1 单旋转104

4.4.2　双旋转106

4.5　伸展树111

4.5.1　一个简单的想法（不能直接使用）112

4.5.2　伸展113

4.6　树的遍历118

4.7　B树119

4.8 标准库中的set和map123

4.8.1 set123

4.8.2 map124

4.8.3　set和map的实现125

4.8.4　使用几个map的例子126

小结130

练习130

参考文献135

第5章　散列137

5.1 基本思想137

5.2　散列函数137

5.3　分离链接法139

5.4　不使用链表的散列表142

5.4.1　线性探测142

5.4.2　平方探测144

5.4.3 散列148

5.5　再散列148

5.6　标准库中的散列表150

5.7　可扩散列151

小结153

练习154

参考文献156

第6章　优先队列（堆）158

6.1　模型158

6.2　一些简单的实现159

6.3 二叉堆159

6.3.1　结构性质159

6.3.2　堆序性质160

6.3.3　基本的堆操作161

6.3.4　堆的其他操作164

6.4　优先队列的应用167

6.4.1 选择问题167

6.4.2　事件模拟168

6.5　d堆169

6.6　左式堆170

6.6.1　左式堆性质170

6.6.2　左式堆操作171

6.7　斜堆175

6.8　二项队列177

6.8.1　二项队列结构177

6.8.2　二项队列操作178

6.8.3　二项队列的实现180

6.9　标准库中的优先队列183

小结185

练习185

参考文献189

第7章　排序191

7.1 预备知识191

7.2　插入排序192

7.2.1 算法192

7.2.2　插入排序的STL实现192

7.2.3　插入排序的分析194

7.3　一些简单排序算法的下界194

7.4　谢尔排序195

7.5 堆排序198

7.6　归并排序200

7.7　快速排序204

7.7.1　选取枢纽元206

7.7.2　分割策略206

7.7.3 小数组208

7.7.4　实际的快速排序例程208

7.7.5　快速排序的分析209

7.7.6 选择问题的线性期望时间算法213

7.8　间接排序213

7.8.1 vector〈Comparable＊〉不运行215

7.8.2　智能指针类216

7.8.3　重载operator<217

7.8.4　使用“＊”解引用指针217

7.8.5　重载类型转换操作符217

7.8.6　随处可见的隐式类型转换217

7.8.7　双向隐式类型转换会导致歧义218

7.8.8　指针减法是合法的218

7.9　排序算法的一般下界218

7.10　桶排序220

7.11　外部排序220

7.11.1　为什么需要新算法220

7.11.2　外部排序模型221

7.11.3　简单算法221

7.11.4　多路合并222

7.11.5　多相合并223

7.11.6　替换选择223

小结224

练习225

参考文献229

第8章　不相交集类231

8.1　等价关系231

8.2　动态等价性问题231

8.3　基本数据结构233

8.4　灵巧求并算法235

8.5　路径压缩237

8.6　按秩求并和路径压缩的最坏情形239

8.7　一个应用243

小结245

练习245

参考文献246

第9章 图论算法248

9.1　若干定义248

9.2　拓扑排序250

9.3　最短路径算法252

9.3.1　无权最短路径254

9.3.2　Dijkstra算法257

9.3.3　具有负边值的图262

9.3.4　无环图263

9.3.5　所有顶点对的最短路径265

9.3.6　最短路径举例266

9.4　网络流问题267

9.5　最小生成树271

9.5.1　Prim算法272

9.5.2　Kruskal算法273

9.6　深度优先搜索的应用275

9.6.1　无向图276

9.6.2　双连通性276

9.6.3　欧拉回路279

9.6.4　有向图282

9.6.5　查找强分支283

9.7　NP完全性介绍284

9.7.1 难与易285

9.7.2　NP类286

9.7.3　NP完全问题286

小结288

练习288

参考文献293

第10章 算法设计技巧296

10.1 贪心算法296

10.1.1　一个简单的调度问题297

10.1.2　赫夫曼编码299

10.1.3　近似装箱问题303

10.2　分治算法310

10.2.1　分治算法的运行时间310

10.2.2　最近点问题312

10.2.3 选择问题315

10.2.4　一些算术问题的理论改进317

10.3　动态规划320

10.3.1　用表代替递归320

10.3.2　矩阵乘法的顺序安排322

10.3.3　最优二叉查找树325

10.3.4　所有点对最短路径327

10.4　随机化算法329

10.4.1　随机数生成器330

10.4.2　跳跃表333

10.4.3　素性测试335

10.5　回溯算法337

10.5.1 公路收费点重建问题337

10.5.2　博弈341

小结346

练习346

参考文献351

第11章 摊还分析355

11.1　一个无关的智力问题355

11.2　二项队列356

11.3　斜堆359

11.4　斐波那契堆361

11.4.1 切除左式堆中的结点362

11.4.2　二项队列的懒惰合并364

11.4.3　斐波那契堆操作366

11.4.4 时间界的证明367

11.5　伸展树368

小结371

练习371

参考文献372

第12章 高级数据结构及其实现374

12.1 自顶向下伸展树374

12.2　红黑树379

12.2.1 自底向上插入380

12.2.2　自顶向下红黑树381

12.2.3　自顶向下删除385

12.3　确定性跳跃表387

12.4　AA树392

12.5　treap树396

12.6　k-d树399

12.7　配对堆401

小结405

练习406

参考文献408

附录 类模板的分离编译411

索引414