高教类课件：C程序设计(第二版).ppt

1、C 程序设计(第二版)总 目 录第1章C语言概述第2章程序的灵魂算法第3章数据类型、运算符与表达式第4章最简单的C程序设计顺序程序设计第5章选择结构程序设计第6章循环控制第7章数组第8章函数第第9章预处理命令章预处理命令第第10章指针章指针第第11章结构体与共用体章结构体与共用体第第12章位运算章位运算第第13章文件章文件第第14章章C+对对C的扩充的扩充第第15章章C+的面向对象基础的面向对象基础第第16章常见错误和程序调试章常见错误和程序调试第1章 C语言概述1.1 C语言出现的历史背景1.2 C语言的特点1.3 简单的C程序介绍1.4 C程序的上机步骤1.5 习题1.1 C语言出现的历史

2、背景C语言是国际上广泛流行的计算机高级语言,既可用来写系统软件，也可用来写应用软件。C语言是在B语言的基础上发展起来的，它的根源可以追溯到ALGOL 60。1960年出现的ALGOL 60是一种面向问题的高级语言，它离硬件比较远，不宜用来编写系统程序。1963年英国的剑桥大学推出了CPL(combined programming language)语言。CPL语言在ALGOL 60的基础上接近硬件一些，但规模比较大，难以实现。1967年英国剑桥大学的Matin Richards对CPL语言做了简化，推出了BCPL(basic combined programming language)语言。1

3、970年美国贝尔实验室的Ken Thompson 以BCPL语言为基础，又做了进一步简化，设计出了很简单的而且很接近硬件的B语言(取BCPL的第一个字母)，并用B语言写了第一个UNIX操作系统，在PDP7上实现。1971年在PDP11/20上实现了B语言，并写了UNIX操作系统。但B语言过于简单，功能有限。1972年至1973年间，贝尔实验室的D.M.Ritchie 在B语言的基础上设计出了C语言(取BCPL的第二个字母)。C语言既保持了BCPL和B语言的优点(精练，接近硬件)，又克服了它们的缺点(过于简单，数据无类型等)。最初的C语言只是为描述和实现UNIX操作系统提供一种工作语言而设计的。

4、1973年，K.Thompson和D.M.Ritchie两人合作把UNIX的90%以上用C改写，即UNIX第5版。原来的UNIX 操作系统是1969年由美国的贝尔实验室的K.Thompson和D.M.Ritchie开发成功的，是用汇编语言写的。1972年至1973年间，贝尔实验室的D.M.Ritchie 在B语言的基础上设计出了C语言(取BCPL的第二个字母)。C语言既保持了BCPL和B语言的优点(精练，接近硬件)，又克服了它们的缺点(过于简单，数据无类型等)。最初的C语言只是为描述和实现UNIX操作系统提供一种工作语言而设计的。1973年，K.Thompson和D.M.Ritchie两人合作

5、把UNIX的90%以上用C改写，即UNIX第5版。原来的UNIX 操作系统是1969年由美国的贝尔实验室的K.Thompson和D.M.Ritchie开发成功的，是用汇编语言写的。后来，C语言多次做了改进，但主要还是在贝尔实验室内部使用。直到1975年UNIX第6版公布后，C语言的突出优点才引起人们的普遍注意。1977年出现了不依赖于具体机器的C语言编译文本可移植C语言编译程序，使C移植到其他机器时所需做的工作大大简化了，这也推动了UNIX操作系统迅速地在各种机器上实现。例如VAX、AT&T等计算机系统都相继开发了UNIX。随着UNIX的日益广泛使用，C语言也迅速得到推广。C语言和UNIX可以

6、说是一对孪生兄弟，在发展过程中相辅相成。1978年以后，C语言已先后移植到大、中、小、微型机上，已独立于UNIX和PDP了。现在C语言已风靡全世界，成为世界上应用最广泛的几种计算机语言之一。以1978年发表的UNIX第7版中的C编译程序为基础，Brian W.Kernighan和Dennis M.Ritchie(合称K&R)合著了影响深远的名著The C Programming Language，这本书中介绍的C语言成为后来广泛使用的C语言版本的基础，它被称为标准C。1983年，美国国家标准化协会(ANSI)根据C语言问世以来各种版本对C的发展和扩充，制定了新的标准，称为ANSI C。ANSI

