目录

第1章集合及其运算1

1.1集合1

1.1.1集合的概念1

1.1.2集合的表示2

1.1.3集合分类3

1.2子集、集合的相等4

1.2.1子集4

1.2.2集合的相等5

1.2.3幂集6

1.3集合的基本运算8

1.3.1并运算8

1.3.2交运算11

1.3.3差运算13

1.3.4对称差运算14

1.3.5求补运算、德·摩根公式15

1.4笛卡儿乘积运算17

1.4.1序对17

1.4.2笛卡儿乘积的定义18

1.4.3n元组18

1.5有穷集合的基数19

1.5.1映射20

1.5.2有穷集合的基数的定义20

1.5.3计数法则20

1.5.4容斥原理21

1.6逻辑与证明24

1.6.1数理逻辑简介24

1.6.2公理系统25

1.6.3命题逻辑26

1.6.4谓词逻辑28

1.6.5推理与证明29

1.7习题选解32

1.7.1建立语言的数学模型321.7.2证明集合相等34

1.7.3建立数学模型35

1.8本章小结37

习题38〖1〗集

合

论

与

图

论〖1〗〖2〗〖2〗目

录第2章映射40

2.1函数的一般概念——映射40

2.1.1函数概念的回顾40

2.1.2映射的定义41

2.1.3有穷集合间的映射42

2.2抽屉原理44

2.2.1抽屉原理的形式44

2.2.2抽屉原理的应用44

2.3映射的一般性质46

2.3.1导出映射46

2.3.2映射的一般性质及其证明46

2.4映射的合成48

2.4.1映射的合成的定义49

2.4.2合成运算的性质49

2.5逆映射50

2.5.1逆映射的存在条件及其唯一性51

2.5.2左(右)可逆映射51

2.6置换52

2.6.1置换的定义52

2.6.2置换的乘积53

2.6.3循环置换与对换53

2.6.4置换的循环置换分解54

2.6.5奇置换和偶置换55

2.7序列、矩阵与运算56

2.7.1序列56

2.7.2矩阵56

2.7.3运算57

2.7.4代数结构58

2.8集合的特征函数59

2.8.1特征函数59

2.8.2集合在计算机中的存储60

2.9习题选解61

2.9.1再论集合相等61

2.9.2利用映射建立数学模型62

2.9.3抽屉原理的应用64

2.9.4映射的性质67

2.9.5置换69

2.10本章小结69

习题69第3章关系71

3.1关系的概念71

3.1.1关系的等价定义71

3.1.2n元关系与关系数据库73

3.2几种特殊的二元关系74

3.2.1自反关系、反自反关系74

3.2.2对称关系、反对称关系74

3.2.3传递关系75

3.2.4相容关系、关系的计数75

3.3关系的运算76

3.3.1关系的集合运算76

3.3.2关系的合成运算77

3.3.3关系合成运算的性质77

3.4二元关系的传递闭包79

3.4.1二元关系的传递闭包、自反传递闭包79

3.4.2传递闭包的性质79

3.4.3迷宫问题81

3.5关系矩阵与关系图81

3.5.1关系矩阵81

3.5.2(0,1)矩阵的运算82

3.5.3Warshall算法82

3.5.4关系的图83

3.6等价关系与集合的划分83

3.6.1等价关系83

3.6.2等价类84

3.6.3集合的划分85

3.6.4等价关系与集合划分互相确定86

3.6.5从等价关系看线性代数87

3.6.6等价闭包与等价关系的合成87

3.7映射按等价关系分解88

3.7.1由映射确定的等价关系与集合划分88

3.7.2商集、自然映射88

3.7.3映射按等价关系分解89

3.7.4与映射相容的等价关系89

3.8偏序关系与偏序集90

3.8.1偏序关系与偏序集的定义90

3.8.2Hasse图91

3.8.3上(下)界、最大(小)元素、上(下)确界91

3.8.4链与反链93

3.9习题选解95

3.9.1利用关系建立数学模型95

3.9.2二元关系的概念97

3.9.3二元关系的闭包98

3.9.4二元关系与映射99

3.9.5等价关系和偏序关系101

3.10本章小结102

习题102第4章无穷集合及其基数104

