第1章 绪论 1
1.1 基本术语 1
1.2 抽象数据类型 4
1.3 算法及其评价 6
1.3.1 算法的定义 6
1.3.2 一个算法设计的例子 7
1.3.3 算法评估标准 10
1.3.4 算法效率的度量 10
1.3.5 空间复杂度 14
习题 14
第2章 线性表 16
2.1 线性表的抽象数据类型定义 16
2.2 顺序表 17
2.2.1 顺序表的插入算法 18
2.2.2 顺序表的删除算法 19
2.3 链表 20
2.3.1 单链表 21
2.3.2 循环链表 32
2.3.3 双向链表 35
2.4 多项式及其相加 39
2.4.1 多项式（polynomial）类的链表定义 39
2.4.2 多项式链表的相加 39
习题 41
第3章 数组和矩阵 43
3.1 数组 43
3.1.1 数组的顺序存储 43
3.1.2 数组的实现 43
3.2 矩阵 47
3.2.1 定义和操作 47
3.2.2 类Matrix 47
3.3 稀疏矩阵 49
3.3.1 稀疏矩阵的定义 50
3.3.2 稀疏矩阵的存储结构 50
3.3.3 稀疏矩阵的运算 53
习题 54
第4章 栈和队列 55
4.1 栈 55
4.1.1 栈的定义及其抽象数据类型 55
4.1.2 栈的存储结构 56
4.1.3 栈的基本操作及其实现 56
4.2 算术表达式的计算 57
4.2.1 算术表达式的表示方法 57
4.2.2 后缀表达式求值算法 58
4.2.3 把中缀表达式转换为后缀表达式的算法 60
4.3 队列 62
4.3.1 队列的定义及其抽象数据类型 62
4.3.2 队列的存储结构 63
4.3.3 队列的基本操作及其实现 64
4.3.4 应用举例 65
习题 69
第5章 递归 71
5.1 递归的概念 71
5.1.1 定义是递归的 72
5.1.2 数据结构是递归的 73
5.1.3 问题的解法是递归的 74
5.2 递归过程与递归工作栈 75
5.3 迷宫问题 78
习题 83
第6章 树 84
6.1 基本概念 84
6.2 二叉树（Binary Tree） 86
6.2.1 二叉树的定义、主要性质及抽象数据类型 86
6.2.2 二叉树的实现 89
6.3 二叉树遍历 94
6.3.1 二叉树遍历的递归算法 94
6.3.2 二叉树遍历的非递归算法 98
6.3.3 二叉树遍历的游标类（Tree Iterator） 99
6.4 线索化二叉树（Threaded Binary Tree） 105
6.4.1 线索的概念 105
6.4.2 中序线索化二叉树 105
6.4.3 前序与后序的线索化二叉树 111
6.5 堆（Heap） 112
6.5.1 堆的定义 112
6.5.2 堆的建立 113
6.5.3 堆的基本操作 115
6.6 树与森林 116
6.6.1 树的存储表示 116
6.6.2 树、森林与二叉树的转换 122
6.6.3 树和森林的遍历 123
6.7 二叉树的计数 126
6.8 霍夫曼树 127
6.8.1 霍夫曼树简介 128
6.8.2 霍夫曼编码 130
习题 131
第7章 图 134
7.1 图的基本概念 134
7.2 图的抽象数据类型 136
7.3 图的存储表示 137
7.3.1 数组表示法 137
7.3.2 邻接表法 139
7.3.3 十字链表法 141
7.4 图的遍历 142
7.4.1 深度优先遍历 143
7.4.2 广度优先遍历 144
7.5 图的生成树与最小生成树 145
7.6 拓扑排序 148
7.7 最短路径 151
7.7.1 单源最短路径 151
7.7.2 所有顶点对之间的最短路径 153
7.8 关键路径 154
习题 156
第8章 搜索 158
8.1 静态搜索结构 158
8.1.1 搜索的一般概念 158
8.1.2 静态搜索结构 159
8.1.3 顺序搜索 160
8.1.4 基于有序顺序表的折半搜索 162
8.1.5 基于有序顺序表的斐波那契搜索和插值搜索 165
8.2 二叉搜索树 167
8.2.1 定义 167
8.2.2 二叉搜索树基本操作 168
8.2.3 与二叉搜索树相关的中序游标类 172
8.3 最优二叉搜索树 174
8.3.1 扩充二叉搜索树 174
8.3.2 最优二叉搜索树 175
8.4 AVL树 179
8.4.1 AVL树的定义 179
8.4.2 平衡化旋转 180
8.4.3 AVL树的插入和删除 184
8.4.4 AVL树的高度 187
8.5 B＿树 189
8.5.1 B＿树的定义 189
8.5.2 B＿树的基本操作 189
8.6 散列索引 195
8.6.1 散列函数 197
8.6.2 解决冲突的方法 199
8.6.3 散列表分析 208
习题 209
第9章 排序 211
9.1 排序的基本概念 211
9.2 插入排序 214
9.2.1 直接插入排序 214
9.2.2 折半插入排序 216
9.2.3 希尔排序 217
9.3 选择排序 219
9.3.1 简单选择排序 219
9.3.2 树形选择排序 220
9.3.3 堆排序 221
9.4 交换排序 224
9.5 归并排序 228
9.6 基数排序 230
9.6.1 多关键字的排序 230
9.6.2 链式基数排序 231
9.7 各种内排序方法的比较 235
9.8 外部排序 235
9.8.1 多路平衡归并的实现 237
9.8.2 置换—选择排序（Replacement—Selection Sorting） 239
习题 242
参考文献 243