第1章 绪论 1
1.1 数据结构的基本概念 1
1.2 抽象数据类型 3
1.2.1 抽象数据类型的定义 3
1.2.2 抽象数据类型的表示与实现 5
1.3 算法和算法分析 5
1.3.1 算法的定义及其特性 6
1.3.2 算法设计的要求 6
1.3.3 算法的分析 6
1.4 关于数据结构课程的学习 9
1.4.1 数据结构课程的发展 10
1.4.2 数据结构课程的地位 10
1.4.3 如何学好数据结构 10
1.4.4 本书内容安排 11
1.5 知识点总结 11
1.6 单元自测 12
第2章 线性表 14
2.1 线性表 14
2.1.1 线性表案例导入 14
2.2 线性表的相关定义 15
2.2.1 线性表的逻辑结构 15
2.2.2 线性表的抽象类型定义 16
2.3 线性表的顺序存储及其实现 17
2.3.1 线性表的顺序存储结构 17
2.3.2 线性表顺序存储结构上的运算 18
2.4 线性表的链式存储及其实现 22
2.4.1 单链表 22
2.4.2 单链表上的基本运算 23
2.4.3 循环链表 29
2.4.4 双向链表 31
2.4.5 静态链表 33
2.5 线性表应用 35
2.6 知识点总结 38
2.7 单元自测 39
第3章 栈和队列 42
3.1 栈 42
3.1.1 栈案例导入 42
3.1.2 栈的相关定义 43
3.1.3 栈的顺序存储及其实现 44
3.1.4 栈的链式存储及其实现 49
3.1.5 栈的应用 50
3.2 队列 58
3.2.1 队列案例导入 58
3.2.2 队列的相关定义 59
3.2.3 队列的顺序存储及其实现 60
3.2.4 队列的链式存储及其实现 63
3.2.5 队列的应用 65
3.3 知识点总结 68
3.4 单元自测 68
第4章 串 71
4.1 串案例导入 71
4.2 串的相关定义 71
4.2.1 串的基本概念 71
4.2.2 串的抽象数据类型 72
4.3 串的存储及其实现 73
4.3.1 定长顺序串 73
4.3.2 堆串 78
4.3.3 块链串 81
4.4 模式匹配算法 82
4.4.1 简单的模式匹配算法 82
4.4.2 KMP算法 83
4.5 知识点总结 86
4.6 单元自测 86
第5章 数组和广义表 89
5.1 数组案例导入 89
5.2 数组的顺序存储和表示 89
5.2.1 数组的相关定义 89
5.2.2 数组的抽象数据类型 90
5.3 数组的顺序存储和实现 91
5.3.1 数组的存储结构 91
5.3.2 地址计算 92
5.4 矩阵的压缩存储 93
5.4.1 三角矩阵 93
5.4.2 稀疏矩阵 94
5.5 广义表 102
5.5.1 广义表的定义 102
5.5.2 广义表的存储 103
5.6 知识点总结 104
5.7 单元自测 105
第6章 树和二叉树 109
6.1 树形结构案例导入 109
6.2 树的相关定义与概念 110
6.2.1 树的定义 110
6.2.2 树的表现形式 110
6.2.3 树的抽象数据类型定义 111
6.2.4 基本术语 113
6.3 二叉树性质及其存储 113
6.3.1 二叉树的定义 113
6.3.2 二叉树的性质 114
6.3.3 二叉树的存储 117
6.4 二叉树的遍历 120
6.4.1 二叉树的遍历方法及递归实现 120
6.4.2 二叉树遍历的非递归实现 124
6.4.3 由遍历序列结果构造二叉树 127
6.5 线索二叉树 129
6.5.1 线索二叉树定义 129
6.5.2 线索二叉树的结点结构 129
6.5.3 对二叉树进行线索化 130
6.5.4 对线索二叉树进行中序遍历 134
6.6 树和森林 135
6.6.1 树的存储结构 135
6.6.2 树、森林与二叉树的交换 138
6.6.3 树和森林的遍历 140
6.7 哈夫曼树及其应用 141
6.7.1 最优二叉树 141
6.7.2 哈夫曼编码 144
6.8 知识点总结 146
6.9 单元自测 146
第7章 图 149
7.1 案例导入 149
7.2 图的相关定义和概念 149
7.2.1 图的定义 149
7.2.2 图的相关术语 150
7.2.3 图的抽象数据类型 152
7.3 图的存储结构 153
7.3.1 邻接矩阵 153
7.3.2 邻接表 155
7.4 图的遍历 156
7.4.1 深度优先搜索（Depth-First-Search:DFS） 157
7.4.2 广度优先搜索（Breadth-First-Search:BFS） 158
7.5 最小生成树 160
7.5.1 无向图的连通分量和生成树 160
7.5.2 最小生成树 161
7.5.3 Prim算法 162
7.5.4 Kruskal算法 164
7.6 拓扑排序 165
7.6.1 有向无环图 165
7.6.2 AOV网（Activity on Vertex Network） 166
7.6.3 拓扑排序 167
7.6.4 拓扑排序算法 168
7.7 最短路径 169
7.7.1 从某个源点到其余各顶点的最短路径 169
7.7.2 每一对顶点之间的最短路径 171
7.8 知识点总结 172
7.8.1 名词术语 172
7.8.2 三种逻辑结构的对比 173
7.8.3 邻接矩阵和邻接表的对比 174
7.9 单元自测 174
第8章 查找 180
8.1 查找案例导入 180
8.2 查找的基本概念 180
8.3 基于线性表的查找方法 181
8.3.1 顺序查找法 181
8.3.2 二分查找法 183
8.3.3 分块查找法 186
8.4 基于树的查找方法 188
8.4.1 二叉排序树 188
8.4.2 平衡二叉排序树 196
8.4.3 B树 209
8.5 基于函数的查找方法 220
8.5.1 哈希函数的构造方法 221
8.5.2 处理冲突的方法 222
8.5.3 哈希表上的操作 225
8.5.4 哈希法性能分析 227
8.6 知识点总结 229
8.7 单元自测 230
第9章 排序 233
9.1 案例导入 233
9.2 排序的基本概念 233
9.3 插入类排序 234
9.3.1 直接插入排序 234
9.3.2 折半插入排序 236
9.3.3 希尔排序 237
9.4 交换类排序 238
9.4.1 起泡排序 238
9.4.2 快速排序 240
9.5 选择类排序 242
9.5.1 简单选择排序 242
9.5.2 树形选择排序 244
9.5.3 堆排序 245
9.6 归并排序 247
9.7 基数排序 249
9.7.1 多关键字的排序 249
9.7.2 链式基数排序 250
9.8 知识点总结 252
9.8.1 各种内部排序方法的比较 252
9.8.2 排序方法的选择 252
9.8.3 外部排序 253
9.9 单元自测 253
参考文献 256