数据结构与算法分析 C++版PDF电子书下载

第一部分 预备知识 2

第1章 数据结构和算法 2

1.1 数据结构的原则 3

1.1.1 学习数据结构的必要性 3

1.1.2 代价与效益 4

1.2 抽象数据类型和数据结构 5

1.3 问题、算法和程序 8

1.4 深入学习导读 9

1.5 习题 10

第2章 数学预备知识 13

2.1 集合和关系 13

2.2 常用数学术语 15

2.3 对数 16

2.4 递归 17

2.5 级数求和与递归 19

2.6 数学证明方法 22

2.6.1 反证法 22

2.6.2 数学归纳法 22

2.7 评估 26

2.8 深入学习导读 26

2.9 习题 27

第3章 算法分析 31

3.1 概述 31

3.2 最佳、最差和平均情况 34

3.3 换一台更快的计算机，还是换一种更快的算法 35

3.4 渐近分析 37

3.4.1 上限 37

3.4.2 下限 38

3.4.3 Θ表示法 39

3.4.4 化简法则 40

3.5 程序运行时间的计算 40

3.6 问题的分析 44

3.7 容易混淆的概念 44

3.8 多参数问题 45

3.9 空间代价 46

3.10 实际操作中的一些因素 48

3.11 深入学习导读 49

3.12 习题 49

3.13 项目设计 52

第二部分 基本数据结构 54

第4章 线性表、栈和队列 54

4.1 线性表 54

4.1.1 顺序表的实现 57

4.1.2 链表 59

4.1.3 线性表实现方法的比较 66

4.1.4 元素的表示 67

4.1.5 双链表 68

4.2 字典ADT 72

4.3 栈 77

4.3.1 顺序栈 77

4.3.2 链式栈 78

4.3.3 顺序栈与链式栈的比较 79

4.3.4 递归的实现 80

4.4 队列 82

4.4.1 顺序队列 82

4.4.2 链式队列 85

4.4.3 顺序队列与链式队列的比较 86

4.5 深入学习导读 86

4.6 习题 86

4.7 项目设计 89

第5章 二叉树 90

5.1 定义及主要特性 90

5.1.1 满二叉树定理 91

5.1.2 二叉树的抽象数据类型 92

5.2 周游二叉树 93

5.3 二叉树的实现 95

5.3.1 使用指针实现二叉树 95

5.3.2 空间代价 99

5.3.3 使用数组实现完全二叉树 101

5.4 二叉查找树 102

5.5 堆与优先队列 108

5.6 Huffman编码树 112

5.6.1 建立Huffman编码树 113

5.6.2 Huffman编码及其用法 118

5.7 深入学习导读 120

5.8 习题 120

5.9 项目设计 122

第6章 树 124

6.1 树的定义与术语 124

6.1.1 树结点的ADT 124

6.1.2 树的周游 126

6.2 父指针表示法 126

6.3 树的实现 131

6.3.1 子结点表表示法 131

6.3.2 左子结点／右兄弟结点表示法 132

6.3.3 动态结点表示法 132

6.3.4 动态左子结点／右兄弟结点表示法 134

6.4 K叉树 134

6.5 树的顺序表示法 135

6.6 深入学习导读 137

6.7 习题 137

6.8 项目设计 139

第三部分 排序和检索 142

第7章 内排序 142

7.1 排序术语及记号 142

7.2 三种代价为Θ（n2）的排序方法 143

7.2.1 插入排序 143

7.2.2 起泡排序 144

7.2.3 选择排序 145

7.2.4 交换排序算法的时间代价 146

7.3 Shell排序 147

7.4 快速排序 149

7.5 归并排序 152

7.6 堆排序 155

7.7 分配排序和基数排序 156

7.8 对各种排序算法的实验比较 160

7.9 排序问题的下限 162

7.10 深入学习导读 164

7.11 习题 165

7.12 项目设计 167

第8章 文件管理和外排序 168

8.1 主存储器和辅助存储器 168

8.2 磁盘 170

8.2.1 磁盘结构 170

8.2.2 磁盘访问代价 173

8.3 缓冲区和缓冲池 175

8.4 程序员的文件视图 178

8.5 外部排序 179

8.6 外部排序的简单方法 181

8.7 置换选择排序 182

8.8 多路归并 185

8.9 深入学习导读 187

8.10 习题 187

8.11 项目设计 189

第9章 检索 190

9.1 检索已排序的数组 190

9.2 自组织线性表 191

9.3 集合的检索 195

9.4 散列方法 196

9.4.1 散列函数 196

9.4.2 开散列方法 199

9.4.3 闭散列方法 200

9.5 深入学习导阅读 208

9.6 习题 209

9.7 项目设计 211

第10章 索引技术 212

10.1 线性索引 213

10.2 ISAM 215

10.3 树形索引 216

10.4 2-3树 218

10.5 B树 222

10.5.1 B＋树 223

10.5.2 B树分析 228

10.6 深入学习导读 229

10.7 习题 229

10.8 项目设计 231

第四部分 应用与高级话题 234

第11章 图 234

11.1 术语和表示法 234

11.2 图的实现 237

11.3 图的周游 241

11.3.1 深度优先搜索 242

11.3.2 广度优先搜索 243

11.3.3 拓扑排序 244

11.4 最短路径问题 246

11.4.1 单源最短路径 246

11.4.2 每对顶点间的最短路径 249

11.5 最小支撑树 250

11.5.1 Prim算法 251

11.5.2 Kruskal算法 253

11.6 深入学习导读 254

11.7 习题 254

11.8 项目设计 256

第12章 线性表和数组高级技术 257

12.1 跳跃表 257

12.2 广义表 261

12.3 矩阵的表示方法 263

12.4 存储管理 265

12.4.1 动态存储分配 266

12.4.2 失败处理策略和无用单元收集 271

12.5 深入学习导读 274

12.6 习题 274

12.7 项目设计 275

第13章 高级树形结构 277

13.1 Trie结构 277

13.2 平衡树 280

13.2.1 AVL树 280

13.2.2 伸展树 282

13.3 空间数据结构 285

13.3.1 k-d树 286

13.3.2 PR四分树 289

13.3.3 其他空间数据结构 292

13.4 深入学习导读 293

13.5 习题 293

13.6 项目设计 293

第14章 分析技术 295

14.1 求和技术 295

14.2 递归关系 297

14.2.1 估计上下限 297

14.2.2 扩展递归 298

14.2.3 分治法递归 299

14.2.4 快速排序平均情况分析 300

14.3 均摊分析 301

14.4 深入学习导读 303

14.5 习题 303

14.6 项目设计 306

第15章 计算的限制 307

15.1 归约 307

15.2 难解问题 311

15.2.1 NP完全性 311

15.2.2 绕过NP完全性问题 315

15.3 不可解问题 316

15.3.1 不可数性 316

15.3.2 停机问题的不可解性 318

15.3.3 确定程序行为是不可解的 320

15.4 深入学习导读 320

15.5 习题 320

15.6 项目设计 321

附录A 实用函数 323

参考文献 324