《六章结构化程序设计.ppt》由会员分享，可在线阅读，更多相关《六章结构化程序设计.ppt（53页珍藏版）》请在三一办公上搜索。
1、第六章 结构化程序设计,武汉大学计算机学院,主讲：谭成予,教 材:C程序设计导论,本讲重点,著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式数据结构算法程序程序算法数据结构程序设计方法语言工具和环境算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。,如何理解程序？,编程过程,问题解决一个复杂的过程.算法解决问题所使用的一系列合乎逻辑的、简洁的步骤.解决问题包含的步骤:分析问题，找出解决问题的模型。根据模型设计出适合计算机特点的处理方法即算法选择适合的计算机语言进行编程，以实现算法
2、。上机编辑、调试、运行所编制的程序得到结果对结果进行分析，整理出文字材料即文档。,编程过程,例：预定火车票的算法:旅客输入如姓名,年龄,路程起点,终点,日期等信息。然后他将订票单交到订票处。柜台工作人员查看是否有坐位。如果存在满足要求的有效座位,就给旅客一张确认票。否则,发给一张等待单。如果有其他人退票,可凭等待单换取车票。如果最终乘客没有订到车票,他将得到退款。,算法的特点,有穷性：一个算法应包含有限个操作步骤。确定性：每个步骤应该是确定的。有0个或多个输入有1个或多个输出有效性：每个步骤都能有效执行。,算法的描述,1.自然语言描述:用自然语言给出解决问题的详细步骤.如前面的例子。2.流程图
3、：用图框表示。3.伪代码：使用介于自然语言和计算机语言之间的文字、符号来描述算法。4.计算机语言：采用这种方法必须严格遵守所使用的语言的语法规则。,算法的描述自然语言,例6.1判断一个数m是否为素数分析：判断整数m（m2）是否为素数的方法是：如果m不能被i整除（i为2到m-1的所有整数），则m是素数。算法如下：S1：输入m的值。S2：i赋初值为2：S3：判断m能否被i整除。若能，转到S6。S4：若m不为被i整除，给i的值加1。若im,则转到S3。S5：若i=m,输出m“是素数”，转到S7。S6：输出m“不是素数”。S7：算法结束。,算法的描述流程图,以图解方式说明实现一个解决方案所需完成的一系
4、列操作.为了达到下列目的:一目了然,比文字描述易懂.程序可以很容易地查看和修改.提供有效的程序文档.解释程序和讨论解决方案变得容易.,传统流程图里常用的符号,开始或结束框“处理框”-运算步骤输入或输出框判断框连接符：一个程序中两个部分之间的连接程序的流程线注释,例6.1 判断一个数m是否为素数流程图,传统流程图里的符号连接符,在为复杂问题准备流程图时流程图可能无法放在一页中要将所有的图块直接连接起来比较困难流程图可以被分割成若干部分.连接符可以用于指定连接的位置.在连接符中指定了一个唯一的数.在图表断开的地方,一个箭头指示了那一点.,传统流程图里的符号连接符,流程图的一些提示,画流程图时应该记
5、住的一些要点:开始把注意力集中在问题的逻辑上,画出流程图的主路径.完成主路径后,加上分支和循环.一个流程图只能含有一个起始点和一个结束点使流程图保持独立,只要可能,就不要用与计算机有关的术语.没有必要在流程图中画出程序的每个步骤.使用描述性的术语来表现问题的逻辑结构.不要用模棱两可的词语.让其他编程人员或用户能够轻松看懂你的流程图,N-S流程图,N-S流程图,AB,PY N A B,顺序结构,分支结构,N-S流程图,当P成立A,A 直到P成立,当型循环,直到型循环,PAD流程图,本讲重点,伪代码描述,伪代码（pseudo code）是用介于自然语言与计算机语言之间的文字和符号来描述算法。无固定
6、的、严格的语法规则，如同一篇文章，自上而下地写下来。可以用自然语言，也可以用程序设计语言或使用自然语言与程序设计语言的混合体。伪代码书写方便，格式紧凑，也比较好懂，便于向计算机语言过渡。,伪代码描述,例6.2求5！即1*2*3*4*5开始置t的初值为1置i的初值为2当i5，执行循环使t=t*i使i=i+1打印t的值结束,也可以写成以下形式：BEGINE1t2Iwhile i5t*iti+1Iprint tEND,用计算机语言表示,/*L6-1.C:判断一个数是否是素数*/#include int main(void)int m,w,i;printf(“input m:n”);scanf(“%d
7、”,本讲重点,结构化程序设计方法,自顶向下逐步细化模块化设计结构化编码,例6-3:求素数,输入1n取出所有非素数打印所有素数,ABC,输入n1i当inixii=i+1,A:,B1B2B3,D,B:,求素数续,E,D:,求素数续,F,E:,求素数续,求素数续,C:,1j当in把未挖掉的xi打印出来i+1i,G,xi=0 Y N 打印xi,G:,求素数续,#include#include int main(void)int n;int*p;int i,j；/*nsqrt为n的平方根*/int nsqrt;printf(Input the max number.n);scanf(%d,for(i=2
8、;i=nsqrt;i+)for(j=i+1;j=n;j+)if(*(p+j)!=0,求素数程序源代码,结构化程序设计程序的层次开发,函数调用图表：规划程序中函数的调用关系，顶端是main()函数,例6.4 编写计算调和级数和的程序。计算结果用有理数表示，即分数形式。,结构化程序设计程序的层次开发,例6.4 编写计算调和级数和的程序。计算结果用有理数表示，即分数形式。,分子、分母约分运算：先求u和v的最大公约数后，才能约分。,结构化程序设计程序的层次开发,void addrat(int a,int b);计算a/b+u/v，结果的分子存在u中，结果的分母存在变量v中；,main()函数,addr
9、at()函数,lowterm()函数,void lowterm();计算u和v的最大公约数，对u/v进行约分。,long u,v;全局变量存放结果的分子和分母,结构化程序设计程序的层次开发,void addrat(int a,int b);计算a/b+u/v，结果的分子存在u中，结果的分母存在变量v中；,u=u*b+a*v;v=v*b;,结构化程序设计程序的层次开发,void lowterm();计算u和v的最大公约数，对u/v进行约分。,numcopy=u;dencopy=v;remainder=numcopy%dencopy;numcopy=dencopy;dencopy=remander
10、;重复35，直到dencopy等于0；numcopy就是最大公约数；完成约分计算。,结构化程序设计程序的层次开发,#include long u,v;void addrat(int,int);void lowterm();int main()int n,nterm;/*n：项数*/scanf(“%d”,结构化程序设计程序的层次开发,void addrat(int a,int b)u=u*b+v*a;v*=b;void lowterm()int numcopy,dencopy;numcopy=u;dencopy=v;while(dencopy!=0)remainder=numcopy%denco
11、py;numcopy=dencopy;dencopy=remander;if(numcopy!=0)u/=numcopy;v/=numcopy;,算法的时间复杂度,算法的复杂度：按算法编制的程序在计算机上执行所耗费时间和所占用空间的分析，是对算法进行评价和选择的依据。时间复杂度：撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量的大小，只依赖于问题的规模，或者说它是问题规模的函数。常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时问量度的依据。如时间复杂度在n级，n的平方级，n的立方级，n的指数级等。,算法的时间复杂度,算法的复杂度：按算法编制
12、的程序在计算机上执行所耗费时间和所占用空间的分析，是对算法进行评价和选择的依据。时间复杂度：撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量的大小，只依赖于问题的规模，或者说它是问题规模的函数。常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时问量度的依据。如时间复杂度在n级，n的平方级，n的立方级，n的指数级等。,算法的空间复杂度,空间复杂度：作为算法所需存储空间的量度，存储空间指算法所处理的数据所需的存储空间与算法操作所需的辅助空间之和。设n为问题规模的大小，f（n）为存储空问，空间复杂度是以f（n）为变量的函数。类似地，也有n级n的平方
13、级，n的立方级，n的指数级等区分,例4.6 求一元人民币兑换成1分、2分、5分共有多少种方法,分析：若5分、2分、1分的个数分别为x个、y个。z个则x的取值为020，y的攻值为050，Z的取值为0100，于是有方程5t2jk100,程序如下：#include int main(void)int i,j,m=0;for(i=0;i21;i+)for(j=0;j51;j+)for(k=0;k101;k+)if(5*i+2*j+k=100)m+=1;printf(“m=%dn”,m);return 0;,循环次数：21*51*101,例4.6 求一元人民币兑换成1分、2分、5分共有多少种方法,改进后
14、的程序如下：#include int main(void)int i,j,m=0;for(i=0;i21;i+)for(j=0;j(100-5*i)/2;j+)m+=1;printf(“m=%dn”,m);return 0;,循环次数：,本讲重点,软件测试,软件测试的目的：找出软件开发过程中的错误。测试的目的不是为了证明程序的正确性，而是“假定程序中存在错误”，要通过测试的方法发现尽可能多的错误。软件测试的原则：测试用例应由输人数据和预期的输出数据两部分组成。测试用例不仅选用合理的输入数据。还要选择不合理的输人数据。除了检查程序是否做完了它应做的事之外，还要检查它是否做了不应做的事,软件测试-
15、白盒法,白盒法要求测试者必须对程序内部结构和处理过程非常清楚。,语句覆盖法例 4.7 有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,选择a=4、b=2、c=3,软件测试-白盒法,2、判定覆盖判定覆盖又称分支覆盖，是指选择足够多的测试用例，使得每个判定的可能的结果（“真”或“假”）都能执行一次，也就是说，程序中的每一个分支都至少执行一次。,例 4.7 有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,a=2、b=2、c=1（使表达式a0&b=2为“真”，表达式a=4|c
16、1为“假”）a=3、b=1、c=4（使表达式a0&b=2为“假”，表达式a=4|c1为“真”）,软件测试-白盒法,3、条件覆盖条件覆盖指选择足够多的测试用例，使得判定中的每个条件的各种可能结果都包含在内。,例 4.7 有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,有四个条件：a0b=2a=4c1因此可以选择：a=4、b=2、c=4a=0、b=1、c=1,软件测试-白盒法,4、判定/条件覆盖 同时满足判定覆盖和条件覆盖就是判定/条件覆盖。,例 4.7 有以下的程序#include int main(void)float a,b,c
17、;scanf(“%f%f%f”,a=4、b=2、c=4a=0、b=1、c=1,软件测试-白盒法,5、条件组合覆盖 条件组合覆盖指选取足够多的测试用例，使得每个判定中的每个条件各种可能组合都至少出现一次。,例 4.7 有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,a0&b=2、a0&b!=2、a1、a=4|c1、a!=4|c=1。,a=4、b=2、c=4（针对，组合）a=4、b=1、c=1（针对，组合）a=0、b=2、c=2（针对，组合）a=0、b=1、c=1（针对，组合）,软件测试黑盒法,黑盒测试是将程序看成是一个黑盒子，只在程
18、序接口上进行测试，主要看软件是否完成功能要求为。因此黑盒测试也称为功能测试。,、等价分类法 例4.8 测试编写的一个计算sqrt(x-4)/（6-x）)的程序。分析：将该程序的输入数据分为三个有效等价类：x4、x=4 三个无效等价类：x6、x=6、x4。为了选择尽可能少的测试用例，首先应该选取尽可能多包含有效等价类的测试用例可以选取x=3，4，5，6，7这几个测试用例。,软件测试黑盒法,2、边界值分析法经验表明，处理边界数据很容易发生错误，所以检查边界值发现错误的可能性高。,3、错误推测法错误推测法指根据经验和直觉选取测试用例。,设计测试用例几点规则可供参考：（1）任何情况都要使用边界值分析法。（2）需要使用等价类法补充测试用例。（3）再用错误推测法做补充。（4）检查以上选取的测试用例的逻辑覆盖程度，如果不能满足某些逻辑覆盖标准，可以再补充测试用例。,THE END,
