第1章 绪论 1
1.1 预备知识 1
1.1.1 数据抽象 1
1.1.2 数据抽象与二元关系 3
1.1.3 二元关系的基本性质和几种重要的关系 5
1.2 什么是数据结构 6
1.2.1 数据结构的引出 6
1.2.2 数据的逻辑结构和存储结构 8
1.2.3 数据结构的表示 11
1.3 抽象数据类型 11
1.3.1 什么是抽象数据类型 11
1.3.2 面向对象方法与抽象数据类型 13
1.3.3 抽象数据类型的实现 15
1.4 算法与算法分析 17
1.4.1 什么是算法 17
1.4.2 算法描述与算法描述语言 19
1.4.3 常用的算法设计方法 29
1.4.4 算法分析 35
习题 38
第2章 线性表及其顺序存储 42
2.1 线性表的概念 42
2.1.1 什么是线性表 42
2.1.2 线性表的抽象数据类型 44
2.2 线性表的顺序存储及其运算实现 45
2.2.1 线性表的顺序存储——顺序表 45
2.2.2 顺序表的基本运算 47
2.2.3 顺序表的类定义 52
2.3 栈 53
2.3.1 什么是栈 53
2.3.2 栈的抽象数据类型 56
2.3.3 栈的顺序存储及其运算 56
2.3.4 顺序栈的类定义 59
2.4 栈与算法设计 60
2.4.1 栈与优先级处理 60
2.4.2 栈与回溯法 68
2.4.3 栈与分治法 73
2.4.4 栈与递归 75
2.5 队列 85
2.5.1 队列及其抽象数据类型 85
2.5.2 顺序队列及其运算 87
2.5.3 队列应用例 92
2.5.4 优先队列 96
2.6 数组与特殊矩阵的表示 98
2.6.1 数组的顺序存储 98
2.6.2 规则矩阵的压缩存储 100
2.6.3 稀疏矩阵的三列二维数组表示——三元组顺序表 102
习题 105
第3章 链表 107
3.1 线性表的链式存储——线性链表 107
3.1.1 线性链表的概念 107
3.1.2 线性链表的运算 109
3.1.3 线性链表的类定义 116
3.2 链式栈与链式队列 116
3.2.1 链式栈 116
3.2.2 链式队列 120
3.3 循环链表 123
3.3.1 循环链表的结构特点 123
3.3.2 循环链表的基本运算 124
3.3.3 循环链表应用例 128
3.4 双向链表与十字链表 136
3.4.1 双向链表 136
3.4.2 稀疏矩阵的十字链表表示 139
3.5 广义表 140
3.5.1 广义表的概念 141
3.5.2 广义表的存储方式 143
3.5.3 广义表的基本运算 144
习题 148
第4章 树与二叉树 151
4.1 树的基本概念 151
4.1.1 什么是树结构 151
4.1.2 树的定义与表示 154
4.1.3 树的性质 156
4.2 二叉树 157
4.2.1 二叉树的定义 157
4.2.2 二叉树的基本性质 158
4.2.3 二叉树的抽象数据类型 160
4.2.4 二叉树的存储结构 161
4.2.5 二叉树的遍历及其他运算 163
4.2.6 线索二叉树 168
4.2.7 二叉树的计数 172
4.3 二叉树应用 174
4.3.1 表达式线性化 174
4.3.2 最优二叉树 176
4.3.3 二叉搜索树 182
4.3.4 堆 188
4.3.5 二叉树与减治法 195
4.4 树的运算 196
4.4.1 树的抽象数据类型 197
4.4.2 树的存储结构 197
4.4.3 树的遍历 199
4.4.4 树的其他运算——树遍历的应用 200
4.5 树结构与算法设计 203
4.5.1 算法的一种描述方式——决策树 203
4.5.2 树与回溯法 204
4.5.3 树与划分等价类 210
4.6 森林与二叉树 213
4.6.1 森林与二叉树的转换 213
4.6.2 森林的遍历 214
习题 215
第5章 图 217
5.1 图的基本概念 217
5.1.1 图的定义和概念 217
5.1.2 图的抽象数据类型 221
5.1.3 欧拉路径和汉密尔顿路径 222
5.2 图的存储结构 224
5.2.1 图的邻接矩阵表示 224
5.2.2 图的邻接表表示 226
5.2.3 图的其他表示方法 229
5.3 图的遍历 231
5.3.1 图的深度优先遍历 232
5.3.2 图的广度优先遍历 233
5.3.3 图遍历的应用 234
5.3.4 广义图搜索 236
5.3.5 图的连通性 237
5.4 有向图与有向无环图 238
5.4.1 有向图的连通性和传递闭包 238
5.4.2 有向无环图与拓扑排序 241
5.4.3 关键路径 244
5.5 最小生成树与贪心算法 246
5.5.1 图的生成树与最小生成树 246
5.5.2 普里姆算法 248
5.5.3 克鲁斯卡尔算法 250
5.5.4 贪心算法 252
5.6 最短路径问题 256
5.6.1 单源最短路径 256
5.6.2 带负权值边的单源最短路径 258
5.6.3 全源最短路径 261
5.6.4 动态规划算法 264
5.7 图应用例——城市间公路交通网问题 269
5.7.1 问题描述 269
5.7.2 问题求解思路 270
习题 270
第6章 查找 273
6.1 线性查找表 274
6.1.1 顺序查找 274
6.1.2 折半查找 274
6.1.3 斐波那契查找 276
6.1.4 线性查找表的性能比较 276
6.2 二叉搜索树的查找性能 277
6.3 AVL树 279
6.3.1 BST的旋转操作 280
6.3.2 AVL树的插入和平衡化旋转 281
6.3.3 AVL树的删除 283
6.3.4 AVL树的性能 285
6.4 B-树 286
6.4.1 多路动态搜索树 286
6.4.2 B-树的查找 287
6.4.3 B-树的插入 287
6.4.4 B-树的删除 289
6.5 2-3-4树和红黑树 291
6.5.1 2-3-4树 291
6.5.2 红黑树 292
6.6 散列方法 296
6.6.1 散列技术 296
6.6.2 散列函数 297
6.6.3 冲突处理 300
6.6.4 散列的删除 302
6.6.5 散列的性能 302
6.7 静态索引结构 303
6.7.1 索引查找 303
6.7.2 索引存储方式 303
6.7.3 索引文件结构 306
6.8 模式匹配算法 309
6.8.1 字符串的概念和ADT 309
6.8.2 字符串的存储表示 310
6.8.3 字符串的模式匹配及简单匹配算法 311
6.8.4 KMP算法 311
6.8.5 Boyer-Moore算法 314
习题 317
第7章 排序 319
7.1 排序的概念及算法性能分析 319
7.2 基本排序方法 321
7.2.1 冒泡排序 321
7.2.2 插入排序 322
7.2.3 直接选择排序 326
7.2.4 基本排序方法的比较 328
7.3 快速排序 328
7.3.1 快速排序的过程 329
7.3.2 快速排序的性能分析 330
7.3.3 快速排序的改进算法 331
7.3.4 三路划分的快速排序算法 332
7.4 归并排序 334
7.4.1 二路归并 334
7.4.2 自底向上的归并排序 335
7.4.3 自顶向下的归并排序 336
7.5 锦标赛排序 337
7.6 堆排序 339
7.6.1 堆排序的思想 339
7.6.2 堆排序的实现 342
7.7 内排序方法分析 343
7.7.1 排序方法的下界 343
7.7.2 内排序方法的比较 345
7.8 线性时间复杂度的排序算法 346
7.8.1 计数排序 346
7.8.2 箱排序 347
7.8.3 基数排序 348
7.9 排序网络 351
7.9.1 排序网络的概念 351
7.9.2 巴彻尔奇偶归并排序 353
7.10 外部排序 356
7.10.1 外部排序方法 357
7.10.2 基于败者树的k路归并算法 357
7.10.3 排序-归并的改进 359
习题 363
参考文献 365