大学课程《C语言程序设计》PPT课件:第二章.pptx
- 文档编号:18866972
- 上传时间:2024-02-03
- 格式:PPTX
- 页数:11
- 大小:551.25KB
大学课程《C语言程序设计》PPT课件:第二章.pptx
《大学课程《C语言程序设计》PPT课件:第二章.pptx》由会员分享,可在线阅读,更多相关《大学课程《C语言程序设计》PPT课件:第二章.pptx(11页珍藏版)》请在冰点文库上搜索。
第二章算法2.1概念2.2表示算法2.3结构化的程序设计2.1概念著名的计算机科学家沃思(Niklaus.Wirth)曾经提出过一个关于程序的经典公式,如下:
数据结构+算法=程序在这个公式里面,我们知道数据结构就是数据的描述和组织形式,那什么是算法呢?
准确地说,算法是为了解决某一特定问题而采用的确定的有限的操作步骤。
生活中的每一件事情的完成都是需要一个步骤的,也就可以认为成一个算法。
我们可以举一个简单的例子来说明什么是算法:
如果你要从北京到上海,首先,你要确定自己要采用什么方式去,坐飞机还是坐火车,也就是说在这里你要做一个分析和判断,确定自己是坐飞机还是火车,假如你确定了是坐火车,那么就需要去买火车票,可以网上购票,也可以去火车站排队买票,此时你又需要做一个分析和判断,确定哪种购票方式更便捷,买完票之后,你就可以拿着车票在预订的时间里面乘车去上海。
上面这一系列的分析、判断和执行的步骤就是算法,通常认为,算法是方法和步骤的集合。
算法是很灵活的,多种多样的,同样一个问题可以用无数种算法来进行求解,然而并不是所有的算法都有意义,只有满足了以下几点特性,一个算法才可以认为是有价值的。
(1)确定性。
算法的每一步都必须有确定的含义,不允许存在歧义。
如执行“1+1=?
”这个算法,执行结果是2,不存在其他任何结果。
理论上,一个有歧义的算法是无法正确解决问题的。
(2)有效性。
算法的每一步都是计算机能够执行的,并且在执行后可以得到确定的结果。
如果一个算法超出了计算机的功能,那么这个算法是无法运行的。
如编程“计算机,倒水”这个算法,计算机做不到,那么类似于这种超出了计算机的功能的算法就属于无效算法。
2.1概念(3)有零个或者多个输入。
任何一个算法都有一个赋初值的过程,也就是给出算法运行的初始量。
可以在编程过程中直接给出算法运行的初始量,那么在程序运行中,就不用临时输入数据,这种赋初值的方式称之为零个输入。
当然,也可以在程序运行过程中从外部设备给算法送值,这种赋初值的方式称之为多个输入。
不管采用哪种方法,都是给算法赋初值,都是可行的。
(4)有一个或者多个输出。
每一个有意义的算法都是有结果的,没有结果的算法是无意义的。
因为编程是为了解决问题,如果程序运行完之后,没有输出结果,那么问题就没有得到解决,也就是说这个程序采用的算法是无效且无意义的。
所以,一个有效的算法至少有一个输出结果,当然,也可以有多个输出结果。
(5)有穷性。
任何一个有实际意义的算法必须是可以执行完的,即它的运算步骤是有限的,而不是无限的循环执行下去,没有终结。
事实上,一个真正有实际意义的算法,都应该是在人类可以接受的时间范围内完成,也就是有一个解决问题的期限,否则失去了实用价值,算法也就无意义了。
总而言之,算法必须是在有限的时间内完成,并且对于同样的输入,应该得到同样的输出。
在C语言中,算法在程序上的运用,是在计算机的功能范围之内,是计算机执行有限个确定性的指令的集合。
一个算法的正确与否,关系到一个程序能否可以执行及执行结果的正确与否,也就关系到我们所要求解的问题是否得到一个正确的结果。
2.2表示方法从上面得知,算法是求解问题方法和步骤的集合,那么它的描述方法也是多种多样的,主要的描述方法有以下几种:
自然语言、传统流程图、N-S图、伪代码等。
1.1.自然语言自然语言自然语言指的是人们日常生活中所运用的语言,符合人的思维习惯,通俗易懂,容易掌握,但是表述冗长复杂。
同一句话在不同的时间和不同的空间里,对不同的人来说,意义是完全不一样的,“一千个人看哈姆雷特,就有一千个哈姆雷特”,说的就是这个意思。
所以用自然语言来描述算法是不适用的,同时也不易被计算机所接受。
【例【例2-12-1】计算的值。
用自然语言来描述这个算法的求解过程如下:
(1)输入x的值。
(2)判断x的值,若x0,令y=x;否则,令y=-x。
(3)输出y的值。
2.2.流程图流程图流程图的诞生对算法的描述来说是一个很大的贡献。
流程图就是采用一些特定的图框加上流线,把一个算法从头到尾很精确直观的表现出来的图形表示方法。
在20世纪五六十年代,流程图几乎成为了程序设计和算法描述不可缺少的工具。
随着时间、地点的推移,流程图的形式也出现了多样化,但是大部分还是有统一的使用标准的。
我国国家标准GB1526-89中推荐了一套标准的流程图符号,如表2-1所示。
2.2表示方法如果我们要比较两个数A、B的大小,若A大于B就输出数A,反之则输出数B,用流程图表示如图2.1所示。
表表2-12-1标准的流程图符号标准的流程图符号符号说明符号说明起止框流程线特定处理框虚线判断框准备框输入输出框处理框连接点图图2.12.1比较两数大小的流程图比较两数大小的流程图输入A、BAB成立不成立AB?
2.2表示方法3.N-S3.N-S结构化流程图结构化流程图N-S结构化流程图是在普通的流程图的基础上进行进一步优化后诞生的。
它是由美国学者I.Nassi和B.Schneiderman于1973年提出的,所以它的命名也就是采用二位学者的名字的首字母。
N-S流程图最突出的特点在于它取消了传统流程图中的流程线,使算法被迫的按照从上到下的顺序进行,这种改进避免了由于流程线太多并且任意转向而带来的困扰,使得算法的描述更加简洁明了,从而保证了程序的质量。
N-S流程图采用了结构化的特点,使得一个算法整体看起来形象直观,同时节省了空间,而且更适合C这种结构化的程序语言。
如把上面标准流程图改为N-S流程图后,如图2.2所示。
4.4.伪码伪码伪码(Pseudocode)是介于自然语言和计算机语言之间的一种代码。
程序员之所以运用伪码,是因为它可以帮程序员制定算法的智能化语言,它很灵活,没有固定的格式和规范,只要程序员能够写出来,或者读者可以看懂即可。
虽然它不能在计算机上运行,但是与计算机语言相比较,还是更易于转换成程序的。
在这里就不再举例说明了。
图图2.22.2比较两数大小的比较两数大小的N-SN-S结构化流程图结构化流程图成立不成立AB输入A、BAB?
2.3结构化的程序设计结构化程序的概念,首先是从以往编程过程中无限制地使用转移语句而提出的。
而转移语句则指的是可以使程序的控制流程强制性的转向程序的任何一处,在上面所讲到的传统流程图中,已经了解到这种流程控制语句的一些特点,就是用“很随意”的流程线来描述转移功能。
如果在一个程序中多处出现这种转移情况,将会导致程序流程无序可寻,程序结构则变得杂乱无章,这样的程序设计是令人费解且难以接受的,而且由于流程线的随意转向,使得程序容易出错。
针对这些问题,1966年,Bohra和Jacopini提出了以下三种基本结构:
顺序结构、选择结构和循环结构,从而解决了上述问题,使得程序的可读性和可修改性大大提高。
任何复杂的算法,都可以由顺序结构、选择(分支)结构和循环结构这三种基本结构组成。
这样在构造算法时,仅以这三种结构作为基本单元,同时规定了遵循这种结构的程序只有一个输入口和一个输出口,并且基本结构之间可以并列和互相包含,但是不允许交叉和从一个结构直接转到另一个结构的内部去。
采用这种程序设计的方法,使得整个程序结构清晰、易于正确性验证和纠正程序中的错误,这就是结构化程序设计方法,我们把遵循这种方法的程序设计称之为结构化程序设计。
下面介绍这三种基本的结构。
1.1.顺序结构顺序结构顺序结构是最简单的一种基本结构,它是按照解决问题的顺序写出相应的语句,并且其执行顺序也是自上而下的依次执行,如图2.3所示。
图中就是采用的顺序结构,其中A和B是按照算法的描述依次写出的,并且执行的时候,先执行A,然后再执行B,不能调换顺序,更不能逆序执行。
图图2.32.3顺序结构顺序结构ABab2.3结构化的程序设计2.2.选择结构选择结构选择结构主要是应用于判断给定的条件,依据判断的结果来控制程序的流程。
选择结构存在的前提是有一个给定的判断条件,只有在判断之后,才选择性的去执行相应的结果,如图2.4所示。
图中最上面的菱形框里的C是条件判断语句,先判断C是否成立,如果成立,则执行A,否则执行B。
不存在A和B同时执行的情况,也就是说,所给定的C这个条件要么成立,要么不成立,不能含糊不清的。
当然,A和B二者之中可以有任何一个是空的,也就是不执行任何操作。
这钟情况就是选择结构里面的单分支结构,A、B同时存在的情况是选择结构的双分支结构,还有多分支结构,在后续的学习中会依次了解到。
图图2.42.4选择结构选择结构AB成立不成立Cbba2.3结构化的程序设计3.3.循环结构循环结构循环结构可以看成是一个条件判断语句和一个有向回转语句的组合,可分为两种结构:
当型循环结构和直到型循环结构。
如图2.5所示是当型循环结构,C1是条件判断语句,先判断C1是否成立,如果成立,则执行A语句,执行完A语句后,再判断C1是否成立,成立的话再执行A语句,反复执行这一过程,直到C1不成立,才结束此循环结构。
之所以称之为当型循环,也就是当C1成立时,这一循环不会结束,只有当C1不成立时,才能跳出此循环。
如图2.6所示是直到型循环结构。
它的功能是先执行A语句,执行完之后判断条件语句C2是否成立,如果C2不成立,则回转过来执行语句A,执行完再判断C2,如果C2不成立,则还执行语句A,如此反复的执行语句A,直到判断C2成立为止。
顾名思义,直到型循环结构也就是直到C2成立时,此循环才终止,否则一直循环下去。
图图2.52.5当型循环结构当型循环结构图图2.62.6直到型循环结构直到型循环结构A成立不成立C1baA不成立成立C2ab2.3结构化的程序设计1996年,计算机科学家Bohm和Jacopini证明了这样的事实:
任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。
所以,这三种结构就被称为程序设计的三种基本结构,也是结构化程序设计必须采用的结构。
同时,以上三种结构有几个共同点:
(1)只有一个入口。
图2.3、图2.4、图2.5、图2.6中的a点均为入口点,有且只有一个。
(2)只有一个出口。
四个图中的b点均为出口点,虽然选择结构有两个出口点,但是在程序执行中,非A即B,二者只能执行其一,那么我们就可以认定选择结构也是只有一个出口。
(3)结构中的每一部分都有机会被执行到。
即在三种基本结构中,不存在多余无用的部分,每一部分都有一条从入口到出口的流线经过,也就有可能被执行。
(4)程序不会出现死循环。
死循环就是不会终止的循环。
三种基本结构都有程序结束的条件,顺序结构不用说了,选择结构有给定的条件判断部分,循环结构有循环判断的语句,所以都不会出现死循环。
结构化程序中的任意基本结构都具有唯一入口和唯一出口,在程序的静态形式与动态执行流程之间具有良好的对应关系。
结构化程序设计(StructuredProgramming)是进行以模块功能和处理过程设计为主的详细设计的基本原则。
1965年,E.W.Dijikstra提出了结构化程序设计的概念,这是软件发展的一个重要的里程碑。
结构化程序设计的主要观点是采用自顶向下、逐步细化及模块化的程序设计方法,也就是使用三种基本控制结构作为任何程序的基本构造。
结构化程序设计是软件发展中的第三个里程碑,主要强调的是程序的易读性。
其设计方法如下:
2.3结构化的程序设计
(1)自顶向下。
在进行程序设计时,首先应先考虑总体规划,然后再考虑细节问题,也就是先考虑全局目标,后考虑局部目标。
而不是一开始就过多考虑到众多的细节,从而使得整个程序设计变得繁琐无序、无章可循。
只有从最上层总目标开始设计,才能逐步使问题具体化。
这就如同我们要写一篇文章,先确定文章主旨,要表述一个什么样的观点,或者传达一个什么样的理念,确定了文章的中心思想,然后根据中心思想开始写出文章的总提纲,总提纲里面的内容一般包含作者想要分几段来写作,每段文字的段落大意等等。
这就是一个自顶向下的文章设计思路。
同样,我们要书写程序,也要求按照这样的思路,这样整个程序才能准确的描述并且解决相应的问题。
(2)逐步细化。
对一些复杂问题而言,我们还应设计一些子目标作为过渡,进行逐步细化。
这就是上面所说的分段问题,确定每段分别表述什么样的段落大意,然后再来思考怎样来表述每段的内容,每一段就像是一个总提纲下面的一些小提纲,需要逐个逐步处理。
例如第一段怎么写?
是开篇点题、直抒胸臆,还是故弄玄虚、引人注意。
对每一小段的分析和处理,就如同把每一个C程序分成一个个的小程序,然后单个的对每个小程序进行编写和修改,这就是细化的过程。
(3)模块化设计。
一个复杂问题一般是由若干个简单的问题构成的。
只有解决了各个小问题,这个复杂的问题才能得以解决。
而模块化就是把程序要解决的总目标分解为子目标,再进一步分解为更具体的小任务,每一个小任务里面又包含若干个函数。
在这里,把每一个小目标称为一个模块。
这就如同我们写文章,如何写好每一段的问题,每一段都有其段落大意,而每一段内容又是由句子组成,句子就相当于C程序的基本组成单元函数,我们可以根据其段落大意来分别处理每一段,采用相应的写作方法来书写每一句,句子组成段落,也就是每一段先是独立的完成,最后将其组合起来,这样整篇文章也就完成了。
这就是模块化处理的基本理念。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C语言程序设计 大学 课程 语言程序设计 PPT 课件 第二