4.1可数集104

4.1.1关于无穷104

4.1.2可数集的定义105

4.1.3可数集的性质105

4.1.4无穷集合107

4.2连续统集108

4.2.1康托对角线法108

4.2.2连续统109

4.2.3连续统的性质109

4.2.4例题111

4.3基数及其比较112

4.3.1基数的定义112

4.3.2基数的比较113

4.3.3连续统假设113

4.3.4康托定理113

4.4康托伯恩斯坦定理114

4.4.1问题114

4.4.2康托伯恩斯坦定理的定义114

4.4.3选择公理116

4.4.4基数的算术运算116

4.5公理化集合论117

4.5.1直觉集合论中一些著名的悖论117

4.5.2一些非数学上的悖论118

4.5.3公理集合论简介118

4.6图灵机、可计算性与计算复杂性120

4.6.1图灵机产生的背景120

4.6.2图灵其人121

4.6.3图灵机的直观模型122

4.6.4图灵机的形式定义123

4.6.5可计算性124

4.6.6计算复杂性126

4.7习题选解127

4.7.1可数集127

4.7.2对角线法128

4.7.3康托伯恩斯坦定理的应用129

4.7.4连续统130

4.8本章小结130

习题131第5章图132

5.1利用图模型解决问题132

5.1.1图论史上的标志性问题133

5.1.2游戏类问题137

5.1.3应用类问题138

5.2基本概念138

5.2.1图的定义138

5.2.2子图141

5.2.3度142

5.2.4正则图142

5.2.5图的同构143

5.3路、圈与连通图144

5.3.1路与圈145

5.3.2图的连通性145

5.3.3连通图的判定146

5.3.4有圈图的判定148

5.4补图与偶图149

5.4.1补图149

5.4.2偶图151

5.4.3极值图论151

5.5欧拉图154

5.5.1欧拉图的定义154

5.5.2欧拉定理154

5.6哈密顿图155

5.6.1哈密顿图及背景155

5.6.2哈密顿图的判定155

5.6.3哈密顿图的几个充分条件156

5.6.4Kp的哈密顿圈分解157

5.6.5比赛图158

5.7图的表示159

5.7.1邻接矩阵159

5.7.2可达矩阵161

5.7.3邻接表161

5.7.4关联矩阵161

5.8带权图163

5.8.1最短路径问题163

5.8.2巡回售货员(货郎担或旅行商)问题165

5.8.3中国邮路问题165

5.9习题选解165

5.9.1连通图、圈165

5.9.2同构167

5.9.3哈密顿图168

5.9.4最长路169

5.10本章小结169

习题169第6章树和割集171

6.1树171

6.1.1树和森林171

6.1.2树的性质172

6.1.3树的中心173

6.2生成树174

6.2.1生成树的定义174

6.2.2生成树计数175

6.2.3最小生成树176

6.3有根树与有序树179

6.3.1有根树179

6.3.2有序树181

6.4割点、桥和割集182

6.4.1割点和桥182

6.4.2割点和桥的特征性质182

6.4.3割集184

6.5习题选解185

6.6本章小结187

习题187第7章连通度、匹配和覆盖188

7.1连通度188

7.1.1连通度的定义188

7.1.2κ(G)、λ(G)、δ(G)的关系189

7.1.3n连通191

7.2门格尔定理192

7.2.1门格尔定理及推论192

7.2.2网络流193

7.2.3割集195

7.2.4求最大流196

7.3匹配198

7.3.1匹配问题及模型199

7.3.2独立集199

7.3.3相异代表系201

7.3.4Hall定理202

7.3.5求最大匹配204

7.4覆盖与支配集205

7.4.1覆盖206

7.4.2支配集206

7.5习题选解208

7.5.1建立网络流模型208

7.5.2连通度209

7.5.3匹配与覆盖210

7.5.4门格尔定理211

7.6本章小结211

习题212第8章平面图与图的着色213

8.1平面图及欧拉公式213

8.1.1背景213

8.1.2平面图的定义213

8.1.3平面图的欧拉公式214

8.1.4K5、K3,3不可平面215

8.2非哈密顿平面图216

8.3库拉托夫斯基定理218

8.4图的顶点着色219