7、 C比原来的标准C有了很大的发展。K&R在1988年修改了他们的经典著作The C Programming Language，按照 ANSI C 标准重新写了该书。1987年，ANSI又公布了新标准87 ANSIC。1990年，国际标准化组织ISO(International Standard Organization)接受87 ANSI C为ISO C 的标准(ISO 98991990)。目前流行的C编译系统都是以它为基础的。本书的叙述基本上以ANSI C 为基础。目前广泛流行的各种版本C语言编译系统虽然基本部分是相同的，但也有一些不同。在微型机上使用的有Microsoft C、Turbo

8、C、Quick C、BORLAND C等，它们的不同版本又略有差异。因此，读者应了解所用的计算机系统所配置的C编译系统的特点和规定(可以参阅有关手册)。1.2 C语言的特点一种语言之所以能存在和发展，并具有生命力，总是有其不同于(或优于)其他语言的特点。C语言的主要特点如下。(1)语言简洁、紧凑，使用方便、灵活。C语言一共只有32个关键字，9种控制语句，程序书写形式自由，主要用小写字母表示，压缩了一切不必要的成分。下面将C与PASCAL语言做一比较。(2)运算符丰富。C的运算符包含的范围很广泛，共有34种运算符。C把括号、赋值、强制类型转换等都作为运算符处理，从而使C的运算类型极其丰富，表达式

9、类型多样化。灵活使用各种运算符可以实现在其他高级语言中难以实现的运算。(3)数据结构丰富，具有现代化语言的各种数据结构。C的数据类型有整型、实型、字符型、数组类型、指针类型、结构体类型、共用体类型等。能用来实现各种复杂的数据结构(如链表、树、栈等)的运算。尤其是指针类型数据，使用起来比PASCAL更为灵活、多样。(4)具有结构化的控制语句(如ifelse语句、while语句、dowhile语句、switch语句、for语句)。用函数作为程序的模块单位，便于实现程序的模块化。C是良好的结构化语言，符合现代编程风格的要求。(5)语法限制不太严格，程序设计自由度大。例如对数组下标越界不做检查，由程序

10、编写者自己保证程序的正确。对变量的类型使用比较灵活，例如整型数据与字符型数据可以通用。一般的高级语言语法检查比较严，能检查出几乎所有的语法错误。而C语言允许程序编写者有较大的自由度，因此，放宽了语法检查。程序员应当仔细检查程序，保证其正确，而不要过分依赖C编译程序去查错。“限制”与“灵活”是一对矛盾。限制严格，就失去灵活性;而强调灵活，就必然放松限制。一个不熟练的编程人员，编一个正确的C程序可能会比编一个其他高级语言程序难一些。也就是说，对用C语言的人，要求对程序设计更熟练一些。(6)C语言能进行位(bit)操作，能实现汇编语言的大部分功能，可以直接对硬件进行操作。因此C既具有高级语言的功能，

11、又具有低级语言的许多功能，可用来写系统软件。C语言的这种双重性，使它既是成功的系统描述语言，又是通用的程序设计语言。有人把C称为“高级语言中的低级语言”或“中级语言”，意为兼有高级和低级语言的特点。按此观点可将各语言分类如下：高级:BASIC,FORTRAN,COBOL,PASCAL,Ada,Modula-2；中级:C,FORTH,宏汇编；低级:汇编语言一般仍习惯将C语言称为高级语言，因为C程序也要通过编译、连接才能得到可执行的目标程序，这是和其他高级语言相同的。C的以上特点，读者现在也许还不能深刻理解，待学完C以后再回顾一下，就会有比较深的体会。我们从应用的角度出发对C语言和其他传统的高级语

12、言作一简单比较。从掌握语言的难易程度来看，C语言比其他语言难一些。BASIC是初学者入门的较好的语言，FORTRAN也比较好掌握。对科学计算多用FORTRAN或PL/;对商业和管理等数据处理领域，用COBOL为宜。C语言虽然也可用于科学计算和管理领域，但并不理想，C的特长不在这里。对操作系统和系统实用程序以及需要对硬件进行操作的场合，用C语言明显地优越于其他高级语言，有的大型应用软件也用C语言编写。从教学角度，由于PASCAL是世界上第一个结构化语言，而曾被认为是计算机专业的比较理想的教学语言。目前在数据结构等课程中一般用PASCAL语言举例。但PASCAL语言难以推广到各实际应用领域，到目前

