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

第1章 绪论 1

1.1 数据结构简介 1

1.1.1 数据结构的发展历史 1

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

1.2 有关的预备知识 3

1.2.1 集合 3

1.2.2 递归 5

1.2.3 数学证明方法 6

习题 7

2.1.1 一个简单的算法 9

2.1 算法的基本概念 9

第2章 算法的基本概念与算法分析 9

2.1.2 什么是算法 10

2.1.3 算法与问题 11

2.1.4 算法与程序 12

2.2 算法的评估 12

2.2.1 算法的正确性 12

2.2.2 时间代价 13

2.2.3 空间代价 14

2.2.4 最优性 14

2.3.1 基本操作 15

2.3 算法的复杂度度量 15

2.3.3 复杂度函数及其渐进性质 16

2.3.2 问题实例长度 16

2.3.4 最坏情形和最优情形 17

2.3.5 平均情形和算法的期望复杂度 18

2.3.6 复杂度函数的表示 19

2.4 算法设计与分析的重要性 20

2.4.1 一个实例 21

2.4.2 计算机应用领域的变化 21

2.4.3 计算机技术的发展需要设计有效算法 22

2.5.1 MAXMIN问题的平凡算法 23

2.5 MAXMIN问题 23

2.5.2 第一次改进算法 24

2.5.3 第二次改进算法 25

2.5.4 采用分治策略的改进算法 26

2.5.5 算法MAXMIN的讨论 27

习题 31

第3章 线性表 34

3.1 线性表的定义和基本运算 34

3.2 线性表的实现 36

3.2.1 顺序存储结构 37

3.2.2 链式存储结构 40

3.2.3 两种基本实现方法的比较 45

3.2.4 循环链表 47

3.2.5 双向链表 47

3.3 线性表的应用 50

习题 53

第4章 栈、队列和数组 55

4.1 栈 55

4.1.2 链式栈 56

4.1.1 顺序栈 56

4.1.3 顺序栈与链式栈的比较 58

4.1.4 栈的应用 58

4.2 队列 62

4.2.1 队列的定义及基本运算 62

4.2.2 顺序队列 63

4.2.3 链式队列 65

4.2.4 队列的应用 67

4.3 数组 69

4.3.1 数组的抽象数据类型 69

4.3.2 数组的存储方式 70

4.3.3 特殊数组 72

4.3.4 数组的应用 76

习题 79

第5章 树形结构 80

5.1 树 80

5.1.1 树的基本概念 80

5.1.2 树的抽象数据类型 82

5.2 二叉树 83

5.2.1 二叉树的定义及其主要特性 83

5.2.2 二叉树的实现 86

5.2.3 二叉树的遍历 91

5.3.1 树的存储结构 93

5.3 树、森林与二叉树的关系 93

5.3.2 森林与二叉树的转换 95

5.3.3 树和森林的遍历 96

5.4 树形结构的应用 97

5.4.1 等价类问题 97

5.4.2 哈夫曼树和哈夫曼编码 101

习题 106

第6章 图 108

6.1 图的基本概念 108

6.1.1 图的基本概念 108

6.1.2 图的抽象数据类型 112

6.2 图的存储结构 113

6.2.1 邻接矩阵 113

6.2.2 邻接表 115

6.2.3 逆邻接表 116

6.2.4 邻接多重表 116

6.2.5 图的实现 117

6.3 图的遍历及求图的连通分量 122

6.3.1 深度优先搜索 123

6.3.2 广度优先搜索 126

6.3.3 无向图的连通分量 128

6.4 生成树和最小代价生成树 130

6.4.1 生成树 130

6.4.2 最小代价生成树 132

6.5 最短路径 140

6.5.1 从某个源点到其他各顶点的最短路径 140

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

6.6 有向无环图及其应用 150

6.6.1 有向无环图 150

6.6.2 拓扑排序 151

6.6.3 关键路径 157

习题 162

第7章 查找 165

7.1 查找的基本概念 165

7.2 顺序表的查找 166

7.2.1 顺序查找 168

7.2.2 折半查找 170

7.2.3 索引顺序表的查找 174

7.3 树表的查找 176

7.3.1 二叉排序树 176

7.3.2 平衡二叉树 185

7.3.3 B-树 197

7.4 哈希表及其查找 202

7.4.1 什么是哈希 203

7.4.2 哈希函数的构造方法 204

7.4.3 处理冲突的几种方法 207

7.4.4 哈希表的查找及其效率分析 209

习题 211

第8章 内部排序 213

8.1 排序的一般概念 213

8.2 插入排序 215

8.2.1 直接插入排序 216

8.2.2 折半插入排序 219

8.2.3 希尔排序 220

8.3 交换排序 224

8.3.1 起泡排序 224

8.3.2 快速排序 227

8.4 选择排序 233

8.4.1 简单选择排序 234

8.4.2 堆排序 235

8.5 归并排序 241

8.5.1 两个有序序列的归并操作 241

8.5.2 归并排序 243

8.6 分配排序和基数排序 245

8.7 有关内部排序算法的比较 250

习题 252

第9章 算法设计技术 254

9.1 求解问题的基本思路 254

9.2 分治技术 256

9.2.1 分治策略的思想 257

9.2.2 大整数乘法 258

9.2.3 矩阵相乘的Strassen算法 260

9.2.4 选择问题的分治算法 261

9.3.1 贪心算法的思想 265

9.3 贪心技术 265

9.3.2 活动安排问题 267

9.3.3 背包问题 269

9.3.4 多机调度问题的近似算法 271

9.3.5 单源最短路径问题的Dijkstra算法 273

9.4 回溯与分枝限界技术 277

9.4.1 两个适合回溯技术的问题 278

9.4.2 八后问题 280

9.4.3 0-1背包问题的回溯算法 284

9.4.4 分枝限界算法 289

9.5 动态规划技术 292

9.5.1 Fibonacci数的计算 293

9.5.2 矩阵连乘的顺序问题 294

9.5.3 适合动态规划算法的两个条件 297

综合练习题一 299

综合练习题二 301

综合练习题三 303

综合练习题四 305

综合练习题五 307

综合模拟题一 309

综合模拟题二 313

参考文献 316