第2章 算法与C语言程序 程序 （1）数据的描述：数据的类型和组织形式（数据结构） （2）操作的描述：操作步骤（算法) 沃思指出： 数据结构+算法=程序 确切的说，除上述要素外，还要采取结构化程序设计的方法和用何种语言来设施。 程序=数据结构+算法 +程序设计方法+语言工具及环境

数据结构： 反映各种类型数据的构造形式，是计算机加工处理的对象 算法： 为解决某一特定问题而采取的确定的有限的步骤，它是程序设计的灵魂，解决做什么和怎么做 程序设计方法： 根据数据类型和算法用计算机语言加以实现，程序中的操作语句实际上是算法的具体体现，不了解算法就谈不上程序设计 语言工具和环境： 用计算机语言编制的程序需相应的编译系统和硬件环境加以实施

计算机求解问题的步骤 问题定义 ---- 明确问题 需求分析 ---- 精确描述 系统设计 ---- 模型或算法 系统实现 ---- 程序编制 系统运行 ---- 运行、求解

2.2 算法的概念 做事情都有——方法、步骤（顺序）——决定事情成败 1、算法：计算机求解末个问题而采用的具体方法、步骤 2.2 算法的概念 做事情都有——方法、步骤（顺序）——决定事情成败 1、算法：计算机求解末个问题而采用的具体方法、步骤 2、两大类计算机算法： 数值运算算法：求数值解、成熟 非数值运算算法：事务管理、广泛 3、算法的特性（p18）：有穷性、确定性、有效性等 4、算法的描述：有多种 归纳为两大类：文字 图形（符号）

2.3 算法的描述 算法常用的方法： 自然语言、传统流程图、结构化流程图、伪代码等 2.3.1用自然语言表示算法 自然语言： 2.3 算法的描述 算法常用的方法： 自然语言、传统流程图、结构化流程图、伪代码等 2.3.1用自然语言表示算法 自然语言： 人们日常使用的语言，可以是英、中、中英文结合 特点： 通俗易懂 缺点： 文字冗长，易出现岐义性，表示算法的含义不太严格，根据上下文才能判断其含义。

起止框： 输入输出框： 判别框： 处理框： 流程线： 注释框： 连接点： 2.3.2用流程图表示算法 ANSI规定的流程图符号，已为世界各国采用，用图框表示操作，用图形表示算法。 特点：直观、形象、灵活、易于理解，可表示任何算法。 起止框： 输入输出框： 判别框： 处理框： 流程线： 注释框： 连接点：

1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式 2.3.3 用N-S流程图表示算法 1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式 特点：去掉带箭头的流程线，全部算法在一个矩形框内，在该框内还可包含从属于它的框，这种流程图称为N-S结构化流程图，受到人们欢迎。 成立 A B 不成立 P 当P1成立 A A 直到P1成立 A B

2.3.4 用伪代码表示算法 它是介于自然语言和计算机语言之间的文字和符号来描述算法。 特点：自上而下书写，每行表示一个基本操作，可用中、英、中英书写。 原则：意思要表达清楚，格式要清晰易懂。

例：求 5! 用流程图算法 用N-S图 表示算法 用伪代码表示 BEGIN（算法开始） 1→t 2→i While i<=5 t ×i →t i +1 →i 直到 i >5 打印t 用N-S图 表示算法 用伪代码表示 BEGIN（算法开始） 1→t 2→i While i<=5 {t×i →t i+1 →i } print t END（算法结束） 开始 1→ t 2→ i t×i→ t i+1→ i i >5 打印 t 结束 N Y

例： 将50名学生中成绩在80分以上者的学号、成绩打印出来 1 →i 输入ni和gi i+1 →i i >50 gi ≥80 打印ni和gi 结束 开始 N Y 用流程图算法

例： 将50名学生中成绩在80分以上者的学号、成绩打印出来 用N-S流程图表示 1→i 输入ni , gi i+1→i 直到i>50 gi >=80 是 否 输出ni , gi 直到 i >50 用伪代码表示 BEGIN（算法开始） 1→i While i<=50 {input ni and gi i+1 →i } { if gi >=80 print ni and gi i+1→i } END（算法结束）

例 用流程图算法判断从2000-2500年每一年是否是闰年 开始 2000 → y y不能被 4整除 100整除 400整除 打印y“是闰年” 打印y“不是闰年” y+1 →y y>2500 结束 Y N

例 判定闰年的算法用N-S图表示 2000 → y 是 否 y / 4 的余数为 0 打印Y “是闰年” “非闰年” y+1 → y

例 用流程图算法求： 开 始 1 → sum 2 → deno 1 → sign (-1)×sign→sign 开 始 1 → sum 2 → deno 1 → sign (-1)×sign→sign sign×(1/deno)→term sum+term→sum deno+1→deno deno>100 结 束 N Y

例 求 算法用N-S流程图表示 1→sum 2→deno 1→sign (-1)×sign→sign Sum+term→sum deno+1→deno 直到 deno > 100 打印 sum

例 求 用伪代码表示算法 BEGIN （算法开始） 1→sum 2→deno 1→sign While deno <=100 { (-1)×sign →sign sign ×1/ deno →term sum+term →sum deno+1 →deno } print sum END（算法结束） 伪代码优点：书写格式自由、容易修改、容易写出结构化算法。 缺点：不太直观，容易出现逻辑上的错误

