章基本符号1
1.1简单值1
1.2标识符和表达式3
1.3函数和过程4
1.4算术函数5
1.4.1加法5
1.4.2减法5
1.4.3乘法6
1.4.4除法6
1.4.5幂运算7
1.4.6过程总结7
1.5过程调用9
1.6λ表达式10
1.6.1变元过程11
1.6.2构建列表13
1.6.3返回多个值13
1.6.4没有结果的计算14
1.7谓词15
1.7.1分类谓词16
1.7.2相等谓词16
1.7.3相等和类型16
1.8条件类型表达式19
1.8.1条件表达式19
1.8.2合取表达式与析取表达式19
1.9定义21
1.9.1过程定义21
1.9.2递归定义22
1.10局部绑定23
1.10.1局部过程24
1.10.2局部递归24
1.10.3收纳表达式25
第2章工具箱27
2.1列表映射27
2.2常量过程28
2.3过程节选29
2.3.1invoke过程30
2.3.2卡瑞化31
2.4耦合器32
2.4.1过程复合32
2.4.2并行应用33
2.4.3调度34
2.5适配器35
2.5.1选择35
2.5.2重排36
2.5.3预处理和后处理36
2.6递归管理器38
2.6.1recur过程39
2.6.2递归谓词40
2.6.3迭代41
2.7欧几里得算法44
2.8高阶布尔过程47
2.8.1布尔值和谓词上的操作47
2.8.2^if过程47
2.9自然数和递归49
2.9.1数学归纳法49
2.9.2自然数上的递归49
2.9.3计数53
2.9.4有界推广54
第3章数据结构56
3.1建模56
3.2空值57
3.3和类型57
3.3.1枚举57
3.3.2可区分并集58
3.3.3递归类型方程59
3.4有序对60
3.4.1命名对61
3.4.2积类型61
3.4.3再议可区分并集62
3.4.4重新实现自然数62
3.5盒64
3.6列表66
3.6.1选择过程67
3.6.2同构列表68
3.6.3列表的递归过程69
3.6.4列表归纳原理70
3.6.5列表递归管理71
3.6.6展开73
3.7列表算法77
3.7.1元数扩展77
3.7.2筛选和划分79
3.7.3子列表80
3.7.4位置选择81
3.7.5列表元素上的谓词扩展到列表82
3.7.6转置、压缩和解压缩83
3.7.7聚合多个结果84
3.8源89
3.9多元组98
3.9.1建立模型99
3.9.2记录类型99
3.10树101
3.10.1树归纳原理103
3.10.2树递归管理103
3.11灌木109
3.11.1灌木归纳原理110
3.11.2灌木递归管理110
3.12包113
3.12.1基本包过程114
3.12.2包操作115
3.12.3包递归管理116
3.13等价关系120
3.14集合123
3.14.1集合递归管理124
3.14.2筛选和划分125
3.14.3其他集合运算126
3.14.4并集、交集和差集127
3.15表132
3.16缓冲区138
第4章排序142
4.1序关系142
4.1.1隐式定义的等价关系142
4.1.2测试一个列表是否有序143
4.1.3查找极值143
4.1.4复合序关系145
4.1.5字典序145
4.2排序算法148
4.2.1插入排序149
4.2.2选择排序149
4.2.3快速排序150
4.2.4归并排序150
4.3二叉搜索树153
4.3.1测试二叉搜索树不变量154
4.3.2从二叉搜索树中提取一个值155
4.3.3二叉搜索树排序156
4.4红黑树158
4.4.1实现红黑树159
4.4.2颜色翻转和旋转160
4.4.3插入161
4.4.4查找163
4.4.5删除163
4.4.6用红黑树实现表168
4.5堆175
4.5.1折叠和展开堆178
4.5.2堆排序178
4.6序统计量181
第5章组合构造183
5.1笛卡儿积183
5.1.1笛卡儿积排序185
5.1.2排位和去排位186
5.2列表选择189
5.2.1子列表189
5.2.2分组193
5.2.3子序列和选择194
5.3包选择199
5.4排列201
5.5划分204
5.5.1包划分204
5.5.2划分自然数206
第6章图208
6.1图的实现208
6.1.1图的构造209
6.1.2图与关系211
6.1.3图的性质212
6.1.4其他图访问方法213
6.1.5无向图215
6.2深度优先遍历221
6.2.1图的遍历221
6.2.2深度优先222
6.2.3拓扑排序223
6.2.4可到达结点223
6.3路径225
6.4广度优先遍历227
6.5生成树229
6.6最短路径233
6.6.1Bellman-Ford算法233
6.6.2Dijkstra算法234
6.6.3Floyd-Warshall算法235
6.7流网络239
第7章子列表搜索244
7.1简单低效的算法244
7.2Knuth-Morris-Pratt算法246
7.3Boyer-Moore算法253
7.4Rabin-Karp算法255
附录A推荐读物260
附录B(afpprimitives)库261
附录C如何使用AFP库263
· · · · · · (收起)