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

第1章 绪论 1

1.1 数据结构的发展及其重要地位 1

1.2 数据结构的基本概念和术语 2

1.3 算法分析概述 5

1.3.1 算法分析评价标准 5

1.3.2 算法的复杂度分析 6

1.3.3 时间复杂度的度量 8

1.3.4 渐进时间复杂度 8

1.3.5 时间复杂度的上界和下界 9

1.3.6 算法的空间复杂度 12

1.3.7 非递归算法分析 13

1.3.8 递归算法的数学分析 15

习题1 16

上篇　数据结构 18

第2章　线性表 18

2.1 线性表的定义及操作 18

2.1.1 线性表的定义 18

2.1.2 线性表的基本操作 19

2.1.3 线性表操作举例 20

2.2 线性表的顺序存储及操作实现 22

2.2.1 线性表的顺序存储结构 22

2.2.2 顺序表的操作实现 23

2.3 线性表的链式存储结构及操作实现 26

2.3.1 单链表 26

2.3.2 单链表上的基本操作 28

2.3.3　循环链表 30

2.3.4 双向链表 31

2.4 顺序表和链表的比较 33

习题2 34

第3章　栈和队列 35

3.1 栈 35

3.1.1 栈的概念及操作 35

3.1.2 栈的存储结构及操作实现 35

3.2 栈的应用举例 40

3.3 队列 45

3.3.1 队列的定义和操作 45

3.3.2 队列的存储结构及操作实现 45

3.4 队列的应用举例 51

习题3 53

第4章 串和数组 55

4.1 串的概念和基本操作 55

4.1.1 串的基本概念 55

4.1.2 串的基本操作 55

4.2 串的存储结构 56

4.2.1 串的顺序存储结构 56

4.2.2 串的链式存储结构 58

4.3 串的操作实现 59

4.4 数组 61

4.4.1 数组的定义 61

4.4.2 数组的顺序存储结构 62

4.5 矩阵的压缩存储 63

4.5.1 特殊矩阵的压缩存储 63

4.5.2 稀疏矩阵的压缩存储 65

习题4 71

第5章　二叉树和树 73

5.1 树和森林 73

5.2 二叉树 74

5.2.1 二叉树的定义和基本术语 74

5.2.2 二叉树的基本性质 76

5.2.3 二叉树的存储结构 77

5.3 二叉树与树、森林之间的转换 79

5.3.1 二叉树与树之间的转换 79

5.3.2 二叉树与森林之间的转换 80

5.4 二叉树遍历 81

5.4.1 二叉树的遍历 81

5.4.2 二叉链表的建立 88

5.5 线索二叉树 90

5.5.1　全线索二叉树 90

5.5.2 线索二叉树 92

5.6 树的应用 96

5.6.1 哈夫曼树及其应用 96

5.6.2 二叉排序树 101

习题5 107

第6章　图和广义表 109

6.1 图的定义和基本术语 109

6.2 图的存储结构 110

6.2.1　邻接矩阵 111

6.2.2 邻接表 112

6.3 图的遍历 115

6.3.1 深度优先搜索遍历 115

6.3.2 图的广度优先搜索遍历 117

6.4 生成树 119

6.4.1 生成树 119

6.4.2 最小生成树 119

6.5 最短路径 124

6.5.1 单源最短路径 124

6.5.2 每一对顶点间的最短路径 128

6.6 拓扑排序 130

6.6.1 AOV网 130

6.6.2 拓扑排序 131

6.7 关键路径 135

6.8　广义表 139

6.8 　广义表的定义 139

6.8.2　广义表的存储 139

习题6 140

第7章 排序 142

7.1 排序的基本概念 142

7.2 简单的排序方法 143

7.2.1 气泡排序 143

7.2.2 简单选择排序 144

7.2.3 插入排序 146

7.3 先进的排序方法 148

7.3.1 快速排序 148

7.3.2 归并排序 150

7.3.3 堆排序 152

7.4 基数排序 154

7.5 各种内部排序方法的综合比较 158

习题7 159

第8章 查找 161

8.1 静态查找表 161

8.1.1 顺序查找 161

8.1.2 折半查找 162

8.1.3 分块查找 163

8.2 动态查找表 165

8.2.1 二叉平衡树 165

8.2.2 B_树 167

8.3 哈希表及哈希查找 169

8.3.1 哈希表概念 169

8.3.2 哈希函数 170

8.3.3 处理冲突的方法 172

