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

第1章 绪论 1

1.1 数据结构的概念 2

1.1.1 引言 2

1.1.2 数据结构的有关概念与术语 5

1.2 抽象数据类型 7

1.3 算法描述与分析 11

1.3.1 什么是算法 11

1.3.2 算法分析技术初步 13

1.4 基本的算法策略 17

1.4.1 穷举法 17

1.4.2 递推法与迭代法 18

1.4.3 分治法 20

1.4.4 贪心算法 22

1.4.5 动态规划 22

1.5 案例分析 25

1.6 小结 26

讨论小课堂1 27

习题1 28

第2章 线性表 30

2.1 线性表的定义及其运算 30

2.1.1 线性表的定义 30

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

2.2 线性表的顺序存储结构及实现 32

2.2.1 顺序存储结构 32

2.2.2 线性表在向量中基本运算的实现 34

2.3 线性表的链表存储结构 39

2.3.1 单链表 39

2.3.2 线性链表基本运算的实现 42

2.4 循环链表和双向链表 49

2.4.1 循环链表 49

2.4.2 双向链表 50

2.4.3 顺序存储结构与链表存储结构的综合分析与比较 51

2.5 单链表的应用 52

2.5.1 多项式相加的链表存储结点 52

2.5.2 多项式相加的算法实现 53

2.6 小结 54

讨论小课堂2 55

习题2 55

第3章 栈和队列 57

3.1 栈 57

3.1.1 栈的定义 57

3.1.2 栈的抽象数据类型 58

3.2 栈的顺序存储结构及实现 59

3.2.1 栈的顺序存储结构 59

3.2.2 顺序栈的定义 60

3.3 栈的链表存储结构及实现 62

3.4 栈的应用 65

3.4.1 表达式的计算 65

3.4.2 子程序的嵌套调用 67

3.4.3 递归调用 68

3.5 队列 69

3.5.1 队列的定义及运算 69

3.5.2 队列的抽象数据类型 70

3.6 队列的顺序存储结构及实现 70

3.7 队列的链表存储结构及实现 74

3.8 队列的应用 77

3.9 算法实例——Hanoi塔问题 78

3.10 小结 79

讨论小课堂3 80

习题3 81

第4章 串 83

4.1 串的基本概念 83

4.1.1 串的定义 83

4.1.2 串的抽象数据类型 84

4.2 串的存储与基本操作的实现 85

4.2.1 定长顺序串 86

4.2.2 堆串 86

4.2.3 块链串 87

4.2.4 串操作的实现 88

4.3 串的模式匹配 91

4.3.1 朴素模式匹配算法 92

4.3.2 模式匹配的KMP算法 92

4.4 串的应用举例：文本编辑 97

4.5 小结 99

讨论小课堂4 99

习题4 100

第5章 数组和广义表 101

5.1 数组 102

5.1.1 数组的基本概念 102

5.1.2 二维数组 102

5.1.3 数组的顺序存储方式 103

5.2 矩阵的压缩存储 104

5.2.1 特殊矩阵 104

5.2.2 稀疏矩阵 107

5.3 广义表 112

5.3.1 广义表的定义 112

5.3.2 广义表的存储结构 113

5.4 案例分析 116

5.4.1 概述和方法 116

5.4.2 算法和程序 118

5.5 小结 120

讨论小课堂5 120

习题5 120

第6章 树与二叉树 122

6.1 树的概念及术语 123

6.1.1 树的定义 123

6.1.2 树的抽象数据类型 124

6.1.3 树的表示方式 125

6.2 二叉树 125

6.2.1 二叉树的定义 125

6.2.2 二叉树的抽象数据类型 126

6.2.3 二叉树的重要性质 127

6.2.4 二叉树的存储结构 128

6.3 二叉树的遍历 130

6.3.1 先序遍历 131

6.3.2 中序遍历 131

6.3.3 后根遍历 132

6.3.4 按层遍历 133

