数据结构PDF电子书下载

第1章 绪论 1

1.1 数据结构的由来与发展 1

1.1.1 什么是数据结构 1

1.1.2 数据结构的发展简史 5

1.2 数据结构的有关概念与术语 6

1.3 抽象数据类型 9

1.4 算法和算法分析 13

1.4.1 算法的概念与性质 13

1.4.2 算法设计的分类 14

1.4.3 算法的设计要求 14

1.4.4 算法分析 15

本章小结 19

习题 19

第2章 线性表 20

2.1 线性表的类型定义 20

2.1.1 线性表的概念 20

2.1.2 线性表的抽象数据类型 21

2.2 线性表的顺序表示和实现 24

2.2.1 顺序表 24

2.2.2 顺序表上基本操作的实现 25

2.2.3 顺序表应用举例 28

2.3 线性表的链式表示和实现 29

2.3.1 线性链表的概念 30

2.3.2 单链表上基本操作的实现 32

2.3.3 线性链表的应用举例 38

2.3.4 循环链表 40

2.3.5 双向链表 41

2.4 静态链表 43

2.5 一元多项式的表示和运算 46

本章小结 48

习题 48

第3章 栈和队列 51

3.1 栈的概念及操作 51

3.1.1 栈的定义 51

3.1.2 栈的抽象类型定义 52

3.2 栈的存储和操作实现 52

3.2.1 顺序栈 53

3.2.2 链式栈 56

3.3 栈的应用举例 57

3.3.1 数制转换问题 57

3.3.2 表达式中括号匹配的检验 58

3.3.3 表达式求值 59

3.3.4 栈与递归 62

3.3.5 迷宫问题 66

3.4 队列的概念及操作 68

3.4.1 队列的定义 68

3.4.2 队列的抽象类型定义 69

3.4.3 其他操作受限的线性表 70

3.5 队列的存储和操作实现 70

3.5.1 顺序队列 70

3.5.2 链队列 74

本章小结 76

习题 76

第4章 数组、串和广义表 79

4.1 数组的概念与实现 79

4.1.1 数组及其抽象数据类型定义 79

4.1.2 数组的顺序实现 80

4.2 矩阵的压缩存储 86

4.2.1 特殊矩阵 86

4.2.2 稀疏矩阵 88

4.3 串 101

4.3.1 串的概念及抽象数据类型定义 101

4.3.2 串的表示与实现 104

4.3.3 串的模式匹配算法 108

4.4 广义表 111

4.4.1 广义表的基本概念 111

4.4.2 广义表的实现 113

本章小结 118

习题 118

第5章 树 121

5.1 树的概念及有关术语 121

5.2 二叉树 125

5.2.1 二叉树的定义与性质 126

5.2.2 二叉树的存储与实现 129

5.2.3 二叉树的遍历 132

5.3 线索二叉树 138

5.4 树和森林 142

5.4.1 树的存储结构 142

5.4.2 树、森林与二叉树的转换 144

5.4.3 树和森林的遍历 145

5.5 Huffman树和Huffman编码 146

5.5.1 Huffman树 146

5.5.2 Huffman编码 150

5.6 等价类问题 152

本章小结 155

习题 155

第6章 图 159

6.1 图的概念及有关术语 159

6.2 图的表示和存储实现方法 162

6.2.1 邻接矩阵存储结构 162

6.2.2 邻接表存储结构 164

6.2.3 十字链表存储结构 168

6.2.4 邻接多重表存储结构 169

6.3 图的遍历 171

6.3.1 深度优先遍历 171

6.3.2 广度优先遍历 172

6.4 最小生成树 174

6.4.1 Prim算法 175

6.4.2 Kruskal算法 177

6.5 最短路径 179

6.5.1 无权图的最短路径 180

6.5.2 Dijkstra算法 181

6.5.3 Floyd算法 184

6.6 拓扑排序 186

6.7 关键路径 188

本章小结 190

习题 191

第7章 查找 195

7.1 查找的基本概念 195

7.2 静态查找表 197

7.2.1 顺序表的查找 197

7.2.2 有序表的查找 199

7.2.3 分块查找 203

7.3 动态查找表 205

7.3.1 二叉排序树 205

7.3.2 平衡二叉树 211

7.3.3 红黑树 218

7.3.4 B-树 221

7.3.5 B＋树 225

7.4 哈希表上的查找 226

7.4.1 哈希表的概念 226

7.4.2 哈希函数构造方法 228

7.4.3 处理冲突方法 230

7.4.4 哈希表的查找及其分析 232

7.4.5 哈希表的有关算法 234

本章小结 236

习题 237

第8章 排序 240

8.1 概述 240

8.2 插入排序 242

8.2.1 直接插入排序 243

8.2.2 折半插入排序 244

8.2.3 二路插入排序 245

8.2.4 表插入排序 247

8.2.5 希尔排序 250

8.3 交换排序 252

8.3.1 冒泡排序 252

8.3.2 快速排序 253

8.4 选择排序 256

8.4.1 简单选择排序 256

8.4.2 树形选择排序 257

8.4.3 堆排序 258

8.5 归并排序 261

8.6 基数排序 262

8.7 内部排序方法比较 266

8.8 外部排序概述 267

本章小结 268

习题 268

第9章 算法设计方法 271

9.1 贪心算法 271

9.1.1 活动安排问题 272

9.1.2 多机调度问题 274

9.1.3 背包问题 274

9.2 分治算法 275

9.3 动态规划 278

9.4 回溯算法 282

9.4.1 0-1背包问题（回溯算法） 283

9.4.2 旅行商问题 285

9.5 分支定界算法 286

9.6 随机化算法 289

本章小结 290

习题 291

附录A 部分习题参考答案或提示 293

主要参考文献 301