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

第1章 概述 1

1.1数据结构的发展 1

1.2数据结构 2

1.2.1数据结构简介 2

1.2.2基本概念 4

1.3数据的逻辑结构 4

1.3.1预备知识 5

1.3.2数据结构的分类 6

1.4抽象数据类型 7

1.5数据的存储结构 9

1.5.1顺序存储结构 9

1.5.2链式存储结构 10

1.6算法与算法分析 10

1.6.1算法 11

1.6.2算法性能分析和度量 11

1.6.3算法的描述 16

1.7ADT的表示与实现间的关系 19

习题1 19

第2章 基本数据结构 21

2.1线性表 21

2.1.1ADT线性表 21

2.1.2线性表的顺序存储 23

2.1.3线性表的链式存储 27

2.2数组 34

2.2.1数组的定义 35

2.2.2数组的存储 35

2.2.3特殊矩阵 37

2.2.4稀疏矩阵 39

2.3字符串 44

2.3.1串的表示与实现 44

2.3.2串的模式匹配算法 49

习题2 55

第3章 栈、队列与广义表 57

3.1栈 57

3.1.1ADT栈 57

3.1.2栈的实现 58

3.1.3栈与递归 61

3.2队列 65

3.2.1ADT队列 65

3.2.2队列的实现 66

3.3栈与队列的应用 71

3.3.1栈的应用 71

3.3.2队列的应用 78

3.4广义表 79

3.4.1广义表的定义和基本运算 79

3.4.2广义表的存储结构 82

3.4.3广义表基本操作的实现 85

习题3 87

第4章 树与二叉树 90

4.1树的定义和相关术语 90

4.2二叉树 92

4.2.1ADT二叉树 92

4.2.2二叉树的遍历 93

4.2.3二叉树的性质 95

4.2.4二叉树的实现 96

4.2.5二叉树遍历的非递归实现 106

4.2.6线索二叉树 109

4.3树与森林 113

4.3.1树与森林的遍历 114

4.3.2树的存储结构 114

4.4森林与二叉树的关系 116

4.5Huffman树与编码 117

4.5.1Huffman树 118

4.5.2Huffman编码 119

习题4 125

第5章 集合与查找 127

5.1集合及其实现 127

5.1.1ADT集合 127

5.1.2用位向量实现集合 128

5.2具有Merge、Find的ADT集合 131

5.2.1ADTMFSet集合 131

5.2.2MFSet的实现 131

5.2.3MFSet实现算法的改进 133

5.2.4MFSet的应用——求等价类 135

5.3静态查找 136

5.3.1查找 136

5.3.2顺序查找 138

5.3.3二分查找 140

5.3.4静态次优查找树 143

5.3.5索引顺序查找 146

5.4哈希表 147

5.4.1哈希函数的构造 148

5.4.2闭哈希法 151

5.4.3开哈希法 156

5.5二叉查找树 158

5.5.1ADT二叉查找树 158

5.5.2二叉查找树的实现 159

5.5.3二叉查找树的应用 164

5.6平衡二叉查找树（或称AVL树） 165

5.6.1AVL树及其性质 166

5.6.2最小局部的不平衡类型及平衡方法 167

5.6.3AVL树的实现 172

5.7B—树与B+树 176

5.7.1B—树 177

5.7.2B+树 183

5.8键树 185

5.8.1双链树 186

5.8.2Trie树 187

习题5 188

第6章 图 191

6.1图的基本概念 191

6.1.1图的定义 191

6.1.2图的术语 192

6.2图的存储结构 195

6.2.1数组（邻接矩阵、相邻矩阵）表示法 196

6.2.2邻接表表示法 197

6.2.3邻接多重表表示法 200

6.2.4十字链表 201

6.3图的遍历 202

6.3.1深度优先遍历 203

6.3.2广度优先遍历 204

6.4无向图的应用 206

6.4.1最小（代价）生成树 206

6.4.2关节点和双连通图 210

6.5有向图的应用 213

6.5.1拓扑排序 213

6.5.2关键路径 216

6.6最短路径 220

6.6.1从一个顶点（源点）到其他顶点的最短路径 221

6.6.2每一对顶点间的最短路径（all-pairs shortest-paths） 223

6.6.3传递闭包 225

习题6 227

第7章 排序 229

7.1内部排序方式 229

7.2插入排序 231

7.2.1直接插入排序 231

7.2.2折半插入排序 232

7.2.3希尔排序 233

7.3选择排序 234

7.3.1直接选择排序 235

7.3.2树形选择排序 236

7.3.3堆排序 236

7.4交换排序 239

7.4.1冒泡排序 239

7.4.2快速排序 241

7.5归并排序 244

7.6基数排序 245

7.6.1多排序码排序 246

7.6.2链式基数排序 246

7.7各种内部排序算法的比较 249

7.7.1各种排序方法的比较 249

7.7.2排序问题的下界 250

习题7 251

第8章 外部排序 253

8.1外部排序的方法 253

8.1.1外部排序的基本过程 253

8.1.2多路平衡归并 255

8.1.3置换-选择排序 257

8.2最佳归并树 261

习题8 263

第9章 动态存储管理 264

9.1概述 264

9.2可利用空间表 266

9.2.1可利用空间表结构 266

9.2.2分配 267

9.2.3回收 268

9.3伙伴系统 268

9.3.1指数伙伴系统的可利用空间表结构 269

9.3.2分配 271

9.3.3回收 272

9.4一个小型的动态存储管理系统 273

9.4.1系统内存结构 273

9.4.2内存分配 275

9.4.3内存释放与垃圾回收 275

习题9 276

第10章 算法分析与设计技术 277

10.1递归算法的分析 277

10.2递归式求解 278

10.2.1展开递归式 278

10.2.2猜解 278

10.2.3大递归式的一般解 279

10.3分而治之与递归 281

10.4动态规划法 283

10.4.1动态规划法的基本思想 283

10.4.2最优二叉查找树 286

10.5贪心法 289

10.6搜索法 291

10.6.1搜索法的基本思想 291

10.6.2启发式搜索 293

10.7NP完全性问题 295

10.7.1问题的描述形式 296

10.7.2P类问题与NP类问题 297

10.7.3NP-Complete类问题 299

10.7.4近似算法 300

习题10 302

参考文献 303