1 绪论 1
1.1 从问题到程序 1
1.1.1 问题分析与抽象 2
1.1.2 程序的设计与实现 3
1.2 抽象数据类型 6
1.2.1 什么是抽象数据类型 6
1.2.2 意义与作用 7
1.2.3 举例 7
1.3 数据结构 8
1.3.1 什么是数据结构 9
1.3.2 数据结构的分类 10
1.3.3 结点与结构 12
1.3.4 外存数据的组织 13
1.4 算法 16
1.4.1 什么是算法 16
1.4.2 算法的设计 17
1.4.3 算法的精化 18
1.4.4 算法的分析 21
小结 25
习题 27
2 线性表 29
2.1 基本概念与抽象数据类型 29
2.1.1 基本概念 29
2.1.2 抽象数据类型 30
2.2 顺序表示 31
2.2.1 存储结构 31
2.2.2 运算的实现 33
2.2.3 分析与评价 36
2.2.4 顺序表空间的扩展 38
2.3 链接表示 39
2.3.1 单链表表示 39
2.3.2 单链表上运算的实现 41
2.3.3 分析与比较 44
2.3.4 单链表的改进和扩充 45
2.4 应用举例 48
2.4.1 Josephus问题 48
2.4.2 采用顺序表模拟 49
2.4.3 采用循环链表模拟 50
2.5 矩阵 53
2.5.1 矩阵的顺序表示 53
2.5.2 稀疏矩阵的表示方法 54
2.6 广义表与动态存储管理 57
2.6.1 广义表 58
2.6.2 结点的动态分配与回收 60
2.6.3 废料收集与存储压缩 64
小结 65
习题 66
3 字符串 69
3.1 字符串及其抽象数据类型 69
3.1.1 基本概念 69
3.1.2 抽象数据类型 70
3.2 字符串的实现 71
3.2.1 顺序表示 71
3.2.2 链接表示 72
3.3 模式匹配 75
3.3.1 朴素的模式匹配 75
3.3.2 无回溯的模式匹配 77
小结 83
习题 83
4 栈与队列 85
4.1 栈及其抽象数据类型 85
4.1.1 基本概念 85
4.1.2 抽象数据类型 86
4.2 栈的实现 86
4.2.1 顺序表示 86
4.2.2 链接表示 89
4.3 栈的应用 91
4.3.1 栈与递归 92
4.3.2 迷宫问题 96
4.3.3 表达式计算 100
4.4 队列及其抽象数据类型 102
4.4.1 基本概念 102
4.4.2 抽象数据类型 102
4.5 队列的实现 103
4.5.1 顺序表示 103
4.5.2 链接表示 106
4.6 队列的应用 109
小结 113
习题 114
5 二叉树与树 117
5.1 二叉树及其抽象数据类型 117
5.1.1 基本概念 117
5.1.2 主要性质 120
5.1.3 抽象数据类型 122
5.2 二叉树的周游 123
5.2.1 什么是周游 123
5.2.2 周游的分类 124
5.2.3 一个例子 125
5.2.4 周游的抽象算法 126
5.3 二叉树的实现 131
5.3.1 顺序表示 131
5.3.2 链接表示 133
5.3.3 线索二叉树 135
5.4 二叉树的应用 139
5.4.1 堆与优先队列 139
5.4.2 哈夫曼树及其应用 144
5.5 树及其抽象数据类型 151
5.5.1 基本概念 151
5.5.2 抽象数据类型 152
5.5.3 树的周游 153
5.6 树的实现 156
5.6.1 父指针表示法 156
5.6.2 子表表示法 158
5.6.3 长子-兄弟表示法 160
5.6.4 树的其他表示法 161
5.7 树林 162
5.7.1 树林的周游 162
5.7.2 树林的存储表示 162
5.7.3 树林与二叉树的转换 163
小结 165
习题 166
6 集合与字典 169
6.1 集合及其抽象数据类型 169
6.1.1 基本概念 169
6.1.2 主要运算 170
6.1.3 抽象数据类型 171
6.2 集合的实现 172
6.2.1 集合的位向量表示 172
6.2.2 集合的单链表表示 177
6.3 字典及其抽象数据类型 180
6.3.1 基本概念 180
6.3.2 抽象数据类型 181
6.4 字典的顺序表示 181
6.4.1 存储结构 181
6.4.2 算法的实现 182
6.4.3 有序顺序表与二分法检索 183
6.5 字典的散列表示 186
6.5.1 基本概念 186
6.5.2 散列函数 187
6.5.3 碰撞的处理 189
6.5.4 散列文件 195
小结 197
习题 198
7 高级字典结构 200
7.1 字典与索引 200
7.1.1 字典的索引 200
7.1.2 索引的抽象 201
7.2 字符树 202
7.2.1 双链树表示 203
7.2.2 多链表示 203
7.3 二叉排序树 205
7.3.1 二叉排序树 205
7.3.2 二叉排序树的检索 206
7.3.3 二叉排序树的插入和构造 206
7.3.4 二叉排序树的删除 209
7.4 最佳二叉排序树 211
7.4.1 基本概念 211
7.4.2 等概率的检索 213
7.4.3 不等概的情况 214
7.5 平衡二叉排序树 220
7.5.1 基本概念 220
7.5.2 调整平衡的模式 221
7.5.3 实现 226
7.6 索引文件 232
7.6.1 多分树 232
7.6.2 B树 234
7.6.3 B＋树 239
小结 242
习题 243
8 排序 245
8.1 基本概念 245
8.2 插入排序 246
8.2.1 直接插入排序 246
8.2.2 二分法插入排序 249
8.2.3 表插入排序 251
8.2.4 Shell排序 252
8.3 选择排序 254
8.3.1 直接选择排序 254
8.3.2 堆排序 255
8.4 交换排序 259
8.4.1 起泡排序 259
8.4.2 快速排序 261
8.5 分配排序 263
8.5.1 概述 264
8.5.2 基数排序 264
8.6 归并排序 267
8.6.1 内排序 267
8.6.2 外排序 270
小结 276
习题 278
9 图 280
9.1 基本概念及其抽象数据类型 280
9.1.1 基本概念 280
9.1.2 抽象数据类型 283
9.2 图的周游 285
9.2.1 深度优先周游 285
9.2.2 广度优先周游 287
9.3 存储表示 288
9.3.1 邻接矩阵表示法 289
9.3.2 邻接表表示法 291
9.3.3 两种表示的比较 292
9.4 最小生成树 293
9.4.1 最小生成树及其性质 294
9.4.2 最小生成树的构造 295
9.5 最短路径 300
9.5.1 Dijkstra算法 301
9.5.2 Floyd算法 304
9.6 拓扑排序 307
9.6.1 AOV网 307
9.6.2 拓扑排序 308
9.7 关键路径 311
9.7.1 AOE网 311
9.7.2 关键路径 312
小结 316
习题 317
10 算法分析与设计 320
10.1 算法分析技术 320
10.1.1 空间代价分析 320
10.1.2 时间代价分析 322
10.2 算法设计技术 326
10 2.1 分治法 326
10.2.2 贪心法 327
10.2 3 动态规划法 330
10.2 4 回溯法 335
10.2.5 分枝界限法与0/1背包问题 338
小结 342
习题 343
参考文献 345
索引 346
算法清单 355
后记 358