8.4.1图的顶点着色的概念219

8.4.2色数的上下界220

8.4.3平面图的4色定理221

8.4.4平面图的5色定理223

8.5图的边着色224

8.5.1边着色及边色数224

8.5.2几个主要结果224

8.6习题选解225

8.7本章小结230

习题230参考文献233第1章程序设计语言基础1

1.1计算机程序1

1.2程序设计语言1

1.3最简单的C语言程序2

1.4C语言的开发环境3

1.5C程序的开发步骤5

思考与练习5

第2章C语言的符号体系和规则体系6

2.1数据概述6

标识符、关键字、常量及变量7

2.2基本数据类型10

2.2.1整型数据10

2.2.2实型数据13

2.2.3字符型数据15

2.3运算符19

2.3.1基本的算术运算符19

2.3.2不同类型数据间的混合运算20

2.3.3强制类型转换运算符21

2.3.4运算符优先级和结合性21

2.3.5上溢和下溢23

2.3.6自增运算符和自减运算符23

2.3.7复合赋值运算符24

2.4基本数据类型与运算符举例26

2.4.1查找关键字26

2.4.2标识符的定义26

2.4.3表达式求值27

思考与练习29

第3章按部就班——顺序结构程序设计31

3.1程序设计的基本步骤及程序执行的流程31

3.2算法及其表示形式31

3.2.1用自然语言表示算法31

3.2.2用流程图表示算法32

3.2.3用伪代码表示算法33

3.3实际问题引例34

3.4C语句35

3.4.1分类35

3.4.2赋值语句36

3.5数据的输入/输出38

3.5.1数据输入/输出的概念38

3.5.2字符数据的输入/输出39

3.6顺序结构程序设计举例46

思考与练习53

〖1〗集

合

论

与

图

论〖1〗〖2〗〖2〗目

录

第4章程序决策——选择结构程序设计57

4.1实际问题引例57

4.2条件判断57

4.2.1关系运算符和关系表达式57

4.2.2逻辑运算符和逻辑表达式58

4.3用if语句实现选择结构60

4.3.1if语句的3种形式60

4.3.2if语句的嵌套63

4.3.3条件运算符与表达式65

4.4利用switch语句实现多分支选择结构67

4.5选择结构程序设计举例69

思考与练习76

第5章周而复始——循环结构程序设计80

5.1实际问题引例80

5.2循环的概念80

5.3用while语句实现循环81

5.3.1while语句的基本形式81

5.3.2while语句特点和说明81

5.4用dowhile语句实现循环84

5.4.1dowhile语句的基本形式84

5.4.2dowhile语句特点和说明84

5.4.3while和dowhile循环的比较85

5.4.4while与dowhile循环程序举例85

5.5用for语句实现循环87

5.5.1for语句的一般形式87

5.5.2for语句的各种形式88

5.5.3for循环程序举例89

5.6循环的嵌套91

5.7用break语句和continue语句改变循环状态92

5.7.1用break语句提前退出循环92

5.7.2用continue语句提前结束本次循环93

5.8基于循环的简单算法95

5.8.1穷举法95

5.8.2程序加密96

5.9循环结构程序设计举例96

思考与练习104

第6章数组——具有相同数据类型的一组数109

6.1数组的概念109

6.2数组实际问题引例109

6.3一维数组的定义和使用110

6.3.1一维数组的定义110

6.3.2一维数组的引用111

6.3.3一维数组的初始化113

6.3.4一维数组应用举例114

6.4二维数组117

6.4.1二维数组的定义117

6.4.2二维数组的引用118

6.4.3二维数组的初始化119

6.4.4二维数组应用举例119

6.5字符数组与字符串124

6.5.1字符数组的定义与初始化124

6.5.2字符串124

6.5.3字符数组的输入与输出125

6.5.4字符串处理函数127

6.5.5字符串处理应用举例130

6.6数组综合案例134

思考与练习151

第7章函数——模块化程序设计157

7.1函数的基本概念157

7.1.1函数概述157

7.1.2函数的概念158

7.1.3函数的分类158

7.2函数实际问题引例158

7.3函数的定义159

7.4函数的调用163

7.4.1函数调用的方式163

7.4.2函数调用时的参数传递164

