数据结构与算法分析 C语言描述PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与算法分析 C语言描述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

总结9

练习9

参考文献10

2.1 数学基础11

第2章 算法分析11

2.2 模型13

2.3 要分析的问题13

2.4 运行时间计算15

2.4.1 一个简单的例子15

2.4.2 一般法则16

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

2.4.4 运行时间中的对数21

2.4.5 检验你的分析24

2.4.6 分析结果的准确性25

总结26

练习26

参考文献29

3.2 表ADT31

3.1 抽象数据类型(ADT)31

第3章 表、栈和队列31

3.2.1 表的简单数组实现32

3.2.2 链表32

3.2.3 程序设计细节33

3.2.4 常见的错误37

3.2.5 双链表38

3.2.6 循环链表38

3.2.7 例子39

3.2.8 链表的游标实现42

3.3 栈ADT46

3.3.1 栈模型46

3.3.2 栈的实现46

3.3.3 应用52

3.4.2 队列的数组实现58

3.4 队列ADT58

3.4.1 队列模型58

3.4.3 队列的应用61

总结62

练习62

第4章 树65

4.1 预备知识65

4.1.1 树的实现66

4.1.2 树的遍历及应用67

4.2 二叉树70

4.2.1 实现70

4.2.2 表达式树70

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

4.3.1 MakeEmpty73

4.3.3 FindMin和FindMax74

4.3.2 Find74

4.3.4 Insert75

4.3.5 Delete76

4.3.6 平均情形分析77

4.4 AVL树80

4.4.1 单旋转82

4.4.2 双旋转84

4.5 伸展树89

4.5.1 一个简单的想法90

4.5.2 展开91

4.6 树的遍历96

4.7 B-树97

总结101

练习102

参考文献107

第5章 散列111

5.1 一般想法111

5.2 散列函数111

5.3 分离链接法113

5.4 开放定址法117

5.4.1 线性探测法117

5.4.2 平方探测法118

5.4.3 双散列122

5.5 再散列123

5.6 可扩散列124

总结126

练习127

参考文献129

6.1 模型133

第6章 优先队列(堆)133

6.2 一些简单的实现134

6.3 二叉堆134

6.3.1 结构性质134

6.3.2 堆序性质135

6.3.3 基本的堆操作136

6.3.4 其他的堆操作139

6.4 优先队列的应用142

6.4.1 选择问题142

6.4.2 事件模拟143

6.5 d-堆144

6.6 左式堆145

6.6.1 左式堆的性质145

6.6.2 左式堆的操作146

6.7 斜堆150

6.8 二项队列152

6.8.1 二项队列结构152

6.8.2 二项队列操作153

6.8.3 二项队列的实现155

总结158

练习159

参考文献162

第7章 排序165

7.1 预备知识165

7.2 插入排序165

7.2.1 算法165

7.2.2 插入排序的分析166

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

7.4 希尔排序167

7.4.1 希尔排序的最坏情形分析168

7.5 堆排序170

7.5.1 堆排序的分析172

7.6 归并排序173

7.6.1 归并排序的分析175

7.7 快速排序177

7.7.1 选取枢纽元179

7.7.2 分割策略179

7.7.3 小数组181

7.7.4 实际的快速排序例程181

7.7.5 快速排序的分析183

7.7.6 选择的线性期望时间算法185

7.8 大型结构的排序186

7.9 排序的一般下界187

7.9.1 决策树187

7.11.1 为什么需要新的算法189

7.10 桶式排序189

7.11 外部排序189

7.11.2 外部排序模型190

7.11.3 简单算法190

7.11.4 多路合并190

7.11.5 多相合并192

7.11.6 替换选择192

总结193

练习194

参考文献197

第8章 不相交集ADT199

8.1 等价关系199

8.2 动态等价性问题199

8.3 基本数据结构201

8.4 灵巧求并算法203

8.5 路径压缩205

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

8.6.1 Union/Find算法分析207

8.7 一个应用211

总结211

练习212

参考文献213

第9章 图论算法215

9.1 若干定义215

9.1.1 图的表示216

9.2 拓扑排序217

9.3 最短路径算法219

9.3.1 无权最短路径220

9.3.2 Dijkstra算法224

9.3.3 具有负边值的图229

9.3.4 无圈图230

9.3.5 所有点对最短路径232

9.4 网络流问题232

9.4.1 一个简单的最大流算法233

9.5 最小生成树236

9.5.1 Prim算法237

9.5.2 Kruskal算法239

9.6 深度优先搜索的应用240

9.6.1 无向图241

9.6.2 双连通性242

9.6.3 欧拉回路245

9.6.4 有向图248

9.6.5 查找强分支249

9.7 NP-完全性介绍250

9.7.1 难与易251

9.7.2 NP类252

9.7.3 NP-完全问题252

总结254

练习254

参考文献258

第10章 算法设计技巧263

10.1 贪婪算法263

10.1.1 一个简单的调度问题263

10.1.2 Huffman编码266

10.1.3 近似装箱问题270

10.2 分治算法276

10.2.1 分治算法的运行时间277

10.2.2 最近点问题279

10.2.3 选择问题281

10.2.4 一些运算问题的理论改进284

10.3 动态规划287

10.3.1 用一个表代替递归287

10.3.2 矩阵乘法的顺序安排289

10.3.3 最优二叉查找树291

10.3.4 所有点对最短路径294

10.4 随机化算法296

10.4.1 随机数发生器297

10.4.2 跳跃表300

10.4.3 素性测试302

10.5 回溯算法304

10.5.1 收费公路重建问题304

10.5.2 博弈308

练习313

总结313

参考文献320

第11章 摊还分析325

11.1 一个无关的智力问题325

11.2 二项队列326

11.3 斜堆329

11.4 斐波那契堆331

11.4.1 切除左式堆中的节点332

11.4.2 二项队列的懒惰合并334

11.4.3 斐波那契堆操作336

11.4.4 时间界的证明337

11.5 伸展树339

总结342

练习342

参考文献343

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

12.1 自顶向下伸展树345

12.2 红黑树351

12.2.1 自底向上插入352

12.2.2 自顶向下红黑树353

12.2.3 自顶向下删除354

12.3 确定性跳跃表357

12.4 AA-树362

12.5 treap树367

12.6 k-d树369

12.7 配对堆372

总结376

练习376

参考文献378

索引381