描述
开 本: 32开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302439943丛书名: 高等教育质量工程信息技术系列示范教材
第1部分是针对C程序设计的初级训练：第1单元介绍进行C语言程序设计首先应当掌握的一些基本概念和方法；第2、3单元在第1单元的基础上介绍判断结构和重复结构，第4单元介绍穷举、迭代、递归和模拟，奠定算法基础。
第2部分是在第1部分的基础上进行数据类型的扩展：第5单元介绍数组，第6单元介绍3种可定制数据结构——构造体、共用体和枚举，第7单元介绍指针及其应用。
第3部分只有第8单元一单元，介绍分治、回溯、贪心策略和动态规划，作为算法设计进阶，可以使读者的程序设计能力提升到较高水平。
第4部分用第9单元一单元介绍一些可能用得着的有关内容，包括外部变量、内联函数、带参宏定义、文件和位操作。
这样的结构可以满足多种不同层次的教和学的需求，并兼顾自学。
作者在编写本书时力求概念准确、难点分散、例题经典、习题丰富、题型全面、注重效果，并以C99作为蓝本，可以作为高等学校各专业的新一代程序设计课程教材，也可供从事程序设计相关领域的人员自学或参考。
目录
第1单元 C程序启步 1
1.1 一个简单的计算器程序设计 1
1.1.1
用伪代码描述的简单计算器程序算法 1
1.1.2
将伪代码描述的算法逐步细化为C程序 2
1.1.3
C语言程序的编译、链接与执行 4
1.2 数据类型、标识符与声明 6
1.2.1
数据类型 6
1.2.2
C语言标识符规则 6
1.2.3
声明 7
1.3 表达式 8
1.3.1
字面量 8
1.3.2
数据实体 8
1.3.3
含有操作符的表达式及其求值规则 10
1.3.4
C语言的实现定义行为和未定义行为 13
1.4 函数 13
1.4.1
用函数组织程序 13
1.4.2
函数定义、函数调用与函数返回 15
1.4.3
函数声明 16
1.4.4
main()函数 17
1.4.5
库函数与头文件 17
1.4.6
printf()函数的基本用法 18
1.4.7
scanf()函数的基本用法 19
1.5 程序测试 22
1.5.1
程序中的语法错误和逻辑错误 22
1.5.2
程序运行中的异常与错误 22
1.5.3
程序测试及其观点 22
1.5.4
程序的静态测试与动态测试 23
1.5.5
设计用户友好的程序 23
1.6 知识链接A：整数类型 24
1.6.1
有符号整数类型与无符号整数类型 24
1.6.2
标准整数类型与扩展整数类型 25
1.6.3
宏与整数类型的极值宏 26
1.6.4
整数常量使用的3种进制 27
1.6.5
整数常量的标识 27
1.7 知识链接B：浮点类型 28
1.7.1
浮点类型的值的特性：取值范围与精度 28
1.7.2
浮点数据的舍入模式 29
1.7.3
浮点类型数据的操作限制 30
1.7.4
浮点类型常量的书写格式 30
1.7.5
_Complex类型和_Imaginary类型 31
1.8 知识链接C：字符类型 31
1.8.1
字符编码概述 31
1.8.2
char类型的基本特点 32
1.8.3
转义字符 33
1.8.4
用scanf()和printf()输入与输出字符 33
1.8.5
用getchar()和putchar()输入与输出字符 34
习题1 35
第2单元 选择程序设计 42
2.1 可选择计算类型的计算器程序算法分析 42
2.1.1
粗略算法分析 42
2.1.2
计算函数calculate()的算法分析 43
2.1.3
判等操作符与关系操作符 44
2.2
if-else型选择结构 44
2.2.1
用if-else实现的calculate()函数 44
2.2.2
if-else结构的特点 45
2.2.3
if-else if结构 46
2.2.4
瘸腿if-else嵌套结构 47
2.2.5
逻辑操作符与逻辑表达式 48
2.2.6
条件表达式 49
2.2.7
良好的程序书写风格 50
2.3 选择结构的测试 51
2.3.1
白箱测试法 51
2.3.2
使用double类型数据的calculate()代码 52
2.3.3
等价分类法 53
2.4
switch型选择结构 56
2.4.1
基于整数值匹配的选择结构——switch结构 56
2.4.2
一个字符分类程序 57
2.4.3
用switch结构实现的calculate()函数 59
2.4.4
switch结构与if-else结构的比较 60
2.5 知识链接D：变量的访问属性 61
2.5.1
变量的生存期与标识符的作用域 61
2.5.2
局部变量 63
2.6 知识链接E：#include指令与const限定符 66
2.6.1
#define指令 66
2.6.2
const限定符 67
2.7 知识链接F：左值表达式与右值表达式 68
2.7.1
左值表达式与右值表达式的概念 69
2.7.2
左值表达式的应用 70
习题2 71
第3单元 重复程序设计 82
3.1 可连续计算的计算器算法分析 82
3.1.1
初步算法 82
3.1.2
算法细化 82
3.1.3
重复结构的C语言实现 83
3.2
while结构 83
3.2.1
while结构的基本原理 83
3.2.2
采用while结构的可连续型计算器主函数 84
3.2.3
逗号操作符 85
3.3
do-while结构 86
3.3.1
do-while结构的基本原理 86
3.3.2
采用do-while结构的可连续型计算器主函数 86
3.4 for结构 87
3.4.1
for结构的基本原理 87
3.4.2
采用for结构的可连续型计算器主函数 87
3.4.3
计数型重复结构 89
3.4.4
复合赋值操作符与增值、自减操作符 93
3.5 重复结构的程序测试 94
3.5.1
基于路径覆盖的重复结构测试 94
3.5.2
边值分析法与重复结构测试 94
3.5.3
基于因果分析的程序测试 96
3.6
break与continue 98
3.6.1
break与continue语法概要 98
3.6.2
实例：求素数 99
3.7 知识链接G：表达式的副作用与序列点 101
3.7.1
表达式的副作用 101
3.7.2
序列点及其对表达式求值顺序的影响 102
3.7.3
副作用编程对策 104
3.8 知识链接H：算术数据类型转换 105
3.8.1
算术表达式中的数据类型转换 105
3.8.2
普通算术转换中的“提升拉齐”规则 105
3.8.3
传送转换中的数据类型转换 107
3.8.4
数据的显式类型转换 108
3.8.5
数据类型转换风险 109
习题3 113
第4单元 算法基础 121
4.1 穷举 121
4.1.1
搬砖问题 122
4.1.2
推断名次 124
习题4.1 128
4.2 迭代与递推 132
4.2.1
用二分迭代法求方程在指定区间的根 133
4.2.2
猴子吃桃子问题 136
4.2.3
用辗转相除法求两个正整数的公因子 138
习题4.2 141
4.3 递归 144
4.3.1
阶乘的递归计算 144
4.3.2
汉诺塔 147
4.3.3
台阶问题 150
习题4.3 151
4.4 模拟算法 152
4.4.1
产品随机抽样 153
4.4.2
用蒙特卡洛法求(的近似值 156
4.4.3
事件步长法——中子扩散问题 157
4.4.4
时间步长法——盐水池问题 159
习题4.4 163
第5单元 数组 166
5.1 一维数组 166
5.1.1
数组类型的特征 166
5.1.2
数组的定义 167
5.1.3
数组的初始化 168
5.1.4
下标变量 169
5.1.5
变长数组与常量数组 170
5.2 排序与查找 171
5.2.1
直接选择排序 171
5.2.2
冒泡排序 173
5.2.3
二分查找 176
5.3 二维数组 177
5.3.1
二维数组的概念 177
5.3.2
二维数组的初始化 178
5.3.3
访问二维数组元素 180
5.4 字符串 181
5.4.1
字符串字面量 181
5.4.2
字符数组与C字符串变量 182
5.4.3
字符串的输入与输出 183
5.4.4
字符串操作的库函数 186
习题5 189
第6单元 可定制数据类型 195
6.1 构造体类型 195
6.1.1
构造体类型的特征与定制 195
6.1.2
用typedef定义类型的别名 196
6.1.3
构造体变量 197
6.1.4
构造体变量的分量及其操作 200
6.1.5
构造体数组 201
6.1.6
复合字面量 204
6.2 共用体类型 205
6.2.1
共用体类型的定制及其变量的定义 205
6.2.2
共用体类型与构造体类型的比较 206
6.2.3
共用体变量的应用举例 208
6.3 枚举类型 210
6.3.1
枚举类型及其定义 210
6.3.2
枚举变量及其声明 211
6.3.3
对枚举变量和枚举元素的操作 211
6.3.4
用枚举为类提供整型符号常量名称 212
习题6 212
第7单元 指针 220
7.1 指针类型与指针变量 220
7.1.1
指针及其声明 220
7.1.2
同类型指针间的赋值与判等操作 221
7.1.3
指针的递引用 223
7.1.4
void指针 224
7.1.5
用const限定指针 224
习题7.1 225
7.2 数组与指针 230
7.2.1
数组名具有退化的左值性 230
7.2.2
下标表达式的指针性质 231
7.2.3
指针与字符串 233
7.2.4
二维数组与指针 235
习题7.2 237
7.3 函数与指针 243
7.3.1
指针作为函数参数 243
7.3.2
带参主函数 250
7.3.3
返回指针值的函数 251
7.3.4
函数类型与指向函数的指针 252
习题7.3 258
7.4 指向构造体的指针与链表 262
7.4.1
指向构造体类型变量的指针 262
7.4.2
链表及其特点 263
7.4.3
构建链表 264
习题7.4 266
7.5 动态存储分配 270
7.5.1
申请需要的存储空间 270
7.5.2
释放一个指针指向的存储空间 272
7.5.3
修改一个指针指向的存储空间大小 273
7.5.4
构建动态链表 273
7.5.5
带有弹性数组成员的构造体 277
习题7.5 278
第8单元 算法设计进阶* 280
8.1 分治策略 280
8.1.1
快速排序 280
8.1.2
自行车带人问题 283
习题8.1 286
8.2 回溯策略 288
8.2.1
迷宫问题 289
8.2.2
八皇后问题 292
习题8.2 294
8.3 贪心策略 296
8.3.1
旅行费用问题 296
8.3.2
删数问题 299
习题8.3 301
8.4 动态规划 303
8.4.1
动态规划概述 303
8.4.2
点数值三角形的路径 305
8.4.3
背包问题 307
习题8.4 311
第9单元 语海拾贝 314
9.1 外部变量 314
9.1.1
外部变量及其定义 314
9.1.2
外部变量的链接性 314
9.1.3
外部变量的风险 319
9.2 带参宏 319
9.2.1
带参宏的基本定义格式 319
9.2.2
使用带参宏的注意事项 320
9.2.3
带参宏与函数的比较 321
9.3 内联函数 322
9.3.1
内联函数的概念 322
9.3.2
内联函数的定义 323
9.3.3
内联函数的限制 323
9.4 数据文件 324
9.4.1
数据文件及其分类 324
9.4.2
FILE类型及其指针 325
9.4.3
数据文件操作的一般过程 326
9.4.4
程序示例 330
9.5 位操作与位段 331
9.5.1
按位逻辑运算 332
9.5.2
移位运算 333
9.5.3
位段 334
习题9 336
附录A C语言运算符的优先级和结合方向 344
附录B C语言的关键字 345
附录C 格式化输出函数printf()的格式 346
C.1
printf()格式参数的结构 346
C.2
printf()格式符 346
C.3 长度修饰符 347
C.4 域宽与精度说明 348
C.5 格式前缀修饰符 348
附录D 格式化输入函数scanf()的格式 349
D.1
scanf()指针参数 349
D.2
scanf()格式参数的结构 349
D.2.1
格式参数字符串的结构 349
D.2.2
基本格式符和长度修正 349
D.2.3
字段宽度 350
D.3
scanf()的停止与返回 351
D.4 数值数据的输入控制 351
D.5 字符型数据的输入控制 351
D.5.1
在格式字段前添加空格使格式字段可以跳过空白字符 351
D.5.2
用扫描集控制字符数组的读入 351
附录E 编译预处理命令 352
E.1 宏定义 352
E.2 文件包含 352
E.3 条件编译 352
附录F C标准库头文件 353
附录G C语言常用的标准库函数 354
G.1 数学函数 354
G.2 字符函数和字符串函数 355
G.3 输入与输出函数 356
G.4 动态内存分配函数 357
G.5 退出程序函数 358
G.6 数值转换函数 358
G.7 时间和日期函数 358
附录H C99、C89与K&R C 主要内容的比较 360
参考文献 361
图0.1 2016年1月份发表的TIOBE编程语言社区排行榜当然，C语言也在不断发展之中。1978年美国电话电报公司（AT&T）的贝尔实验室正式发表了C语言。开发者B.W.Kernighan和D.M.Ritchie随即编写了著名的《The C Programming Language》一书，通常简称为《K&R C》，也有人称之为K&R C标准。但是，K&R C版在很多语言细节上不够精确。1983年美国国家标准化协会（American National Standards Institute）制定了一个C语言标准并于同年发表，通常称之为ANSI C，并在此基础上不断修订，于1989年末提出了一个报告——[ANSI 89]。1990年，国际标准化组织ISO（International Organization for Standards）通过了此项标准，将其作为ISO/IEC 9899:1990国际标准，俗称C89或C90。1995年，ISO修订C90，形成“1995基准增补1（ISO/IEC/9899/AMD1:1995）”，俗称C89修正案1或C95。1999年通过ISO/IEC 9899:1999，ISO对C语言标准进行了更重要的改变，俗称C99。2011年12月8号，ISO 发布了 C 语言的新标准——ISO/IEC 9899:2011，俗称C11。但是，国内C程序设计教材多数还基于C89甚至更早的标准，这种落后使得教学脱离应用，与世界潮流很不合拍。因此当务之急是过渡到C99，这是编写本书的一个主要动机。在出版本书之前，笔者已经在清华大学出版社出版了《新概念C程序设计大学教程（C99版）》，本书在此基础上进一步完善而成。目前支持C99并且简单易用的开发平台是DEV C ，它有两款，即Orwell Dev-C 和wxDev-C 。截止到本书定稿，Orwell Dev-C 的版本是5.7.0，wxDev-C 的稳定版本是7.4.2，它们的下载地址分别如下。 http://bloodshed-dev-c.en.softonic.com/ http://sourceforge.net/projects/orwelldevcpp/?source=typ_redirect http://wxdsgn.sourceforge.net/ （三）本书基于“以计算思维训练为核心，以能力培养为目标”的教学模式和“前期以培养解题思路为主，语法知识够用就行；后期补充必要的语法细节”的教学策略编写。全书共9单元可分为4个部分。第1部分是针对C程序设计的初级训练：第1单元介绍进行C语言程序设计首先应当掌握的一些基本概念和方法；第2、3单元在第1单元的基础上介绍判断结构和重复结构，第4单元介绍穷举、迭代、递归和模拟，奠定算法基础。然而这个基础比较厚重，要想不冲淡突出程序设计思路的主体，又把这个厚重的基础语法讲清楚，在时间上，特别是在课时上是不允许的。为此，这3单元中都含有3个部分内容，即主体部分、知识链接和习题。在主体部分只从如何使用的角度介绍笔者所遇到的语法知识，把进一步的、较为系统的介绍放到知识链接中介绍。教师在讲授时可以以主体部分为主，参考知识链接部分；或者把知识链接部分作为学生课后的阅读材料使用。这样就可以解决学习内容厚重与教学学时有限之间的矛盾，也可以激发学生自学的热情，满足不同学生的学习需求。在这一部分还介绍了非常重要但在之前被忽略的一些语法知识，例如表达式的副作用以及序列点等。第2部分是在第1部分的基础上进行数据类型的扩展，第5单元介绍数组，第6单元介绍3种可定制数据结构——构造体、共用体和枚举，第7单元介绍指针及其应用。第3部分只有第8单元一个单元，介绍分治、回溯、贪心策略和动态规划，作为算法设计进阶，可以使读者的程序设计能力提升到较高水平。第4部分用第9单元一个单元介绍一些可能用得着的有关内容，包括外部变量、内联函数、带参宏定义、文件和位操作。这样的结构可以满足多种不同层次的教和学的需求：以对程序设计作一般了解为目标者，可以重点学习第1部分，并对第2部分进行了解性学习；以掌握程序设计的基本方法为目标者，可以重点学习前两部分内容，对第3部分和第4部分进行了解性学习；以较深入掌握程序设计的方法为目标者，可以在熟练前两部分的基础上，进一步深入学习第3部分和第4部分。（四）为了便于不同角度的复习与训练，本书的习题中设置了5种栏目，即概念辨析、代码分析、探索验证、思维训练和开发练习。“概念辨析”主要提供了一些选择题和判断题，旨在提高读者对基础语法知识的了解。“代码分析”包括指出程序（或代码段）执行结果、改错和填空，旨在提高读者的代码阅读能力，因为读程序也是程序设计的一种基本训练。“探索验证”主要用于提示或者指导学习者如何通过自己的上机验证来提高对语法知识的掌握，除了这个栏目中的习题以外，学习者好能通过设计程序验证自己对于概念辨析栏目中的习题的判断是否正确。“开发练习”是一种综合练习，应当要求学习者写出开发文档，内容主要包括问题（算法）分析、代码设计、测试用例设计、测试及调试结果分析等几个部分，重点应当放在问题分析、代码设计和测试用例的设计上，要把这些都做好，再上机调试、测试，不要什么还没有设计出来就去上机。“思维训练”中给出了有一定难度的问题，只用于算法设计训练，不要求给出程序。这个栏目仅在第4、5、8三个单元设置。为了有的放矢地进行一些重要专题的训练，第4、7、8三个单元的习题以大节为单位给出。（五）在本书的编写过程中，赵忠孝、张秋菊、张展为、张展赫、姚威、史林娟、戴璐、张友明、董兆军等人参与了部分工作。此外，本书初稿完成之后，还承蒙《品悟C—抛弃C程序设计中的谬误与恶习》一书的作者薛非先生为本书提出了许多宝贵的意见。在本书即将出版之际，笔者由衷地感谢以上各位为本书所做的贡献，也要感谢在本书编写过程中参考过的有关资料的作者，包括一些网络佚名作者。同时，殷切地期待广大读者和同仁的批评与建议，让我们共同努力，把程序设计课程的改革做得更有实效。
张基温 2017年1月羊城小海之畔
float a,b,c,d,e;
但这是一种不好的方法。因为这些简单变量无法反映变量之间的关系。假如一个程序中的所有量（例如学生成绩、学生年龄、学生身高、学生体重……）都用简单字母表示，就会造成阅读程序时的混乱。于是，有人想了一个见名知义的命名变量的方法：
double stuScore1, stuScore2, stuScore3, stuScore4, stuScore5;
这个办法比简单地使用一些字母好多了，但是它们在用于某些群体性数据时无法反映出个体与群体之间的联系，例如这个群体有多大，在这个群体中个体与个体之间有什么样的联系性等，都表现不出来。此外，命名的工作量很大，也不能发挥计算机高速处理的优势，不能使用重复结构进行计算处理（如进行求和）。为了对类似的情况进行有效管理和处理，高级计算机程序设计语言都提供了数组。1. 数组类型的群体特征数组类型具有以下3个群体性特征。（1）数组的组成元素是同类型数据，这个类型也称为数组的元素类型或数组的基类型。（2）数组的组成元素（element）具有逻辑顺序，这种逻辑顺序用下标表示。例如，一组学生成绩可以用数组stuScore存储，并分别用stuScore[0]、stuScore[1]、stuScore[2]、stuScore[3]、stuScore[4]等表示其中每个学生的成绩。通常，被括在一对方括号中的数字称为下标，表示这组数据之间的逻辑顺序关系。（3）数组中的各元素按照下标的顺序存储在一段连续内存单元中，所以数组也具有物理的顺序性。2. 数组的个性化参数数组的个性化参数有以下3点：（1）具体的数据类型。（2）具体数组的大小。（3）具体数组的名字具有性。其中前两个参数是数组的存储细节，也是判断两个数组异同的依据，只有两个数组的元素类型和大小都相同时才认为它们是同类型的数组，但不是同一数组。5.1.2 数组的定义数组定义就是根据数组公共属性格式给出具体数组的个性化参数并进行命名的过程，其格式如下：
数组基类型 数组名 [数组长度表达式 ];
说明：（1）数组声明中的一对方括号称为数组类型声明符，它表明所声明的名字是一种聚合数据类型的名字，即这种类型中可以存储多个元素，这些元素的类型相同并且具有顺序性。（2）数组类型和数组长度表达式是由用户补充的存储细节。例如，前面介绍的存储5名学生成绩的数组可以定义为
double stuScore[5];
它表明这个名为stuScore的数组存储细节如下：* 它所存储的元素类型是double类型。* 它所存储的元素数目是5。（3）在C语言中，数组的长度是在编译时计算的，为此数组长度的定义必须使用编译时整数表达式——任何整数常量表达式，例如整数常量、整数宏、字符常量，以及编译时可以直接得到值的其他整数表达式。例如：
double stuScore[5];
也可以写成
double stuScore[2 3]; //正确
或
#define N 5double stuScore[N]; //正确
采用宏定义数组长度的好处是比较灵活，如果以后想改变数组大小，仅在宏定义处修改即可。（4）数组名不能作为左值表达式，因为数组是由若干独立的数组元素组成的，这些元素不能作为一个整体被赋值。例如：
int x[5],y[5]; x = y; //错误
5.1.3 数组的初始化在定义数组时，若仅仅声明了一个数组的名字，则这个数组中每个元素的值可能是不确定的。数组初始化就是在定义数组时给数组元素以确定的值。1．数组全部初始化数组的初始化用初始化列表进行。初始化列表是括在花括号中的一组表达式。例如：
double stuScore[5] = {87.6,90.7 8,76.5,65.4,56.7};
这时，声明语句中可以省略数组大小，由编译器按照初始化列表中的数据个数确定数组的大小。例如：
double stuScore[] = {87.6,98.7,76.5,65.4,56.7};
2．数组开始部分元素初始化当一个数组的初始化列表比数组短时，则后面的元素按照静态方式默认初始化：对于int类型，被初始化为0；对于double类型，被初始化为0.0。例如：
double stuScore[5] = {87.6,98.7};
相当于使用{87.6,98.7,0.0,0.0,0.0}进行初始化。显然，当只有部分元素的初始化列表时不可以省略数组大小，利用这一特点可以很方便地将一个数组初始化为全零。例如：
double stuScore[5] = {0.0};
就将每个元素都初始化为0.0。3．数组元素的下标指定初始化下标是对于数组元素的标号，其起始值为0，值为数组大小减1。C99允许用下标对指定元素初始化。例如：
double stuScore[5] = {[3] = 76.5, [1] = 98.7, [0] = 87.6};
这个数组的大小为5，其下标取值为0、1、2、3、4。在这个声明中，指定对下标为3、1和0的元素分别初始化为76.5、98.7和87.6。其他元素被默认初始化为0。显然，这时不再需要按照顺序。若省略数组大小，则编译器默认数组大小为下标值 1，例如：
double stuScore [ ] ={[4] = 56.7, [1] = 98.7, [3] =65.4};
默认数组大小为4 1 = 5。下面的数组定义也是正确的：
int a[] = {0,1,2,[0] = 3,4,5};
它将元素0初始化了两次，即先初始化为0，后又初始化为3。5.1.4 下标变量1. 下标变量的概念一个数组被定义之后就可以用下标变量对其元素随机访问了。下标变量用数组名加上括在方括号中表示逻辑序号的整数表达式表示，这个表达式称为下标表达式，简称下标（subscripting）。例如在定义了数组stuScore以后可以用stuScore[0]、stuScore[1]、stuScore[2]等表示该数组的各个下标变量。用下标变量可以随机地访问数组中的任何一个元素，对其赋值或引用其值。代码5-1 打印一组学生成绩。
#include int main (void){ double stuScore[] = {87.6,98.7,76.5,65.4,56.7}; //定义一个数组存储学生成绩 printf (“该组学生的成绩为:n”); for(int i = 0; i < sizeof stuScore/sizeof stuScore[0]; i){ printf(“%.1lf,”, stuScore[i]); } printf(“n”, stuScore[i]); return 0; }
说明：（1）sizeof是C语言中的一个操作符，可以用来计算一个表达式或一种类型所占用（或所需要）的内存字节数。所以表达式sizeof stuScore的值是数组stuScore占用的内存字节数，sizeof stuScore[0]的值是数组元素stuScore[0]占用的内存字节数。二者相除，得到的是数组stuScore的元素个数。这种写法可以不考虑小组成员到底有多少人，有几个成绩就有多少人。而下面的写法必须先数有几个成绩，增加了出错的几率。
for (int i = 0; i < 5; i){ printf(“%.1f,”, stuScore[i]); }
（2）在输出格式字段“%.1f”中用“.1”表示小数部分只保留1位。运行该程序，输出结果如下。
该组学生的成绩为:87.6,98.7,76.5,65.4,56.7
2. 使用下标变量应注意的事项（1）在数组声明中，数组名后紧靠的一对方括号称为数组定义符，它要求为一个整数常量表达式。在下标变量中，数组名后紧靠的一对方括号称为下标操作符，它要求为整数表达式，不要求必须是常量，并执行对数组取下标操作或称对数组索引（indexing）操作。C语言规定数组下标的取值始终从0开始，所以一个长度为N的数组的下标是从0到N ? 1。（2）C语言将字符作为整数处理，因此也可以用字符作为下标。但为了把字符放到合适的范围内，可以用a[ch – ‘a’]表示a[0]。（3）C语言标准没有规定要对下标范围进行检查。因此，当程序员使用了超出数组的下标值（常见的是错将n当成下标值）时就会形成未定义操作。例如，对于图5.1所示的内存内容，代码5-2将是一个无限循环。代码5-2 数组越界造成的无限循环。
#define N 3int a[N]; //…for(int i = 1; i <= N; i ) a[i] = 0; //…
当这段程序执行完i = 1、i = 2时，会把a[1]、a[2]都赋值为0。而执行到i = 3时，会把a[3]这个位置的内存也赋值为0。但是内存中a[3]的位置已经超出了数组a的范围，保存的是变量i的值，所以执行到i = 3时是把i赋值为0。这样，就永远不会退出循环。当然，若i不是正好保存在a[3]的位置，就可能不会形成死循环了。不过这总是一个隐患，并已经成为黑客窃取信息的一种手段。（4）下标表达式可以产生左值，而数组名不是左值。（5）用户要注意下标表达式中的副作用。例如在表达式[i ] = a[i ] 2中，i被修改了两次，称为实现定义行为。为避免发生这种行为，可以修改为a[i ] = 2，或i ，a[i] = a[i] 2，或i ，a[i] = 2。再看表达式a[i] = i ，虽然在这个表达式中对于i只修改了一次，但在修改a[i]时要读取i的值，但无法保证读取的是哪个i值。实际上还是一个修改叠加问题。类似的问题还有以下程序段：
int i = 0; while(i < N) a[i] = b[i ]; 5.1.5 变长数组与常量数组1. 变长数组C99支持VLA（variable-length array，变长数组），VLA有以下特点。（1）其长度不是编译时计算，而是运行时计算，因此长度可以用任意整型表达式定义。（2）没有初始化式。（3）一般用在main()之外的其他函数中，每次调用时长度可以不同。2. 常量数组C语言允许将数组定义为常量数组，使每个元素的值都不可再修改。定义常量数组的方法是在数组定义的开始处加上关键字const，例如：
const char octalChars[] = { ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’};
这说明，关键字const不仅可以保护数组元素不被修改，还可以保护任何一个变量的值不被修改。5.2 排序与查找排序（sorting）也称分类，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序方法有很多，主要可以分为选择排序、插入排序、交换排序、归并排序等。不同的排序算法有不同的时间效率和空间效率（多用的存储空间），适合不同的情况。在多个有序的或无序的数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程称为查找（search）。通常，查找的输入有一组数据（如一个数组）、一个关键字。查找的输出分两种情形，若查找成功，则输出查找到的数据；若查找结束，没有相同的关键字，则输出找不到的信息。5.2.1 直接选择排序1. 直接选择排序的基本思路选择排序（selection sort）的基本思路是把序列分为两个部分，即已排序序列和未排序序列。开始前，已排序序列没有元素，未排序序列具有全部元素。若要进行升序排序每次就要从未排序序列中选择一个小值放进已排序序列，直到把未排序序列中的元素都放进已排序序列为止。为了节省空间，可以按照下面的算法进行：首先从未排序序列中选择一个小元素与第1个元素交换，然后把第1个元素作为已排序序列，把其余的元素作为未排序序列；接着再从未排序序列中选择一个小元素与未排序序列的第1个元素交换，使已排序序列增加一个元素……；如此重复N ??1次，就把具有N个元素的序列排好序了。这种算法称为直接选择排序。图5.2为采用直接选择排序对初始序列进行降序排序的情况。
图5.2 直接选择排序算法示例2. 直接选择排序程序代码5-3 一个简单选择排序函数。
void seleSort(int a[],int size){ int k,min,temp; for (int i = 0; i < size – 1; i ){ min = a[i]; k = i; for (int j = i 1; j < size; j ) //在后面的数列中选择比min小的元素 if (min > a[j]){ min = a[j]; //更新小值 k = j; //记录当前小值的位置 } if(k != i){ //交换,形成已排序序列的后一个元素 temp = a[i]; a[i] = a[k]; a[k] = temp; } }}
说明：在这个算法中记录了小元素min和它的位置k。略加分析可以看出，这两者是互相联系的。为此可以省略min，得到下面的算法。代码5-4 修改后的简单选择排序函数。
void seleSort(int a[],int size){ int k,temp; for (int i = 0; i < size – 1; i){ k = i; for (int j = i 1; j < size; j ) //在后面的数列中选择一个小元素位置 if (a[k] > a[j]) k = j; //记录当前小值的位置 if(k != i){ //交换,形成已排序序列的后一个元素 temp = a[i]; a[i] = a[k]; a[k] = temp; } }}
3. 测试设计输入：任意一个数列。输出：已经排序的数列。4. 测试代码5-5 代码5-4的测试程序。
#include #include #include #define N 9void dispAllElemenNumberts(int score[], int size); //输出函数原型声明void seleSort(int a[], int size); //选择排序函数原型声明
int main (void) { int stuScore[N]; //定义一个数组存储学生成绩
srand (time (00)); //用时间函数作为伪随机数序列种子 for (int i = 0; i < N; i){ stuScore[i] = rand () % 101; //产生一个[0,100]区间的随机数赋值给下标变量 } printf(“排序前的序列：”); dispAllElemenNumberts(stuScore,N); //显示所有元素值 seleSort(stuScore,N); //排序 printf(“排序后的序列：”); dispAllElemenNumberts(stuScore,N); //显示所有元素值 return 0; }
void dispAllElemenNumberts(int a[],int size){ for (int i = 0; i < size; i) printf(“%d,”,a[i] ); printf(“n”); }
一次测试结果如下。
排序前的序列:71,33,94,72,11,29,91,35,88.排序后的序列:11,29,33,35,71,72,88,91,94.
5.2.2 冒泡排序1. 冒泡排序算法的基本思路冒泡排序（bubble sort）是一种典型的交换排序算法。它的基本思路是按一定的规则比较待排序序列中的两个数，如果是逆序，就交换这两个数；否则继续比较另外一对数，直到将全部数都排好为止。冒泡排序是通过对未排序序列中两个相邻元素的比较交换来实现排序过程。图5.3为用冒泡排序对数据序列[7,5,3,9,1]进行升序排序的过程，其基本算法是从待排序序列的一端开始，首先对第1个元素（7）和第2个元素（5）进行比较，当发现逆序时进行一次交换；接着对现在的第2个元素（7）和第3个元素（3）进行比较，当发现逆序时进行一次交换；如此下去，直到对第n?1个元素（9）和第n个元素（1）比较交换完为止。这时，的一个元素（9）便被“沉”到了后一个元素的位置上，成为已排序序列中的一个元素，未排序序列成为[5,3,7,1]。接着再重新对这个未排序序列进行比较交换，将次大元素（7）“沉”到倒数第2个元素的位置上。如此操作，直到没有元素需要交换 为止。
图5.3 冒泡排序示例2. 冒泡排序程序代码5-6 一个冒泡排序函数。
void bubbleSort (int a[], int size) { int temp; for (int j = 0; j < size – 1; j ) //总的比较交换轮数 for (int i = 0; i < size – j; i) //每轮中的比较交换次数 if (a[i] > a[i 1]) { temp = a[i]; a[i] = a[i 1]; a[i 1] = temp; }}
说明：（1）在这个函数中，当j = 0时，内层循环变量i = size ?1后，if (a[i] > a[i 1])中的a[i 1]将越界。为了避免产生这种情况，可以使数组元素a[0]空闲，数据从a[1]开始存储。与此相对应，函数bubbleSort ()中的循环也从1开始。（2）在这个算法中，有可能出现某一轮的两两比较后不需要交换的情况。这种情况说明，所有元素的位置都是不需要变动的，就是一个已经排好序的序列了。到此为止，就不需要再进行后面的两两比较交换了。这样可以提高排序的效率。那么，如何判断一轮中有无交换呢？一个简单的方法是在进入一轮前设置一个交换标志（例如exchange）为?1，只要进行了交换，就让交换标志为1。这样，用这个交换标志就可以知道待排序序列是否已经全部有序。代码5-7 改进的冒泡排序函数。
void bubbleSort (int a[], int size) { int temp,exchange; for (int j = 1; j < size – 1; j ) { exchange = -1; //进入每一轮前设置一个交换标志为-1 for (int i = 1; i < size – j; i) if (a[i] > a[i 1]) { temp = a[i]; a[i] = a[i 1]; a[i 1] = temp; exchange = 1; //只要有交换,就使交换标志改变为1 } if (exchange == -1) //交换标志若为-1,就返回 return; }}
3. 程序测试测试程序与代码5-5基本相同，但要进行如下修改。（1）修改排序函数及其声明。（2）将数组元素a[0]赋值为?1，因为学生成绩不可能为?1。（3）将数组元素的输入部分的循环变量起始值修改为1。（4）将dispAllElemenNumberts()函数中的循环变量起始值修改为1。代码5-8 代码5-7的测试程序。
#include #include #include #define N 9void dispAllElemenNumberts(int score[], int size); //输出函数原型声明void bubbleSort (int a[], int size) ; //冒泡排序函数原型声明
int main (void) { int stuScore[N]; stuScore[0] = -1;
srand (time (00)); for (int i = 1; i < N; i ){ //修改循环变量起始值 stuScore[i] = rand () % 101; } printf(“排序前的序列：”); dispAllElemenNumberts(stuScore,N); bubbleSort Sort(stuScore,N); //排序 printf(“排序后的序列：”); dispAllElemenNumberts(stuScore,N); return 0; }
void dispAllElemenNumberts(int a[],int size){ for (int i = 1; i < size; i) //修改循环变量起始值 printf(“%d, “,a[i] ); printf(“n”); }
一次测试结果如下。
排序前的序列: 38,9,26,92,51,39,45,17,94,排序后的序列: 9,17,26,38,39,45,51,92,94,
评论
还没有评论。