6.3.5 非递归遍历算法 133

6.3.6 二叉树的建立 136

6.3.7 二叉树遍历的应用举例 137

6.4 二叉树与树、森林的转换 139

6.4.1 树与二叉树的转换 139

6.4.2 森林与二叉树的转换 140

6.5 树的存储结构 141

6.5.1 树的双亲表示法 142

6.5.2 孩子表示法 142

6.5.3 孩子兄弟表示法 143

6.6 树的遍历 144

6.6.1 一般树的遍历 144

6.6.2 森林的遍历 145

6.7 二叉树的应用 146

6.7.1 哈夫曼树 146

6.7.2 哈夫曼树的构造 146

6.7.3 哈夫曼树的实现算法 148

6.7.4 哈夫曼编码 149

6.8 小结 150

讨论小课堂6 150

习题6 150

第7章 图 153

7.1 图的基本概念 153

7.1.1 图的定义 153

7.1.2 图的术语 155

7.1.3 图的抽象数据类型 156

7.2 图的存储结构 157

7.2.1 图的邻接矩阵 157

7.2.2 邻接矩阵表示法的描述 159

7.2.3 邻接矩阵表示下的基本操作的实现 160

7.2.4 图的邻接链表 161

7.2.5 图的邻接表表示法的描述 162

7.2.6 邻接表表示下基本操作的实现 163

7.3 图的遍历与图的连通性 165

7.3.1 图的深度优先遍历 166

7.3.2 图的广度优先遍历 168

7.3.3 非连通图和连通分量 170

7.4 图的最小生成树 170

7.4.1 最小生成树的基本概念 170

7.4.2 普里姆（Prim）算法 171

7.4.3 克鲁斯卡尔（Kruskal）算法 174

7.5 最短路径 175

7.5.1 从某顶点到其余各顶点的最短路径 175

7.5.2 每对顶点之间的最短路径 178

7.6 拓扑排序与关键路径 180

7.6.1 拓扑排序 180

7.6.2 关键路径 183

7.7 图的应用 189

7.7.1 图在路由器寻径中的应用 189

7.7.2 图在物流信息系统中应用 190

7.8 小结 190

讨论题7 191

习题7 191

第8章 查找 193

8.1 查找的基本概念 194

8.2 静态查找表 195

8.2.1 顺序表的查找 195

8.2.2 有序表的折半查找 196

8.2.3 索引顺序表查找 200

8.3 动态查找表 201

8.3.1 二叉排序树 201

8.3.2 平衡二叉树 210

8.4 案例分析 214

8.4.1 直方图问题 214

8.4.2 箱子装载问题 216

8.5 小结 218

讨论小课堂8 218

习题8 219

第9章 排序 220

9.1 排序的基本概念 220

9.2 插入排序 221

9.2.1 直接插入排序 221

9.2.2 折半插入排序 222

9.2.3 希尔排序 222

9.3 交换排序 224

9.3.1 冒泡排序 224

9.3.2 快速排序 225

9.4 选择排序 229

9.4.1 简单选择排序 229

9.4.2 堆排序 230

9.5 归并排序 233

9.6 基数排序 235

9.7 小结 239

讨论小课堂9 240

习题9 240

第10章 索引结构与哈希 242

10.1 静态索引结构 242

10.1.1 索引表 242

10.1.2 索引表查找 242

10.2 动态索引结构（B-树和B＋树） 245

10.2.1 B-树的定义 245

10.2.2 B-树的运算 246

10.2.3 B＋树 249

10.3 键树及T rie树 250

10.3.1 键树的定义 250

10.3.2 双链树 251

10.3.3 Trie树 252

10.4 哈希表及其查找 253

10.4.1 哈希表与哈希函数 253

10.4.2 构造哈希函数的常用方法 254

10.4.3 解决冲突的主要方法 256

10.4.4 哈希查找的性能分析 260

10.5 小结 261

讨论小课堂10 262

习题10 262

参考文献 265