数据结构PDF电子书下载

第一章 绪论 1

1.1 数据结构概念 1

1.2 面向对象程序设计OOP与抽象数据类型ADT 3

1.3 算法概念和算法描述语言 5

第二章 算法分析基础 9

2.1 引论 9

2.2 算法时间复杂性的分析方法 11

2.3 时间与空间分析 15

习题 16

第三章 面向对象程序设计与C++语言 18

3.1 类和对象 18

3.1.1 类声明 18

3.1.2 类实现 19

3.1.3 对象声明 20

3.2 C++语言的基本操作 21

3.2.1 输入输出的C++实现 21

3.2.2 友元函数(friend function) 23

3.2.3 参数传递 24

3.2.4 多态性 25

3.2.5 动态存储分配 28

3.3 模板 29

3.3.1 模板函数 29

3.3.2 模板类 31

3.4 继承 32

习题 34

第四章 线性表、堆栈、队列 35

4.1 线性表的定义和基本操作 35

4.2 线性表的存储结构 36

4.2.1 顺序存储结构 36

4.2.2 链接存储结构--单链表 36

4.2.3 循环链表 47

4.2.4 双向循环链表 49

4.3 堆栈和队列 53

4.3.1 定义和主要操作 53

4.3.2 顺序存储 56

4.3.3 链接存储 63

4.3.4 应用--算术表达式求值 65

习题 68

第五章 数组、字符串和集合类 71

5.1 数组 71

5.1.1 顺序存储的数组 71

5.1.2 静态数组与动态数组 73

5.1.3 稀疏矩阵 77

5.2 字符串 84

5.2.1 定义和主要操作 84

5.2.2 存储方式 85

5.2.3 模式匹配算法 86

5.3 整型集合 90

习题 94

第六章 树 98

6.1 基本概念 98

6.2 二叉树 99

6.2.1 主要性质和定义 99

6.2.2 二叉树的实现 102

6.2.3 二叉树的遍历 108

6.2.4 复制二叉树 110

6.3 线索二叉树 111

6.4 树和森林 119

6.4.1 树的顺序存储结构 119

6.4.2 树的链接存储结构 121

6.4.3 森林与二叉树的转换 125

6.4.4 树和森林的遍历 126

6.5 压缩与哈夫曼树 131

习题 135

第七章 图 137

7.1 概念和定义 137

7.2 图的存储结构与类Graph 139

7.2.1 存储结构 139

7.2.2 Graph类 141

7.3 遍历函数的实现 153

7.3.1 深度优先遍历 153

7.3.2 广度优先遍历 155

7.4 拓扑排序 156

7.5 关键路径 159

7.6 最短路径问题 163

7.6.1 无权最短路径问题 163

7.6.2 正权最短路径问题 165

7.6.3 负权最短路径问题 168

7.6.4 每对顶点之间的最短路径 171

7.7 最小支撑树 173

7.8 应用 178

7.8.1 可及性与Warshall算法 178

7.8.2 连通分量 180

习题 182

第八章 递归 186

8.1 什么是递归 186

8.2 基本递归过程 188

8.3 递归过程的实现：堆栈与递归 191

8.4 递归到非递归的转换 196

8.5 递归的应用 203

8.5.1 应用实例1：算术表达式求值 203

8.5.2 应用实例2：回溯 205

习题 210

第九章 排序 211

9.1 插入排序 212

9.2 交换排序 217

9.2.1 冒泡排序 217

9.2.2 分划交换排序 222

9.3 选择排序 231

9.3.1 直接选择排序 231

9.3.2 堆排序 232

9.4 合并排序 238

9.5 排序下界 242

9.6 分布排序 243

9.6.1 基数分布 244

9.6.2 值分布 247

9.7 外排序 249

9.7.1 外存储器 249

9.7.2 磁带排序 250

9.7.3 磁盘排序 260

习题 266

第十章 查找 269

10.1 线性表查找 269

10.1.1 顺序查找 270

10.1.2 有序表的查找 271

10.2 二叉查找(搜索)树 278

10.2.1 定义和基本操作 278

10.2.2 静态树 281

10.2.3 动态树 289

10.3 数字查找树 320

10.4 杂凑 322

10.4.1 杂凑表的定义和主要操作 322

10.4.2 杂凑函数 323

10.4.3 冲突调节 326

10.5 (a,b)-树、B树和B’树 334

习题 341

第十一章 内存管理 344

11.1 均匀大小记录的管理和废料收集方法 344

11.1.1 访问计数器法 345

11.1.2 废料收集 346

11.2 不同大小记录的查找分配和压缩分配 350

11.2.1 查找分配 351

11.2.2 压缩分配 357

11.3 伙伴系统 362

11.4 C++中的动态内存分配 368

习题 369

第十二章 复杂数据结构 371

12.1 优先级队列 371

12.1.1 类声明 371

12.1.2 优先级队列的应用：长归并段 372

12.2 不相交集合类 378

12.2.1 等价关系 378

12.2.2 动态等价 379

12.2.3 快速查找算法 383

12.2.4 快速合并算法 384

12.2.5 C++实现 390

12.2.6 最坏情况下的归并和路径压缩 391

第十三章 文件 393

13.1 文件结构概论 393

13.2 顺序文件 396

13.2.1 串行处理文件 396

13.2.2 顺序处理文件 399

13.2.3 增补文件 400

13.3 杂凑(散列)文件 402

13.3.1 杂凑文件的设计 402

13.3.2 可扩充的杂凑文件 405

13.4 索引文件 410

13.4.1 动态索引结构和静态索引结构 414

13.4.2 索引顺序文件 414

13.4.3 B’索引文件 418

13.5 倒排文件和多重链表文件 422

习题 430

第十四章 应用 432

14.1 事件驱动模拟(Event-Driven Simulation) 432

14.1.1 模拟设计 432

14.1.2 模拟建立 436

14.1.3 运行模拟 437

14.2 在线等价类 443

14.2.1 树形描述 443

14.2.2 操作 444

14.2.3 性能评价 445

14.2.4 性能改进 445

14.3 残缺棋盘 451

14.4 图像压缩 454

参考文献 461