六章结构化程序设计学习资料.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 结构化程序设计,武汉大学计算机学院,主讲：谭成予,nadinetan,教 材:C程序设计导论,本讲重点,算法的表示方法,结构化程序设计方法,软件测试的一般方法,算法的概念,著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式,数据结构算法程序,程序算法数据结构程序设计方法语言工具和环境,算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。,算法是解决“,做什么,”和“,怎么做,”的问题。程序中的操作语句，实际上就是算法的体现。,如何理解程序？,编程过程,问题解决,一个复杂的过程,.,算法,解决问题所使用的一系列合乎逻辑的、简洁的步骤,.,解决问题包含的步骤,:,分析问题，找出解决问题的模型。,根据模型设计出适合计算机特点的处理方法即算法,选择适合的计算机语言进行编程，以实现算法。,上机编辑、调试、运行所编制的程序得到结果,对结果进行分析，整理出文字材料即文档。,算法的特点,有穷性：一个算法应包含有限个操作步骤。,确定性：每个步骤应该是确定的。,有0个或多个输入,有1个或多个输出,有效性：每个步骤都能有效执行。,算法的描述,1.自然语言描述:用自然语言给出解决问题的详细步骤.如前面的例子。,2.流程图：用图框表示。,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-1,输出m是素数,输出m不是素数,传统流程图里的符号连接符,在为复杂问题准备流程图时,流程图可能无法放在一页中,要将所有的图块直接连接起来比较困难,流程图可以被分割成若干部分.,连接符可以用于指定连接的位置.,在连接符中指定了一个唯一的数.,在图表断开的地方,一个箭头指示了那一点.,传统流程图里的符号连接符,ab?,读入 a,b,c,开始,ac?,cb?,显示a,显示c,显示 b,结束,N,Y,N,N,Y,Y,流程图的一些提示,画流程图时应该记住的一些要点,:,开始把注意力集中在问题的逻辑上,画出流程图的主路径,.,完成主路径后,加上分支和循环,.,一个流程图只能含有一个起始点和一个结束点,使流程图保持独立,只要可能,就不要用与计算机有关的术语,.,没有必要在流程图中画出程序的每个步骤,.,使用描述性的术语来表现问题的逻辑结构,.,不要用模棱两可的词语,.,让其他编程人员或用户能够轻松看懂你的流程图,N-S流程图,N-S流程图,A,B,P,Y N,A B,顺序结构,分支结构,N-S流程图,当P成立,A,A,直到P成立,当型循环,直到型循环,输入m,w=0,i=2,m%i!=0 T,F,i=i+1,W=1,直到im-1或w=1,w=0,F T,输出m是素数,输出m不是素数,NS流程图,PAD流程图,S1,S2,S3,S1,S1,S,当P,(a)(b)(c),PAD图的基本符号,本讲重点,算法的表示方法,结构化程序设计方法,软件测试的一般方法,算法的概念,伪代码描述,伪代码（pseudo code）是用介于自然语言与计算机语言之间的文字和符号来描述算法。,无固定的、严格的语法规则，如同一篇文章，自上而下地写下来。可以用自然语言，也可以用程序设计语言或使用自然语言与程序设计语言的混合体。,伪代码书写方便，格式紧凑，也比较好懂，便于向计算机语言过渡。,伪代码描述,例6.2求5！即1*2*3*4*5,开始,置t的初值为1,置i的初值为2,当i5，执行循环,使t=t*i,使i=i+1,打印t的值,结束,也可以写成以下形式：,BEGINE,1t,2I,while i5,t*it,i+1I,print t,END,用计算机语言表示,/*L6-1.C:判断一个数是否是素数*/,#include,int main(void),int m,w,i;,printf(“input m:n”);,scanf(“%d”,w=0;i=2;,do,if(m%i=0)w=1;break;,else i+;,while(im),if(w=0),printf(“m isn”);,else,printf(“m is notn”);,return 0;,本讲重点,算法的表示方法,结构化程序设计方法,软件测试的一般方法,算法的概念,结构化程序设计方法,自顶向下,逐步细化,模块化设计,结构化编码,例6-3:求素数,输入1n,取出所有非素数,打印所有素数,A,B,C,输入n,1,i,当in,ix,i,i=i+1,A:,将x,1,去掉(使x,1,=0),2i,当in,如x,i,未去掉,则将x,i+1,到x,n,之间全部是x,i,倍数的数去掉,i+11,B,1,B,2,B,3,D,B:,求素数续,X,i,=0?,Y N,将X,i+1,到X,n,范围,内是X,i,的倍数的,数去掉,E,D:,求素数续,j+1j,将能被x,i,整除的数去掉,当jn,i+1j,F,E:,求素数续,求素数续,F:,使,X,j,=0,X,j,能被X,i,整除,Y N,X,j,=0,Y N,C:,1j,当in,把未挖掉的,x,i,打印出来,i+1i,G,x,i,=0,Y N,打印x,i,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,p=(int*)malloc(sizeof(int)*(n+1);,for(i=1;i=n;i+),*(p+i)=i;,nsqrt=sqrt(n);,*(p+1)=0;,for(i=2;i=nsqrt;i+),for(j=i+1;j=n;j+),if(*(p+j)!=0&j%i=0),*(p+j)=0;,for(i=1;i=n;i+),if(*(p+i)!=0),printf(%dt,*(p+i);,getch();,return 0;,求素数程序源代码,结构化程序设计程序的层次开发,函数调用图表：,规划程序中函数的调用关,系，顶端是main()函数,例6.4 编写计算调和级数和的程序。计算结果用有理数表示，即分数形式。,结构化程序设计程序的层次开发,例6.4 编写计算调和级数和的程序。计算结果用有理数表示，即分数形式。,分子、分母约分运算：,先求u和v的最大公约,数后，才能约分。,结构化程序设计程序的层次开发,void addrat(int a,int b);,计算a/b+u/v，结果的分子存在u中，结果的分母存在,变量v中；,main()函数,addrat()函数,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,;,重复,35,，直到,dencopy,等于,0,；,numcopy,就是最大公约数；,完成约分计算。,结构化程序设计程序的层次开发,#include,long u,v;,void addrat(int,int);,void lowterm();,int main(),int n,nterm;/*n：项数*/,scanf(“%d”,if(n=0)printf(“Bad data!”);,elseif(n=1)printf(“1/1n”);,else,u=1;v=1;,for(nterm=1;nterm=n;nterm+),addrat(1,nterm);,lowterm();,printf(“%d/%dn”,u,v);,return 0;,结构化程序设计程序的层次开发,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%dencopy;,numcopy=dencopy;,dencopy=remander;,if(numcopy!=0),u/=numcopy;,v/=numcopy;,算法的时间复杂度,算法的复杂度：,按算法编制的程序在计算机上执行所耗费时间和所占用空间的分析，是对算法进行评价和选择的依据。,时间复杂度：,撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量的大小，只依赖于问题的规模，或者说它是问题规模的函数。,常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时问量度的依据。如时间复杂度在n级，n的平方级，n的立方级，n的指数级等,。,算法的时间复杂度,算法的复杂度：,按算法编制的程序在计算机上执行所耗费时间和所占用空间的分析，是对算法进行评价和选择的依据。,时间复杂度：,撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量的大小，只依赖于问题的规模，或者说它是问题规模的函数。,常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时问量度的依据。如时间复杂度在n级，n的平方级，n的立方级，n的指数级等,。,算法的空间复杂度,空间复杂度,：作为算法所需存储空间的量度，存储空间指算法所处理的数据所需的存储空间与算法操作所需的辅助空间之和。,设n为问题规模的大小，f（n）为存储空问，空间复杂度是以f（n）为变量的函数。类似地，也有n级n的平方级，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分共有多少种方法,改进后的程序如下：,#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;,循环次数：,本讲重点,算法的表示方法,结构化程序设计方法,软件测试的一般方法,算法的概念,软件测试,软件测试的目的：找出软件开发过程中的错误。测试的目的不是为了证明程序的正确性，而是“假定程序中存在错误”，要通过测试的方法发现尽可能多的错误。,软件测试的原则：,测试用例应由输人数据和预期的输出数据两部分组成。,测试用例不仅选用合理的输入数据。还要选择不合理的输人数据。,除了检查程序是否做完了它应做的事之外，还要检查它是否做了不应做的事,软件测试-白盒法,白盒法要求测试者必须对程序内部结构和处理过程非常清楚。,语句覆盖法例,4.7,有以下的程序,#include,int,main(void,),float,a,b,c,;,scanf(“%f%f%f”,&a,&b,&c,);,if(a,0,if(a,=4|c1)x+;,printf(“a,=%,f,b,=%,f,c,=%,fn”,a,b,c,);,return 0;,选择a=4、b=2、c=3,软件测试-白盒法,2、判定覆盖判定覆盖又称分支覆盖，是指选择足够多的测试用例，使得每个判定的可能的结果（“真”或“假”）都能执行一次，也就是说，程序中的每一个分支都至少执行一次。,例 4.7 有以下的程序#include int main(void),float a,b,c;scanf(“%f%f%f”,if(a0,printf(“a=%f,b=%f,c=%fn”,a,b,c);,return 0;,a=2、b=2、c=1,（使表达式a0&b=2为“真”，表达式a=4|c1为“假”）,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”,if(a0,printf(“a=%f,b=%f,c=%fn”,a,b,c);,return 0;,有四个条件：a0b=2,a=4c1,因此可以选择：,a=4、b=2、c=4a=0、b=1、c=1,软件测试-白盒法,4、判定/条件覆盖 同时满足判定覆盖和条件覆盖就是判定/条件覆盖,。,例 4.7 有以下的程序#include int main(void),float a,b,c;scanf(“%f%f%f”,if(a0,printf(“a=%f,b=%f,c=%fn”,a,b,c);,return 0;,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”,if(a0,printf(“a=%f,b=%f,c=%fn”,a,b,c);,return 0;,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（针对，组合）,软件测试黑盒法,黑盒测试是将程序看成是一个黑盒子，只在程序接口上进行测试，主要看软件是否完成功能要求为。因此黑盒测试也称为功能测试。,、,等价分类法,例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,