数据结构PDF电子书下载

第一章　绪论 1

1.1　数据结构概述 1

目录 1

1.2　数据结构的基本概念 3

1.2.1　基本概念 3

1.2.2　数据结构及其分类 4

1.2.3　数据结构课程的内容 7

1.3　数据类型和抽象数据类型 8

1.3.1　数据类型 8

1.3.2　抽象数据类型 9

1.4.1　算法概念 11

1.4　算法和算法分析 11

1.4.2　算法分析 12

1.5　小结 14

习题1 16

第二章　线性表 17

2.1　线性表的类型定义 17

2.1.1　线性表的定义 17

2.1.2　线性表的基本操作 18

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

2.2.1　顺序表的存储结构 19

2.2.2　顺序表的基本操作 20

2.2.3　顺序表其他算法举例 22

2.3　线性表的链接存储结构及其运算 27

2.3.1　单链表和指针 28

2.3.2　单链表的基本操作 30

2.3.3　单链表的其他操作举例 37

2.3.4　循环链表 47

2.3.5　双向链表 49

2.4　小结 51

习题2 53

3.1.1　栈的定义及基本操作 55

3.1　栈 55

第三章　栈和队列 55

3.1.2　栈的表示和实现 56

3.2　栈的应用举例 60

3.3 队列 77

3.3.1 队列的定义 77

3.3.2　队列的表示和实现 78

3.4　队列应用举例 82

3.5　小结 86

习题3 86

4.1　串的定义和操作 88

第四章　串、数组和广义表 88

4.2　串的存储结构 90

4.2.1 串的顺序存储 90

4.2.2　串的堆分配存储 92

4.2.3　串的链式存储 95

4.3　串的模式匹配算法 96

4.3.1 Brute-Force算法 96

4.3.2　KMP算法 99

4.4　串操作应用举例 103

4.5.1　数组的概念 105

4.5　数组 105

4.5.2　数组的顺序存储结构 107

4.5.3　数组的应用举例 109

4.6　矩阵的压缩存储 112

4.6.1　特殊矩阵的压缩存储 112

4.6.2　稀疏矩阵及存储 114

4.6.3　三元组表 115

4.6.4　十字链表 118

4.7　广义表 119

4.7.1　广义表的递归定义 119

4.7.2　广义表的存储结构 121

4.7.3 广义表的递归算法 124

4.8　小结 127

习题4 129

第五章　树和二叉树 132

5.1　树的概念 132

5.1.1　树的定义 132

5.1.2　树的基本术语 134

5.2　二叉树 134

5.2.1　二叉树的定义和基本术语 134

5.2.2　二叉树的几个基本性质 136

5.2.3　二叉树的存储结构 137

5.3　二叉树的遍历 140

5.3.1　二叉树的遍历方法 140

5.3.2　二叉树遍历算法描述 141

5.3.3　二叉树遍历应用举例 149

5.3.4　线索二叉树 154

5.4　树和森林 158

5.4.1　树和森林的存储结构 158

5.4.2　树和森林的遍历 162

5.5　树的应用 166

5.5.1　集合的表示 166

5.5.2　等价问题 168

5.6.1　哈夫曼树的基本概念 169

5.6　哈夫曼树及其应用 169

5.6.2　判定树 171

5.6.3　哈夫曼编码 173

5.7　小结 176

习题5 177

第六章　图 180

6.1 图的概念 180

6.1.1 图的定义和术语 180

6.1.2 图有关术语的示例 182

6.2.1 图的邻接矩阵存储表示 184

6.2　图的存储结构 184

6.2.2　图的邻接表存储表示 186

6.2.3 图的建立算法 188

6.3　图的遍历 191

6.3.1　深度优先搜索遍历 191

6.3.2　广度优先搜索遍历 195

6.4　连通网的最小生成树 197

6.4.1 克鲁斯卡尔（Kruskal）算法 199

6.4.2　普里姆（Prim）算法 200

6.5.1　单源最短路径 202

6.5　最短路径问题 202

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

6.6　拓扑排序 207

6.7　关键路径 211

6.8　小结 213

习题6 215

第七章　查找 218

7.1　基本概念 218

7.2.3　顺序查找 220

7.2.2　静态查找表的顺序存储结构 220

7.2.1　静态查找的基本操作 220

7.2　静态查找 220

7.2.4　折半查找 222

7.2.5　分块查找 224

7.3　动态查找 227

7.3.1　动态查找的基本操作 227

7.3.2　动态查找表的二叉链表存储结构 227

7.3.3　二叉排序树 228

7.3.4　平衡二叉树 233

7.3.5　B树 238

7.4.1　散列表的概念 239

7.4　散列表 239

7.4.2　散列函数的构造方法 241

7.4.3　处理冲突的方法 244

7.4.4　散列表的查找和分析 247

7.5　查找操作应用举例 249

7.6　小结 251

习题7 252

第八章　排序 255

8.1　基本概念 255

8.2.1　直接插入排序 257

8.2　插入排序法 257

8.2.2　希尔排序 259

8.3　交换排序法 260

8.3.1 冒泡排序 260

8.3.2　快速排序 262

8.4　选择排序法 265

8.4.1　直接选择排序 265

8.4.2　堆排序 267

8.5　归并排序法 273

8.5.1 两个有序序列的归并 273

8.5.2　一趟归并排序 274

8.6.1 多关键字排序 275

8.6　基数排序法 275

8.6.2　链式基数排序 276

8.7　各种内部排序法的比较 281

8.8　排序操作应用举例 282

8.9　小结 284

习题8 285

第九章　文件 287

9.1　外部存储设备简介 287

9.1.1　磁带存储设备 287

9.1.2　磁盘存储设备 289

9.1.3　光盘存储设备 289

9.2　有关文件的基本概念 290

9.3　顺序文件 291

9.4　索引文件 293

9.5　ISAM文件和VSAM文件 294

9.5.1　ISAM文件 294

9.5.2　VSAM文件 296

9.6　倒排文件和多重表文件 298

9.7　散列文件 299

9.8　小结 300

习题9 300

参考文献 301