本书以程序设计的分析问题和解决问题为重点,讲授在C/C 语言环境下程序设计的解题思路、算法设计和程序实现,可帮助读者提高编程能力和上机解题能力。全书语言简洁,示例丰富,深入浅出地引导读者理性思维和理性实践,章节结构安排合理,教学方法引人入胜,便于读者自学。
本书可作为高等院校计算机相关专业程序设计课程的教材,亦可供从事计算机、自动化及其他相关领域的科研技术人员参考。
1. 强调转变观念,以学生为中心,安排教学首先考虑培养目标、学生的认知规律和学习特点。2. 强化实践,让学生在理论指导下动手动脑,更多地上机编程,鼓励和引导探索式的学习;以任务驱动方式,通过示例讲授程序设计的基本概念和方法。3. 重点放在思路、算法、编程构思和程序实现上,训练学生分析问题和解决问题的能力;注重培养学生良好的编程习惯。
第4版前言本书第3版是2010年11月完成的。六年来,我们在使用本教材的过程中,认真听取学生反馈意见,不断改进教学方法、完善教学环节、调整教学次序,使得课程学习效果有了进一步提升。为及时反映课内教学成果,我们又在第3版基础上对文字教材进行了修订,包括调整了若干章节的次序、补充了部分章节的课后习题、修改了一些地方的文字错误和代码错误等等。我们还系统梳理了第3版教材中的所有示例源程序,调整了所有代码中的注释,清除了在部分代码中发现的问题,并用最新的编译环境进行了编译测试。希望本次修订能为计算机语言程序设计学习者提供一本内容与时俱进、更加易学易用的教材。由于时间仓促,作者水平有限,书中难免还有纰漏,欢迎广大读者朋友多提宝贵意见!
吴文虎,徐明星,邬晓钧2017年1月
第3版前言本书的第1版是2003年9月完成的,经过一年的试用,于2004年9月发行了第2版。 学生普遍反映,这本教材思路清晰,重点突出,易学易用,特别是强化实践教学思想,使学生既动手又动脑,学会了编程的基本思路和方法,受到了学生的好评。从第2版的使用到现在又经过了6年时间,这期间我们在实践中认真听取学生的反馈意见,不断改进教学方法,与时俱进地充实教学内容,特别是注重将讲课内容与作业提交系统形成一个有机的整体;使学生的学习更容易做到理性思维和理性实践,以期达到进一步提高教学质量的目标。为此,我们又在第2版的基础上调整了部分章节,增加了一些常用的重要算法及程序实现,形成了现在的第3版。从教材改版的目标而言,我们认为没有最好,只有更好。
吴文虎 徐明星2010年9月
第2版前言本书第1版是2003年9月出版的,经过一年的使用后,学生普遍反映本书重点突出,易学易用。但作为教师,我感到还要不断地研究教学规律,化解教学中的难点。为此,我又重新审阅了全书,在文字上做了调整,内容上做了修正,力求讲得明白透彻。在教学中发现,初学者往往要花费很多的时间在程序调试上,效率很低。实际上程序调试已成为学生编程实践中的拦路虎。所以,配合本书,又专门编著了《程序设计基础(第2版)习题解答与上机指导》,还准备上小班辅导课让学生学会调试程序的基本方法。我认为这可能是进一步提高该课教学质量的一个关键。
吴文虎2004年8月
第1版前言计算机语言与程序设计是一门十分重要的基础课程。该课长期沿袭着这样的教学模式:过于注重语句、语法和一些细节,基本上是以高级语言自身的体系为脉络展开的,没有把逻辑与编程解题思路放在主体地位上;对如何分析问题和解决问题讲得不够,对学生编程的能力、上机解题的能力训练不够。这样就给后续课程及研究生阶段的课题研究留下了缺憾。很多学生在学习这门课时感到枯燥难学,学过之后,不能用来解决实际问题。我个人的经历有些不同,除了学校给我安排的教学和科研任务之外,20年来我一直指导初中学生、高中学生和大学生参加有关计算机的各种比赛,包括国际信息学奥林匹克和ACM世界大学生程序设计竞赛,通过对这些学生成长道路的反复思考和研究,使我感到很有必要改变我们的课程教学模式,用新的教学理念和方法培养一流人才。对这一问题,我和有关领导谈了自己的想法,他们非常支持。从2001年9月起,我接受了程序设计基础课程的教学任务,并开始对该课程教学模式进行改革:以强调动手实践上机编程为切入点;以任务驱动方式,通过实例讲授程序设计的基本概念和基本方法;重点放在思路上,即在C/C 语言的环境下,针对问题进行分析,构建数学模型,理出算法并编程实现。同时,要求学生养成良好的编程习惯;在教学过程中培养学生的思维能力和动手能力,鼓励学生探索、研究和创新。在指导思想上,强调转变观念,以学生为中心,将学生视为教学的主体,安排教学首先考虑培养目标、学生的认知规律和学习特点。在教学的每一个环节,顾及学生的实际情况,多想怎样才能有利于调动学生学习的积极性,引导学生主动学习。具体的改革措施主要针对两个方面:教学模式和对学生学习的评价方式。对教学模式的改革提出强化实践。明确告诉学生:程序设计课是高强度的脑力劳动,不是听会的,也不是看会的,而是自己练会的。只有让学生动手,他才会有成就感,进而对课程产生兴趣,学起来才比较从容。因此,我们的基本思想是在理论指导下,让学生动手、动脑,更多地上机实践。学生只有在编写大量程序之后,才能获得真知灼见,感到运用自如。注重学生动手能力的培养是这门课和以往课程最大的不同之处。提出理性思维和理性实践。按照建构主义的学习理论,学生作为学习的主体在与客观环境(指所学内容)的交互过程中构建自己的知识结构。教师应引导学生在解题编程的实践中探索其中带规律性的认识,将感性认识升华到理性高度,只有这样,学生才能举一 反三。提出授课的原则是要学生抱西瓜而不是捡芝麻,重点放在思路、算法、编程构思和程序实现上。语句只是表达工具,讲一些最主要的,对细枝末节的东西根本不讲。要求学生在课堂上积极思考,尽量当堂学懂。突出上机训练,在编写程序的过程中,使学生提高利用计算机这个智力工具来分析问题和解决问题的能力。提出要让学生养成良好的编程习惯。我们在与国内一些软件公司的技术人员座谈时了解到,中国软件之所以上不去的原因之一就有习惯问题。印度十个人编程,会编出一样的东西,而我们十个人编程可能会有十种风格。因为我们忽略了一个重要问题,即顾客的感受,程序的编写是给别人看的,而不是只给我们自己看的。再者,尽管我们学生模型构思做得很快,但编程的基本功不扎实,往往到了关键的时候,就出问题。鉴于此,在课上我们强调程序的可读性、规范性;要求变量必须加注释;程序构思要有说明;学会如何调试程序;尽量使程序优化;还要求对程序的运行结果做正确与否的判断和分析。提出自学、动手、应用、上网的学习习惯。我认为在本科阶段就应该注意培养学生的自学能力。很多东西完全是可以自学的,尤其是计算机。计算机是实践性极强的学科,所学的内容和要实践的东西是一个整体,因此可以自己动手来学,书上看不懂的在机器上动手试试,往往就弄懂了。上网是指充分利用网络平台,提高获取信息、处理信息和交流信息的能力。对学生学习评价方式的改革考试是检验学生学习效果、评价学生学习业绩的重要环节。考试作为指挥棒对教学目标、教学过程有着相当大的影响。我一直在思考如何进行考试改革,如何借助考试环节调动和激发学生自主学习的积极性、创造性等问题。开学之初,我就向学生宣布考试方式上机解题,判分也是由计算机来完成,对就是对,错就是错,不纸上谈兵,不考笔试,不考死记硬背的东西。我们平时比较注意对学生学习方式的引导,让学生明白:理论很重要,要在理论指导下,动手动脑、有条理地进行实践。实践才能出真知,动手才能学到真本事。我们还将一些有较好程序设计基础的学生组织起来,因材施教,引导他们进行探索式的研究性学习,让他们继续提高。同时让他们在班上担任小教员,帮助同学学习。这样做行不行呢?经过两年的教学实践,这门课取得了很好的教学效果,学生给以很高的评价。学生点评为:授课方式独特新颖,深入浅出,启发式教学,激发学生兴趣,调动学生的积极性,有助于学生独立思考能力的提高。(引自清华大学2001年下半年教学评估结果查询)参加小教员工作的学生,提高了责任感,培养了敬业精神。他们的水平和能力也有相应的提高,其中三名同学代表清华大学参加了2002年ACM世界大学生程序设计竞赛的分区赛和总决赛,取得了世界总排名第四的好成绩(2300支队伍参加区域赛,60支队伍参加总决赛)。2002年5月,在北京市高校计算机基础教育研讨会上,我曾应约就此课程的教学改革作了专题报告,受到了与会专家和老师们的好评,他们认为这是非常好的新的教学范例。改革是没有止境的。经过两年的实践,我感到在一些方面还要进一步努力,还有许多工作要做:要进一步加大学生训练环节的力度;要加强对基础较差学生的辅导;要建立一个因材施教的机制,创造条件,让学生能有更广阔的发展空间;要建立平时的督促机制,让每一个学生真正落实动手实践;要考虑与后续课程的衔接。现在大家看到的这本教材就是在上述的背景下,整理了课上的教案,补充了一些内容写出来的。在教材成文的过程中,我的同事和学生(博士生)起了很大作用。他们提出了很好的建议,对一些算法进行了研究和整理,特别是对全书整体上的结构进行了缜密的 推敲。从一种体系转变为现在的体系是有相当大的难度的,也有风险,学生爱不爱这样学,能不能学到真本事,是不是能够达到预期的教学目标,都会存在问题。但我以为,要改革就要知难而进,不付诸努力就收到良好的教学效果是不可能的。目前这本教材可能存在很多不足,但是我们有这种思想准备,在教学实践中,多听取学生的反馈意见,不断修改,使之日臻完善。我们相信,恒心与虚心能够成就一本好的 教材。参加本书研究、撰写工作的还有徐明星(参加本书总体策划与章节编排)、邬晓钧(撰写第9、10、13章及附录)和李净(进行教案整理、图文设计),此外,赵强工程师和杨非同学也做了大量的书稿整理和成文工作,吴根清、孙辉、刘建、刘林泉、邓菁、陈德锋、侯启明等同学看了本书的第一稿,提出了宝贵的修改意见。在此一并感谢他们所付出的 劳动。由于时间仓促,作者水平有限,书中难免有纰漏,欢迎读者多提宝贵意见。
吴文虎2003年9月
目录
第1章 绪论 1
第2章 编程准备 4
2.1 程序编写 4
2.1.1
用Visual C 6.0编写程序 4
2.1.2
使用Dev-C 开发程序 8
2.2 程序代码及说明 14
2.3 输出流对象cout 15
2.4 程序注释 16
2.5 算术运算符 16
2.6 数学函数 17
2.7 小结 17
习题 17
第3章 代数思维与计算机解题 19
3.1 程序的基本结构 19
3.2 变量与数据类型 21
3.2.1
变量的基本概念 21
3.2.2
数据类型与变量的地址空间 22
3.3 定义变量和赋初值 22
3.4 变量赋值 23
3.4.1
赋值符号与赋值表达式 23
3.4.2
变量赋值的5要素 24
3.5 指针变量 25
3.5.1
指针定义与初始化 25
3.5.2
指针赋值 26
3.5.3
在赋值语句中使用间接访问运算符 26
3.6 小结 27
习题 28
第4章 逻辑思维与计算机解题 29
4.1 关系运算和关系表达式 30
4.1.1
关系运算符 30
4.1.2
关系表达式的一般格式 30
4.1.3
将是否写成关系表达式 30
4.2 枚举法的思路 31
4.3 循环结构 33
4.3.1
使用循环结构的部分程序 33
4.3.2
for语句的格式和执行过程 33
4.3.3
使用for循环解题实例 34
4.3.4
for循环的程序框图 36
4.4 分支结构 36
4.4.1
if语句的格式 37
4.4.2
分支结构的实例 38
4.5 任务4.1的程序框图 39
4.6 任务4.1的参考程序 40
4.7 逻辑问题及其解法 41
4.7.1
逻辑运算符与逻辑表达式 42
4.7.2
逻辑问题的解题思路 43
4.7.3
任务4.2的参考程序 47
4.8 小结 48
课后阅读材料 48
习题 53
第5章 函数思维与模块化设计 55
5.1 函数 55
5.1.1
函数的说明 56
5.1.2
函数的定义 56
5.1.3
函数的返回值 56
5.1.4
函数的调用 57
5.1.5
形式参数和实在参数 57
5.1.6
调用和返回 58
5.1.7
带自定义函数的程序设计 58
5.2 编程实例1 60
5.3 编程实例2 61
5.4 几种参数传递方式的比较 63
5.5 小结 66
习题 66
第6章 数据的组织与处理(1) 数组 69
6.1 数组 69
6.1.1
一维数组的定义 71
6.1.2
数组初始化 71
6.1.3
字符数组的定义、初始化和赋值 72
6.1.4
数组与指针 75
6.2 筛法 77
6.3 线性查找与折半查找 78
6.4 冒泡排序法 80
6.5 递推 82
6.5.1
递推数列的定义 82
6.5.2
递推算法的程序实现 83
6.6 字符数组应用 86
6.7 函数跳转表 91
6.8 二维数组 93
6.8.1
二维数组的定义 94
6.8.2
二维数组的初始化 95
6.8.3
二维数组中的元素存放顺序 95
6.9 小结 97
课后阅读材料 98
习题 102
第7章 数据的组织与处理(2) 结构 105
7.1 结构与结构数组 105
7.1.1
结构体类型的定义 105
7.1.2
结构体变量的定义和引用 106
7.1.3
结构体变量的初始化 107
7.1.4
结构数组 108
7.2 指针和结构 110
7.3 链表 111
7.3.1
建立链表的过程 112
7.3.2
链表结点的插入与删除 116
7.3.3
循环链表 124
7.4 小结 128
习题 128
第8章 数据的组织与处理(3) 文件 130
8.1 将数据保存到文件 130
8.2 从文件中读取数据 132
8.3 利用输入输出文件解交互类型的题 135
8.4 小结 145
习题 145
第9章 递归思想与相应算法 146
9.1 递归及其实现 146
9.2 递归算法举例 153
9.2.1
计算组合数 153
9.2.2
快速排序 154
9.2.3
数字旋转方阵 158
9.2.4
下楼问题 162
9.2.5
跳马问题 164
9.2.6
分书问题 166
9.2.7
八皇后问题 169
9.2.8
青蛙过河 172
9.3 小结 177
课外阅读材料 177
习题 181
第10章 多步决策问题 182
10.1
多步决策问题的解题思路 182
10.1.1
人鬼渡河的任务与规则要点 182
10.1.2
人鬼渡河的安全性考虑 183
10.1.3
安全状态的描述 183
10.2
安全条件形式化 184
10.3
从状态图上研究怎样一步一步过河 186
10.4
多步决策问题的编程思路 186
10.5
小结 189
习题 189
第11章 宽度优先搜索 191
11.1
骑士聚会问题 191
11.2
解题思路 196
11.3
小结 202
习题 203
第12章 深度优先搜索 204
12.1
问题描述 204
12.2
解题思路 205
12.3
深度优先搜索与剪枝 211
12.4
小结 216
习题 216
第13章 贪心法 217
13.1
贪心法解题的一般步骤 217
13.1.1
装船问题 217
13.1.2
事件序列问题 220
13.1.3
贪心法解题的一般步骤 222
13.2
贪心法相关理论 223
13.2.1
多阶段决策问题、无后向性与最优化原理 223
13.2.2
有向图最短路径的Dijkstra算法 223
13.2.3
贪心法解题的注意事项 227
13.3
小结 228
习题 228
第14章 动态规划 230
14.1
最短路径问题 230
14.1.1
问题描述 230
14.1.2
分析与题解 231
14.2
动态规划的基本概念 234
14.3
动态规划思想 235
14.4
举例说明动态规划思路 237
14.5
小结 244
习题 244
第15章 蒙特卡罗法 246
15.1
伪随机数的产生 246
15.1.1
产生随机整数 246
15.1.2
产生随机小数 247
15.2
伪随机数的应用 248
15.2.1
求的近似值 248
15.2.2
计算图形面积 249
15.3
小结 250
习题 250
附录A 程序调试 251
A.1 计分程序的调试 251
A.1.1
编译时的调试 252
A.1.2
运行时的调试 254
A.1.3
其他调试相关知识 259
A.2 跳马程序的调试 260
附录B 库函数 267
B.1 数学函数 267
B.2 字符判断函数 268
B.3 字符串相关函数 271
附录C ASCII码表 277
附录D 输入输出的格式控制 278
D.1 流的概念与输入输出格式 278
D.2 改变整数的进制 278
D.3 设置浮点数的精度 279
D.4 设置输入输出宽度 280
D.5 设置对齐方式和填充字符 281
D.6 其他设置 282
参考文献 284