本书在保持第1版整体结构不变的情况下，对各章节内容进行了全面扩充和修正，增加了各大高校和科研院所近几年硕士研究生入学考试中的经典题目，并进行了详细而全面的解析。大家都知道，剖析、理解经典题目是掌握相应知识点的捷径，这也正是本书一直坚持使用考研真题作为解析知识点的原因所在。同时增加了链表、栈、树、图、排序中的一些必要知识点，并以联想网络的方式与原有知识网有机结合起来。无论是对题目的解析还是对知识点的诠释，本版都试图做到尽可能细致而全面。天下难事必做于易，天下大事必做于细。如果对每个知识点、每道题目都能钻研到细致入微处，那么掌握数据结构这门学科并游刃有余地应用数据结构知识解决实际问题，自然也就变得容易实现多了。

本书介绍数据结构线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、内排序等的基本概念、基本知识点、相关结论和各种数据类型的不同存储结构以及主要操作的实现算法；系统而全面地对读者在学习过程中可能遇到的问题，在相应的知识点处提出并加以解决；精选各大知名院校和研究所的硕士研究生入学试题及国内外教材中有代表性的习题，结合各相关知识点进行深入细致的分析、完整的解答和点评扩展。

本书可作为计算机专业本、专科学生的教学参考书，也可作为报考计算机专业硕士研究生的学习参考书，还适于计算机等级考试者及广大工程技术人员和自学者参考。

第1章 绪论1

 1.1 基本概念1

1.1.1 数据的逻辑结构2

1.1.2 数据的存储结构3

1.1.3 数据的逻辑结构与存储结构的关系3

 1.2 抽象数据类型3

1.2.1 算法4

1.2.2 算法的分析5

第2章 线性表11

 2.1 线性表的逻辑结构11

 2.2 线性表的顺序存储结构12

 2.3 线性表的链式存储结构19

2.3.1 单链表20

2.3.2 静态链表37

2.3.3 循环链表38

2.3.4 双向链表40

第3章 栈和队列45

 3.1 栈45

3.1.1 顺序栈46

3.1.2 双栈49

3.1.3 链栈50

 3.2 队列55

3.2.1 队列的顺序存储结构和循环队列55

3.2.2 循环队列56

3.2.3 链队列60

第4章 字符串66

 4.1 串类型的相关概念66

 4.2 字符串的存储表示和实现68

4.2.1 定长顺序存储表示68

4.2.2 堆分配存储表示和实现69

4.2.3 串的块链存储表示73

 4.3 串的模式匹配算法73

4.3.1 朴素的模式匹配算法73

4.3.2 模式匹配算法的一种改进算法——KMP算法74

第5章 数组和广义表82

 5.1 数组的定义82

 5.2 数组的顺序表示和实现83

 5.3 矩阵的压缩存储87

5.3.1 特殊矩阵的压缩存储87

5.3.2 稀疏矩阵的压缩存储92

 5.4 广义表95

5.4.1 广义表的定义95

5.4.2 广义表的存储结构99目录

第6章 树和二叉树105

 6.1 树105

6.1.1 树的定义和相关术语105

6.1.2 树的存储结构107

 6.2 二叉树109

6.2.1 二叉树的定义109

6.2.2 二叉树的性质111

6.2.3 完全二叉树的性质111

6.2.4 二叉树的存储结构115

 6.3 遍历二叉树120

6.3.1 先序遍历120

6.3.2 中序遍历124

6.3.3 后序遍历126

6.3.4 按层次遍历132

 6.4 表达式树及其构造153

6.4.1 由表达式构造表达式树153

6.4.2 由前缀表达式构造表达式树156

6.4.3 由后缀表达式构造表达式树157

6.4.4 由后缀表达式求值157

6.4.5 由（中缀）表达式直接求其前（后）缀表达式159

 6.5 线索二叉树160

6.5.1 线索二叉树的定义160

6.5.2 二叉树的线索化161

6.5.3 线索二叉树上搜索指定结点的前驱、后继结点163

 6.6 树和森林与二叉树169

6.6.1 树和森林与二叉树的转换169

6.6.2 树和森林的遍历172

 6.7 哈夫曼树及其应用174

6.7.1 哈夫曼树174

6.7.2 哈夫曼编码176

 6.8 树与等价问题181

第7章 图185

 7.1 图的定义和相关概念185

7.1.1 图的定义185

7.1.2 图的相关概念185

 7.2 图的存储表示189

7.2.1 数组表示法189

7.2.2 邻接表表示法190

7.2.3 十字链表表示法192

7.2.4 邻接多重表193

 7.3 图的基本操作及其实现196

7.3.1 图的创建197

7.3.2 图的遍历199

 7.4 最小生成树209

7.4.1 Prim（普里姆）算法209

7.4.2 Kruskal（克鲁斯卡尔）算法212

 7.5 关节点216

 7.6 有向无环图的应用219

7.6.1 表达式的有向无环图220

7.6.2 拓扑排序221

7.6.3 关键路径226

 7.7 最短路径230

7.7.1 单源点的最短路径问题230

7.7.2 每一对顶点之间的最短路径问题234

第8章 查找239

 8.1 基本概念和相关约定239

8.1.1 基本概念239

8.1.2 算法的平均查找长度240

8.1.3 判定树241

8.1.4 相关约定242

 8.2 静态查找表的查找算法243

8.2.1 无序顺序表的查找——顺序查找法243

8.2.2 有序顺序表的查找——折半查找法247

8.2.3 次优查找树254

8.2.4 索引顺序表的查找——分块查找257

 8.3 动态查找表259

8.3.1 二叉排序树260

8.3.2 平衡二叉树280

8.3.3 B-树287

8.3.4 B+树296

8.3.5键树298

 8.4 哈希表300

8.4.1 哈希函数的构造方法300

8.4.2 处理冲突的方法302

8.4.3 哈希表的查找305

8.4.4 哈希表的插入和删除308

 8.5 各种查找方法的比较310

第9章 排序311

 9.1 概论311

 9.2 插入排序313

9.2.1 直接插入排序313

9.2.2 折半插入排序316

9.2.3 希尔排序317

 9.3 交换排序320

9.3.1 冒泡排序320

9.3.2 快速排序324

 9.4 选择排序330

9.4.1 简单选择排序330

9.4.2 树形选择排序334

9.4.3 堆排序336

 9.5 归并排序345

 9.6 基于关键字比较的排序算法的时间下界349

 9.7 基数排序350

9.7.1 多关键字排序350

9.7.2 链式基数排序351

 9.8 各种内部排序方法的比较352

参考文献362