13、为止基本上只是教学语言。C语言也是理想的结构化语言，且描述能力强，同样适于教学。操作系统课程多结合UNIX讲解，而UNIX与C不可分，因此，C语言已经成为被广泛使用的教学语言。C除了能用于教学外，还有广泛的应用领域，因此更有生命力。PASCAL和其他高级语言的设计目标是通过严格的语法定义和检查来保证程序的正确性，而C则是强调灵活性，使程序设计人员能有较大的自由度，以适应宽广的应用面。总之，C语言对程序员要求较高。程序员使用C语言编写程序会感到限制少，灵活性大，功能强，可以编写出任何类型的程序。现在，C语言已不仅用来编写系统软件，也用来编写应用软件。学习和使用C的人已越来越多。1.3 简单的C程

14、序介绍下面先介绍几个简单的C程序，然后从中分析C程序的特性。例 1.1 main()printf(This is a C program.n);本程序的作用是输出以下一行信息:This is a c program.其中 main 表示“主函数”。每一个C程序都必须有一个 main 函数。函数体由大括弧括起来。本例中主函数内只有一个输出语句，printf是C语言中的输出函数(详见第4章)。双引号（双括号）内的字符串原样输出。“n”是换行符，即在输出“This is a c program.”后回车换行。语句最后有一分号。例 1.2main()/*求两数之和*/int a，b，sum;/*这是定

15、义变量*/a=123;b=456;/*以下3行为C语句*/sum=a+b;printf(sum is%d/n，sum);本程序的作用是求两个整数a和b之和sum。/*/表示注释部分，为便于理解，我们用汉字表示注释，当然也可以用英语或汉字拼音作注释。注释只是给人看的，对编译和运行不起作用。注释可以加在程序中任何位置。第2行是声明部分，定义变量a和b，指定 a和b为整型(int)变量。第3行是两个赋值语句，使a和b的值分别为123和456。第4行使sum的值为a+b，第5行中“%d”是输入输出的“格式字符串”，用来指定输入输出时的数据类型和格式(详见第4章)，“%d”表示“以十进制整数形式输出”。

16、在执行输出时，此位置上代以一个十进制整数值。printf函数中括弧内最右端sum是要输出的变量，现在它的值为579(即123+456之值)。因此输出一行信息为sum is 579例1.3main()/*主函数*/int a，b，c;/*声明部分，定义变量*/scanf(%d，%d，&a，&b);/*输入变量a和b的值*/c=max(a，b);/*调用max函数，将得到的值赋给c*/printf(max=%d，c);/*输出c的值*/int max(int x，int y)/*定义max函数，函数值为整型，形式参数x，y为整型*/int z;/*max函数中的声明部分，定义本函数中用到的变量z为

17、整型*/if(xy)z=x;else z=y;return(z);/*将z的值返回，通过max带回调用处*/本程序包括两个函数:主函数main和被调用的函数max。max函数的作用是将x和y中较大者的值赋给变量z。return语句将z的值返回给主调函数main。返回值是通过函数名max带回到main函数的调用处。main函数中的scanf是“输入函数”的名字(scanf和printf都是C系统提供的标准输入输出函数)。程序中scanf函数的作用是输入a和b的值。&a和&b中的“&”的含义是“取地址”，此scanf函数的作用是将两个数值分别输入到变量a和b的地址所标志的单元中，也就是输入给变量a

18、和b。这种形式是与其他语言不同的。它相当于BASIC语言中的INPUT a，b或PASCAL语言中的Read(a，b)。&a和&b前面的“%d，%d”的含义与前相同，只是现在用于“输入”。它指定输入的两个数据按十进制整数形式输入。关于scanf函数详见第4章。main函数中第4行为调用max函数，在调用时将实际参数a和b的值分别传送给max函数中的形式参数x和y。经过执行max函数得到一个返回值(即max函数中变量z的值)，把这个值赋给变量c。然后输出c的值。printf函数中双引号内的“max=%d”，在输出时，其中“%d”将由c的值取代之，“max=”原样输出。程序运行情况如下:8，5 (

19、输入8和5给a和b)max=8 (输出c的值)本例用到了函数调用、实际参数和形式参数等概念，我们只做了很简单的解释。读者如对此不大理解，可以先不予以深究，在学到以后有关章节时，问题自然迎刃而解。在此介绍此例子，无非是使读者对C程序的组成和形式有一个初步的了解。通过以上几个例子，可以看到:(1)C程序是由函数构成的。一个C源程序至少包含一个main函数，也可以包含一个main函数和若干个其他函数。因此，函数是C程序的基本单位。被调用的函数可以是系统提供的库函数(例如printf和scanf函数)，也可以是用户根据需要自 己编制设计的函数(例如，例1.3中的max函数)。C的函数相当于其他语言中的

