第一章 引言 1
1 软件的研制与程序设计方法学 1
1.1 软件的研制 1
1.2 大规模程序设计与软件危机 3
1.3 程序设计方法学的意义、目标与内容 4
2 程序与程序设计的概念 6
2.1 程序与程序设计语言 6
2.2 程序设计风格 7
2.2.1 冯·诺伊曼型程序设计 7
2.2.2 函数型程序设计 8
2.2.3 逻辑型程序设计 11
2.3 程序的设计表示法 16
2.3.1 流程图 16
2.3.2 程序之设计语言PDL 19
2.4 程序设计的基本手段 21
习题 22
第二章 程序结构分析 23
1 程序的数据结构 23
1.1 数据类型抽象 23
1.2 类型扩充手段 24
1.3 数据类型概念的进一步抽象 28
2 程序的控制结构 30
2.1 基本控制成份的抽象 30
2.2 基本控制结构 30
2.3 其他的控制结构 32
3 程序的复杂性 34
3.1 量度程序复杂性的必要性 34
3.2 程序复杂性的若干量度技术 35
3.2.1 控制结构复杂性 35
3.2.2 整体复杂性 37
3.2.3 程序复杂性量度的进一步改进 39
3.3 简评 41
4 结构化程序 41
4.1 结构化程序及其特征 41
4.2 结构化程序的阅读与书写 46
4.2.1 结构化程序的阅读 46
4.2.2 结构化程序的书写 48
习题 50
第三章 程序的功能描述 51
1 概况 51
1.1 程序功能描述的需要 51
1.2 若干概念 52
2 程序功能描述技术 54
2.1 代数功能描述 54
2.1.1 例 54
2.1.2 名称的由来 57
2.1.3 代数技术中要注意的几个问题 58
2.1.4 代数功能描述之书写指导 60
2.2 状态机功能描述 61
2.2.1 例 61
2.2.2 状态机功能描述与安全性的确认 63
2.2.3 状态机技术的几个问题 65
2.2.4 状态机功能描述之书写指导 65
2.3 比较 67
习题 68
第四章 程序的正确性证明 69
1 前言 69
1.1 程序正确性证明的概念 69
1.2 广义归纳法 71
2 程序正确性证明方法 71
2.1 归纳断语法 71
2.2 结构归纳法 75
3 程序完全正确性的证明 78
4 讨论 80
习题 81
第五章 程序设计的基本策略 84
1 大型程序之设计 84
2 程序的逐步精化 84
2.1 设计方法与原则 84
2.2 逐步精化之例 89
2.3 讨论 90
3 模块程序设计 93
3.1 概况 93
3.2 模块程序设计之例 94
3.3 与模块程序设计相关的一些问题 99
3.3.1 模块定义好坏的衡量标准 99
3.3.2 分块编译问题 100
3.3.3 现有非模块化程序设计语言与模块程序设计 101
3.3.4 模块库的建设 102
4 关于结构程序设计 102
4.1 概况 102
4.2 关于goto语句的讨论 104
4.2.1 程序易读性与结构清晰性 104
4.2.2 功效 105
4.2.3 讨论 106
习题 107
第六章 程序的设计技术 108
1 递归程序设计技术 108
1.1 递归的概念 108
1.2 递归数据结构 110
1.3 递归程序的设计及其正确性 113
1.3.1 递归程序的设计 113
1.3.2 递归程序设计的正确性 113
1.4 化递归为迭代 117
2 其他设计技术——面向对象的设计技术 119
2.1 基本思想与步骤 119
2.2 例 120
习题 124
第七章 程序的形式推导 125
1 自然演绎系统 125
1.1 命题 125
1.2 推理规则 128
1.3 自然演绎系统 129
1.4 自然演绎系统证明之开发 134
2 最弱前置条件 135
2.1 谓词 135
2.2 WP(S,R)的引进及其某些性质 137
2.3 WP(S,R)之计算 139
2.3.1 正文替换 139
2.3.2 若干简单情形WP(S,R)的计算 139
3 程序设计语言控制成分的形式定义 142
3.1 警卫与警卫命令 142
3.2 选择结构的形式定义 145
3.3 迭代结构的形式定义 147
4 程序的形式推导 151
4.1 简单程序推导之例 151
4.2 循环程序的推导 153
4.2.1 基于循环不变式与界函数的程序推导 153
4.2.2 循环不变式的研制 155
4.2.3 循环界函数的确定 158
习题 159
第八章 程序的功效 160
1 概述 160
1.1 功效考虑 160
1.2 实现高功效的途径 160
2 编译时刻优化 161
2.1 合并常量运算 162
2.2 消去公共子表达式 162
2.3 外提不变表达式 163
2.4 强度削减 163
3 化递归为迭代 164
3.1 尾调用及其消去 164
3.2 尾递归及其消去 165
3.3 一般递归 167
4 其他方面的优化 169
4.1 测试结构的简化处理 169
4.2 应用于说明的优化 172
第九章 程序设计工具 173
1 引言 173
1.1 程序设计工具与程序设计方法学 173
1.2 程序设计工具的种类 174
2 程序设计工具简介 175
2.1 设计描述工具 175
2.2 编辑工具 176
2.2.1 编辑程序 176
2.2.2 语法制导的正文编辑程序 176
2.3 格式化工具 177
2.4 重构造工具 177
2.5 翻译工具 177
2.5.1 语言预处理程序 178
2.5.2 翻译程序 178
2.5.3 转换工具 179
2.6 调试工具 180
2.7 程序复杂性量度工具 180
2.8 程序验证工具 180
2.9 变换工具 180
总复习思考题 181
参考文献 183