《六章结构化程序设计.ppt》由会员分享，可在线阅读，更多相关《六章结构化程序设计.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、六章结构化程序设计 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望本讲重点本讲重点本讲重点本讲重点算法的表示方法算法的表示方法结构化程序设计方法结构化程序设计方法 软件测试的一般方法软件测试的一般方法算法的概念算法的概念著名计算机科学家沃思著名计算机科学家沃思(Nikiklaus Wirth)提出提出一个公式一个公式数据结构算法程序数据结构算法程序程序算法数据结构程序设计方法语言程序算法数据结构程序设计方法语言工具和环境工具和环境算法是灵魂，数据结构是加工对象，语
2、言是工算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。具，编程需要采用合适的方法。算法是解决算法是解决“做什么做什么”和和“怎么做怎么做”的问题。的问题。程序中的操作语句，实际上就是算法的体现。程序中的操作语句，实际上就是算法的体现。如何理解程序？如何理解程序？编程过程编程过程问题解决问题解决一个复杂的过程一个复杂的过程.算法算法解决问题所使用的一系列合乎逻辑的、简洁的步骤解决问题所使用的一系列合乎逻辑的、简洁的步骤.解决问题包含的步骤解决问题包含的步骤:分析问题，找出解决问题的模型。分析问题，找出解决问题的模型。根据模型设计出适合计算机特点的处理方法即算法根据模型设计出适
3、合计算机特点的处理方法即算法选择适合的计算机语言进行编程，以实现算法。选择适合的计算机语言进行编程，以实现算法。上机编辑、调试、运行所编制的程序得到结果上机编辑、调试、运行所编制的程序得到结果对结果进行分析，整理出文字材料即文档。对结果进行分析，整理出文字材料即文档。编程过程编程过程例：预定火车票的算法例：预定火车票的算法:旅客输入如姓名旅客输入如姓名,年龄年龄,路程起点路程起点,终点终点,日期等信息。日期等信息。然后他将订票单交到订票处。然后他将订票单交到订票处。柜台工作人员查看是否有坐位。柜台工作人员查看是否有坐位。如果存在满足要求的有效座位如果存在满足要求的有效座位,就给旅客一张确认就给
4、旅客一张确认票。票。否则否则,发给一张等待单。发给一张等待单。如果有其他人退票如果有其他人退票,可凭等待单换取车票。可凭等待单换取车票。如果最终乘客没有订到车票如果最终乘客没有订到车票,他将得到退款。他将得到退款。算法的特点算法的特点有穷性：一个算法应包含有限个操作步有穷性：一个算法应包含有限个操作步骤。骤。确定性：每个步骤应该是确定的。确定性：每个步骤应该是确定的。有有0个或多个输入个或多个输入有有1个或多个输出个或多个输出有效性：每个步骤都能有效执行。有效性：每个步骤都能有效执行。算法的描述算法的描述1.自然语言描述自然语言描述:用自然语言给出解决问题用自然语言给出解决问题的详细步骤的详细
5、步骤.如前面的例子。如前面的例子。2.流程图：用图框表示。流程图：用图框表示。3.伪代码：使用介于自然语言和计算机语伪代码：使用介于自然语言和计算机语言之间的文字、符号来描述算法。言之间的文字、符号来描述算法。4.计算机语言：采用这种方法必须严格遵计算机语言：采用这种方法必须严格遵守所使用的语言的语法规则。守所使用的语言的语法规则。算法的描述算法的描述自然语言自然语言例例6.1判断一个数判断一个数m是否为素数是否为素数分析：判断整数分析：判断整数m（m2）是否为素数的方法是：如果）是否为素数的方法是：如果m不能不能被被i整除（整除（i为为2到到m-1的所有整数），则的所有整数），则m是素数。是
6、素数。算法如下：算法如下：S1：输入：输入m的值。的值。S2：i赋初值为赋初值为2：S3：判断：判断m能否被能否被i整除。若能，转到整除。若能，转到S6。S4：若：若m不为被不为被i整除，给整除，给i的值加的值加1。若。若im-1输出输出m是素数是素数输出输出m不是素数不是素数传统流程图里的符号传统流程图里的符号连接符连接符在为复杂问题准备流程图时在为复杂问题准备流程图时流程图可能无法放在一页中流程图可能无法放在一页中要将所有的图块直接连接起来比较困难要将所有的图块直接连接起来比较困难流程图可以被分割成若干部分流程图可以被分割成若干部分.连接符可以用于指定连接的位置连接符可以用于指定连接的位置
7、.在连接符中指定了一个唯一的数在连接符中指定了一个唯一的数.在图表断开的地方在图表断开的地方,一个箭头指示了那一点一个箭头指示了那一点.传统流程图里的符号传统流程图里的符号连接符连接符ab?12读入读入 a,b,c开始开始 ac?cb?12显示显示a显示显示c显示显示 b结束结束NYNNYY流程图的一些提示流程图的一些提示画流程图时应该记住的一些要点画流程图时应该记住的一些要点:开始把注意力集中在问题的逻辑上开始把注意力集中在问题的逻辑上,画出流程图的主路径画出流程图的主路径.完成主路径后完成主路径后,加上分支和循环加上分支和循环.一个流程图只能含有一个起始点和一个结束点一个流程图只能含有一个
8、起始点和一个结束点使流程图保持独立使流程图保持独立,只要可能只要可能,就不要用与计算机有关的就不要用与计算机有关的术语术语.没有必要在流程图中画出程序的每个步骤没有必要在流程图中画出程序的每个步骤.使用描述性的术语来表现问题的逻辑结构使用描述性的术语来表现问题的逻辑结构.不要用模棱两可的词语不要用模棱两可的词语.让其他编程人员或用户能够轻松看懂你的流程图让其他编程人员或用户能够轻松看懂你的流程图N-S流程图流程图N-S流程图流程图ABPY N A B顺序结构顺序结构分支结构分支结构N-S流程图流程图当当P成立成立AA 直到直到P成立成立当型循环当型循环直到型循环直到型循环输入输入mw=0i=2
9、 m%i!=0 T Fi=i+1W=1直到直到im-1或或w=1 w=0 F T输出输出m是素数是素数输出输出m不是素数不是素数NS流程图流程图PAD流程图流程图S1S2S3S1S1S当当P(a)(b)(c)PAD图的基本符号图的基本符号本讲重点本讲重点本讲重点本讲重点算法的表示方法算法的表示方法结构化程序设计方法结构化程序设计方法 软件测试的一般方法软件测试的一般方法算法的概念算法的概念伪代码描述伪代码描述 伪代码（伪代码（pseudo code）是用介于自然语言与）是用介于自然语言与计算机语言之间的文字和符号来描述算法。计算机语言之间的文字和符号来描述算法。无固定的、严格的语法规则，如同一
10、篇文章，无固定的、严格的语法规则，如同一篇文章，自上而下地写下来。可以用自然语言，也可以自上而下地写下来。可以用自然语言，也可以用程序设计语言或使用自然语言与程序设计语用程序设计语言或使用自然语言与程序设计语言的混合体。言的混合体。伪代码书写方便，格式紧凑，也比较好懂，便伪代码书写方便，格式紧凑，也比较好懂，便于向计算机语言过渡。于向计算机语言过渡。伪代码描述伪代码描述 例例6.2求求5！即！即1*2*3*4*5开始开始置置t的初值为的初值为1置置i的初值为的初值为2当当i5，执行循环，执行循环使使t=t*i使使i=i+1打印打印t的值的值结束结束也可以写成以下形式：也可以写成以下形式：BEG
11、INE1t2Iwhile i5t*iti+1Iprint tEND用计算机语言表示用计算机语言表示/*L6-1.C:判断一个数是否是素数判断一个数是否是素数*/#include int main(void)int m,w,i;printf(“input m:n”);scanf(“%d”,&m);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;本讲重点本讲重点本讲重点本讲重点算法的表示方法算法的表示方法结构化程序设计方法结构化程序设计方法
12、 软件测试的一般方法软件测试的一般方法算法的概念算法的概念结构化程序设计方法结构化程序设计方法自顶向下自顶向下逐步细化逐步细化模块化设计模块化设计结构化编码结构化编码例例6-3:求素数求素数输入输入1n取出所有非素数取出所有非素数打印所有素数打印所有素数ABC输入输入n1i当当inixii=i+1A:将将x1去掉去掉(使使x1=0)2i 当当in如如xi未去掉未去掉,则将则将xi+1到到xn之间全部是之间全部是xi倍数的倍数的数去掉数去掉i+11B1B2B3DB:求素数续求素数续 Xi=0?Y N 将将Xi+1到到Xn范围范围 内是内是Xi的倍数的的倍数的 数去掉数去掉ED:求素数续求素数续j
13、+1j将能被将能被xi整除的数去掉整除的数去掉 当当jni+1jFE:求素数续求素数续求素数续求素数续F:使使Xj=0 Xj 能被能被Xi整除整除 Y N Xj=0 Y NC:1j当当in把未挖掉的把未挖掉的xi打印出来打印出来i+1iGxi=0 Y N 打印打印xiG:求素数续求素数续#include#include int main(void)int n;int*p;int i,j；/*nsqrt为为n的平方根的平方根*/int nsqrt;printf(Input the max number.n);scanf(%d,&n);p=(int*)malloc(sizeof(int)*(n+1
14、);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 编写计算调和级数和的程序。计编写计算
15、调和级数和的程序。计算结果用有理数表示，即分数形式。算结果用有理数表示，即分数形式。结构化程序设计结构化程序设计程序的层次开发程序的层次开发例例6.4 编写计算调和级数和的程序。计算结编写计算调和级数和的程序。计算结果用有理数表示，即分数形式。果用有理数表示，即分数形式。分子、分母约分运算：分子、分母约分运算：先求先求u和和v的最大公约的最大公约数后，才能约分。数后，才能约分。结构化程序设计结构化程序设计程序的层次开发程序的层次开发void addrat(int a,int b);计算计算a/b+u/v，结果的分子存在，结果的分子存在u中，结果的分母存在中，结果的分母存在变量变量v中；中；ma
16、in()函数函数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的最大
17、公约数，对的最大公约数，对u/v进行约分。进行约分。1.numcopy=u;2.dencopy=v;3.remainder=numcopy%dencopy;4.numcopy=dencopy;5.dencopy=remander;6.重复重复35，直到，直到dencopy等于等于0；7.numcopy就是最大公约数；就是最大公约数；8.完成约分计算。完成约分计算。结构化程序设计结构化程序设计程序的层次开发程序的层次开发#include long u,v;void addrat(int,int);void lowterm();int main()int n,nterm;/*n：项数：项数*/sc
18、anf(“%d”,&n);if(n=0)printf(“Bad data!”);elseif(n=1)printf(“1/1n”);elseu=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)r
19、emainder=numcopy%dencopy;numcopy=dencopy;dencopy=remander;if(numcopy!=0)u/=numcopy;v/=numcopy;算法的时间复杂度算法的时间复杂度算法的复杂度：算法的复杂度：按算法编制的程序在计算机上执行所按算法编制的程序在计算机上执行所耗费时间和所占用空间的分析，是对算法进行评价和耗费时间和所占用空间的分析，是对算法进行评价和选择的依据。选择的依据。时时间间复复杂杂度度：撇撇开开这这些些与与计计算算机机硬硬件件、软软件件有有关关的的因因素素，可可以以认认为为一一个个特特定定算算法法“运运行行工工作作量量的的大大小小，只
20、只依依赖赖于于问问题题的的规规模模，或或者者说说它它是是问问题题规规模模的的函函数数。常从算法中选取一种与求解问题相关的基本操作，以常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时问量度的依据。该基本操作的重复执行次数作为算法时问量度的依据。如时间复杂度在如时间复杂度在n级，级，n的平方级，的平方级，n的立方级，的立方级，n的指的指数级等数级等。算法的时间复杂度算法的时间复杂度算法的复杂度：算法的复杂度：按算法编制的程序在计算机上执行所按算法编制的程序在计算机上执行所耗费时间和所占用空间的分析，是对算法进行评价和耗费时间和所占用空间的分析，是对算法进行评价和选择
21、的依据。选择的依据。时时间间复复杂杂度度：撇撇开开这这些些与与计计算算机机硬硬件件、软软件件有有关关的的因因素素，可可以以认认为为一一个个特特定定算算法法“运运行行工工作作量量的的大大小小，只只依依赖赖于于问问题题的的规规模模，或或者者说说它它是是问问题题规规模模的的函函数数。常从算法中选取一种与求解问题相关的基本操作，以常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时问量度的依据。该基本操作的重复执行次数作为算法时问量度的依据。如时间复杂度在如时间复杂度在n级，级，n的平方级，的平方级，n的立方级，的立方级，n的指的指数级等数级等。算法的空间复杂度算法的空间复
22、杂度空间复杂度空间复杂度：作为算法所需存储空间的量度，存：作为算法所需存储空间的量度，存储空间指算法所处理的数据所需的存储空间与储空间指算法所处理的数据所需的存储空间与算法操作所需的辅助空间之和。算法操作所需的辅助空间之和。设设n为问题规模的大小，为问题规模的大小，f（n）为存储空问，）为存储空问，空间复杂度是以空间复杂度是以f（n）为变量的函数。类似地，）为变量的函数。类似地，也有也有n级级n的平方级，的平方级，n的立方级，的立方级，n的指数级等的指数级等区分区分 例例4.6 求一元人民币兑换成求一元人民币兑换成1分、分、2分、分、5分共有多少种方法分共有多少种方法分析：分析：若5分、2分、
23、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 m
24、ain(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;循环次数：循环次数：本讲重点本讲重点本讲重点本讲重点算法的表示方法算法的表示方法结构化程序设计方法结构化程序设计方法 软件测试的一般方法软件测试的一般方法 算法的概念算法的概念软件测试软件测试软件测试的目的软件测试的目的：找出软件开发过程中的错误。测试的目：找出软件开发过程中的错误。测试的目的不是为了证明程序的正确性，而是的不是为了证明程序的正确性，而是“假定程序中存在错假定程序中存在错误误”，要通过测试的方法发
25、现尽可能多的错误。，要通过测试的方法发现尽可能多的错误。软件测试的原则：软件测试的原则：测试用例应由输人数据和预期的输出数据两部分组成。测试用例应由输人数据和预期的输出数据两部分组成。测试用例不仅选用合理的输入数据。还要选择不合理的测试用例不仅选用合理的输入数据。还要选择不合理的输人数据。输人数据。除了检查程序是否做完了它应做的事之外，还要检查它除了检查程序是否做完了它应做的事之外，还要检查它是否做了不应做的事是否做了不应做的事 软件测试软件测试-白盒法白盒法 白盒法要求测试者必须对程序内部结构和处理过程非常清楚。白盒法要求测试者必须对程序内部结构和处理过程非常清楚。1.语句覆盖法语句覆盖法例
26、例 4.7 有以下的程序有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,&a,&b,&c);if(a0&b=2)c=c/2;if(a=4|c1)x+;printf(“a=%f,b=%f,c=%fn”,a,b,c);2.return 0;选择选择a=4、b=2、c=3 软件测试软件测试-白盒法白盒法 2、判定覆盖、判定覆盖判定覆盖又称分支覆盖判定覆盖又称分支覆盖，是指选择足够多的测试用例，使得每个判，是指选择足够多的测试用例，使得每个判定的可能的结果（定的可能的结果（“真真”或或“假假”）都能执行一次，也就是说，程序）都能执行一次，
27、也就是说，程序中的每一个分支都至少执行一次。中的每一个分支都至少执行一次。例例 4.7 有以下的程序有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,&a,&b,&c);if(a0&b=2)c=c/2;if(a=4|c1)x+;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为为“真真”）软件测试软件
28、测试-白盒法白盒法 3、条件覆盖、条件覆盖条件覆盖指选择足够多的测试用例，使得判定中的每个条件的各种可条件覆盖指选择足够多的测试用例，使得判定中的每个条件的各种可能结果都包含在内。能结果都包含在内。例例 4.7 有以下的程序有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,&a,&b,&c);if(a0&b=2)c=c/2;if(a=4|c1)x+;printf(“a=%f,b=%f,c=%fn”,a,b,c);return 0;有四个条件：有四个条件：a0b=2a=4c1因此可以选择：因此可以选择：a=4、b=2、c=4a=0、b
29、=1、c=1软件测试软件测试-白盒法白盒法 4、判定、判定/条件覆盖条件覆盖 同时满足判定覆盖和条件覆盖就是判定同时满足判定覆盖和条件覆盖就是判定/条件覆盖条件覆盖。例例 4.7 有以下的程序有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,&a,&b,&c);if(a0&b=2)c=c/2;if(a=4|c1)x+;printf(“a=%f,b=%f,c=%fn”,a,b,c);return 0;a=4、b=2、c=4a=0、b=1、c=1软件测试软件测试-白盒法白盒法 5、条件组合覆盖、条件组合覆盖 条件组合覆盖指选取足够多的测
30、试用例，使得每个判定中的每条件组合覆盖指选取足够多的测试用例，使得每个判定中的每个条件各种可能组合都至少出现一次。个条件各种可能组合都至少出现一次。例例 4.7 有以下的程序有以下的程序#include int main(void)float a,b,c;scanf(“%f%f%f”,&a,&b,&c);if(a0&b=2)c=c/2;if(a=4|c1)x+;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（针对（针对，组
31、合）组合）a=0、b=2、c=2（针对（针对，组合）组合）a=0、b=1、c=1（针对（针对，组合）组合）软件测试软件测试黑盒法黑盒法 黑盒测试是将程序看成是一个黑盒子，只在程序接口上进黑盒测试是将程序看成是一个黑盒子，只在程序接口上进行测试，主要看软件是否完成功能要求为。因此黑盒测试行测试，主要看软件是否完成功能要求为。因此黑盒测试也称为功能测试。也称为功能测试。、等价分类法等价分类法 例例4.8 测试编写的一个计算测试编写的一个计算sqrt(x-4)/（6-x）)的程序。的程序。分析：分析：将该程序的输入数据分为三个有效等价类：将该程序的输入数据分为三个有效等价类：x4、x=4 三个无效等
32、价类：三个无效等价类：x6、x=6、x4。为了选择尽可能少的测试用例，首先应该选取尽可能多包含为了选择尽可能少的测试用例，首先应该选取尽可能多包含有效等价类的测试用例有效等价类的测试用例可以选取可以选取x=3，4，5，6，7这几个测试用例。这几个测试用例。软件测试软件测试黑盒法黑盒法 2、边界值分析法边界值分析法经验表明，处理边界数据很容易发生错误，所以检经验表明，处理边界数据很容易发生错误，所以检查边界值发现错误的可能性高。查边界值发现错误的可能性高。3、错误推测法、错误推测法错误推测法指根据经验和直觉选取测试用例。错误推测法指根据经验和直觉选取测试用例。设计测试用例几点规则可供参考：设计测试用例几点规则可供参考：（1）任何情况都要使用边界值分析法。）任何情况都要使用边界值分析法。（2）需要使用等价类法补充测试用例。）需要使用等价类法补充测试用例。（3）再用错误推测法做补充。）再用错误推测法做补充。（4）检查以上选取的测试用例的逻辑覆盖程度，如果不能满足）检查以上选取的测试用例的逻辑覆盖程度，如果不能满足某些逻辑覆盖标准，可以再补充测试用例。某些逻辑覆盖标准，可以再补充测试用例。THE ENDTHE END