20、子程序，用函数来实现特定的功能。程序中的全部工作都是由各个函数分别完成的。编写C程序就是编写一个个函数。C的函数库十分丰富，ANSI C建议的标准库函数中包括100多个函数，Turbo C和MS C 4.0提供300多个库函数。C的这种特点使得容易实现程序的模块化。(2)一个函数由两部分组成:函数的首部，即函数的第一行。包括函数名、函数类型、函数属性、函数参数(形参)名、参数类型。例如，例1.3中的max函数的首部为int max (int x,int y)函数类型 函数名 函数参数类型 函数参数名 函数参数类型 函数参数名一个函数名后面必须跟一对圆括弧，函数参数可以没有，如main()。函数

21、体，即函数首部下面的大括弧内的部分。如果一个函数内有多个大括弧，则最外层的一对 为函数体的范围。函数体一般包括:声明部分：在这部分中定义所用到的变量，如例1.3中main函数中的“int a，b，c;”。在第8章中还将会看到，在声明部分中要对所调用的函数进行声明。执行部分：由若干个语句组成。当然，在某些情况下也可以没有声明部分(例如，例1.1)。甚至可以既无声明部分，也无执行部分。如:dump()它是一个空函数，什么也不干，但这是合法的。(3)一个C程序总是从main函数开始执行的，而不论main函数在整个程序中的位置如何(main函数可以放在程序最前头，也可以放在程序最后，或在一些函数之前，

22、在另一些函数之后)。(4)C程序书写格式自由，一行内可以写几个语句，一个语句可以分写在多行上。C程序没有行号，也不像FORTRAN或COBOL那样严格规定书写格式(语句必须从某一列开始书写)。(5)每个语句和数据定义的最后必须有一个分号。分号是C语句的必要组成部分。例如:c=a+b;分号不可少。即使是程序中最后一个语句也应包含分号(这是和PASCAL语言不同的)。(6)C语言本身没有输入输出语句。输入和输出的操作是由库函数scanf和printf等函数来完成的。C对输入输出实行“函数化”。由于输入输出操作牵涉到具体的计算机设备，把输入输出操作放在函数中处理，就可以使C语言本身的规模较小，编译程

