c语言程序设计15第十四讲第六章下.ppt

1,C语言编程是一项技艺，需要多年的历练才能达到较为完善的境界！-摘自Expert C Programming,2,高级语言程序设计,主讲教师：贾彩燕计算机与信息技术学院计算机科学与技术系,3,第六章 数组,4,数组的概念、定义和使用数组程序实例数组作为函数参数字符数组和字符串两维和多维数组编程实例,主要内容,一维数值型数组的重要应用,5,要点回顾,一维数组的重要操作排序查找插入删除元素交换字符数组的如何定义，如何初始化？字符数组的有效长度和字符数组？常用的字符串处理函数有哪些？,6,例，找出（标准输入）文本中最长行并输出,保存已读最长行以输出，数组maxline，按字符串形式。数组line保存新行，更长时转存maxline。假定行长不超过1022字符，用符号常量定义数组大小。,函数getline读入一行，存入参数数组并返回行长。需防止越界，用参数limit控制实参数组长度。int getline(int limit,char line);,基本处理框架：while(还有新行输入)if(新行比已记录的最长行更长)记录新行及其长度;输出记录下来的最长行;,7,行总有字符(空行有换行符)，返回值0。文件结束时返回0。设MAXLEN表示数组长度，大循环可写为：while(getline(MAXLEN,line)!=0).,int main()int n,max=0;/*记录当前行和最长行长度*/char lineMAXLEN,maxlineMAXLEN;while(n=getline(MAXLEN,line)0)if(n max)/*新行更长，保存*/strcpy(maxline,line);max=n;if(max 0)printf(”Len:%dn%sn,max,maxline);return 0;,8,整个程序：#include#include enum MAXLEN=1024;int getline(int limit,char line);int main()int getline(int limit,char line)int c,i=0;while(i limit-2,9,#include enum MAXLEN=1024;int getline(void);char lineMAXLEN,maxlineMAXLEN;int main()int n,max=0;/*当前行和最长行长*/while(n=getline()0)if(n max)max=n;strcpy(maxline,line);if(max 0)printf(%sn,maxline);return 0;,另一种写法：把两个数组作为外部变量，各函数里直接访问，不再作为参数传递。,10,int getline(void)int c,i=0;while(i MAXLEN-2,优点：可简化函数定义和参数描述。缺点：数组名写在函数定义里，造成函数对全局数据的依赖。,11,程序的缺点：1）固定数组限制了能读入的最长行；2）出现超长行时出现截断，且长度统计错误。长度统计错误问题易解决：数组满后继续读字符计数，但字符不存入line。最后得到实际最长行的长度，及该行中不超过1022个实际字符。,人们倾向于把程序里大型、唯一、许多函数公用的数据（如大数组）定义为外部变量。一般数据用参数传递。对于具体问题应怎样处理，要考虑软件系统实现各方面的问题，如方便、清晰、数据安全等因素。,怎么办？,12,第十四讲（作业提示）,P215页第5题：写一个把数字字符串转换成整数的函数，它只有一个字符数组参数参照：P192页二进制转换P215页第11题：写程序，它读入一个文件，输出其中最长的词参照：P194页读入文件输出最长行P215页第13题：写一个函数，它能够判断字符串是否是一个回文英文字符串、中文字符串、中英文混杂中文：双字节表示一个中文要求：首字节的ASCII值大于127简单方法准确方法：了解中文的unicode,双字节编码后对应的ASCII值在19968(4E00)至40891(9FBB)之间,13,轻松一下：回文(Palindrome)的乐趣,回文就是指一个单词或短语，其顺读和倒读都是一样的两个经验的回文拿破伦被放逐到Elba岛时说的一句话“Albe was I,ere I saw Elba”A man,a plan,a canal-panama!1983年10月，CMU计算机科学研究生Jim Saxe将它扩展为：A man,a plan,a cat,a canal-panama!一场竞赛开始了,14,世界上最长的回文,耶鲁大学的Steve SmithA tool,a fool,a pool-loopaloofallota!几周之后的扩展A man,a plan,a cat,a ham,a yak,a yam,a hat,a cannal-panama!世界上最长的回文http:/17826个单词,15,清代女诗人吴绛雪的四季回文诗,春：莺啼岸柳弄春晴，夜月明。莺啼岸柳弄春晴，柳弄春晴夜月明。明月夜晴春弄柳，晴春弄柳岸啼莺。夏：香莲碧水动风凉，夏日长。香莲碧水动风凉，水动风凉夏日长。长日夏凉风动水，凉风动水碧莲香。秋：秋江楚雁宿沙洲，浅水流。秋江楚雁宿沙洲，雁宿沙洲浅水流。流水浅洲沙宿雁，洲沙宿雁楚江秋。冬：红炉透炭炙寒风，御隆冬。红炉透炭炙寒风，炭炙寒风御隆冬。冬隆御风寒炙炭，风寒炙炭透炉红。,16,数组的概念、定义和使用数组程序实例数组作为函数参数字符数组和字符串两维和多维数组编程实例,主要内容,一维数值型数组的重要应用,17,6.5 两维和多维数组,一维数组有一个下标，元素线性排列。需要处理更复杂的结构，如数值应用中的矩阵。矩阵为两维，元素通过两个下标指定。如何表示？,例：计算两个88的矩阵的和及乘积计算三维空间中的一系列点的中心。,18,二维数组的定义定义方式：数据类型数组名常量表达式常量表达式；,例 int a34;double b25;int c234;int a3,4;(),行数,列数,元素个数=行数*列数,二维和多维数组,称a为34的int（二维）数组，b为25的double（二维）数组等，c为234的int（三维）数组,19,数组元素的存放顺序原因:内存是一维的二维数组：按行序优先多维数组：最右下标变化最快,二维和多维数组,20,每个元素ai由包含4个元素的一维数组组成,二维数组a是由3个元素组成,二维数组理解,a是开始位置（数组a的首地址）也是a0的开始位置，也是a00的位置,21,二维数组元素的初始化分行初始化：,22,二维数组元素的初始化按元素排列顺序初始化：,23,设有数组定义：double a32;int b44;a表示整个数组，a0、a1和a2表示成员数组。a01表示a的0成员数组中下标1的元素。例：a21=a01+a11;,二维（多维）数组的表示和使用,for(i=0;i 4;+i)for(j=0;j 4;+j)bij=i+j;,24,例：向一个二维数组输入并输出其全部元素,#include int main()int i,j;int b32;printf(“输入数据：n”);for(i=0;i 3;i+)for(j=0;j 2;j+)scanf(“%d”,25,for(i=0;i N;+i)for(j=0;j N;+j)x=0.0;for(k=0;k N;+k)x+=Aik*Bkj;Cij=x;for(i=0;i N;+i)for(j=0;j N;+j)printf(%f%c,Cij,j=N-1?n:);,例：写程序段求出由两维数组A、B表示的55矩阵的乘积，存入两维数组C（设A，B已有值）并输出。,26,例：将5个同学的姓名从小到大排序并输出,27,二维（多维）数组作为函数参数,下面函数求出n5数组中数据均值（n是参数）：double aavg(int n,double a5)int i,j;double sum=0.0;for(i=0;i n;+i)for(j=0;j 5;+j)sum+=aij;return sum/(5*n);,可用于任何n5的数组，但不能用于例如47的数组下章将介绍一种定义通用函数的方法。,作为函数参数时不必给出最左一维长度，但要求给出除最左一维外其他各维的长度。,28,例：有一个3*4的矩阵,求出其中的最大元素的值.,#include int max_value(int,int 4);int max_value(int n,int array4)int i,j,max=array00;for(i=0;i max)max=arrayij;return max;int main()static int a34=1,3,5,7,2,4,6,8,15,17,34,12;printf(“max value is%dn”,max_value(3,a);return 0;,29,数组的概念、定义和使用数组程序实例数组作为函数参数字符数组和字符串两维和多维数组编程实例,主要内容,30,6.6 编程实例（下）,本节讨论一些基于数组的编程实例。一个具体问题可写出许多不同的程序。从问题到程序的工作过程中，许多地方需要编程者做出选择。有些选择涉及对问题的不同考虑或认识，可能引起程序间的显著差异。,31,例1：成绩直方图文件里保存着一批学生成绩，写程序读入这些成绩，产生其平均值M和标准差S，并做直方图。有定义：,程序中需要反复使用学生成绩，应存入数组(double型)。程序工作比较多，考虑将主要工作划分为若干函数。,程序工作分为三步（第一层分解）：输入，计算并输出统计量，计算并输出直方图。,32,enum NUM=200,HISTOHIGH=60;double scoresNUM;int readscores(int lim,double tb);void statistics(int num,double tb);void histogram(int num,double tb,int high);int main(void)int n=readscores(NUM,scores);statistics(n,scores);histogram(n,scores,HISTOHIGH);return 0;,程序主体结构,函数原型,33,int readscores(int lim,double tb)int i=0;while(ilim,输入成绩函数,34,void statistics(int n,double tb)int i;double s,sum,avr;if(n 2)/*项数小于2时的处理*/printf(Data too few.n);return;for(sum=0.0,i=0;i n;+i)sum+=tbi;avr=sum/n;for(sum=0.0,i=0;i n;+i)sum+=(tbi-avr)*(tbi-avr);s=sqrt(sum/(n-1);printf(Total students:%dn,n);printf(Average score:%fn,avr);printf(Std deviation:%fnn,s);,计算并输出统计值函数,如果需要保留 avr和s？,35,直方图生成（用横向的直方图）：,每个成绩段输出一组字符，选H作为基本字符。void prtHH(int n)int i;for(i=0;i n;+i)putchar(H);,分段长度可用符号常量SEGLEN表示，根据它可算出分段数HISTONUM。enum SEGLEN=5,HISTONUM=(100/SEGLEN)+1;,36,分段成绩数统计：用数组统计各分段成绩人数，将数组命名为segs，其中应有HISTONUM个计数器。,处理的是等长分段，存在从成绩得到计数器下标的简便方法。segs(int)scoresi)/SEGLEN+;将成绩强制转到int后除以分段长度得到计数器下标。,下面考虑用如下形式输出直方图行：80:23|HHHHHHHHHHHHHH,为使直方图规范化，最长行HISTOHIGH个字符。,37,void histogram(int n,double tb,int high)int i,mx;int segsHISTONUM;if(n=0)return;for(i=0;i mx)mx=segsi;/*找最大值*/for(i=0;i HISTONUM;+i)/*输出*/printf(%3d:%4d|,(i+1)*SEGLEN,segsi);prtHH(segsi*high/mx);putchar(n);,38,分析和改进若文件中都是0到100的数值，程序能得到正确结果。出现不法数据呢？如混入一个178，程序会怎么样？实际软件应正确处理合法输入，还应在输入有错时合理处置。如果编译程序遇到不合法程序就垮台，还可能破坏操作系统，还有人愿意用它吗？程序抵御不合法数据破坏的能力称为强健性。,修改后的readscores如下首先需要检查每个输入项，只将合法数据存入数组。有关数据是否处理完的情况只能在循环结束后检查。,39,int readscores(int limit,double tb)int i=0,line=1;double x;for(;ilimit,还可考虑其他改进。,40,例2“计算”数组的大小例：求2.38、3.142、5.64、8.27、6.44的平均值。,#include double a5=2.38,3.142,5.64,8.27,6.44;int main()int n;double sum=0.0;for(n=0;n 5;+n)sum+=an;printf(Average:%fn,sum/5);return 0;,缺点：改一组数据（不是5个）就要改程序（程序里的三个5都要改）。,41,运算符sizeof求类型或变量占内存量。sizeof(a)求出a大小，sizeof(a0)求出a元素大小。(sizeof(a)/sizeof(a0)求出数组a的元素个数。,#include#define NUM(x)(sizeof(x)/sizeof(x0)double a=2.38,3.142,5.64,8.27,6.44;int main()int n;double sum=0.0;for(n=0;n NUM(a);+n)sum+=an;printf(Average:%fn,sum/NUM(a);return 0;/*更改数组数据时只需添入新数据*/,42,#define NUM(x)(sizeof(x)/sizeof(x0)double avg(double a)double x=0.0;int i,len=NUM(a);for(i=0;i len;+i)x+=ai;return x/len;这样不行：sizeof是静态处理的运算符，数组参数实际上不是数组（是指针，sizeof(a)求出一个指针的大小（通常等于一个int的大小），详见第7章）。,43,例3：数组的划分节要求分段输出学生成绩。一种可能方式是调整成绩排列，把不及格成绩移到左边，及格成绩移到右边，而后顺序输出按照某种标准把数组里的数据分段称为“划分”,考虑一种划分算法：用两个下标变量，逐步从两端向中间移，保证下图所示的不变关系：,循环开始时令 i=0，j=n-1，关系成立到 i=j 不成立时，划分完成,44,划分循环：for(i=0,j=n-1;i=PASS)-j;if(i j)x=scoresi;scoresi=scores j;scores j=x;+i;-j;if(i=j,循环结束时，scores里下标0到i-1是小于60分的成绩，下标i到n-1是不小于60的成绩，i是不及格人数。,45,划分函数：int partition(int num,double a,double cut)double x;int i=0,j=num-1;while(i=cut)-j;if(i j)x=ai;ai=a j;aj=x;+i;-j;return i;,例4：m个猴子选大王，报n的出列。m=8,n=3,算法思路：,数组am:数组元素下标代表1m只猴子 数组元素内容代表下一只要报数的猴子,整数p:正在报数的猴子整数q:前一个报数的猴子整数t:p所指猴子所报的数,初值,q,p,t=0,const int m=8;n=3;int a=0,2,3,4,5,6,7,8,1;int q=m,p=am,t=0;,或for(i=1;im;i+)ai=i+1;am=1;q=m;p=am;t=0;,0,a0,a0不用,Josephus问题,q,p,t=0,报数开始，直到剩下一只猴子,do,while,下一个要报数的猴子将成为现在报数的猴子,(p!=aq);,确定现在报数的猴子，报数,p=aq;,t=t+1;,if(t%n)!=0),如果t不是n的倍数,yes：,no：,当前报数的猴子p成为前一个报数的猴子q,q=p;,else,当前猴子退出，调整报数次序当前报数猴子的内容ap赋给前一个报数猴子q的内容aq,aq=ap;,q,48,#includeint main()int m=8,n=3;int a=0,2,3,4,5,6,7,8,1;int q,p,t;q=m;t=0;dop=aq;t=t+1;if(t%n)!=0)q=p;elseaq=ap;while(p!=aq);printf(The king is%dthn,p);return 0;,如何用函数改写？,t=1,猴子选大王过程,初值:q=m=5;n=2t=0;,t=2,猴子选大王过程,m=5;n=2;,3,t=3,猴子选大王过程,m=5;n=2;,t=4,猴子选大王过程,m=5;n=2;,5,t=5,猴子选大王过程,m=5;n=2;,t=6,猴子选大王过程,m=5;n=2;,3,t=7,猴子选大王过程,m=5;n=2;,t=8,猴子选大王过程,m=5;n=2;,3,3,t=9,猴子选大王过程,m=5;n=2;,5,大王,58,作业,将一个二维数组行和列互换（矩阵转置），存到另一个二维数组中借助二维数组打印杨辉三角1112113311464115 10 1051找出二维矩阵的鞍点，如果没有鞍点打印相应信息鞍点：该元素在矩阵所在的行中最大，所在的列中最小写程序打印n阶(奇数)魔方阵程序自学节(P208)统计C程序里的关键字，并完成实现相关程序写函数实现猴子选大王程序，函数形式如下int king(int monkey,int n,int key);其中monkey为猴子数组，n为猴子总数，key为报的最大数函数返回最终获胜的猴子,n（奇数）阶幻由1到n2的自然数组成，每行、每列及两条对角线上之和均等于n(n2+1)/2。,三阶、五阶魔方阵,2,9,7,4,5,3,6,1,8,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,8,1,3,6,7,4,9,2,5,60,五阶幻方算法,从左下向右上放数先把1放在第一行的中间位置。下一个数放在上一个数的右上方若右上方已超出方阵的第一行，则下一个数放在该列的最后一行上。若右上方已超出方阵的最后一列，则下一个数放在该行的第一列上。若右上方已有数或右上方已超出方阵的第一行和最后一列，则下一个数放在上一个数的正下方。,61,Q&A!,