例 用流程图算法判断素数 开 始 输入n 2 → i n/ i的余数→ r r=0? i + 1 → i 打印n”不是素数” i > 例 用流程图算法判断素数 开 始 输入n 2 → i n/ i的余数→ r r=0? i + 1 → i i > 打印n”是素数” 结 束 N Y 打印n”不是素数”

三种基本结构和改进的流程图 1966年Bohra和Jacopini提出的三种基本结构，表示良好结构算法 （1）顺序结构 （2）选择（选取、分支）结构

（3）循环（重复）结构 ①当（while）型循环结构 功能：给定条件P1成立时，执行A， 执行完后再判断条件是否成立，如 例：用当型循环实现5个数的打印 输出用传统流程图算法实现 b P1 A 成立 a x+1 → x 0→x X < 5 ? 打印x值 N Y

否成立，若成立，再执行A，如此反复，直到 P2成立为止，此时不在执行A，从b点结束。 ②直到型（Until）循环 功能：先执行A，然后判断给定的条件P2是 否成立，若成立，再执行A，如此反复，直到 P2成立为止，此时不在执行A，从b点结束。 例：用直到型循环实现5个数 的打印输出 用传统流程图算法实现 A P2 不成立 成立 a b 0 → x x+1 → x 打印 x x ≥ 5 N Y

循环结构 根据条件P决定重复执行循环体中的操作

(2)只有一个出口，选择框上的两个出口不代表结构 (3)结构内的每一部分都有机会被执行到， 每一框内都应有一条从入口到出口的路径通过它。 三种结构的共点： (1)只有一个入口 (2)只有一个出口，选择框上的两个出口不代表结构 (3)结构内的每一部分都有机会被执行到， 每一框内都应有一条从入口到出口的路径通过它。 右图的结构中没有一条入口到出口通过A框。 (4)结构内不能存在死循环 结构化程序设计的优点 用三种基本结构组成的程序是结构化程序 优点：易编、易读、易懂、易维护 强调程序设计风格和程序结构的规范化 核心思想：自顶向上，逐步细化，模块化设计，结构化编码 P1 A A B

实践证明： 由三种结构组成的算法结构可以解决任何复杂问题。 结论： 基本结构所构成的算法，属结构化算法，它不存在无规律的转向，只在基本结构内才允许存在分支和向前或向后跳转。 以上所述的四个基本特点，人们还可自己定义基本结构，并由这些基本结构组成结构化程序，如多分支选择结构等，但它们都是由三种基本结构派生出来的。

用计算机语言表示算法 要完成一项工作： （1）设计算法 （2）实现算法 设计算法的目的：是实现算法 实现算法的一般方式： （1）人工心算 （2）笔算、算盘 （3）计算器

计算机无法识别流程图和伪代码 计算机实现算法的过程： 用计算机语言编写的程序才能被计算机识别、解释、执行（编辑、编译、连接，生成可执行程序） 用计算机语言表示算法必须严格遵循所用语言的语法规则 下面用C语言讨论两个简例：

例 求 5！ 前面讨论的算法，用C语言表示 main( ) {int i,t; t=1; i=2; while(i<=5) {t=t*i; i=i+1; } printf(“%d”,t); } 2→i 1 →t t ×i →t i +1 →i 直到 i >5 打印t 用N-S图 表示算法 用伪代码表示 BEGIN（算法开始） 1→t 2→i While i<=5 {t×i →t i+1 →i } print t END（算法结束）

细化

变量定义与初始化 赋值 内循环 选择语句

3.2 C语句概述 C程序：可由若干源程序文件组成，一个源文件可由若干函数和预处理命令及全局变量声明部分组成。 声明部分：指出数据结构，定义数据类型。 函数 执行部分：由语句组成，称数据操作，对提供的数 据进行加工。 语句： 编译指令，向计算机发布相应的操作命令。

C程序组成的示意图 函数 1 预处理命令 函数 n ┄ 全局变量声明 函数首部 函数体 局部变量声明 执行语句 C程序 源程序文件2 源程序文件 1 源程序文件 n

文件：存储在磁盘上的信息集合，可以是一段程序，一组数据。 C源程序文件：存储在磁盘上的函数的集合，包括程序执行中用到的数。 注： （1）所有源程序文件中，只有一个源程序文件中包含一个主函数main( ) ， 其余文件中包含的都是被调用函数。 （2）当各源文件独自存放磁盘上时，运行该程序的方法：在主函数前加 #include “文件名.c ”

C语言提供的语句分五大类： (1)控制语句，完成控制功能 ①if( ) ~ else ~ 条件 ②for ( ) ~ 循环 ③while ( ) ~ 循环 ④do ~ while ( ) 循环 ⑤continue 结束本次循环 ⑥break 中止switch 或循环 ⑦switch 多分支选择 ⑧goto 转向 ⑨return 从函数返回

(2)函数调用语句 函数名（参数）； 如：printf (“This is a C program.\n”); max(a,b); (3)表达式语句 在表达式后加 “ ;” 构成 a=6 a=5 ; 如 i=i+2 表达式 而 i=i+2 ; 表达式语句 x+y x+y ; (4)空语句 ; 无任何操作，但合法，可用于循环中的转折

(5)复合语句 用{ }将若干语句括起来而构成的语句。 如： if (x>y) 与 if (x>y) 意义不同 z=x; { x++; z=x; y- -; x++; y- -; }