目录 1
第一章 引论 1
1.1概述 1
1.2SPARKS 5
1.3怎样建立程序 10
1.4怎样分析程序 18
参考书目和选读资料 23
习题 24
第二章 数组 27
2.1公理化 27
2.2有序表 27
2.3稀疏矩阵 35
2.4数组表示法 42
习题 45
第三章 栈和队列 52
3.1基本原理 52
3.2一个迷宫问题 58
3.3表达式的求值 62
3.4多重的栈和队列 67
习题 68
第四章 连接表 72
4.1单连接表 72
4.2连接的栈和队列 76
4.3存储池 77
4.4多项式加法 80
4.5再论连接表 86
4.6等价关系 88
4.7稀疏矩阵 92
4.8双连接表和动态存储管理 96
4.9广义表 104
4.10无用单元收集和压缩 112
4.11串——实例研究 121
4.11.1串的数据表示法 122
4.11.2字符串的模式匹配 126
4.12实现结点结构 131
参考书目和选读资料 134
习题 135
第五章 树 144
5.1基本术语 144
5.2二叉树 146
5.3二叉树的表示法 148
5.4二叉树的遍历 150
5.5再论二叉树 153
5.6线索二叉树 156
5.7树的二叉树表示法 159
5.8树的应用 162
5.8.1集合的表示法 162
5.8.2判定树 168
5.8.3对策树 169
5.9二叉树的计数 176
参考书目和选读资料 179
习题 180
第六章 图 184
6.1术语和表示法 184
6.1.1引论 184
6.1.2定义和术语 185
6.1.3图的表示法 187
6.2遍历、连通分支和生成树 190
6.3最短路径和传递闭包 196
6.4活动网络、拓扑排序和关键路径 202
6.5所有路径之枚举 212
参考书目和选读资料 215
习题 216
第七章 内排序 220
7.1查找 220
7.2插入排序 226
7.3快速排序 228
7.4排序可能达到的速度 230
7.52路合并排序 231
7.6堆阵排序 235
7.7多关键字排序 238
7.8关于内排序的实用考虑 241
参考书目和选读资料 248
习题 249
第八章 外排序 252
8.1存储设备 252
8.1.1磁带 252
8.1.2磁盘存储器 254
8.2磁盘排序 256
8.2.1k路合并 258
8.2.2平行操作的缓冲区处理 261
8.2.3顺串的生成 266
8.3磁带排序 268
8.3.1平衡合并排序 270
8.3.2多阶段合并 273
习题 276
8.3.3用不到3台磁带进行排序 276
参考书目和选读资料 276
第九章 符号表 278
9.1静态树表 279
9.2动态树表 288
9.3杂凑表 298
9.3.1杂凑函数 300
9.3.2溢出处理 303
9.3.3溢出技术的理论评价 307
参考书目和选读资料 308
习题 309
第十章 文件 312
10.1文件、查询和顺序组织 312
10.2索引技术 316
10.2.1柱面-盘面索引 317
10.2.2杂凑索引 319
10.2.3树形索引——B树 322
10.2.4Trie索引 333
10.3文件组织 337
10.3.1顺序组织 337
10.3.2随机组织 337
10.3.3连接组织 339
10.3.4倒排文件 341
10.3.5单元式分划 342
10.4存储管理 343
参考书目和选读资料 344
习题 344
附录 ASPARKS 349