结构化算法的实现

《结构化算法的实现》由会员分享，可在线阅读，更多相关《结构化算法的实现（24页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,7,章 结构化算法的实现,7.1,基本控制结构的,C+,实现,7.2,子算法设计与,C+,实现,7.3,递归与迭代,学习目的：,理解算法控制结构与,C+,控制语句之间的关系；,能够根据结构化算法的,PAD,图编制,C+,程序；,深入理解递归与迭代的原理与过程；,熟练应用递归技术解决问题。,7.1,基本控制结构的,C+,实现,顺序结构的,C+,实现,分支结构的,C+,实现,循环结构的,C+,实现,7.1.4,复杂结构,C+,实现示例,理想的算法设计应是语言无关的，可使用任何语言实现它，但是这将带来

2、两个问题：,其一，常用算法描述工具的描述能力有限，有些问题采用具体程序语言所提供的语法对算法进行描述效率会更高、结构更简单；,其二，由于算法与语言的脱离，在使用具体语言实现算法时，程序与算法描述之间并不总是一一对应的，经常需要对算法进行适当调整，以利于实现。,在结构化程序设计与实现时巧妙地应用高级语言所提供的各种便利的语法，能起到事半功倍的效果。,顺序结构的,C+,实现,如果将程序中的每条分支语句和循环语句等复杂语句作为一个整体（一条复杂的语句），那么,C+,程序中物理上顺序排列的语句（除,goto,外）的执行顺序与其排列的前后顺序相同，它们之间构成了顺序结构，因此可以将,C+,的所有语法用于

3、顺序结构算法的实现。,#include iostream.h,void main(),double r,Peri_bottom,S_bottom,S_side,V,h;,coutr;,couth;,Peri_bottom=6.28*r;,S_side=Peri_bottom*h;,S_bottom=9.86*r;,V=S_bottom*h;,coutThe lateral area is S_sideendl;,coutThe volume is Vendl;,分支结构的,C+,实现,算法的分支结构在,C+,中可以采用,if,语句或,switch,语句来实现，其中,switch,语句主要用于实

4、现多分支结构，这两种语句的结构与算法的分支结构具有很好的对应关系。,例,7.1,例,2.4,中算法的,C+,实现。,#include iostream.h,#include math.h,void main(),double a,b,c,x1,x2,q;,couta;,coutb;,coutc;,if(a=0),cout,错误输入,endl;,else,q=b*b-4*a*c;,if(q0),cout,没有实数解,endl;,else,/,下面两行为减少运算次数,q=sqrt(q);,a*=2;,x1=(-b+q)/a;,x2=(-b-q)/a;,cout,第一个根为,x1endl;,cout

5、,第二个根为,x2endl;,例,7.2,例,2.6,中算法的,C+,实现,#include iostream.h,void main(),int Month;,coutMonth;,if(Month12),cout,错误月份序号,endl;,else,switch(Month-1),case 0:,coutJanuaryendl;,break;,case 1:,coutFebruaryendl;,break;,case 2:,coutMarchendl;,break;,case 3:,coutAprilendl;,break;,case 4:,coutMayendl;,break;,/,其他

6、月份此处忽略,循环结构的,C+,实现,循环结构在,C+,程序中有多种实现方式，较好的风格是直到型循环使用,do,语句、当型循环使用,while,语句、步长型采用,for,语句。,#include iostream.h,void main(),int n=0,s=0,temp=0;,coutn;,while(n!=0),temp=n/10;,s=s*10+(n-temp*10);,n=temp;,coutsendl;,#include iostream.h,void main(),int n=0,s=0,temp=0;,coutn;,for(;n!=0;temp=n/10,s=s*10+(n-t

7、emp*10),n=temp),;,coutsendl;,7.1.4,复杂结构,C+,实现示例,.,do,if(con2),if(con4),block3,else,block4,else,if(con3),block1,else,block2,while(con1),block5,C,B,A,7.1.4,复杂结构,C+,实现示例,例,7.3,求任意,n,个整数中的最大者与最小者。,算法输入：,依次输入,n,个整数。,算法输出：,上述整数中的最大、最小值。,数据结构：,n,为整数，意义与题同。,Max,和,Min,均为整数，是已经输入数据中的最大和最小数。,x,为每次输入的整数。,i,为整数。

8、,问题分析：,每循环一次输入一个整数，将之与以前的最大数,Max,和最小数,Min,对比后，根据比较结果更新,Max,和,Min,的值。,算法结束,Maxx,Minx,ii+1,n,，,x,Max,，,Min,算法开始,直到,i=n,Maxx,Maxx,Minx,x,void main(),int n=0,x=0,i=2;,coutn;,coutx;,int Max=x,Min=x;,while(i=n),coutx;,if(Maxx),Min=x;,i+;,coutMax=Maxendl;,coutMin=Minendl;,7.2,子算法设计与,C+,实现,参数为普通类型的子算法,参数为指针