7.4.3函数的返回值168

7.4.4函数声明169

7.5数组名作函数参数问题170

7.5.1一维数组名作函数参数171

7.5.2二维数组名作函数参数174

7.5.3多维数组的情况177

7.6函数的嵌套调用和递归调用177

7.6.1函数的嵌套调用178

7.6.2函数的递归调用181

7.7变量的作用域和存储方式186

7.7.1变量的作用域186

7.7.2变量的存储方式193

7.8内部函数与外部函数197

7.9编译预处理198

7.9.1宏定义198

7.9.2文件包含201

7.9.3条件编译201

7.10函数综合案例205

思考与练习215

第8章指针——内存与地址操作222

8.1指针程序设计引例222

8.2指针的基础概念223

8.2.1内存地址223

8.2.2指针223

8.2.3指针变量224

8.3指针变量的声明及赋值225

8.3.1指针变量的声明225

8.3.2指针变量的赋值225

8.4指针变量的使用228

8.4.1指针变量与被指向变量的等价原则228

8.4.2通过一维指针变量p间接访问参照物a228

8.4.3通过二维指针变量q间接访问参照物a229

8.4.4关于符号“”和“&”的说明229

8.5指针与数组230

8.5.1数组元素的指针230

8.5.2指向一维数组的指针变量231

8.5.3指向高维数组的指针变量238

8.6指针与字符串250

8.6.1字符串的引用方式250

8.6.2字符数组与字符指针变量的不同255

8.7动态内存分配255

8.8指针数组261

8.8.1指针数组的定义261

8.8.2指针数组的应用262

8.8.3指向指针数组的指针变量266

8.9指针与函数268

8.9.1指针变量作为函数参数268

8.9.2用指向数组的指针作为函数参数271

8.9.3字符指针作为函数参数273

8.9.4返回指针的函数275

8.9.5指向函数的指针变量276

8.10综合案例282

思考与练习287

第9章结构体与共用体——聚合不同属性的数据类型294

9.1用户自定义类型引例294

9.2结构体数据类型295

9.2.1结构体类型定义295

9.2.2结构体类型变量296

9.2.3结构体变量的引用299

9.2.4结构体变量的初始化301

9.3结构体数组304

9.3.1结构体数组定义305

9.3.2结构体数组的使用306

9.4指向结构体的指针变量308

9.4.1结构体指针变量定义及使用308

9.4.2结构体数组的指针311

9.5结构体与函数312

9.5.1结构体变量作为函数参数求解312

9.5.2结构体指针变量作为函数参数求解315

9.5.3使用结构体数组作为函数参数318

9.6链表320

9.6.1链表基础知识321

9.6.2静态链表的操作323

9.6.3动态链表的操作328

9.7共用体数据类型350

9.7.1共用体类型的定义350

9.7.2共用体变量的定义351

9.7.3共用体变量的引用353

9.7.4共用体变量的赋值353

9.8枚举数据类型354

9.8.1枚举类型的定义354

9.8.2枚举变量的声明355

9.8.3枚举变量的引用356

9.8.4枚举变量的赋值357

9.9综合案例361

思考与练习368

第10章文件——程序的辅助性存储372

10.1文件的相关概念372

10.1.1文件应用概述372

10.1.2文件的定义372

10.1.3文件标识373

10.1.4二进制文件与文本文件373

10.1.5文件缓冲区374

10.1.6FILE结构体与指向文件的指针变量374

10.2文件实际问题引例375

10.3文件的打开与关闭376

10.3.1打开文件376

10.3.2关闭文件378

10.4文件的顺序读写378

10.4.1字符数据的顺序读写379

10.4.2字符串的顺序读写382

10.4.3文本文件的格式化读写385

10.4.4二进制数据的顺序读写387

10.5文件的随机读写391

10.5.1文件位置标记391

10.5.2读写位置定位及随机读写的实现392

10.6文件读写综合案例396

思考与练习399第11章综合实践——产品信息管理系统403

11.1系统功能需求分析403

11.2系统设计404

11.2.1系统功能架构设计404

11.2.2数据结构设计404

11.3系统编码实现405

11.4代码解读及运行结果展示418

11.5综合实践小结423

附录424