第一章 C语言概述

C语言程序设计 教学要求 学习方法 考核方法 掌握程序设计语言的基本知识 常用算法 初步的程序设计能力 多做练习 重视上机实践 10%考勤， 30% 上机考试 ，60% 笔试

如何尽快学会用C语言进行程序设计 了解程序设计语言(C语言) 模仿、改写、编写 通过不断的编程实践，逐步领会和掌握程序设计的基本思想和方法。

教材和参考书 C语言与程序设计(第2版），万常选主编，科学出版社，2009 C++ Primer Plus(第6版)中文版，美]Stephen Prata 著， 人民邮电出版社，2012

§1-1 Ｃ语言出现的历史背景 C语言是国际上广泛流行的高级语言。 程序设计是数据被加工的过程 机器语言 汇编语言 高级语言 面向过程 面向对象 面向机器的语言 CPU指令系统，由0、1序列构成的指令码组成 如：10000000 加 10010000 减 客观世界可以分类，对象是类的实例 对象是数据和方法的封装 对象间通过发送和接受消息发生联系 用助记符号描述的指令系统 如 ADD A, B 程序设计关键是定义类，并由类派生对象 C语言是国际上广泛流行的高级语言。

§1-1Ｃ语言出现的历史背景 1983年,美国国家标准化协会(ANSI)根据C语言各种版本对C的发展和扩充,制定了新的标准ANSI C ，比标准C有了很大的发展。 1988年K & R按照 ANSI C修改了他们的《The C Programming Language》。 1987年,ANSI公布了新标准——87 ANSI C。 1990年，国际标准化组织接受了87 ANSI C为ISO C 的标准(ISO9899—1990)。 1994年，ISO又修订了C语言标准。 目前流行的C语言编译系统大多是以ANSI C为基础进行开发的。

§1-1Ｃ语言出现的历史背景 说明： 不同版本的C编译系统所实现的语言功能和语法规则又略有差别，因此读者应了解所用的C语言编译系统的特点(可以参阅有关手册)。本书的叙述基本上以ANSI C 为基础。

§1-2 Ｃ语言的特点 （1）语言简洁、紧凑,使用方便、灵活。 32个关键字、9种控制语句,程序形式自由 （2）运算符丰富。34种运算符 （3）数据类型丰富,具有现代语言的各种数据结构。 （4）具有结构化的控制语句 ，是完全模块化和结构化的语言。 （5）语法限制不太严格,程序设计自由度大。

§1-2 Ｃ语言的特点 （6）允许直接访问物理地址,能进行位操作,能实现汇编语言的大部分功能,可直接对硬件进行操作。兼有高级和低级语言的特点 。 （7）目标代码质量高,程序执行效率高。只比汇编程序生成的目标代码效率低10％-20%。 （8）程序可移植性好(与汇编语言比)。基本上不做修改就能用于各种型号的计算机和各种操作系统。

§1-2 Ｃ语言的特点 问题：既然有了面向对象的C++语言，为什么还要学习C语言？ 解释2：面向对象的基础是面向过程。C++是面向对象的语言，C是面向过程的，学起来比C语言困难得多，所以不太适合程序设计的初学者。

#include <stdio.h> void main( ) { 说明： 本程序的作用是输出一行信息: This is a C program. §1-3 简单的C语言程序介绍 #include <stdio.h> void main( ) { printf ("This is a C program.\n"); } /*文件包含*/ /*主函数 */ /*函数体开始*/ /*输出语句*/ /*函数体结束*/ 说明： main-主函数名， void-函数类型 每个C程序必须有一个主函数main { }是函数开始和结束的标志,不可省 每个C语句以分号结束 使用标准库函数时应在程序开头一行写： #include <stdio.h>

说明： 输出一行信息:sum is 579 例1.2 求两数之和 #include <stdio.h> void main( ) /*求两数之和*/ { int a,b,sum; /*声明，定义变量为整型*/ /*以下3行为C语句 */ a=123; b=456; sum=a+b; printf(″sum is %d＼n″,sum); } 说明： /*……*/表示注释。注释只是给人看的,对编译和运行不起作用。所以可以用汉字或英文字符表示，可以出现在一行中的最右侧，也可以单独成为一行。