9、的子算法,参数为引用的子算法,7.2.4,子算法设计与,C+,实现示例,对于出现在算法中不同部分的一组相同操作，为减少算法描述工作量，同时使算法更加简洁易读，通常的做法是将这个重复部分提取出来作为一个独立模块并加以命名，在需要的地方通过模块名及参数等信息调用这个模块，而不是反复重复相同的描述，这样的模块被称为,子算法（或函数）。,PAD,图表示方式如下：,进入,返回,具体操作,返回值 子算法名（子算法参数表）,参数为普通类型的子算法,子算法的参数为基本类型变量，调用子算法时的调用参数（实在参数）与子算法输入参数（形式参数）的形实结合采用传值方式，对应于,C+,函数定义及其调用的一般形式,。,算

10、法输入：,子算法入口参数为正整数,n,和,i,。,算法输出：,返回上述整数组成的 的值。,数据结构：,k,为整型变量，含义见下述公式，该量同时用作循环变量。,问题分析：,所给公式中有多个阶乘运算，时间代价较高。同时，阶乘运算的结果往往很大，比如,10,的阶乘就已达,3628800,，因此当,n,稍大就可能造成存储溢出。考虑到分子和分母之间存在公共因子，因此首先对所给公式化简如下：,例,7.4,编写算法求,变形后公式的优点在于：,参数为普通类型的子算法,算法描述及程序实现如下：,int GetCombination(int n,int i),进入,返回,nTemp1,k1,；,k=i,；,kk+

11、1,nTempnTemp*(n-i+k)/k,GetCombinationnTemp,long GetCombination(int n,int i),long nTemp=1;,for(int k=1;k=i;k+),nTemp=nTemp*(n-i+k)/k;,return nTemp;,参数为指针的子算法,这类子算法的参数可以为基本类型指针、数组、函数指针等,。,例,7.5,使用子算法求,n,个正整数中的最小数，并求两组,5,个整数中最小数之和。,算法输入：,子算法的入口参数为一维数组,array,及其所含元素数。,算法输出：,子算法返回数组中的最小值。,数据结构：,data,为整型数组

12、。,n,为所含元素数；,nTemp,、,nTemp1,、,nTemp2,为整型变量存储中间结果。,算法分析：因为需要两次从一个数组中提取最小值，因此将这部分功能独立作为一个模块，形成一个子算法，以便在需要时调用。这个功能比较简单，按照一般思路得到下面子算法及调用子算法的主算法。,参数为指针的子算法,这类子算法的参数可以为基本类型指针、数组、函数指针等,。,i1,；,idatai,nTempdatai,int GetMin(array,nNum),#include iostream.h,int GetMin(int array,int nNum),int nTemp=array0;,for(in

13、t i=0;iarrayi),nTemp=arrayi;,return nTemp;,void main(),int data15=8,12,4,3,6;,int data25=2,7,8,2,1;,int nTemp1=GetMin(data1,5);,int nTemp2=GetMin(data2,5);,coutnTemp1+nTemp2endl;,参数为引用的子算法,引用类型参数使子算法定义形式与其调用形式之间具有直观的对应性，达到类似于传址调用的效果，,引用类型参数可以,提高数据传递效率,。,例,7.7,设计子算法，根据汽车的信息（车牌号、油箱体积、本年度累计加油次数）,计算本年度该

14、汽车使用汽油量。,算法名称：,GetTotalConsumption,；,算法输入：,汽车信息（包括汽车牌照、油箱体积、加油次数）。,算法输出：,子算法返回汽车的年耗油量。,数据结构：,类型,CarInfo,为结构，具有三个字段：,szSerial(,汽车牌照号，字符串,),、,nVol,（油箱体积，整型）、,nNum,（加油次数，整型）。进入返回,问题分析：,由于子算法所需要的输入均与某辆汽车相关，显然最好的风格是将它们作为一个整体，因此在本算法实现中定义了结构类型,CarInfo,，而为了提高参数的传递效率，将子算法的参数类型取为引用类型,CarType&,。具体描述和相应的,C+,实现（

15、其中包括子算法的调用方法示例）如下：,参数为引用的子算法,进入,返回,tempinfo.nVolinfo.nNum,GetTotalConsumptiontemp,int GetTotalConsumption(CarInfo&info),#include iostream.h,#include string.h,struct CarInfo char*szPlate;int nVol;int nNum;,int GetTotalConsumption(CarInfo&info),int temp;,temp=info.nVol*info.nNum;,return temp;,void mai

16、n(),CarInfo i;,i.szPlate=new char10;,strcpy(i.szPlate,京,A:StruRef);,i.nNum=40;,i.nVol=100;,coutGetTotalConsumption(i)endl;,7.2.4,子算法设计与,C+,实现示例,例,7.8,设计一个班级成绩管理程序，该程序能够将每个学生的成绩按照总成绩由高到低的顺序存储，并可通过学号查寻学生的成绩。学生的成绩包括总成绩、语文成绩、数学成绩、化学成绩等。,算法名称：,InsertScore,主要功能：将学生的各科成绩按照总成绩排序插入到班级成绩表的适当位置。,算法输入：,nNum,（整型，学号）、,pName,（字符串，学生姓名）、,nChi,（整型，语文成绩）、,nMath,（整型，数学成绩）、,nChem,（整型，化学成绩）,算法输出：无返回值,数据结构：使用了班级成绩表,ClassScore,。,成绩表第,i,项尚未使用,将成绩插入当前元素处,当前元素总成绩,nTotal,调用,ShiftRight,右移数组元素,在当前位置,插入新成绩,void InsertScore(i