《第4部分控制结构程序设计教学内容》由会员分享，可在线阅读，更多相关《第4部分控制结构程序设计教学内容（156页珍藏版）》请在金锄头文库上搜索。
1、第4章 控制结构程序设计,2020/7/11,解析C程序设计第4章 控制结构程序设计,2,现实问题总是复杂的，面对各种需要解决的问题，人们必须首先对各类问题进行分析，确定解决问题的方法和步骤即算法，再借助具体编程语言编制好一组让计算机执行的指令（即程序），让计算机按人们指定的步骤有效地工作。,2020/7/11,解析C程序设计第4章 控制结构程序设计,3,根据算法，依据某种编程语言的语法规则编写计算机执行的命令序列，就是程序设计。 著名计算机科学家沃思（Nikiklaus Wirth）提出了一个公式：“数据结构算法程序”，即程序设计包括算法设计和数据存储。除此之外，还有结构化程序设计方法和计算
2、机语言。,2020/7/11,解析C程序设计第4章 控制结构程序设计,4,问题的提出,闰年问题：一年12个月，共365天，这是我们说得最多的。但事实上，每年不完全是365天。在中国农历中有闰月的说法，而公历也有闰年的说法。一般情况下，2月是28天，而闰年时是29天，何年的2月是29天呢，这就是闰年问题。编程判断一个年份是否为闰年。 求根问题：编程求解一元二次方程的根。,2020/7/11,解析C程序设计第4章 控制结构程序设计,6,4.1 算法的基础知识,算法是灵魂，是问题求解过程中的精确描述；数据结构是加工对象；语言是工具；编程需要采用合适的方法。 算法：是对特定问题求解步骤的一种描述。程序
3、：是用具体的计算机语言来描述算法的代码，可以输入计算机并产生结果。,2020/7/11,解析C程序设计第4章 控制结构程序设计,7,常用算法,递推化算法(牛顿迭代法、二分法、梯形法、穷举法等)； 排序算法(选择法、冒泡法)； 查找算法(顺序查找、折半查找)； 有序数列的插入、删除操作； 存储区的动态分配与释放，单向线性链表的建立、查找、插入、删除操作； 初等数论问题求解的有关算法(最大公约数、最小公倍数、素数等)； 递归算法(求最大公约数、阶乘等)； 字符串的处理(字符和字符串的插入、删除、字符串的连接、比较等)。,2020/7/11,解析C程序设计第4章 控制结构程序设计,8,算法的五个特性
4、,有穷性：对任何合法的输入值，算法中每个步骤由计算机执行的次数及时间都是有限的。 确定性：算法中每个步骤含义明确，无二义性。在任何条件下，相同的输入，必有相同的输出。 可行性：算法中描述的操作都可通过有限次的基本运算来实现。 输入：一个算法应具有零个或多个输入。 (无输入情况：如求：1*2*3*4*5)。 输出：一个算法应具有一个或多个输入。,2020/7/11,解析C程序设计第4章 控制结构程序设计,9,算法的设计目标,正确性：设计的算法应当满足具有输入、输出和加工处理等明确的无歧义 性的描述的具体问题的需求。验证正确性通常有4个层次： 程序不含语法错误； 程序对于几组输入数据能够得出满足规
5、格说明要求的结果； 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据 能够得出满足规格说明要求的结果； 程序对于一切合法的输入数据能够得出满足规格说明要求的结 果。 一般情况至少通过第层的验证。 可读性：算法主要是为了阅读与交流，其次才是机器执行。可读性好有助 于人对算法的理解；难懂的程序易于隐藏较多错误，难以调试和 修改。 健状性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不 会产生莫名其妙的输出结果。 效率与低存储量的需求：主要指算法执行时的最长时间与所需的最大存储 空间。,2020/7/11,解析C程序设计第4章 控制结构程序设计,10,算法的描述方法,自然语言 流程图
6、 N-S图 PAD图 伪代码,2020/7/11,解析C程序设计第4章 控制结构程序设计,11,用自然语言表示算法,自然语言就是人们日常使用的语言，可以是汉语、英语或其他语言。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。除了简单问题外，一般不用自然语言描述算法。例如：,2020/7/11,解析C程序设计第4章 控制结构程序设计,12,【例4-1】输入三个数，然后输出其中最大的数。 （1) 输入A，B，C。 （2) 若A B，则MAX=A；否则MAX=B。 （3) 若C MAX，则MAX=C。 （4) 输出MAX，MAX即为最大数。,2020/7/11,解析C程序设计第4章 控制结构
7、程序设计,13,例：用自然语言写出求 1-1/2+1/3-1/4+1/99-1/100 的算法。,（1）sign=1 /* 数值的符号 */ （2）sum=1 /* 累加和 */ （3）deno=2 /* 分母值 */ （4）sign=(-1)*sign （5）term=sign*(1/deno) /* 某一项的值*/ （6）sum=sum+term （7）deno=deno+1 （8）若deno100返回第(4)步，否则转第(9)步 （9）输出sum,2020/7/11,解析C程序设计第4章 控制结构程序设计,14,算法的描述流程图,用流程图表示算法，形象直观，比较清楚地显示出各个框之间的逻
8、辑关系， 易于理解。但流程图占用篇幅较多，当算法较复杂时，画流程图既费时，又不 方便。但必须掌握。 美国国家标准化协会ANSI规定了一些常用的流程图符号，并已被世界各国 程序工作者采用：,三种基本结构：,为了解决程序设计混乱的问题，1966年提出了三种基本结构：顺序结构、选 择结构、循环结构，然后由这些基本结构按一定规律组成一个算法结构，整个 算法结构是由上而下将各个基本结构顺序排列起来的。使用这三种基本结构顺 序组成的算法结构，可以解决任何复杂的问题，并且是“结构化”的算法。,2020/7/11,解析C程序设计第4章 控制结构程序设计,15,流程图顺序结构,顺序结构是程序设计中最简单的 一种
9、基本结构。 如右图所示，形象地描述了一个 最简单的顺序结构：图中虚线框内是 一个顺序结构。其中A和B两个框是顺 序执行的，即在执行完A框所指定的 操作后，必然接着执行B框所指定的 操作。,2020/7/11,解析C程序设计第4章 控制结构程序设计,16,流程图选择结构,选择结构(或称选取结构，或称分支结构)：,如下图所示，虚线框内是一个选择结构。此结构必包括一个判断框，根据给 定的条件p是否成立，而选择执行A框或B框。 注意：无论条件p是否成立，只能执行A框或B框之一，不可能既执行A框又执 行B框。A或B两个框中可以有一个是空的，即该空框不执行任何操作。,2020/7/11,解析C程序设计第4
10、章 控制结构程序设计,17,流程图当型循环结构,循环结构(或称重复结构)：,循环结构即反复执行某一部分的操作，分为当型(while型)循环结构和直到 型(until型)循环结构两类。,当型(while型)循环结构： 如右图所示，虚线框内是一 个while型结构。它的功能是当给 定的条件p成立时，执行A框操作，执行完A后再判断条件p是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次p条件不成立为止，此时不执行A框，而是从b点脱离循环结构。,2020/7/11,解析C程序设计第4章 控制结构程序设计,18,流程图直到型循环结构,直到型(until型)循环结构,如右图所示，虚线框内是一
11、 个until型结构。它的功能是先执 行A框，然后判断给定的条件p是 否成立，如果条件p成立，再执 行A框，然后再对条件p作判断， 如果条件p仍然成立，又执行A 框，如此反复执行A框，直到某一 次p条件不成立为止，此时不执行A框，而是从b点脱离本循环结构。,2020/7/11,解析C程序设计第4章 控制结构程序设计,19,三种基本结构的共同特点,只有一个入口 只有一个出口 结构内的每一部分都有机会执行到 结构内不存在“死循环”(无终止的循环),2020/7/11,解析C程序设计第4章 控制结构程序设计,20,流程图其他结构,事实上，基本结构不一定只限于上面三种，只要具有上述基本结构的4个特点的
12、结构都可以作为基本结构。人们可以运用三种基本结构定义自己派生的基本结构，并由这些基本结构组成结构化程序。 如下两图所示。C语言就是采用的这种派生基本结构。,根据表达式的值p进行选择,a,b,A,B,N,p1,p2,pn,a,2020/7/11,解析C程序设计第4章 控制结构程序设计,21,2020/7/11,解析C程序设计第4章 控制结构程序设计,22,流程图举例,用流程图表示出求,的算法。,2020/7/11,解析C程序设计第4章 控制结构程序设计,23,算法的描述N-S图,既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流程线就属多余的了。1973年美国两学者I.N
13、assi和B.Shneiderman提出了一种新的流程图形式，并以他们的名字命名为NS结构化流程图。这种流程图完全去掉了带箭头的流程线，全部算法写在一个矩形框内，在该框内还可以包括其他的从属于它的框，即由一些基本的框组成一个大框。这种NS流程图十分适合结构化程序设计，因而很受欢迎。,三种基本结构对应的NS图符号：,顺序结构 选择结构 当(while)型循环结构 直到(until)型循环结构,2020/7/11,解析C程序设计第4章 控制结构程序设计,24,2020/7/11,解析C程序设计第4章 控制结构程序设计,25,例4-4 用NS图表示求素数的算法,素数是指除了1和该数本身之外，不能被其
14、他任何整数整除的数。 实际上，若要判断一个正整数m是否为素数，只要将2到 间的每一个整数去除m，若有一个能整除m，则m不是素数，若其间的所有整数都不能整除m，则m为素数。,2020/7/11,解析C程序设计第4章 控制结构程序设计,26,算法的描述PAD图,PAD（Problem Analysis Diagram），是近年来在软件开发中被广泛使用的一种算法的图形表示法，与前面介绍的流程图、N-S图相比，流程图、N-S图都是自上而下的顺序描述，而PAD图除了自上而下以外，还有自左向右的展开，所以，如果说流程图、N-S图是一维的算法描述的话，则PAD图就是二维的，它能展现算法的层次结构，更直观易懂
15、。 PAD图表示的三种基本结构如下所示：,2020/7/11,解析C程序设计第4章 控制结构程序设计,27,例：求三个数的最大值的PAD图,2020/7/11,解析C程序设计第4章 控制结构程序设计,28,算法的描述伪代码,用流程图、N-S图、PAD图等描述算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码工具。 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡。因此，实际中常用伪代码描
16、述算法。 例：求三个数的最大值的伪代码算法描述如下： 定义三个变量i、j、k，用来存放三个数，定义变量max存放最大值； 输入三个变量的值； max=ij?i:j； max=maxk?max:k； 输出max。,2020/7/11,解析C程序设计第4章 控制结构程序设计,29,例：用自然语言写出求 1-1/2+1/3-1/4+1/99-1/100 的算法。,（1）sign=1 /* 数值的符号 */ （2）sum=1 /* 累加和 */ （3）deno=2 /* 分母值 */ （4）sign=(-1)*sign （5）term=sign*(1/deno) /* 某一项的值*/ （6）sum=sum+term （7）deno=deno+1 （8）若deno100返回第(4)步，否则转第(9)步 （9）输出sum,2020/7/11,解析C程序设计第4章 控制结构程序设
