本书为与计算机应用相关的专业量身定做，保留了经典数据结构的主要内容，但是做了一些必要的删减，以适应相对较少的课时安排；同时，还选择了一些实用性比较强的实例作为案例。在讲解数据的存储结构时，使用了大量的图表，有助于学生对数据结构及相关算法的理解。

本书的主要内容包括概述、栈与队列、线性表、线性表的链式存储、哈希表与索引表、内排序、树与二叉树和图。在各章内容的安排上不求大而全，力求少而精，讲解透彻，重点突出。

本书既可以作为计算机相关专业本科学生学习数据结构的教材，也可作为自学者的教材或参考书。

数据结构是高等学校计算机和信息类专业的重点课程，也是对本科生来说比较难掌握的一门课程，经常被学生们称为“杀手”。原因是多方面的，例如，最初程序设计的课程未让学生对程序设计感兴趣，反而使学生惧怕程序设计，而数据结构是以程序设计为基础的；又例如，按照计算机学科的要求，学习数据结构之前应该先学习离散数学，由于各种原因，很多学校并未严格按照要求排课。本书尝试简化传统数据结构的内容，突出重点，强调应用，希望学生通过学习数据结构课程能够提高程序设计的能力，使学生们在认真学习了数据结构课程之后，能够编写一些实用的程序。

    对于现阶段的人才培养应该着重对能力的培养，而不是简单地掌握理论。因此本书在编写的过程中，遵循谭浩强老师提出的“提出问题—解决问题—归纳分析”的新三部曲，强调从实践中获取知识。本书给出了能够解决实际问题的大量算法，希望学生们在阅读和总结这些算法的基础上提高自己程序设计的水平。因此，本书的大部分算法只要经过简单的修改，就能上机运行，具有很好的实用价值，也给学习者带来方便。

本书将经典的数据结构内容做了一些重新整合，去掉了一些笔者认为只是为了应付考试而没有实用价值的内容。例如，本书并没有将数组和（字符）串的内容作为单独的章节来讨论，而是将这部分内容融入其他章节，作为解决具体问题的一种方法，从而避免了只讨论抽象而简单的理论，而不注重实用的讲解方法。本书在讲解数据的存储结构时，使用了大量的图表，帮助学生对数据结构的理解。

考虑到在数据结构的学习中，教师需要在课堂上对大量的算法进行讲解，而学生们应该在此基础上大量阅读并理解数据结构的经典算法，因此本书对所有的算法都做了详细的注释，对一些难度比较大的算法，在用C语言描述之前，还使用伪语言对算法进行了描述。

全书共分为8章：第1章概述、第2章栈与队列、第3章线性表、第4章线性表的链式存储、第5章哈希表与索引表、第6章内排序、第7章树与二叉树和第8章图。

注意：本书尝试了一种不同于其他数据结构教材的排列顺序，主要是考虑学生的接受能力，由于线性表的链式存储相对复杂，很多学生在学习中感到很困难，而栈和队列的基本操作比较简单，便于理解，因此将栈和队列内容放在了第2章。但是，有关栈和队列的应用还是有一定难度，可以灵活安排案例讲解的内容和时间，不要求一定按照教材的顺序讲课。本书在编写时，尽量使内容通俗易懂，适于自学，由浅入深，便于理解。在各章内容的安排上不求大而全，力求少而精，讲解透彻，重点突出。

编者水平有限，错误在所难免，请广大读者批评指正。

作者

2013年11月于北京

第1章概述/1

1.1什么是数据结构/1

1.2数据结构的相关概念和术语/5

1.3算法/8

1.3.1算法的概念/8

1.3.2算法的特性/11

1.3.3算法的描述方法——类C语言/12

1.4算法分析/13

1.4.1计算比较次数和移动次数/13

1.4.2大O表示法及算法的时间复杂度/16

1.4.3最好、最差和平均情况/18

1.4.4算法的空间复杂度/19

本章小结/20

习题/20第2章栈与队列/23

2.1栈/23

2.1.1栈的实例/23

2.1.2栈的基本概念/24

2.1.3栈的顺序存储/25

2.1.4顺序栈的基本算法/26

2.1.5顺序栈的算法效率/30

2.1.6栈的链式存储/30

2.1.7单链栈的基本算法/32

2.1.8链栈的算法效率/35

2.1.9栈应用举例/35

2.2队列/39

2.2.1队列的实例/39

2.2.2队列的基本概念/39

2.2.3顺序队列的基本思想/40

2.2.4环形队列的基本算法/43

