本书对常用的数据结构做了系统的介绍，力求概念清晰，注重实际应用。全书共分9章，依次介绍了数据结构的基本概念、线性表、栈和队列、串和数组、树和二叉树、图、查找、排序以及综合应用实例。全书用C语言作为算法描述语言，并且每一章后面均列举了典型应用实例，并配有电子课件，以供教师教学使用。

本书配套出版了《数据结构实验与实训教程》，便于教学实验、课程设计及复习应考。本书主要面向高职高专院校计算机类专业的学生，也可以作为大学非计算机专业学生的选修课教材和计算机应用技术人员的自学参考书。

数据结构（第2版）本教材第1版自2004年出版发行以来，受到了广大师生、读者的热烈欢迎，至今已出版发行近3万册，在此对广大师生、读者表示衷心的感谢。为了更好地适应新形势的发展与需要，我们在广泛收集读者意见的基础上对本书进行了修订再版。本版在保留原版特点的基础上主要作了以下修改：

 (1)  增加了第9章综合应用实例，给出了五个综合应用实例，如约瑟夫环问题、哈夫曼编译码器、用静态栈数据结构实现表达式求值、最小生成树Kruskal算法、汉诺塔游戏程序，以供学生实际实习，进一步加强学生应用能力的培养。

 (2)  对原书中的某些章节进行了小幅调整与修改，使内容更实用。

 (3)  增加和修改了部分例题与习题，更有针对性。

 (4)  修改了本书的电子课件，用户可以上清华大学出版社网站（www.tup.com.cn）下载。

本书第1、2、3、4、5、6、9章由邓文华编写，第7、8章由戴大蒙编写。浙江大学计算机学院孔繁胜教授任主审。全书由邓文华最后修改定稿。

本次修订仍然难免存在疏漏，敬请读者批评指正。

编 者2007年4月数据结构前 言

数据结构（第2版）数据结构是计算机程序设计的重要理论基础，该课程是计算机及其应用专业的一门重要基础课程和核心课程。它不仅是计算机软件专业课程的先导，而且也逐渐为其他工科类专业所重视。

本教材主要面向高职高专院校计算机专业的学生。教材内容结构力求体现以应用为主体，强调理论知识的理解和运用，实现专科教学以实践体系及技术应用能力培养为主的目标。

本书共分8章。第1章叙述数据、数据结构和算法等基本概念。第2~6章分别讨论了线性表、栈和队列、串和数组、树和二叉树、图等基本数据结构及其应用。第7章和第8章分别讨论了查找和排序的各种实现方法及其应用。

本教材具有以下特点：

(1) 基础理论知识的阐述由浅入深、通俗易懂。内容的组织和编排以应用为主线，省略了一些理论推导和数学证明过程，淡化了算法的设计分析和复杂的时空分析。

(2) 各章(除第1、8章外)都配有应用举例，列举分析了很多实用的例子，且大多数算法都直接给出了相应的C语言程序，以便上机练习和实践。

(3) 为了便于复习和掌握每章的重点，每章的起始处都给出了要点，并在每章结尾处给出了小结。

 (4)  本教材配有相应的PowerPoint演示文稿。

本教材推荐课时数约为64学时，上机时数约为20学时（有需要的院校请与我们联系： gzgz@tup.tsinghua.edu.cn) . 本书由邓文华副教授主编，编写了该书的第1~4章，第5、6章由李益明老师编写，第7、8章由戴大蒙老师编写。全书由邓文华老师最后修改定稿。浙江大学计算机学院孔繁胜教授审稿。

编写高职高专计算机专业教材是一项新的尝试，因编写时间紧迫，难免存在疏漏，敬请读者批评指正。

编 者2004年7月

第1章 绪论11.1 数据结构概念1

1.1.1 为什么要学习数据结构1

1.1.2 有关概念和术语4

1.2 算法描述7

1.2.1 算法特性7

1.2.2 算法描述8

1.3 算法分析9

小结10

习题11

第2章 线性表13

2.1 线性表的逻辑结构13

2.1.1 线性表的定义13

2.1.2 线性表的基本操作14

2.2 线性表的顺序存储及操作实现15

2.2.1 顺序表15

2.2.2 顺序表的基本操作实现17

2.2.3 顺序表应用举例21

2.3 线性表的链式存储和运算实现23

2.3.1 单链表23

2.3.2 单链表上基本运算的实现25

2.3.3 循环链表32

2.3.4 双向链表33

2.4 应用举例34

小结37

习题37

数据结构（第2版）目  录第3章 栈和队列40

3.1 栈40

3.1.1 栈的定义和基本运算40

3.1.2 栈的存储实现和运算实现41

3.1.3 栈与递归的实现44

3.2 栈的应用举例50

3.3 队列54

3.3.1 队列的定义和基本运算54

3.3.2 队列的存储实现和运算实现55

3.4 队列应用举例61

小结62

习题63

第4章 串和数组65

4.1 串65

4.1.1 串的基本概念65

4.1.2 串的基本运算66

4.1.3 串的存储和基本运算实现67

4.2 数组70

4.2.1 数组的逻辑结构70

4.2.2 数组的内存映像71

4.2.3 稀疏矩阵72

4.3 应用举例76

小结77

习题77

第5章 树和二叉树79

5.1 树的概念和基本操作79

5.1.1 树的定义和相关术语79

5.1.2 树的基本操作81

5.2 二叉树82

5.2.1 二叉树的基本概念82

5.2.2 二叉树的主要性质83

5.2.3 二叉树的基本操作与存储实现85

5.2.4 二叉树的遍历88

5.3 树和森林91

5.3.1 树的存储91

5.3.2 树、森林与二叉树的转换94

5.3.3 树和森林的遍历96

5.4 最优二叉树--哈夫曼树98

5.4.1 哈夫曼树的基本概念98

5.4.2 哈夫曼树的构造算法99

5.4.3 哈夫曼编码101

5.4.4 哈夫曼编码的算法实现103

5.5 应用举例104

小结107

习题107

第6章 图110

6.1 图的基本概念110

6.1.1 图的定义和术语110

6.1.2 图的基本操作114

6.2 图的存储表示114

6.2.1 邻接矩阵115

6.2.2 邻接表117

6.3 图的遍历119

6.3.1 深度优先搜索119

6.3.2 广度优先搜索121

6.4 图的应用122

6.4.1 最小生成树122

6.4.2 最短路径126

6.4.3 拓扑排序129

6.5 应用举例133

小结137

习题138

第7章 查找141

7.1 基本概念和术语141

7.2 静态查找表143

7.2.1 静态查找表结构143

7.2.2 顺序查找143

7.2.3 有序表的折半查找144

7.2.4 分块查找147

7.3 动态查找表148

7.4 哈希表152

7.4.1 哈希表和哈希方法152

7.4.2 常用的哈希函数153

7.4.3 冲突处理方法155

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

7.5 应用举例159

小结166

习题167

第8章 排序168

8.1 基本概念168

8.2 简单排序方法169

8.2.1 直接插入排序169

8.2.2 冒泡排序171

8.2.3 简单选择排序172

8.3 快速排序173

8.4 堆排序176

8.5 归并排序179

8.6 基数排序181

8.6.1 多关键码排序181

8.6.2 链式基数排序182

8.7 排序方法的比较和讨论184

小结185

习题186

第9章 综合应用实例188

9.1 约瑟夫环问题188

9.2 哈夫曼编译码器190

9.3 用静态栈数据结构实现表达式求值199

9.4 最小生成树Kruskal算法203

9.5 汉诺塔游戏程序207

参考文献213