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

第1章 引论 1

1.1算法及其复杂性的概念 1

算法与程序 1

算法复杂性的概念 2

算法复杂性的渐近性态 3

1.2算法的表达与数据表示 5

问题求解 5

表达算法的抽象机制 5

1.3抽象数据类型 8

抽象数据类型的基本概念 8

使用抽象数据类型的好处 10

1.4数据结构、数据类型和抽象数据类型 10

1.5用C语言描述数据结构与算法 11

变量和指针 11

函数与参数传递 12

结构 13

动态存储分配 14

本章小结 16

习题 16

第2章 表 18

2.1 ADT表 18

2.2用数组实现表 19

2.3用指针实现表 24

2.4用间接寻址方法实现表 28

2.5用游标实现表 31

2.6循环链表 37

2.7双链表 40

2.8表的搜索游标 44

用数组实现表的搜索游标 45

单循环链表的搜索游标 46

2.9应用 48

本章小结 49

习题 49

第3章 栈 52

3.1 ADT栈 52

3.2用数组实现栈 53

3.3用指针实现栈 56

3.4应用 58

本章小结 61

习题 61

第4章 队列 63

4.1 ADT队列 63

4.2用指针实现队列 64

4.3用循环数组实现队列 67

4.4应用 71

本章小结 75

习题 75

第5章 递归 77

5.1递归的概念 77

5.2递归程序设计 83

分治与递归 83

动态规划 84

回溯与递归 91

5.3模拟递归 93

5.4应用 96

本章小结 99

习题 99

第6章 排序与选择 101

6.1简单排序算法 101

冒泡排序 102

插入排序 103

选择排序 103

简单排序算法的计算复杂性 104

6.2快速排序算法 105

算法基本思想及实现 105

算法的性能 106

随机快速排序算法 107

非递归快速排序算法 107

三数取中划分算法 109

三划分快速排序算法 110

6.3合并排序算法 111

算法基本思想及实现 111

对基本算法的改进 112

自底向上的合并排序算法 113

自然合并排序 113

链表结构的合并排序算法 114

6.4线性时间排序算法 115

计数排序 116

桶排序 117

6.5中位数与第k小元素 118

平均情况下的线性时间选择算法 118

最坏情况下的线性时间选择算法 119

6.6应用 121

本章小结 123

习题 123

第7章 树 125

7.1树的定义 125

7.2树的遍历 127

7.3树的表示法 129

父结点数组表示法 129

儿子链表表示法 130

左儿子右兄弟表示法 130

7.4二叉树 131

7.5 ADT二叉树 133

7.6二叉树的实现 133

二叉树的顺序存储结构 133

二叉树的结点度表示法 135

用指针实现二叉树 135

7.7线索二叉树 140

7.8应用 142

本章小结 146

习题 146

第8章 集合 148

8.1以集合为基础的抽象数据类型 148

集合的定义和记号 148

定义在集合上的基本运算 149

8.2用位向量实现集合 150

8.3用链表实现集合 153

8.4应用 157

本章小结 158

习题 158

第9章 符号表 160

9.1实现符号表的简单方法 160

9.2用散列表实现符号表 162

开散列 162

闭散列 164

散列函数及其效率 169

闭散列的重新散列技术 170

9.3应用 170

本章小结 172

习题 172

第10章 字典 174

10.1字典的定义 174

10.2用数组实现字典 175

10.3用二叉搜索树实现字典 175

10.4 AVL树 183

AVL树的定义和性质 184

旋转变换 185

AVL树的插入运算 188

AVL树的删除运算 191

10.5应用 194

本章小结 196

习题 196

第11章 优先队列 198

11.1优先队列的定义 198

11.2用字典实现优先队列 199

11.3优先级树和堆 199

11.4用数组实现堆 201

11.5可并优先队列 204

左偏树的定义 204

用左偏树实现可并优先队列 205

11.6应用 209

本章小结 213

习题 213

第12章 并查集 215

12.1并查集的定义及其简单实现 215

12.2用父亲数组实现并查集 217

12.3应用 220

本章小结 222

习题 222

第13章图 224

13.1图的基本概念 224

13.2抽象数据类型ADT图 227

13.3图的表示法 228

邻接矩阵表示法 228

邻接表表示法 229

紧缩邻接表 229

13.4用邻接矩阵实现图 230

用邻接矩阵实现赋权有向图 230

用邻接矩阵实现赋权无向图 233

用邻接矩阵实现有向图 233

用邻接矩阵实现无向图 234

13.5用邻接表实现图 235

用邻接表实现有向图 235

用邻接表实现无向图 238

用邻接表实现赋权有向图 239

用邻接表实现赋权无向图 243

13.6图的遍历 244

广度优先搜索 244

深度优先搜索 246

13.7最短路径 248

单源最短路径 248

所有顶点对之间的最短路径 251

13.8最小支撑树 253

最小支撑树性质 253

Prim算法 253

Kruskal算法 256

13.9图匹配 258

本章小结 260

习题 260

参考文献 263