2.2.5环形队列的算法效率/47

2.2.6用单链表存储队列的基本算法/47

2.2.7链队列的算法效率/51

2.2.8队列应用举例/51

本章小结/58

习题/59第3章线性表/64

3.1线性表的定义/64

3.1.1线性表实例/64

3.1.2线性表的定义和基本操作/64

3.1.3线性表的数学定义和逻辑图/65

3.2线性表的顺序存储结构/66

3.3顺序表基本算法实现/68

3.3.1线性表内容与线性表长度分别存储的算法实现/68

3.3.2线性表内容与线性表长度存储在一个结构体中的算法实现/75

3.4顺序表的查找/78

3.4.1顺序查找/79

3.4.2二分查找/80

3.4.3顺序查找与二分查找的效率分析/81

3.5插入与删除操作的效率分析/82

3.5.1在顺序表的第i个位置（逻辑位置）

插入一个元素/82

3.5.2插入算法的移动次数/84

3.5.3删除算法的移动次数/84

3.6顺序表应用举例/85

本章小结/92

习题/93第4章线性表的链式存储/97

4.1线性表的链式存储结构/97

4.1.1为什么要使用链式存储结构/97

4.1.2单链表的数据定义/98

4.2基于单链表的算法实现/99

4.2.1单链表的基本算法实现/99

4.2.2单链表中插入运算的进一步讨论/105

4.3单链表应用举例/109

4.4链式存储的其他方法/115

4.5基于带表头结点的单循环链表算法实现/117

4.5.1带表头结点的单循环链表的基本算法实现/117

4.5.2带表头结点的单循环链表的应用举例/122

4.5.3带表头结点与不带表头结点的单循环链表的比较/124

4.6双向链表基本算法实现/126

4.7顺序存储与链式存储方式的比较/132

本章小结/132

习题/133第5章哈希表与索引表/139

5.1查找的基本概念/139

5.2哈希表/140

5.2.1哈希表的基本概念/140

5.2.2冲突的产生/141

5.2.3可以选择的哈希函数/142

5.2.4解决冲突的方法/145

5.2.5基本算法的实现/147

5.2.6哈希表存储方法的性能分析/154

5.2.7哈希表应用举例/155

5.3索引表/157

5.3.1索引表的构成/157

5.3.2索引表的查找/159

5.3.3分块查找/161

5.4各种查找算法的效率分析/162

本章小结/163

习题/164第6章内排序/167

6.1排序的基本概念/167

6.1.1简单选择排序的算法思想和实现/167

6.1.2排序的相关概念/169

6.2插入排序/170

6.2.1直接插入排序的算法思想和实现/170

6.2.2折半插入排序思想和算法实现/173

6.2.3希尔排序思想和算法实现/174

6.2.4插入排序算法效率分析/177

6.3交换排序/179

6.3.1冒泡排序思想和算法实现/179

6.3.2快速排序思想和算法实现/181

6.3.3交换排序算法效率分析/185

6.4归并排序/185

6.5基数排序/188

6.6各种排序算法的比较和分析/192

本章小结/193

习题/193第7章树与二叉树/197

7.1树与二叉树的基本概念/197

7.1.1树与二叉树实例/197

7.1.2树与二叉树的定义/198

7.1.3树与二叉树的相互转换/199

7.2二叉树的基本操作和实现/200

7.2.1二叉树的存储结构/200

7.2.2二叉树的建立/203

7.2.3二叉树的遍历/205

7.3应用举例: 堆排序/211

7.4线索二叉树/215

7.5哈夫曼树/218

7.5.1哈夫曼树与哈夫曼编码/218

7.5.2算法实现/220

7.6二叉搜索树/223

7.6.1二叉搜索树的定义/223

7.6.2二叉搜索树基本操作实现/224

7.6.3应用举例/230

本章小结/232

习题/233第8章图/239

8.1图的基本概念/239

8.1.1图的实例/239

8.1.2图的定义和术语/240

8.2图的存储结构/241

8.2.1图的邻接矩阵表示/242

8.2.2图的邻接表表示/245

8.2.3图的十字链表表示/247

8.3图的操作和实现/249

8.3.1图的建立/249

8.3.2图的遍历/254

8.4图的应用——拓扑排序/260

8.4.1拓扑排序的思想/260

8.4.2拓扑排序的实现/263

8.5图的应用——最小生成树/265

8.5.1最小生成树的构造方法/265

8.5.2构造最小生成树的算法实现/267

本章小结/270

习题/271

参考文献/274