第1章 概述 1
1.1 数据结构的概念 1
1.1.1 问题的求解过程 1
1.1.2 数据和数据结构的意义 2
1.2 算法的描述和实现 3
1.3 算法的评价方法 6
1.3.1 评价标准 6
1.3.2 算法的时间复杂性 7
1.3.3 最坏情况和平均情况 9
1.3.4 计算时间复杂性的一般方法 10
1.3.5 算法的选用原则 12
1.4 算法设计的一般方法 12
1.4.1 递归 12
1.4.2 分治和平衡 16
1.4.3 动态规划 19
1.4.4 贪心法 21
1.4.5 搜索-回溯法 23
习题一 25
2.1.1 术语 27
2.1.2 存储方式 27
第2章 表结构 27
2.1 表结构的概念 27
2.1.3 表结构的运算 31
2.2 顺序表的运算 32
2.2.1 插入和删除 32
2.2.2 查找 33
2.3 链表 38
2.3.1 链表的基本操作 38
2.3.2 链表的种类 43
2.3.3 链表的构造和遍历 44
2.3.4 链表的插入和删除 48
2.4.1 概念 51
2.4 栈和队 51
2.4.2 栈和队的插入删除 52
2.4.3 栈的应用 59
2.5 静态链表 62
2.5.1 静态链表的定义 62
2.5.2 自由队列 64
2.5.3 静态链表的插入删除操作 65
2.5.4 多表共享空间 66
2.5.5 不带数据域的静态链表 67
2.6 矩阵运算 68
2.6.1 矩阵的存储 68
2.6.2 稀疏矩阵的转置 71
2.6.3 稀疏矩阵的乘法 74
2.6.4 稀疏矩阵的链式存储 77
2.7 字符串 78
2.7.1 字符串的运算和存储方法 78
2.7.2 简单的模式匹配算法 80
2.7.3 KMP算法 82
2.7.4 其他模式匹配算法 88
2.8 表结构的其他存储形式 91
2.8.1 目录存储和索引目录存储 91
2.8.2 单链域的双向链表 94
习题二 96
3.1.1 术语 103
第3章 树结构 103
3.1 树结构的概念 103
3.1.2 树的存储方式 107
3.2 二叉树 108
3.2.1 二叉树的概念和基本性质 108
3.2.2 特殊二叉树 110
3.2.3 二叉树的存储方式 113
3.2.4 树和森林与二叉树的相互转换 114
3.3 二叉树的遍历 116
3.3.1 遍历方法 116
3.3.2 递归的遍历算法 118
3.3.3 遍历算法的应用 121
3.3.4 遍历序列的性质 123
3.3.5 非递归的遍历算法 125
3.4 二叉树的构造 128
3.4.1 树的唯一性 128
3.4.2 用先序序列和中序序列构造二叉树 130
3.4.3 用扩充先序序列构造二叉树 131
3.5 检索树 132
3.5.1 检索树的查找 132
3.5.2 检索树的插入和构造 134
3.5.3 检索树的删除 136
3.6 平衡树 140
3.6.1 平衡树的概念 140
3.6.2 平衡树的插入 141
3.6.3 平衡树的删除 146
3.7 红黑树 151
3.7.1 红黑树的概念 151
3.7.2 红黑树的旋转 154
3.7.3 红黑树的插入 155
3.7.4 红黑树的删除 159
3.8 哈夫曼树 163
3.8.1 编码和编码树 163
3.8.2 哈夫曼算法 166
3.9 判定树 169
习题三 173
第4章 图结构 180
4.1 图的概念和存储结构 180
4.1.1 图的概念 180
4.1.2 图的存储结构 184
4.2 先深搜索和先广搜索 191
4.2.1 先深搜索 191
4.2.2 先深搜索的简单应用 195
4.2.3 先广搜索 198
4.3.1 关节点 199
4.3 无向连通图的双连通分量 199
4.3.2 找关节点的算法 201
4.4 最小生成树 203
4.4.1 Kruskal算法 204
4.4.2 Prim算法 208
4.5 最短路径 211
4.5.1 单源最短路径 211
4.5.2 每对顶点之间的最短路径 214
4.6 有向无回路图 216
4.6.1 基本概念 216
4.6.2 拓扑排序 218
4.6.3 关键路径 221
习题四 224
第5章 排序 227
5.1 基本概念 227
5.2 插入排序 228
5.2.1 直接插入排序 229
5.2.2 二分插入排序 231
5.2.3 希尔排序 232
5.3 交换排序 235
5.3.1 汽泡排序 235
5.3.2 快速排序 237
5.4 选择排序 242
5.4.1 树选排序 243
5.4.2 堆排序 244
5.5 合并排序 250
5.5.1 递归的合并排序 250
5.5.2 非递归的合并排序 252
5.6 基数排序 254
5.7 外部排序 259
5.7.1 多路合并 260
5.7.2 胜者树和败者树 262
5.7.3 替代选择算法 264
5.7.4 初始顺串的生成 267
5.7.5 最佳合并树 270
5.7.6 磁带排序 271
习题五 274
第6章 集合运算 279
6.1 集合的基本运算 279
6.2 散列表 281
6.2.1 散列函数 281
6.2.2 散列表的构造 284
6.2.3 散列表的性能分析 286
6.3 最优检索树 288
6.4.1 2-3树 292
6.4 平衡树模式 292
6.4.2 B树和B+树 294
6.4.3 键树 297
6.5 不相交集合的合并 298
6.5.1 问题的背景 298
6.5.2 树结构的union-find算法 299
6.5.3 表结构的union-find算法 302
习题六 304
第7章 类结构 306
7.1 表结构的类 306
7.1.1 栈类和队类 306
7.1.2 顺序表类 308
7.1.3 链表类 310
7.2 树结构的类 317
7.2.1 二叉树类 317
7.2.2 检索树类 319
7.2.3 平衡树类 322
7.3 图结构的类 325
7.3.1 图的存储 325
7.3.2 先深搜索 326
7.3.3 拓扑排序 328
习题七 328
8.1.1 算法的重要性 330
第8章 NP完全问题简介 330
8.1 问题的时间复杂性 330
8.1.2 问题的固有难度 331
8.2 不确定性算法和NP问题 333
8.2.1 不确定性算法 333
8.2.2 P问题类和NP问题类 334
8.3 NP完全问题类 336
8.3.1 NP完全问题的定义 336
8.3.2 问题的NP完全性证明 337
习题八 339
参考文献 340