int max(int x, int y) max(int x,int y); { int z; if (x>y) z=x; 程序运行情况如下： 8,5 ↙(输入8和5赋给a和b) max=8 (输出c的值) 例1.3 求3个数中较大者。 #include <stdio.h> void main( ) /* 主函数*/ { int max(int x,int y); / 对被调用函数max的声明 */ int a, b, c; /*定义变量a、b、c */ scanf(″％d,％d″,&a,&b); /*输入变量a和b的值*/ c=max(a,b); /*调用max函数,将得到的值赋给c */ printf(″max=％d\n″,c); /*输出c的值*/ } max(a,b); int max(int x, int y) { int z; if (x>y) z=x; else z=y; return (z); } max(int x,int y); 说明：本程序包括main和被调用函数max两个函数。max函数的作用是将x和y中较大者的值赋给变量z。return语句将z的值返回给主调函数main。

§1-3 简单的C语言程序介绍 C程序： (1) C程序是由函数构成的。 这使得程序容易实现模块化。 (2) 一个函数由两部分组成: 函数的首部：例1.3中的max函数首部 int max(int x,int y ) 函数体：花括号内的部分。若一个函数有多个花括号,则最外层的一对花括号为函数体的范围。 函数体包括两部分 ： 声明部分：int a,b,c; 可缺省 执行部分：由若干个语句组成。可缺省

这是一个空函数,什么也不做,但是合法的函数。 §1-3 简单的C语言程序介绍 注意： 函数的声明部分和执行部分都可缺省，例如： void dump ( ) { } 这是一个空函数,什么也不做,但是合法的函数。

§1-3 简单的C语言程序介绍 小结： (3) C程序总是从main函数开始执行的,与main函数的位置无关。 (5) 每个语句和数据声明的最后必须有一个分号。 (6) C语言本身没有输入输出语句。输入和输出的操作是由库函数scanf和printf等函数来完成的。C对输入输出实行“函数化”。

§1-4 运行Ｃ程序的步骤和方法 一、运行Ｃ程序的步骤 上机输入与编辑源程序 对源程序进行编译 与库函数连接 运行目标程序

§1-4 运行Ｃ程序的步骤和方法 二、上机运行Ｃ程序的方法 目前使用的大多数C编译系统都是集成环境(IDE)的。可以用不同的编译系统对C程序进行操作 常用的有Turbo C 2.0、Turbo C++ 3.0、Visual C++等 Turbo C++ 3.0：是一个集成环境，它具有方便、直观和易用的界面，虽然它也是DOS环境下的集成环境，但是可以把启动Turbo C++ 3.0 集成环境的DOS执行文件tc.exe生成快捷方式，也可以用鼠标操作。 Visual C++：也可以用Visual C++对C程序进行编译。

例：Turbo C++ 3.0的使用 将Turbo C++ 3.0编译程序装入磁盘某一目录下，例如： 放在C盘根目录下一级TC3.0子目录下。 进入Turbo C++ 3.0集成环境 ①在DOS环境下 C:\TC3.0>tc ↙

② 在Windows环境下 找到可执行文件tc.exe，执行该文件。 主菜单：11个菜单项: File Edit Search Run Compile Debug Project Options Window Help

(2) 编辑源文件 新建：单击“File”菜单下 的“New”, 修改：选择“File”→“Open”(即单击“File” 的下拉菜单中的“Open”项，修改已有的源程序。

在编辑(EDIT) 状态下光标表示当前进行编辑的位置，在此位 置可以进行插入、删除或修改，直到自已满意为止。

保存：在编辑(EDIT) 状态下光标表示当前进行编辑的位置，在此位置可以进行插入、删除或修改，直到自已满意为止。

(3) 对源程序进行编译 选择“Compile”(或“Alt+F9”)对源程序进行编译。 c1.cpp源程序，出现1个错误(error) ，0个警告(warming)。

(4) 将目标程序进行连接 选择菜单“Compile” →“Link” ，如果不出现错误，会得到一个后缀为.exe的可执行文件。 (5) 执行程序。 选菜单“Run” →“Run”( 或按“Ctrl+F9” 键)。 (6) 退出Turbo C++ 3.0环境 选择“File”→“Quit” 。

第二章 程序的灵魂--算法

本章要点 算法的概念 算法的表示 结构化程序设计方法

2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 化程序设计方法 主要内容 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 化程序设计方法

一个程序应包括两个方面的内容: 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm) 著名计算机科学家沃思提出一个公式:  数据结构 + 算法 = 程序 完整的程序设计应该是: 数据结构＋算法＋程序设计方法＋语言工具

§2.1 算法的概念 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 对同一个问题，可有不同的解题方法和步骤 例： 求 例： 求 方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+…+(49 +51)+50 = 100 + 49×100 +50 加51次

§2.1 算法的概念 为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。 计算机算法可分为两大类别： 数值运算算法：求数值解，例如求方程的根、求函数的定积分等。 非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。

太繁琐 §2.2 简单算法举例 例2.1: 求1×2×3×4×5 如果要求1×2×…×1000，则要写999个步骤 例2.1: 求1×2×3×4×5 步骤1：先求1×2，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120 如果要求1×2×…×1000，则要写999个步骤

可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果, 算法可改写： S1：使1=> p S2：使2 => i S3：使p×i，乘积仍放在变量p中，可表示为： p×i =>p S4：使i的值加1，即i+1 => i。 S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。

如果题目改为：求1×3×5×……×1000算法只需作很少的改动： 算法简练 S1：1 => p S2：3 => i S3：p×i => p S4：i+2 => i S5：若i≤1000，返回S3。否则，结束。

用这种方法表示的算法具有通用性、灵活性。S3到S5组成一个循环，在实现算法时 要反复多次执行S3，S4，S5等步骤，直到某一时刻，执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算法结束，变量p的值就是所求结果。

例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。设n表示学号， n1代表第一个学生学号， 代表第i个学生学号。用G代表学生成绩 ， gi代表第i个学生成绩，算法表示如下: S1：1 => i S2：如果gi≥80，则打印成绩，否则不打印。 S3：i+1 => i S4：如果i≤50，返回S2，继续执行。否则算法结束 变量i作为下标，用来控制序号(第几个学生，第几个成绩)。当i超过50时，表示 已对50个学生的成绩处理完毕，算法结束。

例2.3 判定2000～2500年中的每一年是否闰年，将结果输出。 分析：闰年的条件是：(1)能被4整除，但不能被100整除的年份都是闰年，如1996,2004年是闰年；(2)能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。不符合这两个条件的年份不是闰年。

设y为被检测的年份，算法可表示如下 ： S1：2000 => y S2：若y不能被4整除，则输出y “不是闰年”。然后转到S6。 S3：若y能被4整除，不能被100整除，则输出y “是闰年”。然后转到S6。 S4：若y能被100整除，又能被400整除，输出y“是闰年”，否则输出“不是闰年”。 然后转到S6。 S5: 输出y “不是闰年”。 S6：y+1 => y S7：当y≤2500时，转S2继续执行，如y＞2500，算法停止。

以上算法中每做一步都分别分离出一些范围(巳能判定为闰年或非闰年)，逐步缩小范围，直至执行S5时，只可能是非闰年。 “其它” 包括能被4整除，又能被100整除，而不能被400整除的那些年份(如1990) 是非闰年。

S1：sign=1 例2.4 求 算法如下 ： S2：sum=1 单词作变量名，以使算法更易于理解： S3：deno=2 S4：sign=(-1)×sign S5：term=sign×(1/deno) S6：sum=sum+term S7：deno=deno+1 S8：若deno≤100返回S4，否则算法结束。 单词作变量名，以使算法更易于理解： sum表示累加和，deno是英文分母（denominator）缩写，sign代表数值的符号，term代表某一项。 反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是多项式的值。

例2.5 对一个大于或等于3的正整数，判断它是不是一个素数。 概念：所谓素数，是指除了1和该数本身之外，不能被其它任何整数整除的数。例如，13是素数。因为它不能被2，3，4，…，12整除。 分析：判断一个数n(n≥3)是否素数的方法： 将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。

实际上，n不必被2到(n-1)的整数除，只需被2到n/2间整数除，甚至只需被2到 之间的整数除即可。 算法如下 ： S1：输入n的值 S2：i=2  （i作为除数） S3：n被i除，得余数r S4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束。否则执行S5 S5：i=i+1 S6：如果i≤n-1，返回S3。否则打印 n “是素数”。然后结束。 实际上，n不必被2到(n-1)的整数除，只需被2到n/2间整数除，甚至只需被2到 之间的整数除即可。

§2.3 算法的特性 一个算法应该具有以下特点： 有穷性：包含有限的操作步骤 确定性：算法中的每一个步骤都应当是确定的 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息 有一个或多个输出：算法的目的是为了求解，“解” 就是输出 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果 。

§2.4 算法的表示 可以用不同的方法表示算法，常用的有： 自然语言 传统流程图 结构化流程图 伪代码 PAD图

§2.4.1 用自然语言表示算法 自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，一般不用自然语言描述算法。

美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号： §2.4.2 用流程图表示算法 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号： 起止框 判断框 处理框 输入/输出框 注释框 流向线 连接点

例2.6 将求5!的算法用流程图表示 如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。

例2.7 将例2.2的算法用流程图表示。打印50名 学生中成绩在80分以上者的学号和成绩。

如果包括这个输入数据的部分，流程图为

用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。 例2.8 将例2.3判定闰年的算法用流程图表示

例2.9 将例2.4的算法用流程图表示

例2.10 将例2.5判断素数的算法用流程图表示

小结： 流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1)表示相应操作的框； (2)带箭头的流程线； (3)框内外必要的文字说明。

