程序设计(C语言篇).doc

前言前 言不要删除行尾的分节符，此行不会被打印79- -第1章 概述目录前 言I第1章 程序设计基础概述11.1 计算机与程序设计语言11.1.1 计算工具的发展简史11.1.2 计算机与程序51.1.3 程序设计语言的演化与分类81.1.4 C程序设计语言简史121.2 学习C语言的理由151.3 程序设计与算法161.3.1 算法与程序的关系161.3.2 算法的特征161.3.3 算法的描述与分析171.4 C程序的布局形式与组成231.4.1 简单的C程序实例231.4.2 C程序的基本形式与组成261.4.3 C语言的符号类别27习题 129第2章 简单数据处理的编程基础12.1 数据类型12.1.1 C的数据类型12.1.2 基本数据类型32.2 常量与符号常量62.2.1 常量的表示62.2.2 符号常量102.3 变量的定义与属性112.3.1 变量的定义和初始化112.3.2 变量的作用域152.3.3 变量的存储类型192.4 基本输入输出函数252.4.1 格式输入输出函数272.4.2 字符输入输出函数342.4.3 字符串输入输出函数352.5 运算符与表达式362.5.1 算术运算符及其表达式382.5.2 关系运算符及其表达式422.5.3 逻辑运算符及其表达式432.5.4 赋值运算符及其表达式452.5.5 位运算符及其表达式462.5.6 特殊运算符及其表达式522.6 数据类型转换552.6.1 自动类型转换552.6.2 强制类型转换572.7 简单程序设计实例58习题262编程风格（二）62第3章 程序设计的基本流程结构633.1 C语句与程序流程控制概述633.1.1 C语句分类633.1.2 控制语句与程序基本流程结构653.2 分支结构控制语句663.2.1 if-else语句663.2.2 switch语句703.3 循环结构控制语句723.3.1 用goto语句和if语句构造循环723.3.2 while语句733.3.3 do-while语句743.3.4 for语句753.3.5 循环嵌套783.4 break和continue语句793.4.1 break语句793.4.2 continue语句803.5 基本流程结构程序设计实例81习题 385附录89参考文献90千万不要删除行尾的分节符，此行不会被打印。在目录上点右键“更新域”，然后“更新整个目录”。打印前，不要忘记把上面“Abstract”这一行后加一空行第1章程序设计基础概述第1章 程序设计基础概述1.1 计算机与程序设计语言1.1.1 计算工具的发展简史在人类历史的发展长河中，从远古时代开始，人类就不可避免地要和计数与计算打交道。而计算工具作为人们用来进行计算或者辅助计算的工具，也随着社会的发展和科技的进步，同样经历了由简单到复杂、由低级到高级的发展历程。l 早期的计算工具人的两手十指是天然的计算工具，无论是初学算术的儿童，还是知识丰富的成人，都会利用手指计算或计数。“掐指一算”固然方便，但不能存储计算结果。于是，远古时代的人们发明“结绳记事”，以延长自己的记忆能力，并将记事与计数联系在一起，“事大，大结其绳；事小，小结其绳，结之多少，随物众寡”。 随着畜牧业生产的发展，手指头和结绳不在满足需要。在我国，早在公元前5世纪，人们开始用竹子、骨头等材料制成的特殊形式的小棍子（称为“算筹”）来进行计算和计数，设计了相应的数据表示方法和计算规则。“算筹”作为我国古代十进制的计算工具，在公元前3世纪得到普遍的采用，一直沿用了二千年。汉书中说张良“运筹惟幄之中，决胜千里之外”的字句，“筹”即指算筹，但“运筹”已含有筹划的意思。如何用算筹表示数目呢？我国古代数学家们创造了纵式和横式两种摆法，都可以表示1到9（见图11）。记数的方法为：个位用纵式，十位用横式，百位再用纵式，千位再用横式，遇零用空位表示，这样从右到左、纵横相间，以此类推，就可以用算筹表示任意大的自然数。解决数学问题时，需要首先设计解决的具体方法和过程，然后按照算筹的“规则和方式”，对数据进行排列和布棍，并按照方法进行移动等操作，最终得到计算结果。祖冲之就是用算筹算出的值在3.1415926和3.1415927之间。 图11 算筹的纵式和横式排列方式 图12 珠算盘随着计算技术的发展，在求解更复杂的问题时，算筹显得越来越不方便。因此，大约在元朝，中国人在算筹的基础上发明了珠算盘（一般都称为算盘，见图12），并在15世纪得到普遍采用，后来流传到世界各地。用算盘进行珠算，必然就有对应这种工具的计算法则，人们在使用中总结出许多珠算口诀。时至今日，算盘仍然在我国和另外一些国家的日常经济活动中发挥着重要作用。l 机械式计算机15世纪开始后，随着经济、贸易事业的发展、金融业和航运业的繁荣，需要进行大量、繁重的复杂计算，这就迫切需要改进数字计算的方法。人们考虑既然像钟表这样的装置可以用齿轮传动来完成，那么也可以用这种装置来改造计算工具，使得计算得以用机械技术来实现。在此后的几百年里，一批杰出的科学家相继进行了各种机械式计算机的研制，其中的代表人物有帕斯卡、莱布尼茨和巴贝奇。1642年，19岁的法国数学家帕斯卡制造出一种手摇机械式加法机，这是世界上第一台用机械技术来实现数字运算的计算工具。这个机器的诞生说明，用一种纯粹机械的装置去代替人们的思考和记忆是完全可行的。帕斯卡去世后不久，因独立发明微积分而与牛顿齐名的德国年轻数学家莱布尼茨，在1673年发明了乘法机，这是第一台可以运行四则运算的计算机。莱布尼次同时还提出了“可以用机械代替人进行繁锁重复的计算工作”的伟大思想，这一思想至今鼓舞着人们探求新的计算机。到了19世纪，科学技术得到更多发展，迫切需要一种能依一定的“指令”自动控制的计算机。1822年，英国数学家巴贝奇发明了差分机，这台差分机可以保存3个5位的十进制数并进行加法运算，还能打印结果。虽然它只是一种特地供制表人员使用的专用机，但是它能按照设计者的控制自动完成一连串的运算。巴贝奇是计算机先驱者的鼻祖之一，早在现代计算机问世之前一百年，他就对这种计算机的主要组分部分和它们的功能提出了卓越的预见，并对以后计算机的研制产生了深远的影响。l 机电式计算机当电力技术有了很大发展之后，人们就开始考虑用电力代替人工作为计算机的动力，但由于基本计算元件仍然是机械式的，称之为电动式或者机电式计算机。1880年，美国统计学家赫尔曼霍勒瑞斯（Herman Hollerith）根据织布机原理，采用机电技术取代纯机械装置，制造了第一台可以自动进行加减四则运算、累计存档、制作报表的电动穿孔卡片式计算机，该机器参与了美国1890年的人口普查工作，使预计10年的统计工作仅用1年零7个月就完成了，是人类历史上第一次利用计算机进行大规模的数据处理。赫尔曼霍勒瑞斯于1896年创建了TMC公司，1911年，TMC与另外两家公司合并，成立了CTR公司。1924年，CTR公司改名为国际商业机器公司（International Business Machines Corporation），这就是赫赫有名的IBM公司。1941年，德国工程师康纳德楚泽（Konrad Zuse）研制成功Z-3型计算机，这是世界上第一台采用继电器进行控制、穿孔带作为输入的通用自动计算机。继电器其实是一种电磁开关装置，被广泛用于电话中继接线中。当电流切断，电磁消失，继电器就“闭合”，电话就可接通；否则，就不能接通电话。l 电子计算机机电计算机的运算速度很慢，而且很难进一步提高。1904年，第一只电子管真空电子二极管诞生，1906年，真空三极管诞生，这些电子管的开关速度比继电器速度快万倍。此后，电子技术得到更大发展，科学家就开始思考用二极管和三极管等电子元器件来制作计算机。在20世纪30年代后期，许多目光敏锐的学者，纷纷跻身于制造电子计算机这一诱人的前景。1942年，时任美国依阿华州立大学数学物理教授的阿塔纳索夫（John V. Atanasoff）与研究生贝瑞（Clifford Berry）组装了著名的ABC（Atanasoff-Berry Computer）计算机，共使用了300多个电子管，这也是世界上第一台具有现代计算机雏形的计算机。1946年2月14日，美国宾西法尼亚大学摩尔学院教授莫契利（John W. Mauchly）和埃克特（J. Eckert）共同研制成功了一台通用电子数字计算机ENIAC（Electronic Numerical Integrator And Computer)（见Error! Reference source not found.）。这台计算机总共安装了17468只电子管，7200个二极管，70000多电阻器，10000多只电容器，电路的焊接点多达50万个,机器被安装在一排2.75米高的金属柜里，占地面积为170平方米左右，总重量达到30吨，运算速度达到每秒钟5000次加法，可以在3/1000秒时间内做完两个10位数乘法。当然，它有不少缺点：体积大、耗电多；机器运行产生的高热量使电子管很容易损坏，只要有一个电子管损坏，整台机器就无法正常运转；修理时，得先从近1.8万个电子管中找出损坏期间，再换上新的，麻烦程度不言而喻。人类历史上的第一台电子计算机究竟是是阿塔纳索夫和贝瑞设计的ABC，还是莫契利和埃克特研制的ENIAC？这一发明的专利之争还上了美国的法庭，在我国的很多计算机历史著作中也是莫衷一是。但不过怎样，现代计算机的发展终于拉开了序幕，人类历史开始了一场新的信息革命。图13 ENIAC计算机在以后的40多年里，计算机技术发展异常迅速，变化日新月异，构造计算机的电子元器件不断革新，运算速度和处理得到极大提高，对人们的生活和生成方式产生了巨大的影响。按基础元器件的性质，将此后计算机的发展阶段划分为若干“代”。 第一代（19461958）：电子管数字计算机在整个20世纪50年代，计算机的逻辑元件基本都采用电子管，内部的存储器件采用磁鼓、磁芯，应用以科学计算为主。其特点是体积大、耗电大、可靠性差、价格昂贵、维修复杂，但是奠定了以后计算机技术的基础。第二代（19581964）：晶体管数字计算机到了60年代，晶体管被使用到计算机中。相较于体积庞大的电子管，晶体管体积更小，速度更快，价格更加低廉，性能更加可靠。因此，这一代的计算机体积小、速度快、功耗低、性能更稳定，主要用于原子科学的大量数据处理，但是机器价格昂贵，生产数量极少。世界上第一台晶体管计算机是贝尔实验室为美国空军所研制。 第三代（19641971）：集成电路数字计算机晶体管比起电子管当然是巨大的进步，但是晶体管仍然会产生大量的热量，并导致计算机内部的敏感部分。之后，科学家开始逐渐将大量晶体管、其他各种电器组件和连接导线安置在一片硅板上，形成集成电路，是计算机变得更小、功耗更低、可靠性更高。IBM360机型是这一时期的著名代表。第四代（1971现在）：大规模集成电路计算机在出现集成电路后，后续的发展方向则是扩大集成电路的规模，在工艺上采用大规模集成电路，让计算机在性能上有更大的提升。大规模集成电路（LSI）可以在一个芯片上容纳几百个元件，到了80年代，超大规模集成电路（VLSI）在芯片可容纳几十万个元件，后来的更扩充到到百万级。在硬币大小的芯片上容纳如此数量的元件，使得计算机的体积和价格不断下降，而功能和可靠性不断增强。计算机工业发展到今天，集成电路的密度已接近当前所用技术的理论极限。为了使得晶体管计算机更够继续发展下去，研究者仍然在探索运算速度更快、处理能力更强的新一代计算机，包括寻找新的计算机结构，借鉴生物界的各种处理问题的方式，进行生物计算机模型等的研究。1.1.2 计算机与程序计算机这种新型的计算和处理工具的发明，对人类生活和生产方式的影响史无前例。如今，计算机已经渗入到人类生活的方方面面，几乎是无所不在、无时不有。人们可以在家用计算机上制作视频、书籍、音乐和电影，并传播给他人；通讯也因个人计算机和互联网而变得迅速便捷；视频聊天可让距离遥远的朋友们像面对面一样地聊天，还不用担心像电话一样产生高额费用。可以说，计算机成为了人们日常生活中须臾不可缺少的工具，极大地改变了人类的生活和生产方式。计算机如此重要、如此强大，它到底是怎么工作的呢？我们首先从计算机的基本结构说起。l 冯诺依曼体系结构从ENIAC诞生到今天，计算机的应用范围不断扩大，解决的问题规模和复杂程度也不断增加，但计算机基本的结构仍然一直遵循“冯诺依曼体系结构”，该结构由现代计算机之父冯诺依曼在1945年6月总结提出。冯诺依曼体系结构的基本思想为：1）计算机的组成部件应包含有五个基本部件：控制器、运算器、存储器（指内存储器）、输入设备、输出设备。其中，控制器和运算器就是中央处理器CPU；存储器是按地址访问的线性编址的一维结构，每个单元所能存储的数据位数是固定的；控制器靠指令指挥其他部件工作，而使用者要用指令表达自己的计算意图，并交给控制器去控制执行。2）在计算机内部，指令和数据均用二进制表示。每条指令一般具有一个操作码和一个地址码，其中操作码表示运算性质，地址码指出操作数在存储器中的地址。一台计算机所能执行的各种不同指令的全体，叫做计算机的指令系统，每种计算机均有自己的特定的指令系统，其指令内容和格式都有所不同。3）采用存储程序方式。程序就是一系列按一定顺序排列组合的计算机指令集合，执行程序的过程就是计算机的工作过程。程序和数据不加区别混合存储在同一个存储器中。程序的全部指令在存储器中按其执行顺序存放，由控制器内部的指令计数器指明要执行的指令所在的存储单元地址。指令计数器只有一个，一般按顺序递增，但执行顺序可按运算结果或当时的外界条件而改变。使用者将编好的程序送入存储器中之后，就可启动计算机工作，期间无需操作人员干预，计算机能自动逐条取出指令和执行指令。 图14 冯诺依曼计算机结构 图15 计算机的处理过程尽管在在冯诺依曼体系结构下，计算机在运行时是使用内存来保存程序和数据，但绝大多数的内存都有一个缺点：断电即失，当计算机被断电关机后，内存中的信息将会全部丢失。为此，需要有一种不需要依赖电力就可以保存信息的存储设备，这往往就是硬盘等外存储器。根据冯诺依曼计算机的原理，从较宏观的角度，计算机的工作处理流程可以简单概括为输入、处理、输出和存储4个过程。1）输入：当使用者从输入设备（如键盘、鼠标）输入程序和数据后，将用户的输入保存到内存储器（简称内存）中；2）处理：根据程序要求对数据进行加工处理，并按一定方式进行转换；3）输出：将处理结果在输出设备（如显示器、打印机等）上显示或者打印输出等；4）存储：将用户输入的原始数据或处理结果保存到硬盘等外存储器。这4个步骤形成一个循环过程。输入、处理、输出和存储并不一定严格按照上述的顺序操作，计算机根据程序的要求决定采取哪一个步骤。在较微观的角度，计算机在自动执行内存中的程序时，程序指令的执行过程为：1）取指令：从存储器某个地址中取出要执行的指令，再送到控制器的指令寄存器暂存。每条指令明确规定了计算机从哪个地址取数，进行什么操作，然后送到什么地方去等步骤。2）分析指令：把保存在指令寄存器中的指令送到指令译码器，译出对应的微操作。3）执行指令：控制器根据指令译码器的结果，向各个部件发出完成操作所需的一系列控制电位信号，完成指令规定的操作，比如从内存中取出数据，让运算器进行指定的运算和逻辑操作等，然后再按地址把结果送到内存中去。 4）形成下一条指令地址。 程序计数器中的地址值变化，为执行下一条指令做好准备，例如程序计数器中的地址值自增1。l 程序的作用到此，我们可以看出，无论计算机的功能多么强大，都是在程序的控制之下运行的。计算机的CPU、内存、输入/输出设备等硬件仅仅是建立了计算机运行的物质基础，而程序则提供了发挥硬件功能的方法和手段，扩大其应用范围，并能改善人机界面，方便用户使用。没有配备程序的计算机称为“裸机”，是没有多少实用价值的。计算机中的程序往往会有一些相应的文档资料，说明程序的使用方法和要求等。而在一个具体的应用功能中，可能需要有多个程序来描述实现应用需要的计算机指令集合。经常将这些程序、相应的文档一起，称为“软件”。硬件与软件的关系可以形象地比喻为：硬件是计算机的“躯体”，软件是计算机的“灵魂”。因此，要想让计算机能发挥其强大的处理能力，实现我们的应用需求，就需要靠编写优良的程序来“控制”计算机硬件去完成。1.1.3 程序设计语言的演化与分类 要让计算机能够实现一定的功能，首先就需要给计算机输入完成这项功能的程序指令。计算机硬件能够直接理解和处理的指令代码的形式是纯粹的二进制数“0”和“1”的各种序列组合，也就是机器代码。指令代码有一定的位数，内部实际上包含若干段，各段的编码表示不同的含义。每种机器的指令，其格式和代码所代表的含义都是硬性规定的，故称之为面向机器的语言，也称为机器语言。假设某台计算机字长为16位，即有16个二进制数组成一条指令或其它信息。16个0和1可组成各种排列组合，通过线路将这些变成电信号，让计算机执行各种不同的操作。如某条指令为1011011000000000，表示让计算机进行一次加法操作；而指令1011010100000000则表示进行一次减法操作。这些指令的前八位表示操作码，而后八位表示地址码。从上面两条指令可以看出，它们只是在操作码中从左边第0位算起的第7和第8位不同。这种机型可包含256（=28）个不同的指令。因此，程序员要么直接用机器语言来编写计算机要执行的程序，要么用人类更容易理解的某种程序设计语言将计算机处理的过程表达出来，形成程序设计语言形式的程序，再由计算机运行第三方特殊的程序，将程序设计语言程序翻译成机器可理解的二进制指令集合。事实上，随着计算机技术的发展，程序设计语言（也叫编程语言）也经过了一个不断演化的过程，经历了从机器语言、汇编语言，到高级语言的发展历程。l 机器语言：第一代编程语言计算机硬件所能理解的语言就是二进制“0”和“1”组合成的机器语言。在电子计算机发明之初，人们只能用机器语言去命令计算机工作，也就是写出一串串由“0”和“1”组成的指令序列交由计算机执行。例如，假设我们要用Intel x86计算机来实现1+1的计算，如果用机器语言来编写运算程序，则程序内容如下： 10111000 00000001 00000000 00000101 00000001 00000000在计算机刚诞生不久的年代，程序员要给计算机输入程序，得先在纸上把程序设计好，然后进行持续数周的扳开关和接电线的工作，期间万一哪根线断了，排查起来简直就是恶梦。后来，通过打孔卡片（有孔和没孔代表二进制的“1”和“0”）进行程序输入，程序员的负担稍有减轻。总体来说，用机器语言编写程序十分痛苦，当程序有错时，修改调试尤其麻烦。而且，由于不同类型计算机的指令系统往往各不相同，在一台计算机可以执行的程序，在另外的计算机上就没法执行。但由于使用的直接是计算机的指令，故而运算效率最高。 l 汇编语言：第二代编程语言为了减轻用机器语言编程的痛苦，后来就开始用一些专门的英文单词、符号串来替代一个特定指令的二进制串，如用“ADD”代表加法，“MOV”代表数据移动等等。用符号串编写的程序比较容易理解，纠错及维护都则更为方便。把这些符号串及其语法规则构成的程序设计语言称为汇编语言。计算机并不理解这些符号，因此需要一个专门的程序，专门负责将这些符号翻译成二进制形式的机器语言，这种翻译程序被称为编译程序。例如，用汇编语言编写计算1+1程序，内容如下： MOV AX, 1 ADD AX, 1该程序经过编译程序的翻译，最终会得到计算1+1的机器语言程序。相较于机器语言，用汇编语言编写程序负担更轻。但汇编语言仍然距离机器语言较近，编程时需要对计算机硬件有良好的理解；用汇编语言编写的程序，其内部结构和逻辑理解起来也非常困难，因此阅读、调试、维护的效率仍然较低；另外，不同类型的CPU，其所支持的汇编语言形式也不尽相同，因此程序可移植性较差。l 高级语言：第三代编程语言机器语言和汇编语言都是面向具体硬件进行操作的低级语言，语言的语法完全依赖于特定的机器类型，要求使用者必须对计算机的硬件结构及其工作原理都十分熟悉，这对非专业人员来说过于困难。因此，研究者们意识到，应该设计接近于数学语言或人类的自然语言、同时又不依赖于计算机硬件、编出的程序能在很多机器上通用的程序设计语言；相对于机器语言和汇编语言，把这样的设计语言称为高级程序设计语言。自从1955年第一个完全脱离机器硬件的高级语言Fortran（名称取自“FORmula TRANslator”，公式翻译器）问世之后，在此后的几十年间，高级程序设计语言层出不穷。在这些程序设计语言中，根据所编写的程序被翻译成机器语言的方式，可将语言分类编译型和解释型。编译型：程序在执行之前，首先需要经过编译处理，将程序全部翻译为机器语言的可执行文件。在程序正式运行时就不再需要翻译过程，因此这类语言编写的程序执行效率高。解释型：不是提前一次性地将全部程序都翻译为机器语言，而是在程序执行期间，专门有一个解释器，首先对要执行的语句临时翻译成机器代码，再执行该语句。在以下部分，我们来总结一下不同时期所出现的主要的程序设计语言。1）1950年代除了Fortran，在1950年代被设计出来的高级语言还有：LISP（名称取自“LISt Processor”，列举处理器）、COBOL（名称取自COmmon Business Oriented Language，通用商业导向语言）。这三个现代编程语言衍生的其它高级语言直到今日仍旧广泛地被采用。1950年代晚期的另外一个里程碑是由美国与欧洲计算机学者针对“算法的新语言”所组成的委员会出版的ALGOL 60报告（名称取自“ALGOrithmic Language”，算法语言）。2）1960年代1970年代在这一时期，编程语言的发展也有重大的成果。大多数现在所使用的主要语言范式都是在这段期间中发明。这个阶段产生的重要的编程语言有： Pascal：1970产生，第一个结构化程序设计语言。 C：在1969至1973年间由贝尔实验室的研究人员丹尼斯里奇（Dennis M. Ritchie）与肯汤普逊（Ken Thompson ）开发，可用于系统程序开发。 Smalltalk：于1970年代中期所开发，是一个完全从零开始设计的面向对象编程语言。 Prolog：1972年产生，是第一个逻辑程序语言。3）1980年代从8 0年代初开始，程序设计思想有了极大的变革，面向对象的程序设计成了主流。这一阶段产生的编程语言与之前相较，显得更为强大。C+语言结合了面向对象和系统程序设计两方面的优点。在这段期间被开发出来的重要语言包括有： C+：产生于1980年，拥有面向对象的特性，同时又具有C语言的优点。 Ada：产生于1983年 Common Lisp：1984年 Perl：1987年 Tcl：1988年4）1990年代编程语言在1990年代未见到有什么重大的创新，大多都是以前构想的重组或变化。这段时期主要着眼与提升程序员的生产力，许多“快速程序开发（RAD）”语言应运而生，这些语言大多都有相应的集成开发环境、垃圾回收等机制，且大多是先前语言的衍生语言。另外，产生了几种新的脚本编程语言，这些语言并非直接从其他语言衍生。脚本语言比RAD语言的开发效率更高，但是执行速度较慢。尽管如此，脚本语言在网络层面的应用上大放异彩。在这段期间被开发出来的重要语言包括有： Python: 1991年产生，是一种解释性的面向对象的动态开源脚本编程语言。 Java：诞生于1991，是一种跨平台、面向对象、解释性、可移植的动态语言。 Ruby：1993年开始编写，1995年正式发布，是一种为支持简单面向对象编程而设计的语言。 Lua：1993年诞生，是脚本语言，被广泛应用于游戏编写领域。5）21世纪编程语言持续在学术及企业两个层面中发展进化，目前的一些发展趋势有：在语言中增加安全性与可靠性验证机制，如额外的堆栈检查；支持面向组件（component-oriented）的软件开发；重视分布式及移动计算的应用；能与数据库良好整合；支持使用Unicode编写程序，使得源代码不会受到ASCII字符集的限制等。在这段期间被开发出来的重要语言包括有： C#：2001年由微软公司推出，是一种最新的、面向对象的编程语言。它使得程序员可以快速地编写各种基于Microsoft .NET平台的应用程序。 Visual Basic .NET：2001年问世，是基于微软.NET框架的面向对象的中间解释性语言，可以看作是Visual Basic在.Net框架平台上的升级版本，增强了对面向对象的支持。 Go：由搜索引擎公司Google于2009年推出，设计者的目标是希望用这种语言编程时，在不损失应用程序性能的情况下能够降低代码的复杂性。1.1.4 C程序设计语言简史 l C语言的诞生C程序设计语言的原型可追溯到早期的ALGOL 60语言。ALGOL是计算机发展史上首批产生的高级语言，它的诞生在计算机科学中具有重要意义。1958年5月，由美国计算机学会（ACM）的4名代表和德国应用数学和力学学会（GAMM）的4名代表，在瑞士苏黎世召开ACM-GAMM会议，讨论规划一种新型的编程语言，叫作国际代数语言（IAL）。 为了描述即将诞生的语言，约翰巴科斯（John Backus）首先提出了一套用来描述语言的语言，称为巴科斯范式（后来也被称为巴科斯-诺尔范式，简称BNF范式）。与会8名代表充分利用自己在语言设计方面的经验，并利用BNF范式，制定出国际代数语言的标准。后经ACM小组的主席艾伦佩利（Alan Perlis）建议，“IAL”被ALGOL（ALGOrithmic Language的缩写，即算法语言）所取代。 在不久之后的1958年年底，第一套ALGOL语言及其编译器成功地开发出来了，按照年份，命名为ALGOL58。 ALGOL58诞生一年多之后，佩利、巴科斯等主要参与者们，都在实践当中对新语言进行了更真实的体会。关心ALGOL的13名著名计算机科学家来到巴黎，再次对语言设计进行讨论。为了更清晰地描述下一代ALGOL语言，彼得诺尔（Peter Naur）对BNF范式进行了大幅度的简化（这也是巴科斯范式就叫巴科斯-诺尔范式的原因）。13名代表对彼得诺尔修改后的范式通过后，就开始讨论新一代ALGOL本身的设计。经过艰苦漫长的讨论，终于终一了意见，完整地规划出了新一代ALGOL语言，按照年份，命名为ALGOL60。在会议的最后，由彼得诺尔对此进行总结，整理会议讨论的ALGOL60的所有特性，形成了后来著名的算法语言ALGOL60报告。算法语言ALGOL60报告的撰写充分体现了彼得诺尔的才华和BNF范式的力量。在Algol 60报告出版之前，计算机语言是通过说明性的使用手册和编译代码本身，而没有正式定义。而这个报告通过使用BNF来定义语法，并用精心选择的说明文字定义语义，从而简洁、有力而又清晰，短短的17页报告内容，完整地描述了ALGOL60语言的所有特性，却不依赖任何机器细节，从而成为了计算机科学史上的名作。到了1960年夏天，荷兰计算机科学家狄克斯特拉（Edsger Dijkstra）开发出了ALGOL60的编译器，ALGOL正式登上了计算机科学的舞台。Algol 60的发展是一群天才在一起的工作成果。其中，艾伦佩利是首届（1966年）图灵奖获得者，狄克斯特拉是1972年的图灵奖获得者，约翰巴科斯是1977年的图灵奖获得者，彼得诺尔是2005年图灵奖的获得者。1963年，剑桥大学将ALGOL 60语言发展成为CPL（Combined Programming Language）语言。但CPL的最大缺点是太大，不能在很多应用程序中使用。1967年，剑桥大学的马丁理察斯（Matin Richards）对CPL语言进行了简化，设计出了BCPL（Basic CPL）语言。1970年，美国贝尔实验室的肯汤普逊（Ken Thompson）用PDP-7汇编语言，为PDP-7系统编写了一简易的操作系统UNIX。但是，用汇编语言编写的操作系统难以调试，理解起来也很困难，因此他想利用高级语言BCPL的一些优点，但发现BCPL太慢了，因此对BCPL进行了实验性的修改，并为它起了一个有趣的名字B语言，意思是将CPL语言进行压缩，提炼出它的精华。1972年，当PDP-11系统进入贝尔实验室后，肯汤普逊又用PDP-11汇编语言重新实现了UNIX。而肯汤普逊的同伴，同样在贝尔实验室的丹尼斯里奇（Dennis M. Ritchie）从BCPL中抽取了一些共性放入B语言中，对B进行改进，并且在里面加入了数据类型，他把这个扩展的语言称为NB（New B）。随后，由于他对新语言又进行大量修改，于是他取了B后面的字母作为这种语言的名字，这就是C语言。1973年，丹尼斯里奇完成了C语言核心。然后，肯汤普逊和丹尼斯里奇用C重写了整个UNIX内核。之后，他们C语言多次做了改进，但主要还是在贝尔实验室内部使用。 为了推广UNIX操作系统，肯汤普逊在1977年发表了不依赖于具体机器硬件系统的C语言编译文本可移植的C语言编译程序。随着UNIX的日益广泛使用，C语言也迅速得到推广。 鉴于肯汤普逊和丹尼斯里奇在贝尔实验室的出色工作，美国政府在1999年向他们授予了美国国家技术奖章。他们在1983年就已经共同获得了图灵奖。图 16 美国前总统克林顿向肯汤普逊（左一）和丹尼斯里奇（左二）授予国家技术奖章1978年，Brian W. Kernighian和Dennis M. Ritchie出版了长久不衰的经典之作The C Programming Language，把C从贝尔实验室推向世界，从而使C语言成为目前世界上流行最广泛的程序设计语言之一。在这本书中介绍的C语言标准也被C语言程序员称作“K&R C”。l C语言的标准化在C语言诞生后，在工业界得到了广发的使用。到了1980年代年，随着个人计算机PC的日益普及，很多个人和计算机公司针对C语言进行了各种形式的改进和扩充。由于没有统一的标准，使得这些C语言之间出现差异。这种情况自然会给C的学习者带来困惑，对C语言程序的理解和移植性带来极大不便。为了实现C语言的“书同文”目标，1983年，美国国家标准局（American National Standards Institute，ANSI）开始综合C语言问世以来的各种发展与扩充，来制定新的标准草案。经过旷日持久的争论与修改，到了1989年12月，C语言标准草案最终被ANSI委员会采纳为第一个完整的C语言标准，这就是我们经常所说的“ANSI C”，也简称C89。在随后的1990年，国际标准化组织ISO也接受了ANSI C为ISO C的标准（ISO 9899-1990），这也是有些文章或者书籍中将ANSI C又称为C90的原因。之后，不同的计算机软件厂家以C89为基础，开发出了针对不同计算机类型的C语言编译系统，如在PC计算机上使用的Microsoft C 、Turbo C、Borland C等，它们的语法和语句功能是一致的，差异主要体现在各自的标准函数库中收纳的函数种类、格式和功能上。在ANSI标准化后，尽管C继续在改进，但C语言的标准在一段相当的时间内都保持不变。1999年，在对C语言进行了一些修改和完善之后，ANSI/ISO委员会又批准了新的语言标准C99，正式名称是ISO/IEC9899:1999。1.2 学习C语言的理由C语言自1970年代诞生以来到现在，已经经历了近40年的时间了。在此期间，产生出的高级语言有2000多种，但其中能被广泛使用的不过几十种，绝大部分都是昙花一现。而在如此之多的高级语言当中，C语言经久不衰，市场份额在近10年来长期保持在15%至20%之间，在TIOBE编程语言社区排行榜上一直处于前列。在网络技术迅猛发展的今天，应用软件开发的主流语言，则基本上是Java、C#等面向对象编程语言、Python和PHP等脚本语言。而C语言应用的空间主要是在系统软件开发、嵌入式软件开发方面。从趋势上看，C语言已不再是软件开发的主流语言。即使如此，对于初学者来说，将C语言作为学习程序设计的入门语言，仍有充分的理由。主要原因如下。 C语言是一门很基础的语言，兼顾低级语言和高级语言的特点。所以，学会C语言，则会比较容易熟习计算机硬件结构，理解计算机原理。 C语言一个特点就是接近计算机硬件，很多系统软件开发（如Linux操作系统、MySQL数据库管理系统等）、设备驱动程序是用C语言编写的。所以，学习C语言，可以为开发系统软件打下基础。 C语言在嵌入式软件、自动控制软件开发中被广泛应用。 C语言是很多语言的元语言，如面向对象程序设计语言Java、脚本语言Python，都是用C语言编写而成。 C语言的语法严格，逻辑严密。学习C语言，可锻炼面向计算机的思维能力，培养程序设计的基本素质。1.3 程序设计与算法1.3.1 算法与程序的关系计算机在执行一个程序时，都是针对一定的输入数据，根据程序的要求，在内部对数据进行一定的处理，然后再输出处理结果。问题的求解和处理步骤可能不止一种，如对N个输入的数进行从小到大的排序，可以有很多方法。计算机在处理一个问题时到底该采用什么样的步骤？这就靠程序中的指令来确定。程序犹如菜谱，给出了计算机求解时具体的处理步骤和方法。著名的计算机科学家沃思（N. Wirth）提出过一个公式：程序 = 数据结构 + 算法数据结构：就是对所要处理的数据的描述和组织形式。比如要对N个数进行排序，如何看待这N个数之间的逻辑关系？将这些数据存到内存中时，在内存一维的线性空间中该如何组织它们之间的物理关系？这就是数据结构。算法：算法是程序的逻辑抽象，是解决某类客观问题的数学过程。程序设计语言仅仅是对问题解决步骤的具体描述方法，而解决步骤的逻辑关系和具体过程，则需要程序的设计者去构思，并将构思的结果用程序设计语言描述出来，从而形成程序。这个问题解决的步骤就是算法。 若把数据结构比喻为建筑工程中的建筑设计图，那么算法就是工程中的施工流程图。因此，算法在程序中具有关键的作用，面对问题，在编写程序之前，首先需要设计好解决的算法。1.3.2 算法的特征简单来说，算法（Algorithm）就是解决问题的方法。一般情况下，我们所说的算法仅指计算机算法，因此，算法就是一系列设计良好的计算过程和步骤，用来将输入数据转换成输出结果。根据要解决问题的类型，可将算法分类两大类：1）数值运算算法：目标是求解数值解的问题，如求一个函数的定积分、求方程的根等。2