本书以C语言为基础,系统地介绍程序语言、算法与数据结构以及高级编程技术。全书由13章组成,以程序设计语言、程序设计方法和程序设计技术三大主题组织教材内容,采用了“数据表示”和“程序实现”双线索知识体系,优化了程序设计知识的安排。
本书结构清晰、语言通俗易懂,示例代码具有专业的编程风格;内容由浅入深、知识循序渐进,例题丰富,体现了程序设计和算法、数据结构的紧密结合。本书注重典型案例的精选与提炼。本书的高级编程技术内容便于开展课程设计和研究型学习。本书配套有经过多年教学实践的程序设计综合训练平台。
本书可作为高等院校理工类专业和信息技术类培训机构“程序设计”、“软件开发技术”课程的教材,也可作为计算机程序设计爱好者学习程序开发和编程技术的自学教材。
程序设计是大学计算机基础教育和计算机专业基础的核心课程,它既为其他技术课程奠定程序开发基础,又是其他专业课或实践环节的软件工具,因此成为各类专业的必修课程。程序设计覆盖面广、影响大,是卓越工程师教育培养计划的通识教育基础,同时也是大学生参加课程设计、毕业设计、创新实验、科技制作和学科竞赛等活动的重要平台。
C语言是国内外广泛使用的计算机程序设计语言。其功能强大、灵活自由、数据表示丰富、代码运行效率高、可移植性好,囊括了高级语言和低级语言各自的优点,适合编写系统软件和各类应用程序。世界上大多数软件都是由C语言和C++语言开发的,在TIOBE编程语言排行榜上,C语言、C++语言及其衍生发展起来的Java语言多年来始终处在前三位。学习程序设计从C语言入手,对于培养算法设计与分析能力、抽象数据描述与表示能力以及利用计算机求解现实问题的计算思维能力具有其他语言无法比拟的优点。而且在完全掌握了C语言之后,再学习其他程序语言就会轻车熟路。
然而,C语言的学习难度也是很大的。很多学生往往是“考完即忘”,学了后面的忘了前面的,低年级时学习的程序设计到了高年级即处于犹如从未学过的状态,更谈不上利用程序设计解决实际应用问题。而且面对庞大、复杂的C语言知识系统,不少学生甚至教师在教与学的过程中始终感觉“只见树木,不见森林”,对学过的程序思路不甚了解、数据描述不清楚、算法设计不到位,最后连最基本的语言知识也掌握不住,最基本的开发环境也不会使用。缺少以技能为目标的程序设计教材是造成这一局面的重要原因之一。
现有的C语言和C++程序设计类的教材多偏重语言知识,罗列语法多、千篇一律、大同小异,在如何应用程序解决实际问题方面下的工夫少;程序设计方法与语言结合少,缺少推动学生计算思维的训练;生硬的例子与实际应用脱节,缺少应用编程技术的展开。教学中尽管有诸如“案例教学”、“项目驱动”的做法,但由于缺少成熟的教学平台和系统化、规范化的教学资源,难以培养和提高学生应用程序设计解决实际问题的技能。
需要知道,人类学自然语言时,学的不仅是听还有说;学字时,学的不仅是读还有写。随着人们向一个越来越数字化的信息世界迈进,不仅应该学会如何使用程序,还要学会如何编写程序。当语言知识转化为编程技能时,就没有知识会遗忘了,应用程序设计解决实际问题的计算能力如同学习语言时的听、说、读、写一般。
为此,我们在多年程序设计课程的一线教学经验和软件开发科研工作基础上,结合自主研发的程序设计综合训练平台和系列教育软件,推出以语言知识为工具、以技能培养为目标、以编程技术为核心的系列程序设计教材。 本教材遵循我们多年提倡的“精讲多练、注重技能、开拓设计”教学理念编写。在程序语言知识体系的选取与深度的把握上,在算法、数据结构与程序设计的结合上精心设计,力图适合高等院校和专业计算机培训的教学目标与知识结构的要求,体现了以下几个特色。
(1) 首创双线索的程序设计知识体系。
任何一本程序设计教材必然是以程序语言为背景的,本书也不例外。然而C语言具有庞大的语言知识内容,因此以语言知识为教学线索必然是整体感凌乱。表现为教学学时始终处在不够的“高压状态”,学生学习始终抓不住主次。
本教材的双线索程序设计知识体系以“数据表示”和“程序实现”作为教学上的两条主线索,螺旋上升、交叉,推进,如图0.1所示。
图0.1 双螺旋线索C语言知识体系示意
首先,教材通过简单程序引出程序基本结构,以编程为目标给出两条线索:数据表示和程序实现。其次,从引入简单数据开始,逐步解决运算和程序组织,进而上升到程序模块化的实现。然后,从基本类型提高到复杂数据类型,上升到数据结构层面的数据表示,程序模块进阶到算法实现。最后,两条线索交汇到高级编程技术应用专题,揭示程序设计与应用软件开发的一般规律。
实际教学效果表明,双线索程序语言知识体系突出了程序设计方法学,使程序语言成为服务于编程的工具而不是目标,学习者既能获取语言知识,又能掌握编程技能。
(2) 优化程序设计知识安排。
多数现有教材中的知识安排导致以技能为目标的程序设计难于实现,出现教学瓶颈。表现在语言阶段冗长,使得以函数、自定义类型等内容为教学中心的编程阶段在实际教学中接近课程末期,从而让应用程序设计教学目标落空。
本教材在程序语言知识方面采用了“快节奏”,在程序设计方法和编程技术方面采用了“慢节奏”,解决了多年来程序设计教与学的难题和瓶颈问题。“快节奏”体现为语言基础知识学时被大幅度压缩, 从一开始即以简单程序框架展开程序知识,直接进入以程序模块化为主的教与学环境。方便教师精讲知识,学生早早练习进而多练,教材不在语言细节、小片段程序上反复循环。“慢节奏”体现为以(较难的)编程技术为研究专题展开(费时的)编程方法教学,方便教师组织技能训练,学生获取编程技巧。本教材将软件开发中的结构化、面向对象、组件模型和敏捷思想融入每个章节,让学习者接受专业化训练。
如图0.2所示是本教材的知识安排,与传统的C语言教学相比,增加了“设计阶段”的教学。显然,优化的知识体系使教师在教学时能够“抓大”(设计方法)“放小”(语言知识),学生学习时能够得到最大化的“饱满感”编程训练。
图0.2 优化的C语言程序知识安排
(3) 首创高级编程技术教学新思想。
由于没有更高层次的应用程序开发内容,许多教材的实际教学效果就是教师和学生都集中在做题上面。如数学一般,将程序设计演变成“程序语言 +计算方法”, C语言成了数学工具。殊不知计算方法(数值计算、非数值计算)仅是程序设计方法的一种,程序方法学中还有诸如操作系统、人机界面、图形图像、多媒体、网络通信、数据库、硬件接口等技术领域,每个领域都有独特的编程技术和精巧的解决方法。
衡量程序设计教学效果有两个重要指标:编程累计行数(TLOC)和单个程序行数(SLOC) 。以解题为主的编程训练能提高TLOC,但却止步于SLOC。即使将习题做上百题,虽然TLOC指标上去了,但SLOC却不见长。一般地,在专业的软件开发技术领域,SLOC小于300行时很难让人体会到应用开发的“感觉”.
高级编程技术是本教材主要的创新成果之一。通过研究型专题的技术教学,拓宽了学生的知识面,使其充分认识到程序是如何解决应用问题的,有极大的兴趣展开研究型学习。在这样的教与学环境下,才能从根本上提高SLOC,提升技能训练层次。
(4) 注重程序设计和算法、数据结构的紧密结合。
程序设计与算法、数据结构实际上是一个统一体,不应该也不可能将它们对立与分割。我国计算机基础教育的实际情况是,不少非计算机专业在程序设计课程后不再涉及算法和数据结构。即使是计算机专业开设有专门的算法和数据结构课程,也是“自说自话”,并不是站在软件系统开发(SSD)的角度使之有机地联系在一起。
算法和数据结构是程序设计的理论升华,是培养学生向应用程序开发转型的主要工具。本教材给出算法和数据结构的初步知识,克服了简单罗列算法、数据结构内容和算法与程序设计脱节、数据结构与程序数据表示脱节的问题。在讲述每一种常用算法和数据结构的基本思路与设计步骤的基础上,落实到每一个案例求解,从案例的提出到算法设计与数据描述、从程序实现到案例结果的讨论与分析,环环相扣,融为一体,力求理论与实际相结合,数据描述与数据表示、算法与程序实现相统一,切实提高对所学算法、数据结构的理解和掌握。
(5) 注重典型案例的精选与提炼。
培养学生的学习兴趣,激发学生的学习热情,不是一两句空洞说教所能奏效的,必须通过一些有价值的实际案例来引导。本教材设计了初等难度语言示范型、中等难度算法和数据结构应用型、较高难度综合设计型三种梯度的案例。这些案例的精选与提炼,有利于提高学生学习程序设计的兴趣,有利于学生在计算机现实问题求解上开阔视野,使之在程序设计方法和思路的开拓与编程技巧的应用上有一个深层次的锻炼与提高。其中难度较大的高级编程技术综合设计案例可作为课程设计、大作业与课后专题研究选用。
算法、数据结构与程序设计都不是一成不变的,可以实施多层次多方位的变通,变通出效果,变通长能力。本教材的部分示例给出了算法改进与程序优化的过程,既是提高案例求解效率的过程,也是算法设计能力培养与提高的过程,更是优化意识与创新能力增强的过程。
(6) 注重编程风格。
本书使用ISO/IEC 9899:1999 C语言标准(简称C99标准),充分体现了程序语言的最新进展和当前业界的最佳实践。
书中广泛采纳各专业软件公司编程规范的优点,无论语法语义、书写形式、示例代码等,均采用专业编程风格编写,潜移默化地引导学习者与专业化接轨。
书中所有程序均在Visual C++ 6.0和GCC 4.x (Code::Blocks)上调试通过。同时,教材中的所有源程序与各章习题的完整代码均可在清华大学出版社网站下载。
(7) 配套程序设计教学平台、系列教育软件和教学资源。
学习程序设计,上机实验是重要的环节。而实验环节重要的是什么呢?是性能优越的计算机或者环境良好的机房吗?答案不是。那种在实验课上做题、讲题的教学模式是很难培养程序设计技能的,本质上这种模式一开始就是奔期末考试(等级考试)去的。
程序设计实验环节最重要的是要有优秀的教学平台、教育软件和完整的教学资源。以技能培养为目标、以编程技术为核心的教学模式不是传统实验手段自发实现的,而是通过高集成度的程序设计综合训练平台,全程自动化辅助教学和教学管理来实现的。
自2001年以来,基于专业的软件开发科研优势,结合一线教学和课程改革的经验,围绕课堂、实验、作业、设计、考核5个教学环节,我们开发了系列教育软件。例如,“程序设计在线评测系统INPOJ”采用计算机应用系统使学生通过大量习题的训练提高解题速度(POJ训练)以解决TLOC; “软件设计协同开发平台DevForge”按专业软件开发方式引导、跟踪、自动评阅学生课程设计程序和报告以解决SLOC; “远程网络考试系统inTest”实现技能测试和实践考核,等等。这些教学平台的使用,使得实验机房变成了学生讨论、思考、相互教授的研究场所,形成数字化课堂教学、网络辅助教学、电子教室、智能答疑、综合训练等立体化教学环境,为落实教学理念和教学目标提供了先进工具。
使用本教材的高等院校和培训机构想要进一步了解有关程序设计综合训练平台和系列教育软件更多的信息,请与作者(jxf@nwpu.edu.cn)联系。
本书有两本配套的教学参考书:
(1) 《C程序设计实验教程》。该书分为4部分。前两部分详细介绍了Visual C++和GCC开发工具的使用方法和程序调试技术;第三部分是与教材知识体系相对应的实验内容,分为验证型实验和设计型实验,主要突出综合性实验,并结合算法、数据结构知识设计了一些有难度的实验题目;第四部分是课程设计专题研究实验内容,其目的是使读者能够训练应用程序开发,获取设计C程序项目的初步知识和工程经验,掌握高级编程技术。
(2) 《C程序设计习题与解析》。该书主要包括3个方面的内容:知识点与考点提炼、经典例题解析、典型习题与解答。内容紧扣课程教材和实验教材,对课程的讲授、学习以及考查起到积极的指导和辅助作用,其目的是使读者加强程序语言知识的掌握。
此外,向使用本书的教师提供讲课的电子演示文稿和素材,以节省教师的备课时间。向使用本书的高校和培训机构提供“程序设计课程教学指南”,方便组织教学、实施课程管理。
本书第1~7章和第13章由姜学锋编写,第8~12章由曹光前、姜学锋编写,全书由姜学锋主编并统稿。在书稿的编著过程中,得到了多位专家的关心和热情支持,西北工业大学计算机学院的同事们提出了许多宝贵的意见和建议,清华大学出版社对本书的出版十分重视并做了周到的安排。在此,对所有鼓励、支持和帮助过本书编写工作的领导、专家、同事和广大读者表示真挚的谢意!
由于时间紧迫以及作者水平有限,书中难免有错误、疏漏之处,恳请读者批评指正。
姜学锋2011年7月于西北工业大学
第1章 程序设计基础11.1 计算机系统和工作原理1
1.1.1 计算机系统的组成1
1.1.2 指令与程序3
1.2 信息的表示与存储5
1.2.1 计算机的数字系统5
1.2.2 进位计数制的转换6
1.2.3 数值数据的表示9
1.2.4 非数值数据的表示13
1.3 程序设计语言14
1.3.1 机器语言与汇编语言14
1.3.2 高级语言15
1.4 程序设计概述16
1.4.1 计算机问题求解的基本特点16
1.4.2 算法的定义与特性17
1.4.3 算法的表示17
1.4.4 结构化程序设计19
1.4.5 面向对象程序设计20
1.4.6 程序设计技术前沿21
1.5 C语言概述21
1.5.1 C语言的历史与特点21
1.5.2 C语言基本词法22
1.5.3 简单的C程序24
1.5.4 C程序基本结构26
1.5.5 C程序开发步骤27
1.5.6 C程序编码风格28
习题28第2章 数据类型与表达式30
2.1 数据类型30
2.1.1 整型31
2.1.2 浮点型32
2.1.3 字符型33
2.2 常量34
2.2.1 整型常量34
2.2.2 浮点型常量35
2.2.3 字符常量35
2.2.4 字符串常量37
2.2.5 符号常量38
2.3 变量39
2.3.1 变量的概念39
2.3.2 定义变量39
2.3.3 使用变量40
2.3.4 存储类别41
2.3.5 类型限定41
2.4 运算符与表达式42
2.4.1 运算符与表达式的概念42
2.4.2 算术运算符45
2.4.3 自增自减运算符46
2.4.4 关系运算符47
2.4.5 逻辑运算符48
2.4.6 条件运算符50
2.4.7 位运算符51
2.4.8 赋值运算符55
2.4.9 取长度运算符57
2.4.10 逗号运算符57
2.4.11 圆括号运算符58
2.4.12 常量表达式58
2.5 类型转换59
2.5.1 隐式类型转换59
2.5.2 显式类型转换61
习题62
第3章 程序控制结构64
3.1 语句64
3.1.1 简单语句64
3.1.2 复合语句66
3.1.3 注释67
3.1.4 语句的写法68
3.2 输入与输出69
3.2.1 字符输入与输出69
3.2.2 格式化输出71
3.2.3 格式化输入76
3.3 程序顺序结构79
3.3.1 顺序执行79
3.3.2 跳转执行79
3.4 程序选择结构80
3.4.1 if语句80
3.4.2 switch语句84
3.4.3 选择结构的嵌套86
3.4.4 选择结构程序举例90
3.5 程序循环结构92
3.5.1 while语句92
3.5.2 do语句94
3.5.3 for语句96
3.5.4 break语句97
3.5.5 continue语句98
3.5.6 循环结构的嵌套99
3.5.7 循环结构程序举例99
习题103
第4章 函数106
4.1 函数定义106
4.1.1 函数定义的一般形式106
4.1.2 函数返回109
4.2 函数参数110
4.2.1 形式参数110
4.2.2 实际参数111
4.2.3 参数传递机制111
4.2.4 函数调用栈112
4.2.5 const参数114
4.2.6 可变参数函数114
4.3 函数原型与调用116
4.3.1 函数声明和函数原型116
4.3.2 库函数的调用方法119
4.3.3 标准库函数120
4.4 内联函数124
4.5 函数调用形式125
4.5.1 嵌套调用125
4.5.2 递归调用128
4.6 作用域和生命期130
4.6.1 局部变量130
4.6.2 全局变量131
4.6.3 作用域132
4.6.4 程序映像和内存布局135
4.6.5 生命期138
4.7 对象初始化141
4.8 声明与定义143
4.9 变量修饰小结145
4.10 程序组织结构146
4.10.1 内部函数146
4.10.2 外部函数146
4.10.3 多文件结构147
4.10.4 头文件与工程文件148
4.10.5 提高编译速度149
4.11 函数应用程序举例151
习题154
第5章 预处理命令156
5.1 宏定义156
5.1.1 不带参数的宏定义157
5.1.2 带参数的宏定义159
5.1.3 #和##预处理运算163
5.1.4 预定义宏163
5.2 文件包含164
5.3 条件编译166
5.3.1 #define定义条件166
5.3.2 #ifdef、#ifndef166
5.3.3 #if-#elif167
5.4 其他命令168
习题169
第6章 数组171
6.1 一维数组的定义和引用171
6.1.1 一维数组的定义171
6.1.2 一维数组的初始化173
6.1.3 一维数组的引用173
6.2 多维数组的定义和引用175
6.2.1 多维数组的定义175
6.2.2 多维数组的初始化177
6.2.3 多维数组的引用178
6.3 数组与函数181
6.3.1 数组作为函数的参数181
6.3.2 数组参数的传递机制182
6.4 字符串185
6.4.1 字符数组185
6.4.2 字符串187
6.4.3 字符串的输入和输出189
6.4.4 字符串数组190
6.4.5 字符串处理函数191
6.5 数组应用程序举例196
习题206
第7章 指针208
7.1 指针与指针变量208
7.1.1 地址和指针的概念208
7.1.2 指针变量209
7.2 指针的使用及运算211
7.2.1 获取对象的地址211
7.2.2 指针的间接访问212
7.2.3 指针变量的初始化与赋值214
7.2.4 指针的有效性216
7.2.5 指针运算217
7.2.6 指针的const限定222
7.3 指针与数组224
7.3.1 指向一维数组元素的指针224
7.3.2 指向多维数组元素的指针228
7.3.3 数组指针232
7.3.4 指针数组234
7.3.5 指向指针的指针236
7.4 指针与字符串238
7.4.1 指向字符串的指针239
7.4.2 指针与字符数组的比较241
7.4.3 指向字符串数组的指针242
7.5 指针与函数244
7.5.1 指针作为函数参数244
7.5.2 函数返回指针值253
7.5.3 函数指针254
7.6 动态内存258
7.6.1 动态内存的概念258
7.6.2 动态内存的分配和释放259
7.6.3 动态内存的应用260
7.7 带参数的main函数264
习题266
第8章 自定义数据类型267
8.1 结构体类型267
8.2 结构体对象269
8.2.1 结构体对象的定义269
8.2.2 结构体对象的初始化272
8.2.3 结构体对象的使用272
8.3 结构体与数组274
8.3.1 结构体数组274
8.3.2 结构体数组成员274
8.4 结构体与指针275
8.4.1 指向结构体的指针275
8.4.2 指向结构体数组的指针277
8.4.3 结构体指针成员278
8.5 结构体与函数279
8.5.1 结构体对象作为函数参数279
8.5.2 结构体数组作为函数参数279
8.5.3 结构体指针作为函数参数280
8.5.4 函数返回结构体对象或指针280
8.6 共用体281
8.6.1 共用体概念及类型声明281
8.6.2 共用体对象的定义282
8.6.3 共用体对象的使用282
8.6.4 结构体与共用体嵌套284
8.7 枚举类型284
8.7.1 枚举类型的声明284
8.7.2 枚举类型对象285
8.8 位域285
8.8.1 位域的声明285
8.8.2 位域的使用287
8.9 用户自定义类型288
习题291
第9章 链表293
9.1 链表概述293
9.1.1 链表的概念293
9.1.2 单链表与双链表294
9.2 链表的创建295
9.2.1 创建单链表295
9.2.2 创建双链表298
9.3 链表的运算299
9.3.1 链表的遍历299
9.3.2 销毁链表301
9.3.3 查找结点302
9.3.4 链表的逆序304
9.4 结点的插入与删除304
9.4.1 单链表插入结点304
9.4.2 单链表删除结点305
9.4.3 双链表插入结点306
9.4.4 双链表删除结点307
习题308
第10章 文件311
10.1 文件概述311
10.1.1 文件系统311
10.1.2 流式文件312
10.1.3 文件指针312
10.2 文件打开与关闭313
10.2.1 文件打开313
10.2.2 文件关闭314
10.2.3 文件状态315
10.2.4 文件缓冲316
10.3 文件读写操作317
10.3.1 文件读写操作的基本形式317
10.3.2 读写字符数据317
10.3.3 读写字符串数据318
10.3.4 读写格式数据319
10.3.5 读写数据块321
10.4 文件定位324
习题325
第11章 算法327
11.1 算法基本概念327
11.1.1 什么是算法327
11.1.2 算法基本要素327
11.1.3 算法求解过程328
11.2 算法分析329
11.2.1 时间复杂度329
11.2.2 空间复杂度332
11.3 常用算法332
11.3.1 分治法332
11.3.2 动态规划335
11.3.3 贪心算法338
11.3.4 回溯法341
习题343
第12章 数据结构345
12.1 数据结构基本概念345
12.1.1 什么是数据结构345
12.1.2 逻辑结构与存储结构346
12.1.3 数据结构与数据类型346
12.2 线性表347
12.2.1 线性表的基本概念347
12.2.2 线性顺序表及其运算350
12.2.3 线性链式表及其运算355
12.3 栈和队列355
12.3.1 栈的定义355
12.3.2 栈的顺序存储及基本运算356
12.3.3 栈的链式存储及基本运算358
12.3.4 队列的定义358
12.3.5 队列的顺序存储及基本运算359
12.3.6 队列的链式存储及基本运算361
12.4 树和二叉树361
12.4.1 树的基本概念361
12.4.2 二叉树及其基本性质364
12.4.3 二叉树的存储结构367
12.4.4 二叉树的遍历368
习题370
第13章 高级编程技术372
13.1 配置开发环境372
13.1.1 开发环境的路径参数372
13.1.2 开发环境的路径设置373
13.1.3 开发环境的配置375
13.1.4 函数库的包含和连接376
13.1.5 函数库配置举例378
13.2 界面编程381
13.2.1 Windows编程的基本概念381
13.2.2 数据定义与数据类型382
13.2.3 消息与消息循环385
13.2.4 资源与资源文件387
13.2.5 Windows应用程序结构396
13.2.6 Windows编程框架402
13.2.7 图形输出409
13.2.8 事件处理425
13.2.9 控件与对话框434
13.3 图形编程441
13.3.1 图形编程概述441
13.3.2 OpenGL简介442
13.3.3 GLUT编程模式444
13.3.4 Win32编程模式449
13.4 多媒体编程456
13.4.1 MCI编程456
13.4.2 MCIWnd编程462
13.4.3 MMAPI编程467
13.5 网络编程472
13.5.1 Winsock简介472
13.5.2 Winsock编程473
13.5.3 TCP编程模式476
13.5.4 UDP编程模式480
13.6 数据库编程483
13.6.1 数据库编程概述483
13.6.2 ODBC简介484
13.6.3 ODBC编程487
13.6.4 数据库编程举例494
习题497
附录A ASCII码对照表499
附录B C语言关键字500
附录C C语言运算符及其优先级、结合性502
参考文献504