第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 算法的评价标准和评价方法 10
1.2.3 计算时间复杂性的一般方法 14
习题 16
第2章 表结构 20
2.1 基本概念和存储方法 20
2.1.1 基本概念 20
2.1.2 存储方法 22
2.2 顺序表 25
2.2.1 插入和删除 25
2.2.2 查找 27
2.3 链表 31
2.3.1 基本概念和链操作方法 31
2.3.2 链表的种类 36
2.3.3 链表的构造 39
2.3.4 链表的遍历 42
2.3.5 链表的插入和删除 44
2.4 栈和队 50
2.4.1 基本概念 50
2.4.2 进栈和退栈算法 52
2.4.3 进队和出队算法 56
2.4.4 应用举例 60
2.5 静态链表 62
2.5.1 静态链表的一般原理和操作方法 62
2.5.2 静态链表的应用 65
2.5.3 单链域的双向链表 69
2.6 矩阵 72
2.6.1 基本概念和存储方法 72
2.6.2 稀疏矩阵运算示例 76
2.7 字符串 81
2.7.1 基本概念和存储方法 81
2.7.2 简单模式匹配算法 83
2.7.3 KMP算法 85
2.7.4 BM算法和KR算法 90
2.8 广义表 93
2.9 目录存储和索引目录存储 95
习题 97
第3章 树结构 116
3.1 基本概念和存储方法 116
3.1.1 普通树的基本概念 116
3.1.2 二叉树的基本概念 120
3.1.3 普通树与二叉树的相互转换 124
3.1.4 树的存储方法 126
3.2 二叉树的遍历和构造 129
3.2.1 二叉树的遍历 129
3.2.2 遍历序列的前驱和后继 133
3.2.3 遍历的应用示例 135
3.2.4 二叉树的构造 138
3.2.5 非递归的遍历算法 142
3.3 检索树 144
3.3.1 检索树的查找 144
3.3.2 检索树的插入和构造 146
3.3.3 检索树的删除 148
3.4 哈夫曼树 152
3.4.1 哈夫曼算法 152
3.4.2 哈夫曼树的构造和应用 153
3.5 判定树 156
习题 159
第4章 图结构 170
4.1 基本概念 170
4.1.1 图的定义和种类 170
4.1.2 有关术语 171
4.2 图的存储方法 174
4.2.1 号名对照表 174
4.2.2 邻接矩阵的顺序存储 175
4.2.3 邻接表 176
4.2.4 邻按表的变种 178
4.3 图的遍历 179
4.3.1 先深搜索 180
4.3.2 先深搜索的应用 184
4.3.3 先广搜索 187
4.4 无向图的双连通性 189
4.4.1 关节点 189
4.4.2 找关节点的算法 190
4.5 最小生成树 193
4.5.1 Kruskal算法 194
4.5.2 Prim算法 199
4.6 最短路径 202
4.6.1 Dijkstra算法 202
4.6.2 Floyd算法 206
4.7 有向无回路图 208
4.7.1 基本概念 208
4.7.2 拓扑排序 210
4.7.3 关键路径 213
习题 217
第5章 集合运算的数据结构 227
5.1 集合的基本运算 227
5.2 散列表 229
5.2.1 散列函数 229
5.2.2 散列表的处理算法 233
5.2.3 散列表的性能分析 236
5.3 最优检索树 239
5.4 平衡树 243
5.4.1 AVL树 243
5.4.2 红黑树 251
5.4.3 B树 260
5.4.4 B＋树 263
5.4.5 Trie树 267
5.5 union-find运算 269
5.5.1 树结构的union-find算法 269
5.5.2 表结构的union-find算法 272
习题 275
第6章 排序 279
6.1 基本概念 279
6.2 插入排序 280
6.2.1 直接插入排序 280
6.2.2 二分插入排序 283
6.2.3 希尔排序 284
6.3 交换排序 287
6.3.1 冒泡排序 288
6.3.2 快速排序 290
6.4 选择排序 296
6.4.1 一般原理和效率分析 296
6.4.2 树选排序 297
6.4.3 堆排序 298
6.5 合并排序 304
6.5.1 递归的合并排序 304
6.5.2 非递归的合并排序 306
6.6 基数排序 309
6.6.1 基本原理和示例 309
6.6.2 算法的实现和分析 312
6.7 外部排序 314
6.7.1 文件的组织结构 314
6.7.2 顺串的合并 318
6.7.3 初始顺串的生成 327
6.7.4 最佳合并树 329
6.7.5 磁带排序 331
习题 333
第7章 问题的固有难度和算法设计的一般方法 343
7.1 问题的固有难度 343
7.1.1 算法的重要地位 343
7.1.2 问题的固有难度 344
7.2 不确定性算法和NP-完全问题 347
7.2.1 不确定性算法 347
7.2.2 三大重要的问题类 349
7.3 算法设计的一般方法 351
7.3.1 递归、分治和平衡 351
7.3.2 贪心法 357
7.3.3 动态规划法 359
7.3.4 搜索-回溯法 361
习题 364
第8章 数据结构的类实现 367
8.1 表结构的类 367
8.1.1 栈类和队类 367
8.1.2 顺序表类 369
8.1.3 链表类 372
8.1.4 用模板实现链表类 376
8.2 树结构的类 379
8.2.1 二叉树类 379
8.2.2 检索树类 381
8.3 图结构的类 384
习题 388
附录 389
附录A 名词中英文对照索引 389
附录B 部分习题参考答案 398
参考文献 410