第1章 绪论 1
1-1 数据结构的概念 1
1-1-1 为什么要学习数据结构 1
1-1-2 相关概念和术语 4
1-1-3 数据结构课程的内容 6
1-2 数据类型和抽象数据类型 7
1-2-1 数据类型 7
1-2-2 抽象数据类型 8
1-3 算法和算法分析 9
1-3-1 算法特性 9
1-3-2 算法描述 9
1-3-3 算法性能分析与度量 10
习题 11
第2章 线性表 13
2-1 线性表的逻辑结构 13
2-1-1 线性表的定义 13
2-1-2 线性表的基本操作 13
2-2 线性表的顺序存储及运算实现 14
2-2-1 顺序表 14
2-2-2 顺序表上基本运算的实现 16
2-2-3 顺序表应用举例 19
2-3 线性表的链式存储和运算实现 22
2-3-1 单链表 22
2-3-2 单链表上基本运算的实现 24
2-3-3 循环链表 30
2-3-4 双向链表 31
2-3-5 静态链表 32
2-3-6 单链表应用举例 34
2-4 顺序表和链表的比较 36
习题 37
第3章 栈和队列 39
3-1 栈 39
3-1-1 栈的定义及基本运算 39
3-1-2 栈的存储实现和运算实现 40
3-2 栈的应用举例 43
3-3 队列 53
3-3-1 队列的定义及基本运算 53
3-3-2 队列的存储实现及运算实现 54
3-4 队列应用举例 59
习题 62
第4章 串 63
4-1 串及其基本运算 63
4-1-1 串的基本概念 63
4-1-2 串的基本运算 63
4-2 串的定长顺序存储及基本运算 64
4-2-1 串的定长顺序存储 64
4-2-2 定长顺序串的基本运算 65
4-2-3 模式匹配 66
4-3 串的堆存储结构 72
4-3-1 串名的存储映像 72
4-3-2 堆存储结构 74
4-3-3 基于堆结构的串的基本运算实现 74
习题 76
第5章 数组和广义表 77
5-1 多维数组 77
5-1-1 数组的逻辑结构 77
5-1-2 数组的内存映像 77
5-2 特殊矩阵的压缩存储 80
5-2-1 对称矩阵 80
5-2-2 三角矩阵 81
5-2-3 带状矩阵 82
5-3 稀疏矩阵 83
5-3-1 稀疏矩阵的三元组表存储 83
5-3-2 稀疏矩阵的十字链表存储 90
5-4 广义表 95
5-4-1 广义表的定义和基本运算 95
5-4-2 广义表的存储 96
5-4-3 广义表基本操作的实现 99
习题 102
第6章 二叉树 104
6-1 二叉树的定义与性质 104
6-1-1 二叉树的基本概念 104
6-1-2 二叉树的主要性质 106
6-2 二叉树的基本操作与存储实现 107
6-2-1 二叉树的存储 107
6-2-2 二叉树的基本操作及实现 110
6-3 二叉树的遍历 112
6-3-1 二叉树的遍历方法及递归实现 112
6-3-2 二叉树遍历的非递归实现 115
6-3-3 由遍历序列恢复二叉树 118
6-3-4 不用栈的二叉树遍历的非递归方法 120
6-4 线索二叉树 121
6-4-1 线索二叉树的定义及结构 121
6-4-2 线索二叉树的基本操作实现 123
6-5 二叉树的应用 128
6-5-1 二叉树遍历的应用 128
6-5-2 最优二叉树——哈夫曼树 131
习题 139
第7章 树与森林 141
7-1 树的概念与表示 141
7-1-1 树的定义及相关术语 141
7-1-2 树的表示 142
7-2 树的基本操作与存储 143
7-2-1 树的基本操作 143
7-2-2 树的存储结构 144
7-3 树、森林与二叉树的转换 147
7-3-1 树转换为二叉树 147
7-3-2 森林转换为二叉树 148
7-3-3 二叉树转换为树和森林 149
7-4 树和森林的遍历 150
7-4-1 树的遍历 150
7-4-2 森林的遍历 150
7-5 树的应用 151
7-5-1 判定树 151
7-5-2 集合的表示 152
7-5-3 等价问题 154
习题 155
第8章 图 157
8-1 图的基本概念 157
8-1-1 图的定义和术语 157
8-1-2 图的基本操作 160
8-2 图的存储结构 160
8-2-1 邻接矩阵 160
8-2-2 邻接表 162
8-2-3 十字链表 164
8-2-4 邻接多重表 166
8-3 图的遍历 168
8-3-1 深度优先搜索 168
8-3-2 广度优先搜索 170
8-3-3 应用图的遍历判定图的连通性 172
8-4 生成树与最小生成树 172
8-4-1 生成树和生成森林 172
8-4-2 最小生成树的概念 174
8-4-3 构造最小生成树的Prim算法 175
8-4-4 构造最小生成树的Kruskal算法 178
8-5 最短路径 180
8-5-1 从一个源点到其他各点的最短路径 180
8-5-2 每一对顶点之间的最短路径 184
8-6 有向无环图及其应用 186
8-6-1 有向无环图的概念 186
8-6-2 AOV网与拓扑排序 187
8-6-3 AOE图与关键路径 192
习题 196
第9章 查找 199
9-1 基本概念 199
9-2 静态查找表 200
9-2-1 静态查找表结构 200
9-2-2 顺序查找 200
9-2-3 有序表的查找 201
9-2-4 分块查找 205
9-3 动态查找表 206
9-3-1 二叉排序树 206
9-3-2 平衡二叉树 211
9-3-3 B树和B＋树 218
9-4 哈希表查找（杂凑法） 225
9-4-1 哈希表与哈希方法 225
9-4-2 常用的哈希函数 226
9-4-3 处理冲突的方法 228
9-4-4 哈希表的查找分析 230
习题 231
第10章 排序 234
10-1 排序的基本概念 234
10-2 插入排序 235
10-2-1 直接插入排序 235
10-2-2 折半插入排序 236
10-2-3 表插入排序 237
10-2-4 希尔排序 239
10-3 交换排序 240
10-3-1 冒泡排序 240
10-3-2 快速排序 241
10-4 选择排序 244
10-4-1 简单选择排序 244
10-4-2 树形选择排序 244
10-4-3 堆排序 245
10-5 归并排序 248
10-6 基数排序 250
10-6-1 多关键码排序 250
10-6-2 链式基数排序 251
10-7 外排序 253
10-7-1 外部排序的方法 253
10-7-2 多路平衡归并的实现 255
习题 258
参考文献 260