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

第一部分 预备知识 1

第1章 数据结构和算法 1

1.1数据结构的原则 1

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

1.1.2代价与效益 2

1.1.3本书的目的 3

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

1.3问题、算法和程序 5

1.4算法的效率 7

1.5深入学习导读 7

1.6习题 8

第2章 数学预备知识 11

2.1集合 11

2.2常用数学术语 12

2.3对数 13

2.4递归 14

2.5级数求和与递归 16

2.6数学证明方法 18

2.6.1反证法 18

2.6.2数学归纳法 18

2.7评估 21

2.8深入学习导读 22

2.9习题 22

第3章 算法分析 25

3.1概述 25

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

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

3.4渐近分析 31

3.4.1上限 31

3.4.2下限 32

3.4.3？表示法 33

3.4.4简化法则 34

3.5程序运行时间的计算 34

3.6问题的分析 38

3.7多参数问题 38

3.8空间代价 39

3.9实际操作中的一些因素 41

3.10深入学习导读 43

3.11习题 43

3.12项目设计 45

第二部分 基本数据结构 47

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

4.1线性表 47

4.1.1顺序表的表示法 49

4.1.2链表 52

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

4.1.4元素的表示 61

4.1.5双链表 62

4.1.6循环链表 65

4.2栈 66

4.2.1顺序栈 66

4.2.2链式栈 67

4.2.3顺序栈与链式栈的比较 68

4.2.4递归的实现 69

4.3队列 69

4.3.1顺序队列 70

4.3.2链式队列 73

4.2.3顺序队列与链式队列的比较 74

4.4习题 74

4.5项目设计 76

第5章 二叉树 77

5.1定义及主要特性 77

5.1.1满二叉树定理 79

5.1.2二叉树结点的抽象数据类型 80

5.2周游二叉树 81

5.3二叉树的实现 81

5.3.1使用指针实现二叉树 81

5.3.2空间开销 85

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

5.4Huffman编码树 87

5.4.1建立Huffman编码树 88

5.4.2Huffman编码及其用法 92

5.5二叉检索树 94

5.6堆与优先队列 100

5.7深入学习导读 106

5.8习题 106

5.9项目设计 108

第6章 树 110

6.1树的定义与术语 110

6.1.1树结点的抽象数据类型 110

6.1.2树的周游 110

6.2父指针表示法 112

6.3树的实现 117

6.3.1子结点表表示法 117

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

6.3.3动态结点表示法 118

6.3.4动态“左子结点／右兄弟结点”表示法 120

6.4K叉树 120

6.5树的顺序表示法 121

6.6深入学习导读 123

6.7习题 123

6.8项目设计 125

第7章 图 126

7.1术语和表示法 126

7.2图的实现 129

7.3图的周游 133

7.3.1深度优先搜索 134

7.3.2广度优先搜索 135

7.3.3拓扑排序 136

7.4最短路径问题 139

7.4.1单源最短路径 139

7.4.2每对顶点间的最短路径 142

7.5最小支撑树 144

7.5.1Prim算法 144

7.5.2Kruskal 算法 147

7.6深入学习导读 149

7.7习题 149

7.8项目设计 150

第三部分 排序和检索 151

第8章 内排序 151

8.1排序的术语及记号 151

8.2三种代价为？（n2）的排序算法 152

8.2.1插入排序 152

8.2.2起泡排序 154

8.2.3选择排序 155

8.2.4交换排序算法的时间代价 156

8.3Shell排序 157

8.4快速排序 158

8.5归并排序 164

8.6堆排序 166

8.7分配排序和基数排序 167

8.8对各种排序算法的实验比较 173

8.9排序算法的下限 174

8.10深入学习导读 177

8.11习题 177

8.12项目设计 180

第9章 文件管理和外排序 181

9.1主存储器和辅助存储器 181

9.2磁盘和磁带 183

9.2.1磁盘访问开销 186

9.2.2磁带 188

9.3缓冲区和缓冲池 188

9.4程序员的文件视图 190

9.5外排序 191

9.6外排序的简单方法 193

9.7置换选择排序 195

9.8多路归并 198

9.9深入学习导读 200

9.10习题 200

9.11项目设计 202

第10章 检索 204

10.1检索已排序的数组 205

10.2自组织线性表 205

10.3集合的检索 209

10.4散列方法 209

10.4.1散列函数 210

10.4.2开散列方法 212

10.4.3闭散列方法 214

10.5深入学习导读 222

10.6习题 222

10.7项目设计 224

第11章 索引技术 225

11.1线性索引 226

11.2ISAM 229

11.3树形索引 230

11.4 2-3树 231

11.5B树 237

11.5.1B＋树 238

11.5.2B树分析 244

11.6深入学习导读 244

11.7习题 244

11.8项目设计 246

第四部分 应用与高级技术 247

第12章 线性表和数组的深入研究 247

12.1跳跃表 247

12.2广义表 251

12.3矩阵的表示方法 253

12.4存储管理 256

12.4.1动态存储分配 257

12.4.2失败策略和无用单元收集 263

12.5深入学习导读 266

12.6习题 267

12.7项目设计 268

第13章 高级树结构 269

13.1Trie结构 269

13.2伸展树 272

13.3空间数据结构 275

13.3.1k-d树 277

13.3.2PR四分树 280

13.3.3其他空间数据结构 282

13.4深入学习导读 283

13.5习题 284

13.6项目设计 284

第14章 算法分析技术 286

14.1求和技术 286

14.2递归关系 288

14.2.1估计上下限 288

14.2.2扩展递归 289

14.2.3分治法递归 290

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

14.3缓冲分析 292

14.4深入学习导读 294

14.5习题 294

14.6项目设计 296

第15章 计算的限制 298

15.1概述 298

15.2归约 298

15.3难解问题 301

15.3.1NP完全性 302

15.3.2绕过NP完全性问题 304

15.4不可解问题 305

15.4.1不可数性 306

15.4.2停机问题的不可解性 308

15.4.3确定程序行为是不可解的 310

15.5深入学习导读 310

15.6习题 311

15.7项目设计 312

附录A C和Pascal程序员的C＋＋导引 313

A.1例1：线性表的ADT 314

A.2例2：顺序表的实现 317

A.3例3：链表的实现 320

A.4例4：可利用空间表 323

A.5例5：转化为模板 325

A.6例6：虚函数 328

附录B 参考书目 331