前言
第1章 绪论1
1.1 数据结构的基本概念1
1.2 抽象数据类型3
1.2.1 抽象数据类型的定义3
1.2.2 抽象数据类型的描述3
1.3 数据的逻辑结构与存储结构4
1.3.1 逻辑结构4
1.3.2 存储结构5
1.4 算法的特性与算法的描述6
1.4.1 算法的定义6
1.4.2 算法的特性6
1.4.3 算法的描述6
1.5 算法分析7
1.5.1 算法设计的要求8
1.5.2 算法时间复杂度8
1.5.3 算法空间复杂度13
1.6 关于数据结构课程的地位及
学习方法13
习题14
第2章 线性表17
2.1 线性表的概念及运算17
2.1.1 线性表的逻辑结构17
2.1.2 线性表的抽象数据类型18
2.2 线性表的顺序表示与实现19
2.2.1 线性表的顺序存储19
2.2.2 顺序表的基本运算20
2.2.3 基本操作算法分析23
2.2.4 顺序表应用举例23
2.3 线性表的链式表示与实现27
2.3.1 单链表的存储结构27
2.3.2 单链表上的基本运算28
2.3.3 单链表应用举例33
2.3.4 循环单链表38
2.3.5 双向链表41
2.4* 静态链表43
2.4.1 静态链表的存储结构44
2.4.2 静态链表的实现44
2.4.3 静态链表应用举例46
2.5 线性表应用举例：一元多项式的
表示与相乘48
2.5.1 一元多项式的表示48
2.5.2 一元多项式的相乘49
2.6 小结53
习题54
第3章 栈与队列59
3.1 栈的表示与实现59
3.1.1 栈的定义59
3.1.2 栈的抽象数据类型60
3.1.3 顺序栈61
3.1.4 链栈65
3.2 栈的应用68
3.2.1 数制转换68
3.2.2 行编辑程序68
3.2.3 算术表达式求值70
3.3 递归76
3.3.1 递归的定义76
3.3.2 消除递归79
3.4 队列的表示与实现82
3.4.1 队列的定义82
3.4.2 队列的抽象数据类型82
3.4.3 顺序队列83
3.4.4 顺序循环队列85
3.4.5* 双端队列88
3.4.6 链式队列88
3.4.7 链式队列的实现90
3.5 队列的应用92
3.5.1 队列在杨辉三角中的应用92
3.5.2 队列在回文中的应用94
3.6 综合案例：停车场管理97
3.7 小结105
习题105
第4章 串109
4.1 串109
4.1.1 串的定义109
4.1.2 串的抽象数据类型109
4.2 串的表示与实现111
4.2.1 定长顺序存储表示与实现111
4.2.2* 堆串的存储分配表示与实现117
4.2.3* 块链存储表示与实现123
4.3 串的模式匹配128
4.3.1 Brute-Force经典算法128
4.3.2 KMP算法130
4.3.3 模式匹配应用举例134
4.4 小结138
习题138
第5章 数组与广义表141
5.1 数组的定义与运算141
5.1.1 数组的定义141
5.1.2 数组的抽象数据类型142
5.1.3 数组的顺序表示与实现142
5.2 特殊矩阵的压缩存储146
5.2.1 对称矩阵的压缩存储147
5.2.2 三角矩阵的压缩存储147
5.2.3 对角矩阵的压缩存储148
5.3 稀疏矩阵的压缩存储149
5.3.1 稀疏矩阵的定义149
5.3.2 稀疏矩阵的抽象数据类型149
5.3.3 稀疏矩阵的三元组表示与实现150
5.3.4 稀疏矩阵应用举例156
5.3.5 稀疏矩阵的十字链表表示与实现160
5.4 广义表164
5.4.1 广义表的定义164
5.4.2 广义表的抽象数据类型165
5.5 广义表的头尾链表表示与实现165
5.5.1 广义表的头尾链表存储结构166
5.5.2 广义表的基本运算166
5.5.3 广义表应用举例169
5.6 广义表的扩展线性链表表示与
实现172
5.6.1 广义表的扩展线性链表存储172
5.6.2 广义表的基本运算173
5.6.3 采用扩展线性链表存储结构的
广义表应用举例175
5.7 广义表应用举例：导师-本科生
制管理178
5.8 小结183
习题184
第6章 树188
6.1 树188
6.1.1 树的定义188
6.1.2 树的逻辑表示189
6.1.3 树的抽象数据类型190
6.2 二叉树191
6.2.1 二叉树的定义191
6.2.2 二叉树的性质193
6.2.3 二叉树的抽象数据类型195
6.2.4 二叉树的存储表示与实现196
6.3 二叉树的遍历201
6.3.1 二叉树遍历的定义202
6.3.2 二叉树的先序遍历202
6.3.3 二叉树的中序遍历203
6.3.4 二叉树的后序遍历205
6.4 二叉树的线索化207
6.4.1 二叉树的线索化定义207
6.4.2 二叉树的线索化实现209
6.4.3 线索二叉树的遍历210
6.4.4 线索二叉树应用举例212
6.5 树、森林与二叉树215
6.5.1 树的存储结构215
6.5.2 树转换为二叉树217
6.5.3 森林转换为二叉树219
6.5.4 二叉树转换为树和森林219
6.5.5 树和森林的遍历220
6.6 综合应用举例：哈夫曼树221
6.6.1 哈夫曼树的定义221
6.6.2 哈夫曼编码222
6.6.3 哈夫曼编码算法的实现223
6.7 小结226
习题227
第7章 图232
7.1 图的定义与相关概念232
7.1.1 图的定义232
7.1.2 图的相关概念233
7.1.3 图的抽象数据类型235
7.2 图的存储结构236
7.2.1 邻接矩阵表示法236
7.2.2 邻接表表示法240
7.2.3 十字链表表示法244
7.2.4 多重表表示法245
7.3 图的遍历246
7.3.1 图的深度优先遍历246
7.3.2 图的广度优先遍历249
7.4 图的连通性问题251
7.4.1 无向图的连通分量与生成树251
7.4.2 最小生成树252
7.5 有向无环图257
7.5.1 AOV网与拓扑排序257
7.5.2 AOE网与关键路径260
7.6 最短路径264
7.6.1 从某个顶点到其余各顶点的
最短路径264
7.6.2 每一对顶点之间的最短路径271
7.7 图的应用举例275
7.7.1 距离某个顶点的最短路径长度为
k的所有顶点275
7.7.2 求图中顶点u到顶点v的简单
路径277
7.8 图的综合应用：铁路交通线路
规划279
7.9 小结286
习题287
第8章 查找291
8.1 查找的基本概念291
8.2 静态查找292
8.2.1 顺序表的查找292
8.2.2 有序顺序表的查找293
8.2.3 索引顺序表的查找295
8.3 动态查找296
8.3.1 二叉排序树296
8.3.2* 平衡二叉树303
8.4* B-树与B+树311
8.4.1 B-树311
8.4.2 B+树319
8.5 哈希表320
8.5.1 哈希表的定义320
8.5.2 哈希函数的构造方法321
8.5.3 处理冲突的方法322
8.5.4 哈希表查找与分析324
8.5.5 哈希表应用举例324
8.6 小结328
习题329
第9章 排序332
9.1 排序的基本概念332
9.2 插入排序333
9.2.1 直接插入排序333
9.2.2 折半插入排序335
9.2.3 希尔排序336
9.2.4 插入排序应用举例338
9.3 选择排序339
9.3.1 简单选择排序339
9.3.2 堆排序340
9.4 交换排序346
9.4.1 冒泡排序346
9.4.2 快速排序347
9.4.3 交换排序应用举例350
9.5 归并排序353
9.6 基数排序354
9.6.1 基数排序算法355
9.6.2 基数排序应用举例357
9.7 小结360
习题361
参考文献364