数据结构

第1章 绪论1

1.1 数据结构的概念1

1.1.1 引言1

1.1.2 数据结构的发展及其在计算机科学中所处的地位2

1.1.3 什么是数据结构3

1.1.4 有关概念和术语3

1.2 数据类型和抽象数据类型6

1.2.1 数据类型6

1.2.2 抽象数据类型6

1.3 算法和算法分析6

1.3.1 算法特性7

1.3.2 算法描述7

1.3.3 算法性能分析与度量8

第2章 线性表11

2.1 线性表的类型定义11

2.2 线性表的顺序存储结构及实现13

2.2.1 线性表的顺序存储13

2.2.2 顺序表的实现14

2.3 线性表的链式存储结构及实现18

2.3.1 线性表的链式存储18

2.3.2 单链表的实现18

2.3.3 其他形式的链表25

2.4 线性表的其他存储方法27

2.4.1 顺序存储与链式存储的比较27

2.4.2 静态链表28

2.4.3 间接寻址29

2.5 线性表应用举例29

第3章 特殊线性表35

3.1 栈35

3.1.1 栈的逻辑结构35

3.1.2 栈的顺序存储结构及实现37

3.1.3 栈的链式存储及实现40

3.1.4 顺序栈和链栈的比较42

3.1.5 栈的应用举例42

3.2 队列48

3.2.1 队列的逻辑结构49

3.2.2 队列的顺序存储结构及实现50

3.2.3 队列的链式存储及实现54

3.2.4 队列的应用57

第4章 串及其模式匹配59

4.1 串的定义59

4.1.1 串的相关概念59

4.1.2 串的抽象数据类型定义60

4.2 串的存储结构61

4.2.1 串的顺序存储结构62

4.2.2 串的链式存储结构62

4.2.3 串的索引存储结构63

4.2.4 串的堆存储64

4.3 顺序串的实现64

4.3.1 常用C++字符串函数64

4.3.2 串类65

4.4 串操作举例71

4.5 模式匹配72

第5章 广义线性表79

5.1 数组79

5.1.1 数组的定义79

5.1.2 数组的顺序存储81

5.2 矩阵的压缩存储83

5.2.1 特殊矩阵的压缩存储83

5.2.2 稀疏矩阵的压缩存储85

5.2.3 稀疏矩阵的运算87

5.3 广义表97

5.3.1 广义表的逻辑结构97

5.3.2 广义表的存储100

5.3.3 广义表的实现102

第6章 树和二叉树107

6.1 树的定义和基本术语107

6.2 二叉树109

6.2.1 二叉树的基本概念109

6.2.2 二叉树的主要性质114

6.3 二叉树的存储结构与实现116

6.3.1 二叉树的存储116

6.3.2 二叉树的基本操作及实现118

6.4 二叉树的遍历126

6.4.1 二叉树的遍历方法及递归实现126

6.4.2 二叉树遍历的非递归实现131

6.4.3 由遍历序列恢复二叉树134

6.4.4 不用栈的二叉树遍历的非递归方法136

6.5 线索二叉树137

6.5.1 线索二叉树及其结构137

6.5.2 线索二叉树的基本操作实现138

6.6 二叉树的应用143

6.6.1 二叉树遍历的应用143

6.6.2 最优二叉树——哈夫曼树145

6.7 树151

6.7.1 树的基本操作151

6.7.2 树的存储结构153

6.8 树、森林与二叉树的转换157

6.8.1 树转换为二叉树157

6.8.2 森林转换为二叉树158

6.8.3 二叉树转换为树和森林159

6.9 树和森林的遍历159

6.9.1 树的遍历159

6.9.2 森林的遍历160

6.10 树的应用160

6.10.1 判定树161

6.10.2 集合的表示162

6.10.3 求关系等价类问题164

第7章 图167

7.1 图的基本概念167

7.2 图的存储结构及实现172

7.2.1 邻接矩阵172

7.2.2 邻接表174

7.2.3 十字链表178

7.2.4 邻接多重表181

7.3 图的遍历182

7.3.1 深度优先搜索183

7.3.2 广度优先搜索185

7.4 图的连通性186

7.4.1 无向图的连通性186

7.4.2 有向图的连通性187

7.4.3 生成树和生成森林187

7.4.4 关节点和重连通分量190

7.5 最小生成树193

7.5.1 最小生成树的基本概念193

7.5.2 构造最小生成树的Prim算法194

7.5.3 构造最小生成树的Kruskal算法196

7.6 最短路径199

7.6.1 从一个源点到其他各点的最短路径199

7.6.2 每一对顶点之间的最短路径202

7.7 有向无环图及其应用204

7.7.1 有向无环图的概念204

7.7.2 AOV网与拓扑排序205

7.7.3 AOE图与关键路径210

第8章 查找217

8.1 基本概念与术语217

8.2 静态查找表219

8.2.1 静态查找表结构219

8.2.2 顺序查找220

8.2.3 有序表的折半查找222

8.2.4 有序表的其他查找方法225

8.2.5 分块查找226

8.3 动态查找表227

8.3.1 二叉排序树227

8.3.2 平衡二叉树（AVL树）234

8.3.3 B-树和B+树240

8.4 哈希表查找（杂凑法、散列法）245

8.4.1 哈希表与哈希方法245

8.4.2 常用的哈希函数246

8.4.3 处理冲突的方法248

8.4.4 哈希表的查找分析250

第9章 排序257

9.1 基本概念257

9.2 插入排序258

9.2.1 直接插入排序258

9.2.2 折半插入排序260

9.2.3 表插入排序261

9.2.4 希尔排序264

9.3 交换排序266

9.3.1 冒泡排序267

9.3.2 快速排序268

9.4 选择排序271

9.4.1 简单选择排序272

9.4.2 树形选择排序273

9.4.3 堆排序276

9.5 归并排序279

9.6 基数排序281

9.6.1 多关键字排序281

9.6.2 链式基数排序282

9.7 各种内部排序方法的比较286

参考文献288

《数据结构》根据数据结构的特点，充分考虑到教师教学、学生学习与进一步深造，以及相关人员实际工作需要，在处理好数据结构的组织方式和强化算法的实践与应用的同时，使学生通过实现算法的复杂程序训练，编写出结构清晰、正确易读、符合软件工程规范的程序；使教师方便组织教学内容，教学过程结构清晰，内容循序渐进且易于讲解。
《数据结构》符合教育部计算机及相关专业研究生考试大纲对数据结构内容的要求。
《数据结构》使用C++作为数据结构和算法的描述语言。采用C++语言中的类来表示抽象数据类型（ADT） ， 用C++的类和面向对象结构实现数据结构的算法。所使用的C++代码在Visual C++编译器上全部通过测试。
为了方便《数据结构》的学习和教学，提供有配套教材《数据结构实践教程》、《数据结构学习指导与习题集》和相关的学习课件，本系列教材的所有源代码都可以从清华大学出版社网站上免费下载。
《数据结构》可作为计算机类及其相关专业的教材，也可供从事计算机工程与应用的科技工作者参考。

数据结构实践教程（配光盘）（普通高校本科计算机专业特色教材精选·算法与程序设计）


普通高校本科计算机专业特色教材精选·算法与程序设计——数据结构学习指导与习题集