第2章 算法与C语言程序 程序 （1）数据的描述：数据的类型和组织形式（数据结构） （2）操作的描述：操作步骤（算法) 沃思指出：

Presentation on theme: "第2章 算法与C语言程序 程序 （1）数据的描述：数据的类型和组织形式（数据结构） （2）操作的描述：操作步骤（算法) 沃思指出："— Presentation transcript:

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

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

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

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

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

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

7 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

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

9

10 例：求 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

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

12 例： 将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（算法结束）

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

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

15 例 用流程图算法求： 开 始 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

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

17 例 求 用伪代码表示算法 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（算法结束） 伪代码优点：书写格式自由、容易修改、容易写出结构化算法。 缺点：不太直观，容易出现逻辑上的错误

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

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

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

21 否成立，若成立，再执行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

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

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

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

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

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

27 例 求 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（算法结束）

28 细化

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

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

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

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

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

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

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