8.3.4 哈希表的查找 174

8.3.5 哈希表的删除 174

习题8 175

第9章 文件 176

9.1 文件的基本概念 176

9.2 顺序文件 178

9.3 索引文件 179

9.4 索引顺序文件 181

9.4.1 ISAM文件 181

9.4.2 VSAM文件 183

9.5 散列文件 185

9.6 多关键字文件 186

9.6.1 多重表文件 186

9.6.2 倒排文件 187

习题9 188

下篇　算法分析 190

第10章　蛮力法 190

10.1 算法概述 190

10.2 货郎担问题 191

10.2.1 问题陈述 191

10.2.2 问题分析及算法设计分析 191

10.2.3 实例分析 192

10.3 0/1背包问题 193

10.3.1 问题陈述 193

10.3.2 问题分析及算法设计分析 193

10.4 狱吏问题 194

10.4.1 问题陈述 194

10.4.2 问题分析和算法设计分析 195

习题10 195

第11章　贪心法 196

11.1 算法概述 196

11.1.1 贪心选择性质 196

11.1.2 最优子结构性质 197

11.1.3 贪心算法的设计步骤 197

11.2 活动安排问题 198

11.2.1 问题陈述 198

11.2.2 问题分析及算法设计分析 198

11.2.3 实例分析 199

11.2.4 最优性分析 200

11.3 背包问题 200

11.3.1 问题陈述 200

11.3.2 问题分析及算法设计分析 201

11.3.3 实例分析 201

11.3.4 最优性分析 202

11.4 集装箱装载问题 203

11.4.1 问题陈述 203

11.4.2 问题分析及算法设计分析 203

11.4.3 最优性分析 204

习题11 204

第12章　分治法 206

12.1 算法概述 206

12.1.1 分治法的设计步骤 206

12.1.2 分治法的算法分析 207

12.2 大整数乘法 208

12.2.1 问题陈述 208

12.2.2 问题分析及算法设计分析 208

12.3 棋盘问题 211

12.3.1 问题陈述 211

12.3.2 问题分析及算法设计分析 212

12.4 循环赛日程表 214

12.4.1 问题陈述 214

12.4.2 问题分析及算法设计分析 214

习题12 216

第13章　动态规划法 218

13.1 算法概述 218

13.1.1 动态规划法的设计步骤 218

13.1.2 动态规划法与贪心法的比较分析 220

13.2 矩阵连乘问题 221

13.2.1 问题陈述 221

13.2.2 问题分析及算法设计分析 221

13.2.3 实例分析 223

13.3 最长公共子序列问题 224

13.3.1 问题陈述 224

13.3.2 问题分析及算法设计分析 225

13.3.3 实例分析 227

13.4 流水作业调度问题 228

13.4.1 问题陈述 228

13.4.2 问题分析及算法设计分析 228

13.4.3 实例分析 231

习题13 231

第14章　回溯法 234

14.1 算法概述 234

14.1.1 问题的解空间 234

14.1.2 回溯法的设计步骤 235

14.2 n后问题 237

14.2.1 问题陈述 237

14.2.2 问题分析及算法设计分析 237

14.3 图的m—着色问题 239

14.3.1 问题陈述 239

14.3.2 问题分析及算法设计分析 240

习题14 242

第15章　计算复杂性理论 244

15.1 计算复杂性概述 244

15.1.1 易解问题和难解问题 244

15.1.2 不可解问题与停机问题 245

15.2 P类与NP类问题 245

15.2.1 确定性算法和非确定性算法 245

15.2.2 P类问题和NP类问题 246

15.3 NP完全问题 247

15.3.1 多项式归约 247

15.3.2 NP完全性 248

15.3.3 Cook定理 249

15.3.4 NP完全性证明 249

习题15 250

第16章　分布式算法 251

16.1 分布式系统 251

16.1.1 分布式系统概述 251

16.1.2 分布式计算 252

16.1.3 分布式系统特点 252

16.1.4 分布式系统的体系结构 253

16.2 同步技术 255

16.2.1 同步机构 255

16.2.2 物理时钟 255

16.2.3 逻辑时钟 256

16.3 容错技术 258

16.3.1 容错性概述 258

16.3.2 故障检测和诊断 258

16.3.3 故障屏蔽 259

16.3.4 故障恢复 259

16.4 分布式调度 260

16.4.1 调度算法概述 260

16.4.2 静态调度 261

16.4.3 动态调度 262

习题16 263

参考文献 265