大学计算机程序设计基础（C语言2）ppt.ppt

程序设计基础 (国家级精品课) 张长海 程序设计基础 (国家级精品课) n第四章 循环程序设计 n第五章 模块化程序设计函数 n第六章 批量数据组织数组 第四章 循环程序设计 n循环程序 n多重循环 n程序设计实例 作业 4.14 4.18 4.20 习题集 P2348.3；P2566 练习 4.2 4.3 4.5 4.9 4.11 4.23 4.24 4.26 4.31 4.1 计算平均成绩循环程序 例4.1 某评估单位要对学生的学习情况 进行评估，需要计算每个学生的平均学习成 绩。编程序，从终端逐次输入一个学生n门 课程的成绩，计算并输出他的平均成绩。 #include #define n 40 void main(void) float sum ; int k , m; k1； sum0； do printf(“pleace input a achievement :“); scanf(“%d“, sum = sum + m; k = k+1 ; while ( k 0 yy = yy+4 开始 结束 求 yy 后第一个闰年 yy 是闰年 输出yy n= n-1 /*PROGRAM find leap year*/ #include “stdio.h“ void main() int yy,n; printf(“please input begin year:“); scanf(“%d“, printf(“please input the number of the leap year:“); scanf(“%d“, yy=(yy/4+1)*4; do if( (yy%4=0) n-; yy=yy+4; while(n0); 运行结果演示 例4.4 编程序，解方程 2X3+0.5X2-X+0.093=0 n变换方程为：X = 2X3 + 0.5X2 + 0.093 n若某个 X 代入右端后，计算结果正好是 X ， 则这个 X 值就是方程的根 简单迭代法 g (x) = 0x = f (x) 等价变换 n采用迭代法方法求解x=f(x)方程的根 选定一个 x的初值 x0 ； 以 x0 代入右端计算出一个值 x1=f(x0) 若 x1 等于x0 ，显然 x0 为根，转向 否则若 x1x0 则令 x0=x1 ，转向 结束，停止计算 f (x) y=x f (x0) x0 x1 f (x1) x*x2 可以使用简单迭代的情况 f (x2) f (x) y=x f (x1) x2x1 f (x0) x*x0 不可以使用简单迭代的情况 f (x2) n简单迭代方法使用条件 对于方程xf(x)，当任意x(a, b) 存在0 X0 = X1 X1 = f(X0) 开始 结束 #include “stdio.h“ #include “math.h“ #define eps 1e-6 void main() float x0,x1; x0=0.0; x1=0.0; do x0=x1; x1=2*x0*x0*x0 +0.5*x0*x0 +0.093; while(fabs(x1-x0)eps); printf(“x=%fn“,x0); 运行结果演示 4.1.2 先判断条件的循环 sum=0; k=1; 读入一科成绩 m sum =sum+m; k = k+1 ; 开始 k #define n 40 void main(void) float sum ; int k , m; k1； sum0； while ( k eps e=e+r ; 开始 结结束 r=r*1/n ; n=n+1; #include “stdio.h“ #define eps 1e-5 void main( ) int n ; float e,r ; e=1.0; n=1; r=1.0; while ( reps ) e=e+r; n=n+1; r=r/n; printf (“ e=%fn“,e) ; e=1.0; n=1; r=1.0; ne=2.0; n=2; r=0.5; ne=2.5; n=3; r=0.1667; ne=2.6667; n=4; r=0.0417; n 运行结果演示 例4.7 编程序，统计以100为结束符的整数 输入流中 -1 、0 、+1 的出现次数并输出 while num != 100 i=0; j=0; k=0; 输出 i,j,k 开始 结束 输入一个数 num i+ j+ k+ num -1 0 1 输入一个数 num #include #define n 100 void main(void) int i , j , k , num ; i=0; j=0; k=0; printf(“pleace input a integer :“); scanf(“%d“, while ( num != n ) switch (num) case -1 : i+; break; case 0 : j+; break; case 1 : k+; printf(“pleace input a integer :“); scanf(“%d“, printf(“number of -1 : %dn“ , i ); printf(“number of 0 : %dn“ , j ); printf(“number of 1 : %dn“ , k ); 运行结果演示 +和- v0 1一元-v v0 v0 1 后缀缀 v- v0 + 1 一元 +v v0 v0 + 1 后缀缀v+ 运算后表达式值值运算后v的值值类别类别表达式 表达式 v+ 是先求表达式的值，后对v加1 。结果表达式 的值是对v进行加1之前的v值，即v0 。 表达式 +v 是先对v加1 ，后求表达式的值。结果表达式 的值是对v进行加1之后的v值，即v0+1 。 4.1.3 for 语句 研究先判断条件的循环 e=1.0; n=1; r=1.0; while ( reps ) e=e+r; n=n+1; r=r/n; e=1.0; n=1; for ( r=1.0; reps; r=r/n ) e=e+r; n=n+1; “r=1.0”是循环控制的初值； “reps”是循环控制； “r=r/n”是对循环控制条件的修正。 由于这种程序模式在程序设计中经常出现，C为这种程序模 式提供一种简写形式for语句 nfor语句最经常被用于描述循环次数已知循环 sum = 0 ; k = 1 ; while( k=2;j-) flag = true i%j = 0 for (i=2; i=2; j-) flag = true i%j = 0 #include “stdio.h“ void main( ) int i ，j ; bool flag; for ( i = 2 ;i 2 ; j- ) if ( i % j = 0 ) flag=false ; if ( flag ) printf(“%5dn“ , i ) ; 运行结果演示 n多重循环程序编写要点 内外循环控制条件不要互相冲突 for ( i = 2 ;i = 2 ; i- ) if ( i % j = 0 ) flag=false ; if ( flag ) printf(“%5dn“ , i ) ; 4.3 程序设计实例 n打印数列 n求两数最大公因数 n阶乘求和 n“百钱百鸡“问题 n打印字符方阵 【例4.11】编程序，输出斐波纳契（Feibnaqi）序列的前 20 项。该序列的前两项为 1 ，以后各项为其前两项之和。即 ： 1、1、2、3、5、8、13、21、 解：该问题应该用两个变量u、v分别保存已经生成的两项 ，用一个变量w保存当前正生成的一项。然后一项一项的生成， 生成一项输出一项。在生成一项并输出之后，要考虑为生成下 一项做准备，应该把后边的项向前串， 项数项数 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 1 1 1 u u v v 2 2 ww 1 1 2 2 u u v v 3 3 ww 2 2 3 3 u u v v 5 5 ww 3 3 5 5 u u v v 8 8 ww 5 5 8 8 u u v v 1313 ww k/ 括入标准输入输出函数库头文件 float xa,ya,xb,yb,xc,yc;/分别保存三角形顶点的X、Y方向坐标 float xd,yd,xe,ye ; /分别表示中点D、E坐标 float a1,b1,a2,b2;/分别表示中线AD、BE的方程系数 float xo,yo;/重心O的坐标 void main(void) / 主函数 / 输入三个点的X、Y方向坐标 printf(“please input xa,ya,xb,yb,xc,yc:n“); scanf(“%f%f%f%f%f%f“, xd=(xb+xc)/2; /求BC边的中点D yd=(yb+yc)/2; a1=(ya-yd)/(xa-xd); /求过A、D两点的直线方程 b1=ya-a1*xa; xe=(xa+xc)/2; /求AC边的中点E ye=(ya+yc)/2; a2=(yb-ye)/(xb-xe); /求过B、E两点的直线方程 b2=yb-a2*xb; xo=(b2-b1)/(a1-a2); /求AD、BE交点O yo=a1*xo+b1; printf(“重心坐标：x=%10.3f y=%10.3f n”,xo,yo); “求BC边的中点D”和“求AC边的中点E”的两段程序是一样的， 在程序中重复写了一次。 再回顾第二章例2.4的程序，在计算矩形周长时，计算两个边长 度的程序也是一样的，在程序中重复写了一次。 ab=sqrt( (xa-xb)* (xa-xb)+(ya-yb)* (ya-yb) );/边ab长 bc=sqrt( (xb-xc)* (xb-xc)+(yb-yc)* (yb-yc) );/边BC长 在例2.5的程序中 “计算三角形ABD的面积”和“计算三角形 BCD的面积”程序也是一样的，在程序中重复写了一次； / 计算一个三角形面积 ab=sqrt( (xa-xb)* (xa-xb)+(ya-yb)* (ya-yb) );/边ab长 bd=sqrt( (xb-xd)* (xb-xd)+(yb-yd)* (yb-yd) );/边bd长 ad=sqrt( (xa-xd)* (xa-xd)+(ya-yd)* (ya-yd) );/边ad长 s=(ab+bd+ad)/2;/s s1=sqrt( s*(s-ab)*(s-bd)*(s-ad) );/面积 / 计算另一个三角形面积 bc=sqrt( (xb-xc)* (xb-xc)+(yb-yc)* (yb-yc) );/边BC长 cd=sqrt( (xc-xd)* (xc-xd)+(yc-yd)* (yc-yd) );/边CD长 s=(bc+bd+cd)/2; /边BD长bd前边已经计算 s2=sqrt( s*(s-bc)*(s-bd)*(s-cd) ); 在计算三角形面积时，计算一个边长度的程序也是一样的， 在程序中重复照写了五次。 一般程序设计语言都为这种“计算过程一致，而参与运 算的数据不同”的请况，提供一种机制子程序。在 C 中子程序体现为函数（function）。下边用函数来重写 例5.1的程序。 #include / 括入标准输入输出函数库头文件 float xa,ya,xb,yb,xc,yc; /分别保存三角形三个顶点点的X、Y方向坐标 float xd,yd,xe,ye ; /分别表示中点D、E坐标 float a1,b1,a2,b2,a,b;/分别表示中线AD、BE的方程系数, a、b临时变量 float xo,yo;/重心O的坐标 float lines( float xr,float yr,float xs,float ys,float xt,float yt )/* 求中线：参数：三角形三个顶点r、s、t的x、y坐标 */ float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 void main(void) / 主函数/14 printf(“please input xa,ya,xb,yb,xc,yc:n“);/15 / 输入三个点的X、Y方向坐标 346 360 416 108 116 212 scanf(“%f%f%f%f%f%f“,/16 b1=lines(xa,ya,xb,yb,xc,yc); /求BC边的中线AD/17 a1=a;/18 b2=lines(xb,yb,xa,ya,xc,yc); /求AC边的中线BE/19 a2=a;/20 xo=(b2-b1)/(a1-a2); /求AD、BE交点O/21 yo=a1*xo+b1;/22 printf(“重心坐标：x=%10.3f y=%10.3f n”,xo,yo);/ 打印输出/23 /24 对照例5.2与例5.1的 程序。例5.2引进函 数计算中线，当具体 计算某条中线时，调 用该函数。程序显得 干净、利索、清晰， 即好读又好看，并且 与原始问题目有相当 高的可对照性。因为 这里使用了“子程序” 技术。 这就是模块化程序。 以模块为指导思想的程序设计过程称 模块化程序设计。 运行结果演示 狭义的讲，模块化程序设计依赖于子程序，每个模 块是一个子程序。在C中子程序体现为函数，程序的每个 模块是一个函数。 /* 求中线：参数：三角形三个顶点r、s、t的x、y坐标 */ float lines( float xr,float yr ,float xs,float ys ,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 5.2 函数 函数定义 void main(void) / 主函数/14 / 输入三个点的X、Y方向坐标 346 360 416 108 116 212 printf(“please input xa,ya,xb,yb,xc,yc:n“);/15 scanf(“%f%f%f%f%f%f“,/16 b1=lines(xa,ya,xb,yb,xc,yc); /求BC边的中线AD/17 a1=a;/18 b2=lines(xb,yb,xa,ya,xc,yc); /求AC边的中线BE/19 a2=a;/20 xo=(b2-b1)/(a1-a2); /求AD、BE交点O/21 yo=a1*xo+b1;/22 printf(“重心坐标：x=%10.3f y=%10.3f n”,xo,yo);/ 打印输出 /23 函数调用 5.2.1 函数定义 除标准库函数外, 程序中使用函数必须先定义，然后 再用“函数调用”调用它。 标准函数是系统已经定义好的函数，不必定义即可直 接调用。 /* 求中线：参数：三角形三个顶点r、s、t的x、y坐标 */ float lines( float xr,float yr ,float xs,float ys ,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 /* 求中线：参数：三角形三个顶点r、s、t的x、y坐标 */ float lines( float xr,float yr ,float xs,float ys ,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 函数定义的形式: 函数类型函数名 形式参数表 形式参数 参数类型 返回语句 函数定义说明符 函数体 复合语句 /* 求中线：参数：三角形三个顶点r、s、t的x、y坐标 */ float lines( float xr,float yr ,float xs,float ys ,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 函数定义的形式: 函数类型函数名 形式参数表 形式参数 参数类型 返回语句 函数定义说明符 函数体 复合语句形式如下 TT F ( 参数列表) 具体指明： 函数的结果类型 由“类型说明符”( TT )标明； 函数的名字 由类型说明符后的“标识符” ( F )标明； 函数的形式参数个数和每个形式参数的特性 由“参数列表”标明。 函数类型 函数的结果类型 缺省 int 类型 结果类型不能是数组类型、函数类型 函数可以是无值的，即“无类型”的 void 参数列表形式 T id ，T id ，. ，T id 每个参数声明形式： 类型说明符 标识符 C允许使用无参函数，无参函数的参数列表为空，或使 用“空类型”的类型说明符“void” TT F() TT F (void ) 函数名是一个标识符 int f(int x, int y, float z) int f(int x,y ; float z) int f(int x,y , float z) /* 求中线：参数：三角形三个顶点r、s、t的x、y坐标 */ float lines( float xr,float yr ,float xs,float ys ,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 函数定义的形式: 函数类型函数名 形式参数表 形式参数 参数类型 返回语句 函数定义说明符 函数体 复合语句 复合语句（compound-statement）由声明和语句 列表组成 声明部分具体的说明本函数内使用的其它量； 语句部分规定在本函数中要执行的算法动作。 返回语句形式： return 表达式； return ； n函数定义的形式： TT F ( T id ，T id ，. ，T id ) . void main(void) / 主函数/14 / 输入三个点的X、Y方向坐标 346 360 416 108 116 212 printf(“please input xa,ya,xb,yb,xc,yc:n“);/15 scanf(“%f%f%f%f%f%f“ ,/16 b1=lines(xa,ya,xb,yb,xc,yc); /求BC边的中线AD/17 a1=a;/18 b2=lines(xb,yb,xa,ya,xc,yc); /求AC边的中线BE/19 a2=a;/20 xo=(b2-b1)/(a1-a2); /求AD、BE交点O/21 yo=a1*xo+b1;/22 printf(“重心坐标：x=%10.3f y=%10.3f n” ,xo,yo);/ 打印输出/23 5.2.2 函数调用 一般形式 F (U, U, ,U) F ( ) 被调用函数名 实在参数表 实在参数 调用过程 首先顺序计算实参表中各实参值 然后把这些值顺序传入形参表的各个形参中 最后进入函数执行复合语句。 被调用函数名：标识符 实在参数表由逗号分隔开的一个个表达式组成 每个实在参数是一个表达式 主程序 调用函数 返回 结束 函数 调用一个函数的大致执行过程是： #include / 括入标准输入输出函数库头文件 float lines( float xr,float yr,float xs,float ys,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 void main(void) / 主函数/14 b1=lines(xa,ya,xb,yb,xc,yc); /求BC边的中线AD/17 a1=a;/18 b2=lines(xb,yb,xa,ya,xc,yc); /求AC边的中线BE/19 a2=a;/20 函数返回返回方式： return ； return 表达式； 函数运行到复合语句末尾。 函数值 执行返回语句时，表达式计算出的值 #include / 括入标准输入输出函数库头文件 float lines( float xr,float yr,float xs,float ys,float xt,float yt ) float xu,yu;/中点u坐标/7 xu=(xs+xt)/2; /求st边的中点u/8 yu=(ys+yt)/2;/9 /求过r、u两点的直线方程/10 a=(yr-yu)/(xr-xu); /计算系数a/11 return yr-a*xr ;/计算系数b，并带着b值返回/12 void main(void) / 主函数/14 b1=lines(xa,ya,xb,yb,xc,yc); /求BC边的中线AD/17 a1=a;/18 b2=lines(xb,yb,xa,ya,xc,yc); /求AC边的中线BE/19 a2=a;/20 n有返回类型的函数 int f (int x, int y) if (x=y) return x; else return y; n无返回类型的函数 void g( int w) if (w=1) return; else x=3; n有返回类型函数的函数值 使用 return e; 向调用函数的主程序传递函数值 return e ; 的执行过程是： 计算表达式e的值 把表达式值按赋值转换规则，转换成函数的结 果类型； 返回语句中表达式的类型与函数的结果类型必 须赋值兼容。 用类型转换后的值作为函数值，并带着它返回 到调用该函数处 n无返回类型函数的函数值 void g( int w) if (w=1) return; else x=3; n在函数调用处，所调函数无值可以带回。 对于无类型函数，在函数调用处不需要函数值， 这种返回是正常的； 对于有类型函数，在函数调用处极可能需要函数 值参加下一步运算，这将带来不可预料的结果 5.2.3 先调用后定义函数原型 【例5.3】用函数重新写第四章例4.11，打印 100 以内素数。 /* PROGRAM writeprime */ #include “stdio.h” bool prime( int n ) int j ; for ( j = n / 2 ; j = 2 ; j- ) if ( n%j = 0 ) return false ; return true ; void main( ) int i ; for ( i = 2 ;i = 2 ; j- ) if ( n%j = 0 ) return false ; return true ; n一般形式 TT F ( T ，T ，. ，T ); TT F ( T id ，T id ，. ，T id ); n如下两个函数原型等价 float f ( int, float, int, char ) ; float f ( int z, float u, int v, char w ) ; n函数原型的功能 满足了C标识符先定义后使用的要求 并向编译系统提供所调用函数的信息 函数返回类型 函数的参数个数 函数参数特性等信息 程序设计风格 最好把所有函数原型集中，放在主函数之 前 5.3 程序设计实例 n重写打印字符矩阵 n重写打印100以内素数 n验证哥德巴赫猜想 n验证 Pascal 定理 n十六进制数翻译 【例5.5】用函数重新写第二章例2.4的程序，求植树棵数。 #include / 括入标准输入输出函数库头文件 #include / 括入标准数学函数库头文件 float xa,ya,xb,yb,xc,yc,xd,yd; /分别保存四个点的X、Y方向坐标 float ab, bc ; /分别表示矩形的两个相邻边 float ss; int m;/ 计算用变量；ss表示周长；m表示植树棵树 /* 计算r、s两点距离：参数：r点x、y坐标，s点x、y坐标 */ float lines( float xr,float yr,float xs,float ys ) return sqrt( (xr-xs)*(xr-xs)+(yr-ys)*(yr-ys) ); void main(void) / 主函数 / 输入四个点的X、Y方向坐标 printf(“please input xa,ya,xb,yb,xc,yc,xd,yd:n“); scanf(“%f%f%f %f%f%f %f%f“ , / 计算边长 ab=lines( xa,ya,xb,yb );/边ab长 bc=lines( xb,yb,xc,yc ); /边BC长 ss=(ab+bc)*2;/s m=ss/2;/ 计算总植树棵数 printf(“总植树棵数：%10dn”,m);/ 打印输出 运行结果演示 【例5.6】用函数重新写第二章例2.5的程序，求四边形地块玉米产量。 #include / 括入标准输入输出函数库头文件 #include / 括入标准数学函数库头文件 float xa,ya,xb,yb,xc,yc,xd,yd; /分别保存四个点的X、Y方向坐标 float s1,s2,ss,m;/ 计算用变量；ss表示总面积；m表示总产量 float areauvw ( float xu,float yu,float xv,float yv ,float xw,float yw );/函数原型 void main(void) / 主函数 / 输入四个点的X、Y方向坐标 printf(“please input xa,ya,xb,yb,xc,yc,xd,yd:n“); scanf(“%f%f%f%f%f%f%f%f“ , s1 = areauvw (xa, ya, xb, yb, xd, yd );/ ABD面积 s2 = areauvw (xb, yb, xc, yc, xd, yd );/ BCD面积 ss=s1+s2; / 总面积S=SI+S ss=ss*15/1000; / 折合成亩 m=ss*650;/ 计算总产量 printf(“m=%10.3fn”,m);/ 打印输出 /* 计算r、s两点距离：参数：r点x、y坐标，s点x、y坐标 */ float liners( float xr,float yr,float xs,float ys ) return sqrt( (xr-xs)*(xr-xs)+(yr-ys)*(yr-ys) ); /* 计算三角形uvw面积，参数：u点x、y坐标，v点x、y坐标 ，w点x、y坐标 */ float areauvw ( float xu,float yu,float xv,float yv ,float xw,float yw ) float uv , uw , vw ;/ 三条边长 float s ; uv = liners ( xu, yu, xv, yv ); /边uv长 uw = liners ( xu, yu, xw, yw );/边uw长 vw = liners ( xv, yv, xw, yw );/边vw长 s=(uv+uw+vw)/2;/s return sqrt( s*(s-uv)*(s-uw)*(s-vw) );/ 返回面积 运行结果演示 例5.7 验证哥德巴赫猜想: 任意一个大偶数都可以分解为两个素数之和。随机产生 10 个大于 6 的偶数进行验证, 并对每个偶数输出分解结果。 输入偶数N 开始 结束 while N 0 输入偶数N N可分解 输出OK！ 输出NO! 结束 开始 n 是素数 n =N/2; n- ) return flag flag = false #include “stdio.h“ bool analyze( int );/函数原型 bool prime( int ) ; main()/主函数 int N; printf(“pleace input N:“); scanf(“%d“, while (N0) if(analyze(N) printf(“n-OK!-n”); else printf(“n-NO!-n”); printf(“pleace input N:“); scanf(“%d“, bool analyze( int N )/分解 int n; bool flag; flag = false;/ 先假设哥德巴赫猜想错误，标志置“假” for ( n=N-2; nN/2; n- ) if( prime(n) flag = true; /哥德巴赫猜想正确，标志置“真” return flag;/带标志返回 bool prime( int n ) /判断n是否素数 int j ; for ( j = n / 2 ; j = 2 ; j- ) if ( n%j = 0 )/有其它因子，不是素数 return false ; return true ;/无其它因子，是素数 运行结果演示 本章小结 n函数的定义 n函数的调用 n模块化程序设计思想 第六章 批量数据组织数组 n成绩统计数组类型 n统计多科成绩多维数组 n程序设计实例 n成绩排序数组初值 n输出回文字字符串 n类型定义 作业: 6.1 6.3 6.7 6.9 6.22 习题集：P5111；P58125 练习: 6.2 6.4 6.6 6.10 6.14 6.15 6.16 6.18 6.1 成绩统计数组类型 【例6.1】为了分析学生对程序设计课程的掌握程度，需 要对该课程成绩进行统计。编程序，输入一个班50名学生的 程序设计课程成绩，然后按10分为一段，统计各段成绩的学 生人数，并输出。 。 解：该问题的算法很简单。首先用一个循环顺序输入50 名学生的成绩，设为a0、a1、a2、 、a49；再用11个计数器 j0、j1、j2、 、j10分别记录0-9、10-19、91-99、100各 个分数段的学生数。方法是先把诸 j 清“0”，再扫描这50个分 数，判断每个分数所在分数段，给相应计数器加1。最后用一 个循环输出每段分数的个数。该算法可以描述为如图的PAD 。 开始 结束 for (i=0;iai+1则交换ai、ai+1 如此反复进行，直到某一次扫描，没有数据交换为止 ，便完成了对数组A的排序 至多扫描次就可以使数组A完成排序，所以该算法能 够终止。 例6-6 对整数组进行 冒泡法排序 7 4 1 6 5 4 1 7 6 5 1 4 6 5 7 第一轮: 第二轮 : 4 7 1 6 5 1 6 4 1 6 7 5 4 1 6 5 7 1 4 5 6 7 4 1 6 5 7 第三轮 : 1 4 5 6 7 0 1 2 3 4 下标 用bool型变量flag标志一次扫描过程中是否有数据交换 n判断是否需要进行下一轮扫描步骤 每次扫描开始令 flag=false ，假设没有数据交换 然后，当有数据交换时令 flag=true 最后在一遍扫描结束后: 若 flag=true 则说明本次扫描有数据交换，还应 进行下一次扫描 否则扫描终止 冒泡排序 结束 flag for(i=0;iai+1 void sortofup ( int n, int a ) int i,r ; bool flag ; flag = true ; while ( flag ) flag = false ; for ( i=0 ; i ai+1 ) r = ai ; ai = ai+1 ; ai+1 = r ; flag=true; 运行结果演示 例6.7 顺序检索 n “检索”与“分类”是互相联系在一起的，也是 计算机科学中研究的一类重要课题。 n我们仍以整数组为背景介绍两种较常见的 算法 nA已经按递增排序。 n检索思想 顺次用欲检索的关键字值key与数组中元素 a0、a1、. 、an-1逐一进行比较。 找到一个j使key=aj： 位置为j，函数search带着j返回； 直到结束，没有使key=aj的j存在： 未找到，函数search带回值 1 。 int search (int n, int a , int key ) / key为检索关键字 int j ; /* 返回位置 */ for (j=0; jaj: key在aj与aupper之间， 检索区间缩小一半,lower=j+1 重复上述过程。重复的终止条件为 upper-lower aj: lower=j+1 j=(lower+upper)/2 key=aj: return j 2433455760616270757780909499 lowerupper j upper j lower j 2433455760616270757780909499 lowerupper j upper j lower j 以关键字key值为58为例的检索过程 j=(lower+upper)/2 keyaj: lower=j+1 j=(lower+upper)/2 keyaj: lower=j+1 upper-lower=0 lower=0；upper=n-1； 结束 key=aj j=(lower+upper) / 2 return j lower=j+1 upper=j-1 keyaj return -1 编出函数如下： int half_search (int n, int a , int key ) /* key为检索关键字 */ int lower,upper,j; lower = 0 ; upper = n-1 ; while ( upper-lower=0 ) j = ( lower+upper ) / 2 ; /* 两分 */ if ( key=aj ) return j ; /* 已经找到，位置为*/ else if ( key aj ) lower=j+1 ; /* key在aj+1与aupper之间 */ else upper=j-1 ; /* key在alower与aj-1之间 */ return -1 ; 运行结果演示 【例6.9】编一个函数，求两矩阵乘积。 解：设设有矩阵阵 mp 、pn ，则则其乘积积矩阵阵 mn 的元素 ij 为为 for (i=0;i=0; i-) 求 xi 求xi 已知：xi+1,xn-1 需求：i+1n-1的和，用j标识 求xi时的条件是：xi+1 、xi+1 、. 、xn-1 已经求出； 第i个方程是： aii*xi + aii+1*xi+1 + . + ain-1*xn-1 = ain 所以该方程的解应该是： xi=( ain-( aii+1*xi+1 + . + ain-1*xn-1) )/aii 开始 结结束 for(i=0; i=0; i-) r = 0 for(j=i+1; j=0 ; i- ) /* 从最后一个方程（第n-1行）