数据结构PDF电子书下载

目录 1

第一章 概论 1

1.1 为什么要研究数据结构 1

1.2 数据结构的概念 2

1.2.1 几个基本概念 2

1.2.2 数据结构 4

1.3 算法和抽象数据类型的描述 7

1.3.1 算法及其描述 7

1.3.2 算法评价和算法分析 7

1.3.3 程序设计步骤和算法实例 10

1.3.4 抽象数据类型的描述 13

习题 17

第二章 线性表 18

2.1 线性表 18

2.1.1 线性表的定义和特点 18

2.1.2 线性表上的操作说明 19

2.2 顺序存储实现线性表 23

2.3 链接存储实现线性表 33

2.3.1 单链表 33

2.3.2 循环链表 42

2.3.3 双向链表 44

2.3.4 对称链表 46

2.3.5 静态链表 49

2.3.6 三元整系数多项式的算术运算 51

2.4 索引存储实现线性表 57

2.5 动态存储管理 59

2.5.1 边界标识法 60

2.5.2 伙伴系统 67

2.6 广义表 72

习题 78

第三章 数组、栈和队列 81

3.1 数组的顺序分配 81

3.1.1 数组的顺序分配 81

3.1.2 特殊矩阵 83

3.2.1 顺序存储 85

3.2 稀疏矩阵 85

3.2.2 矩阵的转置 87

3.2.3 正交（十字）链表 91

3.3 栈 94

3.3.1 栈的定义及其说明 94

3.3.2 数组实现的栈 96

3.3.3 链表实现的栈 99

3.4 栈的应用实例 101

3.4.1 后缀表达式的求值 101

3.4.2 地图着色问题 106

3.5 栈与递归 108

3.5.1 如何实现递归 109

3.5.2 采用递归算法的问题 111

3.5.3 递归转换为非递归 114

3.6 队列 119

3.6.1 队列及其说明 119

3.6.2 循环数组实现的队列 120

3.6.3 链表实现的循环队列 124

习题 125

第四章 字符串 129

4.1 串及其说明 129

4.1.1 串的概念 129

4.1.2 串的说明 130

4.2 串的存储结构 132

4.2.1 顺序存储 132

4.2.2 链接存储 133

4.3 串的模式匹配 134

4.3.1 简单的模式匹配算法 134

4.3.2 无回溯匹配算法 135

4.3.3 从模式末端往前匹配算法 140

4.3.4 模式匹配KMP-BM算法 142

4.3.5 字符串的广义匹配 145

习题 147

5.1.1 树的定义 149

5.1 基本概念 149

第五章 树 149

5.1.2 基本术语 150

5.2 二叉树 151

5.2.1 二叉树的定义 151

5.2.2 二叉树的性质 153

5.2.3 二叉树的说明 155

5.2.4 二叉树的存储结构 157

5.3 遍历二叉树 160

5.3.1 二叉树三种遍历的递归算法 161

5.3.2 二叉树三种遍历的非递归算法 165

5.3.3 巧用二叉树遍历递归算法 169

5.4.1 建立线索树 174

5.4 线索二叉树 174

5.4.2 检索线索二叉树中结点 176

5.4.3 在中序线索树中插入结点 178

5.5 树和森林 179

5.5.1 森林和二叉树的转换 179

5.5.2 遍历树和森林 180

5.5.3 树的存储结构 181

5.6 哈夫曼树及其应用 188

5.6.1 扩充二叉树和哈夫曼树定义 188

5.6.2 建立（构造）哈夫曼树的方法 191

5.6.3 哈夫曼树的应用 195

5.7 树的应用 198

5.7.1 用树结构表示集合 199

5.7.2 判定树 201

5.7.3 表达式求值 203

习题 206

第六章 图 211

6.1 图的基本概念 212

6.2 图的存储表示法 215

6.2.1 图的矩阵表示法 215

6.2.2 图的邻接表表示法 218

6.3 图的运算 222

6.4.1 深度优先搜索（depth first search） 225

6.4 图的遍历 225

6.4.2 宽度优先搜索（breadth first search） 228

6.4.3 图中两顶点间所有简单路径 231

6.5 拓扑排序和关键路径 233

6.5.1 拓扑排序（topological sort） 233

6.5.2 关键路径（critical path） 237

6.6 最小代价生成树 243

6.6.1 Prim算法 244

6.6.2 Kruskal算法 247

6.7 最短路径 253

6.7.1 单源最短路径 254

6.7.2 每对顶点之间的最短路径 258

习题 261

第七章 查找 263

7.1 集合与查找 263

7.2 有序表查找 266

7.2.1 顺序查找（sequential search） 267

7.2.2 对半查找 268

7.2.3 一致对半查找 272

7.2.4 斐波那契（Fibonacci）查找 274

7.2.5 索引顺序查找 278

7.3 树表查找 281

7.3.1 二叉排序树 281

7.3.2 二叉平衡树 291

7.3.3 B-树 309

7.3.4 键树（key tree） 317

7.4 散列表查找 325

7.4.1 散列表 325

7.4.2 散列函数 327

7.4.3 冲突调节 328

习题 332

第八章 内部排序 334

8.1 基本概念 334

8.2 插入排序 335

8.2.1 直接插入排序 335

8.2.2 希尔排序 336

8.3.1 冒泡排序 339

8.3 交换排序 339

8.3.2 快速排序 340

8.4 选择排序 343

8.4.1 简单选择排序 343

8.4.2 堆排序 344

8.5 合并排序 347

8.5.1 两路合并排序 347

8.5.2 自然两路合并排序 350

8.6 基数排序 352

习题 356

9.1.1 磁带存储器 359

第九章 文件 359

9.1 外存储器简介 359

9.1.2 磁盘存储器 361

9.2 文件的基本概念 363

9.3 顺序文件 366

9.4 散列文件 369

9.5 索引文件 370

9.5.1 ISAM文件 371

9.5.2 VSAM文件 376

9.6 多关键字文件 378

9.6.1 多重表文件 379

9.6.2 倒排文件 380

习题 381

第十章 外部排序 383

10.1 外排序、初始游程、多路合并 383

10.1.1 外排序 383

10.1.2 初始游程的生成 383

10.1.3 多路合并 387

10.2 磁盘排序 391

10.3 磁带排序 392

习题 397

11.1 算法分析技术 398

11.1.1 空间分析 398

第十一章 算法分析和设计技术 398

11.1.2 时间分析 401

11.2 算法设计技术 408

11.2.1 分治法 409

11.2.2 贪心法 410

11.2.3 动态规划法 412

11.2.4 回溯法 420

11.2.5 分枝界限法 424

习题 431

第十二章 数据结构的程序设计实例 434

附录 名词索引 468

参考文献 475