软件技术基础 离散数学、数据结构、C++编程实训

第1章　绪论 1

1.1　本课程的知识结构 1

1.2　离散数学 1

目录 1

1.3　数据结构与算法设计 2

1.4　C++语言 2

1.5　学习要求和方法 3

1.6　书后配盘 4

1.7　软件技术教育 4

习题 6

2.1　命题逻辑的基本概念 7

2.1.1　命题 7

第2章　命题逻辑 7

2.1.2　复合命题 8

2.2　命题公式与真值表 12

2.2.1　命题公式 12

2.2.2　真值表 12

2.2.3　永真式、永假式及可满足公式 13

2.3　命题演算 13

2.3.1　命题公式的化简 13

＊2.3.2　命题推理规则与方法 15

2.4　命题模型 17

2.4.1　命题建模 17

＊2.4.2　命题模型推理 19

习题 20

3.1　谓词命题和谓词公式演算 22

3.1.1　谓词和个体词 22

第3章　谓词逻辑 22

3.1.2　量词 23

3.1.3　谓词公式演算 24

3.2　谓词模型 27

3.2.1　谓词建模 27

＊3.2.2 谓词推理 28

习题 29

第4章　集合论 31

4.1　集合的概念 31

4.1.1　集合 31

4.1.2　集合的描述方法 32

4.2　集合运算 33

4.2.1　集合的运算 33

4.1.3　集合间的关系 33

4.2.2　集合的运算定律 34

4.3　集合模型 35

4.3.1 集合建模 36

＊4.3.2　集合命题推理 37

＊4.4　集合基数推理 38

习题 39

第5章　图论 42

5.1　图与树 42

5.1.1 图 42

5.1.2　图的性质 43

5.1.3　完全图和子图 44

5.1.4　图的同构 45

5.1.5 平面图 45

5.1.7　树和根树 46

5.1.6　有权图和网络 46

5.1.8　二叉树 48

5.2　图的运算 48

5.2.1　图的连通性 48

5.2.2　欧拉回路 49

5.2.3 哈密顿回路 51

5.2.4　生成树和最小费用生成树 52

5.2.5　狄克斯特算法 53

5.2.6　图的遍历 54

5.2.7　树的遍历 56

5.2.8　二叉树的遍历 56

5.3　图论建模 57

5.3.1 用图表示网络关系 57

5.3.2　用树表示分类的层次关系 59

5.3.3　搜索树 60

习题 62

第6章　C++编程作业入门 64

6.1　程序编写作业概述 64

6.1.1 编程语言 64

6.1.2　编译器与编译作业流程 65

6.2　用VC++编译器进行编程作业 66

6.2.1 建立VC++项目 66

6.2.2　编辑源代码文件 69

6.2.3　编译和查错 71

6.2.4　连编和运行程序 73

6.2.6　向项目中添加文件和从项目中 74

删除文件 74

6.2.5 项目的关闭和再打开 74

6.3　C++语言词法概要 76

6.3.1　基本词汇 77

6.3.2　标点符号 77

6.3.3　关键词 78

6.3.4　标识符 78

6.3.5　常数 79

6.3.6　运算符 81

6.3.7　注释 83

6.4　C++语言句法概要 84

6.4.1　定义语句 84

6.4.2　数据类型的转换 86

6.4.3　导出数据类型 87

6.4.4　函数和函数调用机制 88

6.4.5　运算式 92

6.4.6　程序控制语句 93

6.4.7 应用数理逻辑设计程序控制 96

语句 96

6.4.8　指针变量 99

6.4.9　字符串的运算 101

6.4.10　数据的输入输出函数 103

习题 109

第7章　用类编写面向对象的程序 111

7.1　C++语言中类的概念 111

7.1.1　概述 111

7.1.2　类定义 114

7.1.3　构造函数和析构函数 115

7.1.4 成员函数的定义与调用 117

7.1.5　引用数据类型和左值成员函数 119

7.1.6　成员函数的重载与运算符成员函数 121

7.1.7　案例——用类的运算符函数解 122

线性方程组 122

7.2　面向对象程序设计方法与C++的类 126

7.2.1　人的抽象思维方法 126

