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

数据结构与算法分析 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 字典ADT72

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 树结点的ADT124

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 ISAM215

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