计算机科学的基础

第 1 章 计算机科学：将抽象机械化........... 1

1.1 本书主要内容 ........................................... 3

1.1.1 数据模型 ....................................... 3

1.1.2 数据结构 ....................................... 4

1.1.3 算法 ............................................... 4

1.1.4 基本思路 ....................................... 4

1.2 本章主要内容 ........................................... 4

1.3 数据模型 ................................................... 5

1.3.1 编程语言数据模型........................ 5

1.3.2 系统软件的数据模型.................... 6

1.3.3 电路的数据模型 ........................... 7

1.3.4 习题 ............................................. 10

1.4 C语言数据模型....................................... 10

1.4.1 C语言类型系统........................... 11

1.4.2 函数 ............................................. 14

1.4.3 C语言数据模型中的操作........... 14

1.4.4 数据对象的创建和销毁.............. 14

1.4.5 数据的访问和修改...................... 15

1.4.6 数据的组合 ................................. 15

1.4.7 习题 ............................................. 16

1.5 算法和程序设计 ..................................... 16

1.5.1 软件的创建 ................................. 16

1.5.2 编程风格 ..................................... 17

1.6 本书中用到的一些C语言约定 ............... 17

1.7 小结 ......................................................... 19

1.8 参考文献 ................................................. 19

第 2 章 迭代、归纳和递归........................... 20

2.1 本章主要内容 ......................................... 21

2.2 迭代 ......................................................... 22

2.2.1 排序 ............................................. 22

2.2.2 选择排序：一种迭代排序

算法 ............................................. 23

2.2.3 习题 ............................................. 27

2.3 归纳证明 ................................................. 27

2.3.1 归纳证明为何有效...................... 29

2.3.2 检错码 ......................................... 30

2.3.3 习题............................................. 33

2.4 完全归纳 ................................................. 35

2.4.1 使用多个依据情况进行归纳...... 35

2.4.2 验证完全归纳 ............................. 36

2.4.3 算术表达式的规范形式 ............. 36

2.4.4 习题............................................. 40

2.5 证明程序的属性 ..................................... 41

2.5.1 循环不变式 ................................. 41

2.5.2 while循环的循环不变式 .......... 45

2.5.3 习题............................................. 46

2.6 递归定义 ................................................. 47

2.6.1 表达式 ......................................... 49

2.6.2 平衡圆括号 ................................. 50

2.6.3 习题............................................. 54

2.7 递归函数 ................................................. 55

2.8 归并排序：递归的排序算法 ................. 59

2.8.1 合并............................................. 59

2.8.2 分割表 ......................................... 62

2.8.3 排序算法 ..................................... 63

2.8.4 完整的程序 ................................. 65

2.8.5 习题............................................. 66

2.9 证明递归程序的属性 ............................. 67

2.10 小结....................................................... 69

2.11 参考文献 ............................................... 69

第 3 章 程序的运行时间............................... 70

。。。