7.2.2　C++的类的聚集机制 127

7.2.3　C++的类的继承机制 128

7.2.4　按C++的类划分程序模块 131

习题 134

第8章　用类模板实现线性数据结构 138

8.1　类模板 138

8.1.1　数据结构和离散数学 138

8.1.2　固定长度的List模板 139

8.1.3　模板的实例化 141

8.1.4　长度可自动改变的List模板 143

8.1.5　List模板三 146

8.1.6　Linked List 149

8.2　矢量、矩阵和线性方程组的C++模板 150

8.2.1　矢量和矩阵的数学概念 150

8.2.2　矢量和矩阵的模板 151

8.3　排序和检索 153

8.3.1　气泡法排序和函数模板 153

8.3.2　对分检索法 156

8.3.3　插入排序 157

8.4　队列和堆栈 158

8.4.1　Stack模板 159

8.4.2　Queue模板 160

习题 162

第9章　编程作业全过程 164

9.1　软件系统开发过程 164

9.1.1　系统分析、系统设计和系统实施 164

9.1.2　UML方法 165

9.2　用类图建立数据模型 166

9.2.1　类和实例 167

9.2.2　属性 167

9.2.3　运算 167

9.2.4　类的图形表示 168

9.2.5　关联 168

9.2.7　关联的约束 169

9.2.6　关联类 169

9.2.8　继承 170

9.2.9　聚集 171

9.2.10　案例——学籍管理系统的数据模型 172

9.3　由数据模型设计C++程序 172

9.3.1　类的映射规则 172

9.3.2　继承的映射规则 173

9.3.3　聚集的映射规则 173

9.3.4　关联的映射规则 175

9.3.5　关联类的映射规则 182

9.3.6　通过计算获取冗余信息 184

9.4　数据模型的一致性和完整性 185

9.4.1　数据模型的概念一致性 185

9.4.2　数据一致性和完整性的动态维护 187

9.5.1　用户界面的作用 189

9.5　用户界面的设计 189

9.5.2 UCD 190

9.5.3　设计用户菜单 192

9.5.4　验证用户输入 194

9.5.5　输出数据的可读性 195

9.6　程序的检测 195

9.6.1　程序错误的种类和原因 195

9.6.2　程序运行检测步骤 197

9.6.3　用VC++编译器的调试功能跟踪 197

程序运行过程 197

9.7　编程作业的文档工作 201

习题 201

9.6.4　测试数据 201

第10章　树和图的C++模板 203

10.1　根树模板 203

10.1.1　根树的数据模型和C++模板 203

10.1.2　根树的广度优先遍历函数 205

10.1.3　根树的深度优先遍历函数 206

10.1.4　求根树中所有路径 207

10.2　二叉树 208

10.2.1　二叉树的数据模型和C++模板 208

10.2.2　二叉树的遍历算法 209

10.2.3　二叉检索树简介 210

10.3　递归 210

10.3.1　递归的数学概念 210

＊10.3.2　递归算法的化解 212

10.4.1 图的数据模型和C++模板 215

10.4　图的C++模板和程序 215

10.4.2　无向图的最小费用生成树和克鲁斯克尔函数 216

习题 219

第11章　课程作业 221

11.1　课程作业一——学籍管理系统 221

11.1.1　根据系统数据模型设计C++类 221

定义 221

11.1.2　定义管理实例的序列 221

11.1.3　完成UCD 222

11.1.4　设计菜单函数 222

11.1.5　设计交互式数据输入函数 224

11.1.6　划分程序模块 226

11.2.1　程序工作原理分析 227

11.2　课程作业二——五子棋游戏 227

11.1.9　其他要求 227

11.1.8　编写完整的文档 227

11.1.7　测试程序 227

11.2.2　数据建模 228

11.2.3　函数Win（）的实现 229

11.2.4　显示棋盘和棋子的函数 230

11.2.5　主函数控制逻辑 231

11.2.6　产生棋着的算法 232

11.2.7　其他要求 235

附录一　名词索引 236

附录二　离散数学部分习题参考 243

答案和提示 243

附录三　如何阅读用形式文法描述的 248

C++语法规则 248

参考文献 251