§2.4.3 三种基本结构和改进的流程图 1、传统流程图的弊端 传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图：

缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。 解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。 传统流程图的流程可以是： 这种如同乱麻一样的算法称为BS型算法，意为一碗面条(A Bowl of Spaghetti)，乱无头绪。

2、三种基本结构 Bohra和Jacopini提出了以下三种基本结构： 顺序结构、选择结构、循环结构 用这三种基本结构作为表示一个良好算法的基本单元。

三种基本结构的图示： 顺序结构 选择结构

循环结构的图示： 当型(While型)循环结构 直到型(Until型)循环

三种基本结构的共同特点： (1)只有一个入口； (2)只有一个出口；（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。） (3)结构内的每一部分都有机会被执行到； (4)结构内不存在“死循环”(无终止的循环)。

不正确的流程表示： 图中没有一条从入口到出口的路径通过A框。 流程内的死循环

小结： 由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。

扩展： 只要具有上述四个特点的都可以作为基本结构。可以自己定义基本结构，并由这些基本结构组成结构化程序。 此图符合基本结构的特点

这是一个多分支选择结构，根据表达式的值决定执行路线。虚线框内的结构是一个入口一个出口，并且有上述全部的四个特点。由此构成的算法结构也是结构化的算法。可以认为这是由三种基本结构所派生出来的。

