目 录 1
第一章抽象数据类型和算法描述 1
1.1抽象和实现 1
1.2术语和概念 3
1.3抽象数据类型 5
1.4算法分析 13
习题一 23
第二章线性表和数组 24
2.1抽象数据类型LIST 24
2.2线性表的实现 27
2.3特殊链表 37
2.4应用举例——模拟存储管理 40
2.5数组 51
习题二 56
第三章栈和队列 58
3.1栈的数据类型 58
3.2栈的实现 62
3.3队列 69
3.4算术表达式的计算 75
3.5习题三 80
第四章树 82
4.1树的基本概念和术语 83
4.2一般树 85
4.3二叉树 88
4.4遍历二叉树 95
4.5分类二叉树 102
4.6穿线二叉树 109
4.7最优二叉树 115
4.8堆和优先队列 120
4.9背包问题 125
习题四 131
第五章无向图 134
5.1基本概念 134
5.2抽象数据类型GRAPH 136
5.3图的表示和实现 137
5.4图的遍历 149
5.5生成树和最小代价生成树 152
5.6割点和双连通分量 161
5.7货郎担问题 164
习题五 168
第六章有向图 170
6.1有向图的概念和表示 170
6.2单源最短路径 171
6.3所有顶点间的最短路径和传递闭包 175
6.4强连通分量 178
6.5无圈有向图 180
习题六 184
第七章集合与查找技术 185
7.1抽象数据类型SET 185
7.2集合的表示和实现 187
7.3查找表 191
7.4散列技术 195
7.5 MERGE—FIND抽象数据类型 205
习题七 211
第八章分类 212
8.1分类的概念 212
8.2简单分类方法 213
8.3时间复杂性为O(Nlog2N)的比较型分类 219
8.4其他的比较型分类 231
8.5分布型分类 234
8.6外部分类 241
习题八 252
第九章文件 253
9.1文件的基本概念 253
9.2顺序文件 256
9.3索引文件 257
9.4散列文件 260
9.5多关键字文件 261
习题九 263
参考文献 264