目录
第1章 绪论1
1.1 基本概念1
1.2 算法描述11
1.3 算法评价13
本章小结19
习题120
第2章 集合24
2.1 集合的定义和运算24
2.1.1 集合的定义24
2.1.2 集合的抽象数据类型25
2.1.3 集合运算举例26
2.2 集合的顺序存储结构和操作实现27
2.3 集合的链接存储结构和操作实现34
2.3.1 链接存储的概念34
2.3.2 链接集合类的定义和实现36
2.4 集合应用举例42
本章小结49
习题249
第3章 线性表52
3.1 线性表的定义和运算52
3.1.1 线性表的定义52
3.1.2 线性表的抽象数据类型53
3.1.3 线性表运算举例55
3.2 线性表的顺序存储和操作实现56
3.3 有序线性表的定义和实现65
3.4 链接存储的一般概念和方法70
3.5 线性表的链接存储和操作实现74
3.6 有序线性表的链接存储和操作实现81
3.7 多项式计算84
3.7.1 多项式表示与求值84
3.7.2 两个多项式相加87
3.8 稀疏矩阵90
3.8.1 稀疏矩阵的定义90
3.8.2 稀疏矩阵的转置运算93
3.8.3 稀疏矩阵的加法运算95
本章小结99
习题3100
第4章 栈和队列108
4.1 栈的定义和运算108
4.1.1 栈的定义108
4.1.2 栈的抽象数据类型109
4.1.3 栈的运算举例109
4.2 栈的顺序存储结构和操作实现110
4.3 栈的链接存储结构和操作实现113
4.4 栈的简单应用举例115
4.5 栈与递归119
4.6 算术表达式的计算127
4.6.1 算术表达式的两种表示127
4.6.2 后缀表达式求值的算法128
4.6.3 把中缀表达式转换为后缀表达式的算法131
4.7 队列134
4.7.1 队列的定义134
4.7.2 队列的抽象数据类型135
4.7.3 队列的顺序存储结构和操作实现136
4.7.4 队列的链接存储结构和操作实现141
本章小结142
习题4143
第5章 树和二叉树147
5.1 树的概念147
5.1.1 树的定义147
5.1.2 树的表示148
5.1.3 树的基本术语148
5.1.4 树的性质149
5.2 二叉树151
5.2.1 二叉树的定义151
5.2.2 二叉树的性质151
5.2.3 二叉树的抽象数据类型153
5.2.4 二叉树的存储结构154
5.3 二叉树遍历159
5.4 二叉树其他运算162
5.5 二叉搜索树167
5.5.1 二叉搜索树的定义167
5.5.2 二叉搜索树的抽象数据类型和链接存储类167
5.5.3 二叉搜索树的运算方法168
5.6 堆175
5.6.1 堆的定义175
5.6.2 堆的抽象数据类型和接口类176
5.6.3 堆的存储结构和顺序存储类177
5.6.4 堆的运算178
本章小结182
习题5183
第6章 图188
6.1 图的概念188
6.1.1 图的定义188
6.1.2 图的基本术语189
6.2 图的存储结构192
6.2.1 邻接矩阵192
6.2.2 邻接表193
6.2.3 边集数组195
6.3 图的抽象数据类型和接口类196
6.4 图的邻接矩阵和邻接表存储类197
6.5 图的遍历199
6.5.1 深度优先搜索遍历200
6.5.2 广度优先搜索遍历202
6.5.3 非连通图的遍历204
6.6 对图的其他运算的算法205
6.7 图的生成树和最小生成树215
6.7.1 生成树的概念215
6.7.2 普里姆算法217
6.7.3 克鲁斯卡尔算法221
本章小结225
习题6225
第7章 查找229
7.1 查找的基本概念229
7.2 顺序表查找230
7.2.1 顺序查找231
7.2.2 二分查找232
7.3 索引查找235
7.3.1 索引的概念235
7.3.2 索引查找算法238
7.4 散列查找240
7.4.1 散列的概念240
7.4.2 散列函数241
7.4.3 处理冲突的方法243
7.4.4 散列表的运算247
7.5 B树查找256
7.5.1 B_树的定义256
7.5.2 B_树查找257
7.5.3 B_树的插入259
7.5.4 B_树的删除263
7.5.5 定义B_树的类264
本章小结267
习题7268
第8章 排序272
8.1 排序的基本概念272
8.2 插入排序274
8.3 选择排序275
8.3.1 直接选择排序275
8.3.2 堆排序276
8.4 交换排序280
8.4.1 气泡排序280
8.4.2 快速排序282
8.5 归并排序285
8.6 外排序289
8.6.1 外排序概念289
8.6.2 外排序算法290
本章小结298
习题8299附录A 习题中部分算法设计题参考解答302参考文献310