23、序简单，很容易在各种机器上实现，程序具有可移植性。当然，不同的C语言系统需要对函数库中的函数作不同的处理。不同的C系统除了提供函数库中的标准函数外，还按照硬件的情况提供一些专门的函数。因此不同的系统所提供的函数个数和功能是有所不同的。(7)可以用/*/对C程序中的任何部分作注释。一个好的、有使用价值的源程序都应当加上必要的注释，以增加程序的可读性。1.4 C程序的上机步骤我们已经看到了一些用C语言编写的程序。为了使计算机能按照人们的意志进行工作，必须根据问题的要求，编写出相应的程序。所谓程序，就是一组计算机能识别和执行的指令。每一条指令使计算机执行特定的操作。程序可以用高级语言（例如QBASI

24、C，FORTRAN，PASCAL，C等）编写。用高级语言编写的程序称为“源程序”（source program）。从根本上说，计算机只能识别和执行由0和1组成的二进制的指令，而不能识别和执行用高级语言写的指令。为了使计算机能执行高级语言源程序，必须先用一种称为“编译程序”的软件，把源程序翻译成二进制形式的“目标程序”，然后将该目标程序与系统的函数库和其他目标程序连接起来，形成可执行的目标程序。图1.1在编好一个C源程序后，如何上机运行呢?在纸上写好一个程序后，要经过以下几个步骤：上机输入与编辑源程序对源程序进行编译与库函数连接运行目标程序这样几个步骤。以上过程如图1.1所示。其中实线表示操作流

25、程，虚线表示文件的输入输出。例如，编辑后得到一个源程序文件f.c，然后在进行编译时再将源程序文件f.c输入，经过编译得到目标程序文件f.obj，再将目标程序文件f.obj输入内存，与系统提供的库函数等连接，得到可执行的目标程序文件f.exe，最后把f.exe调入内存并使之运行。在了解了C语言的初步知识后，读者最好上机运行一个C程序，以建立对C程序的初步认识。下面分别就三种不同的环境下运行C程序作一简单介绍。1.用Turbo C 运行C程序的步骤Turbo C是在微机上广泛使用的编译程序。它具有方便、直观、易用的界面和丰富的库函数。它向用户提供一个集成环境，把程序的编辑、编译、连接和运行等操作全

26、部集中在一个界面上进行，使用十分方便。为了能使用Turbo C，必须先将Turbo C编译程序装入磁盘的某一目录下，例如放在C盘根目录下一级TC子目录下。图1.2(1)调用调用 Turbo C程序。如果用户的当前目录是程序。如果用户的当前目录是Turbo C编译程序所在的子目录（例如编译程序所在的子目录（例如TC子目子目录），只需从键盘键入录），只需从键盘键入“tc”命令即可命令即可:C:TCtc 屏幕上出现Turbo C集成环境，见图1.2所示。从图1.2可以看到在集成环境的上部，有一行“主菜单”，其中包括下面8个菜单项:File Edit Run Compile Project Optio

27、n Debug break/watch用户可以通过以上菜单项来选择使用Turbo C集成环境所提供的Turbo C的各项主要功能。以上8个菜单项分别代表：文件操作、编辑、运行、编译、项目文件、选项、调试、中断/观察等功能。用键盘上的“”和“”键可以选择菜单条中所需要的菜单项，被选中的项以“反相”图1.3形式显示（例如主菜单中的各项原来以白底黑字显示，被选中时改为以黑底白字显示）。此时若按回车键，就会出现一个下拉菜单。例如在选中“File”菜单并按回车键后，屏幕上“File”下面出现下拉菜单，见图1.3所示。它是一个子菜单，提供多项选择。可以用“”键选择所需要的项。例如选择“New”处，并按回车

28、键，表示要建立一个新的C源程序。图图1.3如果选择“Load”，并按回车键，表示要调入一个已有的源文件，此时屏幕上出现一个对话框(见图1.4)。要求你输入该文件的名字。用户可输入该文件名，例如:tc1.c，如果已存在此文件，则系统会将此文件调入内存并显示在屏幕上。此时自动转为编辑(Edit)状态。如果原来不存在此文件名，则系统会建立一个以指定的名字命名的新文件。图图1.4(2)编辑源文件。在编辑(Edit)状态下可以根据需要输入或修改源程序。(3)编译源程序。选择“Compile”菜单并在其下拉菜单中选择“Compile to OBJ”，则进行编译，得到一个后缀为.obj的目标程序（为方便起见

29、，在一般书刊中，以上菜单的选择以“Compile/Compile to OBJ”表示)。然后再选菜单“Compile/Link EXE file”，进行连接操作，可得到一个后缀为.exe的可执行文件。也可以将编译和连接合为一个步骤进行。选菜单“Compile/Make EXE file”或按“F9”键，即可一次完成编译和连接。在屏幕上会显示编译或连接时有无错误和有几个错误，见图1.5所示。此时按任何一个键，图1.5所显示的“编译信息框”会图1.5 消失，屏幕上会恢复显示源程序，光标停留在出错之处。失，屏幕上会恢复显示源程序，光标停留在出错之处。在屏幕的下半部分显示出有错误的行和错误的原因。根据

30、在屏幕的下半部分显示出有错误的行和错误的原因。根据此信息修改源程序。修改完毕认为无错后，再按此信息修改源程序。修改完毕认为无错后，再按“F9”，再次进行编译和连接，如此反复进行到不显示出错为止。再次进行编译和连接，如此反复进行到不显示出错为止。(4)执行程序。按“F10”键，在窗口上部的主菜单中某一项处出现“反相”显示（黑色亮块）。File Edit Run Compile Project Option Debug Break/watch用“”键将亮块移到“Run”，按回车键，在其下拉菜单中选择“Run”项，或直接按Ctrl+F9键，系统就会执行已编译好的目标文件。此时，TC集成环境窗口消失，

31、屏幕上显示出程序运行时输出的结果。如果程序需要输入数据(如例1.3)，则应在此时，从键盘输入所需数据，然后程序会接着执行，输出结果。如果发现运行结果不对，要重新修改源程序，可以再按“F10”键，并用“”使亮块移到“Edit”处，按回车键，即进入编辑状态，可以根据需要修改源程序，并重复上述(2)，(3)，(4)步，直到得到正确结果为止。(5)可以用“Alt”和“X”键(同时按此两键)，脱离Turbo C，回到DOS命令状态。此时，可以用DOS命令显示源程序和运行程序:C TYPE tc1.c (列出源程序清单)C tc1 (执行目标程序 tc1.exe)如果想再修改源程序，可以重新执行步骤（1）

32、，并输入源程序文件名即可。2.在UNIX操作系统下运行C程序的步骤(1)用编辑程序(如UNIX系统的文本行编辑程序ed，或屏幕编辑程序vi)将源程序输入计算机，经修改认为无误后，存入文件系统。设用户将源文件定名为f.c(C源程序的后缀一般定为“.c”)。(2)编译。调用C编译程序cc对源文件进行编译。可打入命令:cc f.c 如果在编译过程中发现源程序有语法错误，则系统会输出“出错信息”，告诉用户第几行有什么样的错误。用户应重新调用编辑程序，修改后再进行编译。如此直到编译通过为止。编译时先生成一个汇编语言程序(即将C源程序翻译成为一个汇编语言程序)，然后由编译程序再将汇编语言程序翻译成机器指令

33、程序，即目标程序。目标程序的文件名与相应的源程序同名，但后缀为“.o”（表示它是目标文件），上述源文件f.c经编译后得到目标程序f.o。(3)连接。将目标程序和库函数或其他目标程序连接成可执行的目标程序。在UNIX系统下，连接是由cc自动完成的。最后得到可执行文件，文件名由系统自动确定为a.out。如果不想用系统定的文件名a.out，也可以在编译时自己指定可执行文件名。例如想指定为f.out，可以在编译时打入以下命令:cc -o f.out f.c它的作用是将源程序f.c编译成可执行程序，文件名为f.out。(4)执行程序。只需输入可执行文件名即可。例如:a.out (系统指定的文件名)或f.

34、out (用户指定的文件名)3.在DOS下用Microsoft C 6.0编译程序运行C程序的步骤Microsoft C是微软公司为IBM系列微机开发的C编译系统。MS C 6.0版本提供了多个库函数。老版本的MS C采用基于DOS平台的命令行方式。MS C 6.0增加了基于鼠标和窗口的“程序员工作台”（programmers work bench，缩写为PWB），它也是一个集成环境。MS C也是人们常用的C编译系统之一。目前，大多数使用MS C的人习惯用命令行方式。因此我们在这里只简单地介绍命令行方式的用法。(1)编辑C源程序。可以用任何全屏幕编辑系统输入和编辑源程序。假设已输入和编辑好的源

35、文件名为a1.c。(2)编译和连接。MS C提供了一个功能很强的CL命令，可一次完成程序的编译和连接。CL是Compile和Link的第一个字母。用法如下：CL a1.c (对源程序a1.c进行编译和连接)如果在编译和连接时出现“出错信息”，则需要重新编辑(修改)源程序。编译和连接完成后，产生一个可执行文件a1.exe。(3)执行程序。只需输入可执行文件名:a1即可得到运行结果。以上步骤只需上机试一下，即可明白。习题1.1 请根据自己的认识，写出C语言的主要特点。1.2 C语言的主要用途是什么?它和其他高级语言有什么异同?1.3 写出一个C程序的构成。1.4 C语言以函数为程序的基本单位，有什

36、么好处?1.5 请参照本章例题，编写一个C程序，输出以下信息:*Very good!*1.6 编写一个C程序，输入a、b、c 3个值，输出其中最大者。1.7 上机运行本章3个例题，熟悉所用系统的上机方法与步骤。1.8 上机运行本章习题1.5和1.6。2.1算法的概念2.2简单算法举例2.3算法的特性2.4怎样表示一个算法2.5结构化程序设计方法习题第第2 2章章 程序的灵魂程序的灵魂算法算法一个程序应包括以下两方面内容:(1)对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(data structure)。(2)对操作的描述。即操作步骤，也就是算法(algorithm)。数据

37、是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤(即算法)。因此，著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式数据结构+算法=程序实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：程序=算法+数据结构+程序设计方法+语言工具和环境也就是说，以上4个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的知识。在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做

38、什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。我们的目的是使读者通过学习本书，能够知道怎样编写一个C程序，并且能够编写出不太复杂的C程序。书中将通过一些实例把以上4个方面的知识结合起来，介绍如何编写一个C程序。由于算法的重要性，在本章中先介绍有关算法的初步知识，以便为后面各章的学习建立一定的基础。2.1 算 法 的 概 念从事各种工作和活动，都必须事先想好进行的步骤，然后按部就班地进行，才能避免产生错乱。不要认为只有“计算”的问题才有算法。广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。对同一个问题，可以有不同的解题方法和步骤。

39、方法有优劣之分。有的方法只需进行很少的步骤，而有些方法则需要较多的步骤。一般说，希望采用简单的和运算步骤少的方法。因此，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。本书所关心的当然只限于计算机算法，即计算机能执行的算法。计算机算法可分为两大类别：数值算法和非数值算法。数值运算的目的是求数值解。非数值运算包括的面十分广泛，最常见的是用于事务管理领域。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模型，可以运用数值分析方法，因此对数值运算的算法研究比较深入，算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这

40、些算法汇编成册(写成程序形式)，或者将这些程序存放在磁盘或磁带上，供用户调用。而非数值运算的种类繁多，要求各异，难以规范化，因此只对一些典型的非数值运算算法(例如排序算法)作比较深入的研究。其他的非数值运算问题，往往需要使用者参考已有的类似算法重新设计解决特定问题的专门算法。本书不可能罗列所有算法，只是想通过一些典型算法的介绍，帮助读者了解如何设计一个算法，推动读者举一反三。希望读者通过本章介绍的例子了解怎样提出问题，怎样思考问题，怎样表示一个算法。2.2 简单算法举例例2.1 求12345。可以用最原始的方法进行。步骤1：先求12，得到结果2。步骤2：将步骤1得到的乘积2再乘以3，得到结果6

41、。步骤3：将6再乘以4，得24。步骤4：将24再乘以5，得120。这就是最后的结果。这样的算法虽然是正确的，但太繁琐。如果要求121000，则要写999个步骤，显然是不可取的。而且每次都直接使用上一步骤的数值结果(如2，6，24等)，也不方便。应当找到一种通用的表示方法。可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设p为被乘数，i为乘数。用循环算法来求结果。可以将算法改写如下：S1：使p=1S2：使i=2S3：使pi，乘积仍放在变量p中，可表示为pi=pS4：使i的值加1，即i+1=iS5：如果i不大于5，返回重新执行

42、步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。上面的S1，S2代表步骤1，步骤2S是step(步)的缩写。这是写算法的习惯用法。请读者仔细分析这个算法，能否得到预期的结果。显然这个算法比前面列出的算法简练。如果题目改为求1357911。算法只需作很少的改动即可：S1：1=pS2：3=iS3：pi=pS4：i+2=iS5：若i11，返回S3；否则，结束。可以看出，用这种方法表示的算法具有通用性、灵活性。S3到S5组成一个循环，在实现算法时，要反复多次执行S3、S4、S5等步骤，直到某一时刻，执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算

43、法结束，变量p的值就是所求结果。由于计算机是高速进行运算的自动机器，实现循环是轻而易举的，所有计算机高级语言中都有实现循环的语句。因此，上述算法不仅是正确的，而且是计算机能实现的较好的算法。请读者仔细分析循环结束的条件，即S5步骤。如果在求1211时，将S5步骤写成S5：若i11，返回S3。这样会有什么问题?会得到什么结果?例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下。S1：1=iS2：如果gi80，则打印ni和gi，否则不打印S3：i+1=iS4：如

44、果i50，返回S2，继续执行；否则，算法结束。本例中，变量i作为下标，用它来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。例2.3 判定20002500年中的每一年是否闰年，将结果输出。闰年的条件是：能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年；能被100整除，又能被400整除的年份是闰年。如1600年、2000年是闰年。不符合这两个条件的年份不是闰年。算法可表示如下：设y 为被检测的年份。可采取以下步骤：S1：2000=yS2：y不能被4整除，则输出y“不是闰年”。然后转到S6S3：若y能被4整除，不能被100

45、整除，则输出y“是闰年”。然后转到S6S4：若y能被100整除，又能被400整除，输出y“是闰年”；否则输出“不是闰年”。然后转到S6S5：输出y“不是闰年”S6：y+1=yS7：当y2500时，转S2继续执行，如y2500，算法停止。在这个算法中，采取了多次判断。先判断y能否被4整除，如不能，则y必然不是闰年。如y 能被4整除，并不能马上决定它是否闰年，还要看它能否被100整除。如不能被100整除，则肯定是闰年(例如1996年)。如能被100整除，还不能判断它是否闰年，还要被400整除，如果能被400整除，则它是闰年，否则不是闰年。在这个算法中，每做一步，都分别分离出一些范围(巳能判定为闰年

46、或非闰年)，逐步缩小范围，使被判断的范围愈来愈小，直至执行S5时，只可能是非闰年。见图2.1示意。图 2.1从图2.1可以看出：“其他”这一部分，包括能被4整除，又能被100整除，而不能被400整除的那些年份(如1900年)，是非闰年。在考虑算法时，应当仔细分析所需判断的条件，如何一步一步缩小被判断的范围。有的问题，判断的先后次序是无所谓的，而有的问题，判断条件的先后次序是不能任意颠倒的，读者可根据具体问题决定其逻辑。例2.4 求1-1/2+1/3-1/4+1/99-1/100。算法可以表示如下：S1：1=signS2：1=sumS3：2=denoS4：(-1)sign=signS5：sign

47、(1/deno)=termS6：sum+term=sumS7：deno+1=denoS8：若deno100返回S4；否则算法结束。在步骤S1中先预设sign（代表级数中各项的符号，它的值为1或-1）。在步骤S2中使sum等于1，相当于已将级数中的第一项放到了sum中。在步骤S3中使分母的值为2。在步骤S4中使sign的值变为-1。在步骤S5中求出级数中第2项的值-1/2。在步骤S6中将刚才求出的第二项的值-1/2累加到sum中。至此，sum的值是1-1/2。在步骤S7中使分母deno的值加1（变成3）。执行S8步骤，由于deno100，故返回S4步骤，sign的值改为1，在S5中求出term的

48、值为1/3，在S6中将1/3累加到sum中。然后S7再使分母变为4。按此规律反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是级数的值。例2.5 对一个大于或等于3的正整数，判断它是不是一个素数。所谓素数，是指除了1和该数本身之外，不能被其他任何整数整除的数。例如，13是素数，因为它不能被2，3，4，12整除。判断一个数n(n3)是否素数的方法是很简单的：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法可以表示如下：S1：输入n的值S2：2=i（i作为除数）S3：n被i除，得余数rS4：如

49、果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1=iS6：如果in-1，返回S3；否则打印 n“是素数”，然后结束。实际上n不必被2到(n-1)的整数除，只需被2到n的开方间整数除即可，甚至只需被2到n之间的整数除即可。例如，判断13是否素数，只需将13被2、3除即可，如都除不尽，n 必为素数。S6步骤可改为：S6：如果in，返回S2；否则算法结束。通过以上几个例子，可以初步了解怎样设计一个算法。2.3 算法的特性一个算法应该具有以下特点：1.有穷性一个算法应包含有限的操作步骤，而不能是无限的。事实上，“有穷性”往往指“在合理的范围之内”。究竟什么算“合理限

50、度”，并无严格标准，由人们的常识和需要而定。2.确定性算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。3.有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。4.有一个或多个输出算法的目的是为了求解，“解”就是输出。没有输出的算法是没有意义的。5.有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果。对于不熟悉计算机程序设计的人来说，他们可以只使用别人已设计好的现成算法，只需根据算法的要求给以必要的输入，就能得到输出的结果。对他们来说，算法如同一个“黑箱子”一样，他们可以不了解“黑箱子”中的结构，只是从外部特性上了解算法的作用，即可