§2.4.4 用N--S流程图表示算法 1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称N--S结构化流程图 。

N--S流程图用以下的流程图符号： (1)顺序结构 (2)选择结构 (3)循环结构

用三种N--S流程图中的基本框，可以组成复杂的N--S流程图。图中的A框或B框，可以是一个简单的操作，也可以是三个基本结构之一。

例2.11 将例2.1的求5!算法用N--S图表示

例2.12 将例2.2的算法用N--S图表示。（打印50名学生中成绩高于80分的学号和成绩） 没有输入数据

例2.12 将例2.2的算法用N--S图表示。（打印50名学生中成绩高于80分的学号和成绩） 有输入数据

例2.13 将例2.3判定闰年的算法用N--S图表示

例2.14 将例2.4的算法用N--S图表示

例2.15 将例2.5判别素数的算法用N--S流程图表示。 传统流程图分析： 出口1 此图不符合基本结构特点！由于不能分解为三种基本结构，就无法直接用N--S流程图的三种基本结构的符号来表示。因此，应当先作必要的变换。 出口2

例2.15 将例2.5判别素数的算法用N--S流程图表示。 传统流程图变换为： 一个出口

用N--S流程图表示：

N--S图表示算法的优点 比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N--S流程图中的上下顺序就是执行时的顺序。用N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。

小结： 一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。

概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。 §2.4.5 用位代码表示算法 概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。 特点：它如同一篇文章一样 ，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便 、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。 用处：适用于设计过程中需要反复修改时的流程描述。

例： “打印x的绝对值”的算法可以用伪代码表示为： IF x is positive THEN print x ELSE print -x 也可以用汉字伪代码表示： 若 x为正 打印 x 否则 打印 -x 也可以中英文混用，如： IF x 为正 print -x 例： “打印x的绝对值”的算法可以用伪代码表示为：

置t的初值为1 例2.16 求5!。用伪代码表示算法： 也可以写成以下形式： 开始 置i的初值为2 当i<=5，执行下面操作： 使t=t×i 使i=i+1 ｛循环体到此结束｝ 输出t的值 结束 例2.16 求5!。用伪代码表示算法： 也可以写成以下形式： BEGIN｛算法开始｝ 1t 2  i while i≤5 {t×i t  i+1  i} print t END｛算法结束｝

例2.17 输出50个学生中成绩高于80分者的学号和成绩。 用伪代码表示算法： BEGIN｛算法开始｝ 1  i while i≤50 {input and  i+1  i} 1  i {if ≥80 print and i+1  i} END｛算法结束｝

特点：用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。 §2.4.6 用计算机语言表示算法 概念：用计算机实现算法。计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行。因此在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序。 特点：用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。 用处：要完成一件工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。

例 2.20 将例2.16表示的算法（求5!）用C语言表示。 #include <stdio.h> void main( ) {int i,t; t=1; i=2; while(i<=5) {t=t*I; i=i+1; } printf(“%d\n”,t); 例 2.20 将例2.16表示的算法（求5!）用C语言表示。

应当强调说明：写出了C程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。

结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 § 2.5 结构化程序设计方法 一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。 结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。

§ 2.5 结构化程序设计方法 采取以下方法来保证得到结构化的程序： 自顶向下； 逐步细化； 模块化设计； 结构化编码。 两种不同的方法： 自顶向下，逐步细化； 自下而上，逐步积累。

用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。

自顶向下，逐步细化方法的优点： 考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。

模块设计的方法： 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。 在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。 子模块一般不超过50行 划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。