[课件资料]第5章数组

1,第5章数组,今年五.一节,某公司要庆祝一下。经理对公司的100个员工说：做一个游戏，让每个人把出生年+月+日得到一个数。例如：1996年12月10日=1996+12+10=2018。然后把这个数报上来。公司里有一笔钱要作为游戏的奖金，数额为M元。如果有人报上来的数字与2018相同，就把这笔钱发给这些人。如果只有一个人得奖，奖金都归这个人。如果有多于一个人得奖，则他们平分这笔钱。现在让我们来写一段程序算算都有哪些人得到了奖金？得到多少？,2,问题求解定义一个数组存放所有员工上报的数据定义一个数组存放获奖者的编号(幸运者数组)定义一个整数存放获奖者人数员工顺序报上数字，其相应的编号就是存放其数据的数组元素下标：0，1，2，报上数字与2018相等，则记录编号到幸运者数组中获奖者人数加1输出获奖者编号和获得的奖金数额,3,4,#include#defineLUCK_NUM2018#defineN100intmain()intpeopleN,luckyN,count=0,i;scanf(“%d”,问题引导,投票程序：学校要举行“十佳青年”选举活动，以表彰品学兼优的青年学生标兵。选举过程如下：先自荐报名并提交支撑材料，由选举委员会从中选出50名候选人，然后参加网上公开投票。每张选票最多只能填写10个对应的候选人编号，否则选票作废。投票结束后，选委会进行选票统计工作。由于选票众多，需要编写一个程序实现选票统计任务，不仅能够选出得票前十名的候选人，还能够查询每个候选人的票数,5,6,教学目标,掌握数组数据结构掌握数组的声明和存放，初始化和数组元素的引用方法掌握数组下标的使用方法了解声明和操作多维数组掌握字符串定义及使用方法初步理解排序和查找等基本算法,基本概念,数组定义：一组类型相同的数据对象构成的集合特点：存储在一个连续区域内，引用时用同一名字(序号不同)数组名：数据集合的名称数组元素：该集合的各数据元素。具有相同的数据类型,用集合的名称(数组名)和(元素的位置)索引(也叫下标)确定,7,5.1一维数组,8,数组的特征,数组元素的类型存储在数组元素中的值的数据类型(数组类型)数组的大小数组中能够存放多少个数组元素(数组长度),9,一维数组的定义,10,定义方式：数据类型数组名常量表达式；,合法标识符,表示元素个数,下标从0开始不能为变量,例inta6;,编译时分配连续内存,数组名表示内存首地址(address);它是地址常量,例intdata5;data5=10;/C语言对数组不作越界检查，使用时要注意,例inti=15;intdatai;(不能用变量定义数组维数),例#defineI4intdataI;(常量表达式包括常量、符号常量),一维数组的定义,一维数组的总字节数可按下式计算:总字节数sizeof(数组元素的数据类型)*数组长度其中sizeof是计算数据类型在存储空间中占用字节数的运算符。数组x所占用的存储字节数为：sizeof(double)*5,11,一维数组的定义,12,例5.1数组的声明语句及含义,一维数组的定义,例5.2将每张选票的投票数据存入数组相应的数组元素中。,13,#include#defineN50intmain()intaN;inti;for(i=0;iN;i+)scanf(%d,一维数组的注意事项,数组的长度是一个整型常量inta10;使用符号常量的形式定义数组的大小#defineN10intaN；数组的命名方式与其他变量一样，符合标识符的定义规范数组元素的起始下标为0,14,一维数组的存储结构,若有数组：inta10;,15,char型数组str的存储结构示意图charstr5=H,e,l,l,o;,一维数组的存储结构,16,一维数组元素的引用,数组必须先定义，后使用只能逐个引用数组元素，不能一次引用整个数组数组元素表示形式：数组名下标其中：下标可以是常量或整型表达式,17,例inta10;printf(“%d”,a);(-只能得到地址不能得到数组元素)必须for(j=0;j10;j+)printf(“%dn”,aj);(),数组元素的引用,一维数组元素的引用,18,在C语言中，使用下标，从数组的第一个元素开始，顺序处理数组的元素，使用循环语句实现对数组元素的遍历。,一维数组元素的引用,例5.3保存一个10以内的整数的所有约数。,19,#includeintmain()inta5,n;inti,j=0;printf(输入一个整数(10):);scanf(%d,程序运行结果：输入：输入一个整数(10):8输出：约数为：1248,数组的初始化,变量初始化:在声明简单变量时，初始化形式：inti=0；定义数组时直接初始化：各元素的值用逗号分隔，填充到数组元素所在的存储空间中。例如：intb4=1,2,3,4;,20,数组的初始化,错误的初始化：intd10;d=0,1,2,3,4,5,6,7,8,9;/*错误的赋值*/正确的初始化方法为：intd10=0,1,2,3,4,5,6,7,8,9;根据初值计算长度intd=0,1,2,3,4,5,6,7,8,9;,21,数组的初始化,部分初始化charletters26=A,B;,22,5.1.3数组的初始化,问题：若初始化了很多数组元素，如何确定数组的大小？,23,sizeof(d)/sizeof(d0),数组的初始化,例5.4:统计问题导引中的候选人选票情况。,24,#includeintmain()inta51=0;inti=0;intx10=0;intflag=1;while(flag)for(i=0;i10;i+)scanf(%d,for(i=1;i0)printf(%5d:%6dn,i,ai);return0;,利用数组解决问题,例5.5：在N个数中找最大值和最小值,25,26,#include#defineN10intmain()intxN,i,max,min;printf(输入N个整数:n);for(i=0;ixi)min=xi;printf(最大值是：%dn,max);printf(最小值是：%dn,min);return0;,例5.6:已知数组a中有n个互不相等的元素，数组b中有m(mn)个互不相等的元素，而数组c中包含那些在a中但不在b中的元素，编程产生数组c(产生新数组),12,-1,3,2,77,31,-6,2,-14,77,-1,76,a,12,3,31,-6,c,b,0,0,#include#defineN8#defineM5intmain()inti,j,k=0,aN,bM,cN;for(i=0;i=M)ck=ai;k+;for(i=0;ia1，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上(2)对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置(3)重复上述过程，共经过n-1趟冒泡排序后，排序结束,30,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,#include#defineN10intmain()intaN,i,j,t;for(i=0;iaj+1)t=aj;aj=aj+1;aj+1=t;printf(Thesortednumbers:n);for(i=0;iN;i+)printf(%d,ai);return0;,思考,如果要将n个数从大到小排序，流程和程序该如何设计？,32,利用数组解决问题,例：将一串整数，依次左移一个数，且原来的第1个数移到最后去,33,34,#include#defineN1000intmain()inti,t,n,aN;scanf(%d,思考,如果要依次右移，该如何修改程序？如果要依次移动k个位置，程序该如何设计？,35,例:输入m和k,将大于整数m且紧靠m的k个素数存入数组中并输出。例如,若输入17,5,则应输出19,23,29,31,37。,36,37,#include#defineN1000intmain()intm,k,i,j,n,xN;scanf(%d%d,向函数传递一维数组,分类：数组元素作为函数的参数printf(%6c,vi);scanf(“%lf”,数组名作为函数的参数,38,数组元素作为函数的参数,例5.8：写程序建立一个包含Fibonacci数列前20项的数组，然后从大到小输出这个数组中所有的数。,39,数组元素作为函数的参数,#include#defineMAX20intmain()longfibMAX;intn;fib0=1;fib1=1;for(n=2;n=0;-n),40,printf(%ld,fibn);putchar(MAX-n-1)%6=5?n:);return0;,数组元素作为函数的参数,数组名作为函数参数,数组元素作为参数传递，函数会接收到数组元素的一个副本，参数传递方法为值传递。数组名为函数的参数，函数操作与实参数组一致的数组元素。传地址：将数组在内存中的存储地址作为参数来传递,41,2数组参数,例5.6voidinit(inta,intn,intvalue)inti;for(i=0;in;i+)ai=value;,42,函数的参数是一个数组定义，而不是数组元素,43,#includevoidinit(inta,int,int);intmain()intb10,i;init(b,8,-1);for(i=0;i8;i+)printf(%d,bi);return0;,2数组参数,44,8,-1,-,数组名b,实参将数据传递给形参,数组a,例5.10：定义了一个函数sum，返回数组中所有元素值的和，函数不能改变数组元素。,45,intsum(inta,intn)inti,s=0;for(i=0;in;i+)s+=ai;returns;,例5.11:用数组表示A和B两个向量，定义函数实现两个向量的和(对应项相加)存入数组C中。,46,voidsum(inta,intb,intn,intc)inti;for(i=0;in;i+)ci=ai+bi;,intmain()intx10,y10,z10,i;for(i=0;i10;i+)scanf(%d,说明：数组名作为函数参数的语法为：元素类型数组名数组名后的不能省略数组作为参数时，实参中只须写实参数组名，不能再取其地址了。如：,47,charname10;scanf(%s,name);scanf(“%s”,/*错误！name已经是数组名*/,一维数组应用,例5.12:设计一个函数，在数组中查找指定的元素，并返回元素所在的位置。,48,intsearch(inta,intt,intn)inti,found=0,p;i=0;while(!found,一维数组应用,例5.13将一个数组中的元素首尾依次逆转并输出,49,#includevoidinv(intx,intn);intmain()inti,a10=8,6,7,1,0,9,3,5,4,2;printf(数组元素的原先顺序:n);for(i=0;i10;i+)printf(%d,ai);printf(n);inv(a,10);printf(逆序操作后的顺序:n);for(i=0;i10;i+)printf(%d,ai);printf(n);return0;,voidinv(intx,intn)intt,i,j,m=(n-1)/2;for(i=0;i=m;i+)j=n-1-i;t=xi;xi=xj;xj=t;,例5.14根据每个候选人的得票情况，依次输出前10为候选人,50,voidsort(intx,intn)inti,j,t;for(i=0;ixj)t=xj;xj=xj+1;xj+1=t;,51,#includevoidsort(int,int);intmain()inta51=0;inti=0,j=0;intx10=0;intflag=1;while(flag)for(i=0;i50)flag=0;break;axi+;,for(i=1;i0)printf(“%5d:%6dn”,i,ai);j+;sort(a,j);printf(排序后的数据n);for(i=0;i10;i+)printf(%dt,ai);printf(n);return0;,52,例5.15:期中考试后,某专业两个班分别对计算机课程的考试成绩进行了排名,现要按专业来进行排名,确定整个专业的排名情况。,一维数组应用,voidsort(intarr,intk)/*排序*/inttemp;inti,j;for(i=0;ik-1;i+)for(j=0;jk-i-1;j+)if(arrjarrj+1)temp=arrj;arrj=arrj+1;arrj+1=temp;,voidmerge(inta,intb,intc,intm,intn)/*合并*/inti=0,j=0,k=0;while(im,#include#defineM5#defineN4voidsort(intx,int);voidmerge(inta,intb,intc,int,int);intmain()intj;intaM=98,64,75,91,55;intbN=90,58,84,61;intcM+N;printf(a数组排序前:n);for(j=0;jM;j+)printf(%5d,aj);printf(n);printf(b数组排序前:n);for(j=0;jN;j+)printf(%5d,bj);printf(n);,sort(a,M);printf(a数组排序后:n);for(j=0;jM;j+)printf(%5d,aj);printf(n);sort(b,N);printf(b数组排序后:n);for(j=0;jN;j+)printf(%5d,bj);printf(n);merge(a,b,c,M,N);printf(合并a和b后:n);for(j=0;jM+N;j+)printf(%5d,cj);printf(n);return0;,程序运行结果：a数组排序前:9864759155b数组排序前:90588461a数组排序后:9891756455b数组排序后:90846158合并a和b后:989190847564615855,55,补充：校门外的树,题目描述：某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。（L=100000）输入要求:输入两个整数L(1=L=10000)和M(1=M=100)，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。输出要求:占一行,马路上剩余的树的数目输入样例:5003150300100200470471输出样例:298,57,5.2二维数组,在实际计算中，有时需要更复杂的结构来存储数据完成相应的计算任务，例如经常需要表示和处理一个班级中学生各门课程的成绩之和矩阵：矩阵是由行和列组成的数阵，它是一个二维的结构，是由若干行元素构成的数组，每一个行元素表示一个长度一致的一维数组。,58,5.2.1二维数组的声明,定义方式：数据类型数组名常量表达式常量表达式；,数组元素的存放顺序原因:内存是一维的二维数组：按行序优先多维数组：最右下标变化最快,例inta32;floatb25;inta3,4;(),inta32,对于doublea32;逻辑结构物理结构,59,5.2.1二维数组的声明,二维数组的初始化分行赋值floata34=1,2,3,4,5,6,7,8,9,10,11,12;顺序赋值floata34=1,2,3,4,5,6,7,8,9,10,11,12;部分赋值:其他为0floata34=1,9;全部赋值：一维长度可以省略floata3=1,0,3,4,0,0,0,8,0；,5.2.2二维数组的初始化,61,doubleE33=1.0,0.0,0.0,0.0,1.0,0.0,0.0,0.0,1.0;,inta33=1,2,3,4,5,6;,intb33=1,2,3,4,5,6;,5.2.2二维数组的初始化,例5.16：二维数组的初始化,62,printf(“nb:n”);for(i=0;i2;i+)for(j=0;j3;j+)printf(%5d,bij);printf(n);return0;,#includeintmain()inta23=1,2,3,4,5,6;intb23=1,2,3,4,5,6;inti,j;printf(a:n);for(i=0;i2;i+)for(j=0;j3;j+)printf(%5d,aij);printf(n);,5.2.3二维数组应用,例5.17实现矩阵的输入与输出,63,#include#defineM3#defineN4intmain()intaMN;inti,j;for(i=0;iM;i+)for(j=0;jN;j+)scanf(%d,程序运行结果输入：123434564567输出：123434564567,例5.18:编写函数实现两个矩阵的加和乘运算以及矩阵的转置运算,64,voidadd(intaMN,intbMN,intcMN)inti,j;for(i=0;iM;i+)for(j=0;jN;j+)cij=aij+bij;,65,voidtranspose(intaMN,inttNM)/转置inti,j;for(i=0;iM;i+)for(j=0;jN;j+)tji=aij;,voidproduct(intaMN,intbNM,intrMM)/相乘inti,j,k=0;for(i=0;iM;i+)for(j=0;jM;j+)rij=0;for(i=0;iM;i+)for(k=0;kM;k+)for(j=0;jN;j+)rik+=aij*bjk;,5.2.3二维数组应用,66,例5.19：将例5.14的投票结果排序后，输出前10位候选人序号，并查询指定候选人的得票数。分析：当候选人编号与得票数经过排序后仍然保持对应关系，需要将序号和票数整体构成候选人的信息，为此，选用二维数组中的每一行存储一个候选人的序号和票数，按票数排序时，序号也跟着变动，从而保证了排序序号和得票数的对应关系程序：p169,67,#includevoidsort(int2,int);intmain()intb512=0,0;inti=0,j=0,flag=1,number=0;intx10=0;while(flag)for(i=0;i10;i+)/输入选举人的选票信息scanf(%d,/票数,68,printf(排序前的数据n);for(i=1;i51;i+)/*输出得票数前10位的候选人编号*/printf(编号:%dt票数%dn,bi0,bi1);sort(b,50);printf(排序后的数据,前10名的候选人n);for(i=1;ij,ij,i+jN-1,思考：左拐角方阵,输出n阶左拐角方阵(1=n=20)，下图是n=5的输出形式。,71,ij,72,#include#defineN21intmain()inti,j,n,aNN;scanf(%d,5.3字符数组,字符数组就是存储字符数据的数组，比如单词，电话号码等等文本数据。C语言提供非常强大的处理字符序列或文本的功能。当然这些功能都是从存储字符型数据开始的。,73,5.3.1字符数组的定义,一维字符数组声明的形式：char数组名称长度;二维字符数组声明的形式：char数组名称行长度列宽度;例如，charline80;chartext1000;charname520;,74,常量表达式指定了长度，即可以存放字符数据的个数,理解为:定义了五名同学的姓名，每个姓名不超过20个字符。,5.3.2字符数组元素的引用,数组元素的赋值操作for(i=0;i80/*输出数组元素的值*/,75,5.3.3字符数组元素的初始化,逐个字符赋值,76,用字符串常量,逐个字符赋值,用字符串常量,5.3.3字符数组元素的初始化,charstr20=Nanjing;或charstr20=Nanjing;,77,5.3.3字符数组元素的初始化,78,例chardiamond5=,*,*,*,*,*,*,*,*;,5.3.4字符串的表示,字符串：双引号对()引起的部分。字符：指的是一个字符数据或转义字符，其常量的表示用单引号对()表示。字符串指的是一组有意义字符构成的数据。scanf(%f,79,用字符串常量,用字符串常量,字符串的存储,在C语言中，字符串的存储是利用字符数组来实现的。编译系统将字符串以字符数组的形式存储，即从内存空间中分配连续的若干存储单元，依次保存字符串中的字符，且每个字符占用一个字节。C语言规定：在字符串常量中所有字符之后，增加一个空字符0作为字符串的结束标志。,80,字符串的存储,81,例如:charstr=Nanjing;,注意：当字符串初始化缺省长度时，数组的长度必为字符串字符个数再加一个存放空字符的字节数。,字符串数组,字符串数组可以看成是一个二维字符数组，该数组中的每一行都是一个字符串。,82,#defineWEEK_DAY7#defineNAME_LEN10charweekdayWEEK_DAYNAME_LEN=Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday“;,5.3.5字符数组的输入与输出,字符数组的输入与输出用gets()函数输入，puts()函数输出用循环：与值型数组类似，字符数组也是从索引号为0的元素开始访问的。使用循环计数器作为数组的下标可以依次地遍历数组中的所有元素。用格式字符%s,83,例5.20:输入一行字符，统计其中有多少个单词,85,#includeintmain()charstring81;inti=0,num=0,word=0;charc;gets(string);for(i=0;(c=stringi)!=0;i+)if(c=)word=0;elseif(word=0)word=1;num+;printf(%dn,num);return0;,86,分析：一行文字中单词间的分隔符，我们一般认为是非字母字符数据。在给定问题中，我们首先需要找到单词，即寻找单词的开始和结束位置，并设计一个计数器记录单词的长度，通过比较找到最大值，并记录单词的起始位置，以便输出该单词。,补充例题：从标准输入设备(键盘)中输入一行文字，查找该行文字中最长的单词。,#include#includeintmain()charline100;intmaxlen=0,i=0,max=0,end=0;intwordflag=0;while(linei+=getchar()!=n,elsewordflag=0;if(maxmaxlen)max=maxlen;end=i;maxlen=0;for(i=end-max;iend;i+)printf(%c,linei);printf(n);return0;,例5.21：使用%s格式实现对字符串的输出与输入。要求用户输入一个代表课程名称的字符串、表示星期几的整数以及表示该课程上课节次串，输出该节次对应的课程表。,89,5.3.5字符数组的输入与输出,#include#defineWEEK_DAY7#defineNAME_LEN10charweekdayWEEK_DAYNAME_LEN=Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday;intmain()charcourse_name20;intdays;chartime6;inti;scanf(%s,course_name);scanf(%d,90,for(i=0;iWEEK_DAY;i+)printf(%10s,weekdayi);printf(n%s,time);for(i=0;i0)printf(str1字典序中排在str2的后面n);elseprintf(“str1字典序中排在str2的前面n”);,字符串和数值型数组的区别,100,5.3.7字符数组应用,例5.22：编写一个函数，完成字符串的复制操作voidstr_copy(chartarget,charsource)inti=0;while(sourcei!=0)targeti=sourcei;i+;targeti=0;,101,结束字符串,while(targeti=sourcei)!=0)i+;,while(targeti=sourcei)i+;,例5.23:假定输入的字符串中只包含字母和*号。请编写程序:将字符串中的前导*号全部删除，中间和后面的*号不删除。例如,若字符串中的内容为*A*BC*DEF*G*，删除后,字符串中的内容则应当是A*BC*DEF*G*。,102,103,#include#defineN80intmain()inti=0,k;charaN;gets(a);puts(a);while(ai=*)i+;k=i;for(i=0;ak!=0;i+,k+)ai=ak;ai=0;printf(%sn,a);return0;,思考：如何删除最右边的*或中间的*,补充：说反话,题目描述：Tom的一个朋友Jerry疯了，最近他老爱说反话，别人说什么他就倒着说一遍，真是个奇怪的人。那他到底说了什么呢？他说的话不超过1000个字符。输入要求：输入一个正整数n，表示说话的次数。下面n行表示说的话。输出要求：占n行，每行表示对应输入的反话样例输入：2IamspeakingACMer样例输出：gnikaepsmaireMCA,补充：字符串排序,问题描述:2014年在南京举行了第2届奥林匹克青年运动会,在开幕式的运动员出场顺序上,按照国家名字的英文字母顺序来出场,请编写一个计算机程序实现国家名字的排序(升序),东道主中国(China)在最后一个出场输入要求:输入参加国家数n(占一行)，下面n行是国家明(必须包含China)输出要求：按字母序输出国家名字，东道主国家名字最后输出。输入实例：5FranceRussiaJapanGermanyChina输出实例FranceGermanyJapanRussiaChina,5.4多维数组,5.4.1多维数组的定义类型说明符数组名第一维第二维第N维;如：inttable10450；数组table描述了学校各学院、年级和课程的选课人数。假设学校有10个学院，每个学院的在校生分成4个年级，每一级需要修50门课程，则可以描述这样一个数据结构，可以存储每一门课程的选课人数。,106,5.4多维数组,107,例5.21定义table数组中寻找和输出每个学院每门课程的选修人数。for(course=0;course50;course+)for(campuse=0;campuse10;compuse+)stu_sum=0;for(rank=0;rank4;rank+)stu_sum+=tablecampuscourserank;printf(Compus%dCourse:%d:StudentsNumber:%d,campus,course,stu_sum);,5.4.2多维数组的初始化,intb222=1,2,3,4,5,6,7,8;三维数组在内存中先按页、再按行、最后按列存放。多维数组在内存中排列顺序的规律是：第一维的下标变化最慢，最右边的下标变化最快。多维数组的数组元素的引用：数组名下标1下标2下标k。多维数组的数组元素可以在任何相同类型变量可以使用的位置引用。只是同样要注意不要越界。,108,intc234,5.6数组应用举例,109,补充：将一个一维数组循环向右移