第1章 绪论 1
1.1从问题到程序 1
1.1.1问题分析与抽象 2
1.1.2程序的设计与实现 4
1.2抽象数据类型 6
1.2.1什么是抽象数据类型 7
1.2.2意义与作用 7
1.2.3举例 8
1.3数据结构 9
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
习题 26
第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
小结 66
习题 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
习题 84
第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抽象数据类型 103
4.5队列的实现 103
4.5.1顺序表示 103
4.5.2链接表示 107
4.6队列的应用 109
小结 113
习题 115
第5章 二叉树与树 117
5.1二叉树及其抽象数据类型 117
5.1.1基本概念 117
5.1.2主要性质 120
5.1.3抽象数据类 123
5.2二叉树的周游 124
5.2.1什么是周游 124
5.2.2周游的分类 124
5.2.3一个例子 126
5.2.4周游的抽象算法 126
5.3二叉树的实现 132
5.3.1顺序表示 132
5.3.2链接表示 134
5.3.3线索二叉树 136
5.4二叉树的应用 140
5.4.1堆与优先队列 140
5.4.2哈夫曼树及其应用 145
5.5树及其抽象数据类型 151
5.5.1基本概念 152
5.5.2抽象数据类 153
5.5.3树的周游 154
5.6树的实现 157
5.6.1父指针表示法 157
5.6.2子表表示法 159
5.6.3长子-兄弟表示法 161
5.6.4树的其他表示法 162
5.7树林 163
5.7.1树林的周游 163
5.7.2树林的存储表示 163
5.7.3树林与二叉树的转换 164
小结 167
习题 167
第6章 集合与字典 170
6.1集合及其抽象数据类型 170
6.1.1基本概念 170
6.1.2主要运算 171
6.1.3抽象数据类型 172
6.2集合的实现 173
6.2.1集合的位向量表示 173
6.2.2集合的单链表表示 178
6.3字典及其抽象数据类型 181
6.3.1基本概念 181
6.3.2抽象数据类型 182
6.4字典的顺序表示 182
6.4.1存储结构 183
6.4.2算法的实现 183
6.4.3有序顺序表与二分法检索 184
6.5字典的散列表示 187
6.5.1基本概念 188
6.5.2散列函数 188
6.5.3碰撞的处理 190
6.5.4散列文件 196
小结 198
习题 199
第7章 高级字典结构 204
7.1字典与索引 204
7.1.1字典的索引 204
7.1.2索引的抽象 206
7.2字符树 206
7.2.1双链树表示 207
7.2.2多链表示 207
7.3二叉排序树 209
7.3.1二叉排序树 209
7.3.2二叉排序树的检索 210
7.3.3二叉排序树的插入和构造 210
7.3.4二叉排序树的删除 213
7.4最佳二叉排序树 216
7.4.1基本概念 216
7.4.2等概率的检索 218
7.4.3不等概的情况 219
7.5平衡二叉排序树 225
7.5.1基本概念 225
7.5.2调整平衡的模式 227
7.5.3实现 232
7.6索引文件 237
7.6.1多分树 237
7.6.2 B树 239
7.6.3 B+树 244
小结 247
习题 248
第8章 排序 252
8.1基本概念 252
8.2插入排序 253
8.2.1直接插入排序 253
8.2.2二分法插入排序 255
8.2.3表插入排序 257
8.2.4 Shell排序 259
8.3选择排序 261
8.3.1直接选择排序 261
8.3.2堆排序 262
8.4交换排序 266
8.4.1起泡排序 266
8.4.2快速排序 268
8.5分配排序 270
8.5.1概述 271
8.5.2基数排序 271
8.6归并排序 274
8.6.1内排序 274
8.6.2外排序 277
小结 283
习题 285
第9章图 287
9.1基本概念及其抽象数据类型 287
9.1.1基本概念 287
9.1.2抽象数据类型 291
9.2图的周游 292
9.2.1深度优先周游 293
9.2.2广度优先周游 294
9.3存储表示 295
9.3.1邻接矩阵表示法 296
9.3.2邻接表表示法 298
9.3.3两种表示的比较 299
9.4最小生成树 301
9.4.1最小生成树及其性质 302
9.4.2最小生成树的构造 303
9.5最短路径 309
9.5.1 Dijkstra算法 309
9.5.2 Floyd算法 312
9.6拓扑排序 315
9.6.1 AOV网 316
9.6.2拓扑排序 316
9.7关键路径 319
9.7.1 AOE网 320
9.7.2关键路径 320
小结 325
习题 326
第10章 算法分析与设计 329
10.1算法分析技术 329
10.1.1空间代价分析 329
10.1.2时间代价分析 331
10.2算法设计技术 335
10.2.1分治法 335
10.2.2贪心法 336
10.2.3动态规划法 339
10.2.4回溯法 344
10.2.5分枝界限法与0/1背包问题 347
小结 352
习题 353
索引 356
算法清单 363
参考文献 366