C语言教学课件：13-1_数组的概念、定义和使用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,课程内容,第一章 程序设计和,C,语言,第二章 数据对象与计算,第三章 变量、函数和控制结构,第四章 基本程序设计技术,第五章,C,程序结构（函数）,第六章 数组,第七章 指针,第八章 文件和输入输出,第九章 结构和其它数据机制,第十章 程序开发技术,第十一章 标准库,2,第十三部分 数组,3,语言需要提供一套,数据机制,，描述与数据有关的问题：,必须足够丰富，以满足需要；,不能过庞杂，臃肿难用；,也不能太低级，使描述过于烦琐。,高级语言的,数据机制,：,把数据分为类型，每个类型是一个数据集。,提供一组基本数据类型；确定其书写方式；为各类型提供一组基本操作。,提供一组由简单数据类型或对象构造复合数据类型或对象的机制。,组合的数据对象称为,复合数据对象,。由所有“同类的”复合对象形成的类型称为,复合数据类型,，组成部分称为,成分,/,成员,/,元素,。,4,基本类型,构造类型,指针类型,空类型,void,定义类型,typedef,数值类型,字符类型,char,8,位,枚举类型,enum,整 型,浮点型,单精度型,float,32,位,双精度型,double,64,位,短整型,short,16,位,长整型,long,32,位,整型,int,16,位,数组,结构体,struct,共用体,union,C,数据类型,由基本类型数据按一定规则组成的，,也称为“导出类型”,数组,5,问题,:,输入学生的学号,成绩,计算平均成绩,计算每个学生的成绩与平均成绩的差,差,=10,成绩等级,A,0=,差,10,成绩等级,B,其它 成绩等级,C,设,:,学号,double n1,n2,n3,n4,n30;,成绩,double s1,s2,s3,s4,s30;,能否,:,一个变量名对应多个连续的存储单元,:,数组,数组,是程序中最常用的结构数据类型，用来描述由,固定数目,的,同一类型,的元素组成的数据结构,6,数组的概念、定义和使用,数组程序实例,数组作为函数参数,字符数组和字符串,两维和多维数组,编程实例,主要内容,7,1,数组的概念、定义和使用,数组（,array,）,:,是多个,同类型,数据对象的组合。,一个数组汇集了多个数据项，,数组元素,。,可从数组出发处理各元素，以统一方式处理一批,/,所有元素，是,数组,和,一组独立变量,的主要区别。,为此需要：,数组描述,，数组变量定义，初值化,数组使用,，包括通过数组变量使用其元素,数组实现,，数组的存储方式,8,数组变量定义,定义数组变量（,定义数组,）时需说明：,数组元素类型,数组（变量）名,数组（变量）的元素个数（也称数组,大小,或,长度,）,定义方式：,数据类型 数组名,常量表达式,；,例，定义两个数组：,int a10,;,double a1100,;,数组定义可以与其他变量定义写在一起，如：,int a216,n,a325,m,;,方括号内整型表达式说明元素个数，表达式应能静态确定值，可用,字面量,或,枚举常量,9,可定义外部数组,和局部数组,，包括局部静态数组（用,static,）,作用域与存在期与简单变量相同。,数组的外部说明不必描述数组大小。例：,extern int a;,extern double a1;,下面函数里数组定义不合法：,void f(int m,int,n,),int bn,;/*,非法，编译时无法确定大小*,/,.,新,C99,标准支持这种定义，满足,C99,的编译器很少,10,基本操作是元素访问。元素顺序编号，首元素序号,0,，其余顺序编号。,n,元数组元素编号是,0,到,n-1,。定义：,int b100;,元素编号为,0,、,1,、,2,、,、,99,。称为,下标,或,指标,。,元素访问通过,运算符，优先级最高，运算对象是数组名和括号里表示下标的表达式。,表达式、语句里的,b3,称为,下标表达式,或,带下标的变量,。,例：有上面定义后，可写：,b0=1;b1=1;,b2=b0+b1;,b3=b1+b2;,数组的使用,11,数组的真正意义,在于能以,统一方式描述对一组数据,的处理。,下标表达式,可用一般的整型表达式。如：,bi=bi-1+bi-2;,访问哪个元素由,i,值确定,。同一语句可访问不同元素，可用在循环里访问一批元素。,for(i=0;i 100;+i),bi+=a1i*a2i,;,/*,假设数组都有定义*,/,循环中涉及到,300,个基本数据对象。,12,#include,int main(),long fib30;int n;,fib0=1;fib1=1;,for(n=2;n 30;+n),fibn=fibn-1+fibn-2;,for(n=0;n 30;+n),printf(%d,fibn);,putchar(,n%6=5?n:,);,/*6,个数输出一行*,/,return 0;,例：写程序创建包含前,30,个,Fibonacci,数的数组，然后打印数组中所有的数。,13,对数组的多个或全部元素操作，常用,for,语句。,令,循环变量,遍历数组下标：,for(n=0;n,数组长度,;+n).,问题：,fib,是,30,个元素的数组，假设程序里写：,for(n=2;n=30;+n),fibn=fibn-1+fibn-2;,循环中试图访问,fib30,，实际无此元素。,用超范围的下标访问称为,越界访问,，是数组使用中最常见的错误。,下标值超范围是运行中的问题,。,C,不检查数组元素访问的合法性，运行中出现越界不会报错。,超范围访问是严重错误，后果无法预料,。,14,数组的负数下标,C,语言只规定数组的下标必须是整型数据，因此负数下标也合法，但是语义上是否正确，取决于用负数下标访问时是否越界。,a-1,a-2,a0,a2,a3,a1,内存空间,例,给定数组、函数及其调用,int a10;,int func(int arr,int n);,func(,则在,func,内部，对,arr-2,和,arr-1,的访问分别对应于,a0,和,a1,，是合法的，并没有产生实际的越界，在,arr-3,就不一定能保证语义正确性了,。,15,16,数组的实现,数组占据一片连续存储区，元素顺序排列，,0,号元素在最前面，各元素占相同空间。如有：,int a8;,a,的存储恰好能存放,8,个整型数据，情况如图：,a,至少相当于,8,个,int,变量，,a0,a7,可以看作,“变量名”,。保证元素排在一起，能以统一方式使用。,数组名表示内存首地址，,是,地址常量,编译时分配连续内存,内存字节数,=,数组元素个数*,sizeof(,元素数据类型,),17,在一些系统里越界访问可能导致动态错，系统强行终止出错的程序。越界可能破坏本程序的数据,/,程序本身,/,其他软件，甚至 是整个系统。,编程者要保证数组下标值的合法性，保证不越界。,数组初始化,定义数组时可直接初始化。外部、局部静态或自动数组都可在定义时进行初始化。,方法一：定义时直接初始化,int b4=1,1,2,3;,double ax6=1.3,2.24,5.11,8.37,6.5;,初值表达式必须是常量表达式。,外部和静态数组在程序开始执行前建立并初始化，局部自动数组在程序执行进入相应函数或复合语句体时建立和初始化,18,这种写法只能用于数组初始化，,不能用在语句里,。,若定义时未初始化，外部和局部静态数组的元素自动初始化为,0,；自动数组处在不明确的状态。,方法二：只为部分元素提供初值，其余元素将自动置,0,。初始化表元素个数不得超过数组元素个数。例：,int b14=1,2;,b12,、,b13,将给初值,0,。,方法三：若给了所有元素的初值，可以不写数组大小而只写方括号,，元素个数由初值个数确定。例：,int fib=1,1,2,3,5,8,13,21,34,55;,这种写法能减少维护负担，有利于程序修改。,在语句中对数据元素赋值的方法？,19,说明：,数组必须,先定义,，,后使用,只能逐个引用数组元素，不能一次引用整个数组,数组元素表示形式：,数组名,下标,其中：下标可以是常量或整型表达式,/,顺序输入输出数组元素,#include,void main(),int i,a10;,for(i=0;i 10;i+),ai=i;,for(i=0;i=9;i+),printf(“%4d”,ai);,/,将数组元素逆序输出,#include,void main(),int i,a10;,for(i=0;i 10;i+),ai=i;,for(i=9;i=0;i-),printf(“%4d”,ai);,例一维数组的输入与输出。,20,数组的概念、定义和使用,数组程序实例,数组作为函数参数,字符数组和字符串,两维和多维数组,编程实例,主要内容,21,2,数组处理程序实例,例：从字符到下标（整数）,写程序统计由标准输入得到的文件中数字字符的个数。,可定义,10,个计数变量，用,if,或,switch,区分情况，遇数字字符（,isdigit,）时对应计数器加,1,。,不需要数组。,将字符看作整数可得到另一解法。常见字符集里数字顺序排列，,ASCII,字符集里,0,到,9,的编码是,48,到,57,。,利用这个事实，用,10,个元素的计数器数组可以更方便地完成对数字出现的统计。,22,int cs10;,用,cs0,记录,0,出现次数，余类推。若,c,是数字，对应计数器加,1,可以写成：,+csc-0;/*,c-0,正是对应计数器的下标,*,/,#include,#include,int cs10=0,0,0,0,0,0,0,0,0,0;,int main(),int,c,i;,while(c=getchar()!=EOF),if(isdigit(c),+csc-0,;,for(i=0;i 10;+i),printf(Digit%d:%dn,i,csi);,return 0;,23,例：筛法求素数,筛法是求素数的著名方法：,用空间换时间，,1,亿以内的素数只需要十几秒的时间,(,如不考虑输出,),具体算法：取,2,开始的整数序列：,令,n,等于,2,，它是素数；,划掉序列中所有,n,的倍数；,令,n,等于下一未划元素（它是素数），回到步骤,2,。,用数组表示整数序列，以元素下标表示对应整数。,数组,an,，,an0,代表,0,，,ani,代表,i,。,每个数只需表示划掉或未划掉，,用,0/1,表示。,开始时元素置,1,（,即假设所有元素都是素数,），而后不断将元素置,0,，直到确定了给定范围里的所有素数。,24,假设,NUM,是给定范围：,/*,建数组,an,，元素初始化,1,，,将,an0,和,an1,置,0,（它们不是素数）*,/,for(int i=2;i,值不大于某个数,;+i),if(ani=1)/i,是素数,for(int j=i*2;j NUM;j+=i),anj=0;/,*,i,的倍数都不是素数*,/,外层循环何时结束？可用,NUM,作为界限。,检验一个数是不是素数，只要看比它的,平方根,小的素数是不是能整除它,，因此只要,i,超过,NUM,的平方根，就可以划掉到既定,范围内,的所有合数。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25,1,不算,遍历一遍，划掉,2,的倍数：得,2 3 5 7 9 11 13 15 17 19 21 23 25,遍历一遍，划掉,3,的倍数：得,2 3 5 7 11 13 17 19 23 25,遍历一遍，划掉,5,的倍数：得,2 3 5 7 11 13 17 19 23,25,#include,enum,NUM=200;,int an,NUM+1,;,int main(,void,),int i,j;,an0=an1=0;/*,建立初始向量,*,/,for(i=2;i=NUM;+i)ani=1;,for(i=2;,i,*i,=NUM,;+i),if(ani=1),for(j=i*2;j=NUM;j+=i),anj=0;,for(i=2,j=0;i=NUM;+i),if(ani!=0)printf(%d,i);,putchar(n);,return 0;,26,例：成绩分类,写程序输入一批学生成绩（,200,）。先输出不及格成绩，再输出及格成绩，最后输出不及格和及格的人数。,无法在输入过程中完成,(,除非输入两遍,),。用数组记录学生成绩，输入记入数组，而后输出，可避免重复输入,数据装入数组后有许多可能处理方法。,最简单的是两次扫描数组，第一次输出不及格成绩，第二次输出及格的成绩。,统计工作可在某次扫描中完成（也可在输入中完成），两部分人数之和就是总人数，统计一部分就够了。,27,enum NUM=200;,const,double PASS=60.0;,double scoresNUM;,int main(),int i,n=0,fail;,while(,nNUM,&scanf(%lf,&scoresn)=1),+n;,/*,输入时需要判断不越界,*,/,for(fail=0,i=0;i n;+i),if(scoresi PASS),printf(%fn,scoresi);,+fail;,for(i=0;i=PASS),printf(%fn,scoresi);,printf(Fail:%dnPass:%dn,fail,n-fail);,return 0;,28,例：多项式求值,设数组,p,中存放下列多项式的系数，其中,pi,存放,写程序求,p,表示的多项式在指定点的值。,方法,1,：求出各项值累加。假设指定点值存于,x,：,for(sum=0.0,n=0;n TERMS;+n),for(t=pn,i=1;i=n;+i)t*=x;,sum+=t;,循环体内可以改写为（先算,x,的幂）：,for(t=1.0,i=1;i=n;+i),t*=x;,sum+=t*pn;,可发现有大量重复计算。,29,通过保存前次的,t,值：,for(sum=0.0,t=1.0,n=0;n=0;-n),sum=sum*x+pn;,从计算量上比较它们：需要多少次加法，多少次乘法,。,30,定义数组的问题,如果数组表示的是全局数据集合,，需要在多个函数里使用，那么可考虑定义为外部数组。,大的数组应定义为外部,，以免占大量运行栈空间。一般系统不允许在函数内定义特别大的数组。,若数组保存着递归定义函数的局部数据,，就必须定义为自动数组。因为递归调用时需要数组的多份拷贝。,其他情况可以根据需要自由选择。,31,数组的概念、定义和使用,数组程序实例,数组作为函数参数,字符数组和字符串,两维和多维数组,编程实例,主要内容,32,3,数组作为函数参数,数组可以作为函数的参数，但是在向函数传递数组时通常有两种方法：即：,“,地址,”,的传递,“,值,”,的传递,33,方法一：,用数组名作为实际参数，给函数传递数组的地址，通过这个地址就可以访问到数组的元素了,双向传递,。,#include,#define N 20,void f(int,b,int n,int m),int i;,for(i=m;i=n;i-),bi+1=bi,;,void main(),int i,aN=1,2,3,4,5,6,7,8,9,10;,f(,a,2,9);,for(i=0;i y?x:y);,void main(),int a10,j,max;,for(j=0;j=9;j+),scanf(“%d”,max=a0;,for(j=1;j=9;j+),max=fmax(,max,aj,);,printf(“n,最大值为,：,%8dn”,max);,35,对函数参数的小结：,“,值”传递,形参和实参都是普通变量,实参是数组元素，形参是普通变量,“,地址”传递：形参、实参都是数组名，完成,双向传递,。,完成,单向传递,36,假设有多个数组都需要求平均值,?,解决方法：,定义以数组为参数的函数,。,以数组为参数，不同调用可以完成对不同数组的计算。,定义以,double,类型的数组为参数求元素平均值的函数，就可解决所有,double,数组的平均值问题,设常量,LEN,是被处理数组的长度。,double avg0(,double,a),double x=0.0;int i;,for(i=0;iLEN;+i)x+=ai;,return x/LEN;,/*,注意：数组形参不需要写数组大小,*,/,37,若数组,a1,长,LEN,，可用：,x=avg0(a1);,avg0,有,一定,通用性，若数组,a2,长度也是,LEN,：,y=avg0(a2);,用符号常量指定数组大小可解决许多问题。,缺点,：若数组长度不是,LEN,，就不能用,avg0,处理。,可见：,avg0,不够通用,，只能正确处理长为,LEN,的数组。,参数,是使函数能处理一类问题的基本机制。,为提高数组处理函数的通用性，定义时应引进长度参数，使函数能处理任何,给定长度,的数组。,38,改造后的函数：,double avg(,int len,double a),double x=0.0;,int i;,for(i=0;i len;+i)x+=ai;,return x/len;,对调用提出的新要求,：必须正确提供数组长度。,应用实例：,int main(),double b1=1.2,2.43,1.74,b2=6.5,9.2,8.6,4.5,0.3;,printf(%f,%fn,avg(,3,b1),avg(,5,b2);,return 0;,39,长度参数提高了函数的通用性。,但使用时,必须,关注越界问题。,avg(5,b1),引起数组越界（,b1,有,3,个元素）。,长度实参可小于数组大小，,avg(3,b2),求,b2,前,3,个元素的平均值。,可将数组前段当作数组使用。,C,语言函数参数表中的数组参数,其实是指针参数,。,将参数写成数组的形式只是为了提示调用者：,传给函数的东西应该是一个段给定长度的元素类型相同的连续存储空间,。,但是，函数的指针参数中,并不仅仅是针对数组的,。,40,函数与数组数据修改,回忆参数机制,函数参数都是,值参数,形参是函数体的内部变量,。,调用时将实参的值拷贝送给形参。,数组作为函数的参数时，在调用的过程同样完全遵循这个机制。,以,数组形式定义函数的某个参数,等于定义了一个,指针参数,，这个参数将用于存放某个空间的地址，如数组的首地址。,收到地址的函数知道了存储空间的地址，即可以,方便修改这段存储空间中的内容,。,如果传来的参数是某个数组的首地址，在函数内就可以通过这个首地址修改数组每个元素的值,41,例,设有函数定义,void func(int narr,int nLen),for(i=0;i nLen;i+),narri+;,return;,设有调用代码,int b5=1,2,3,4,5;,int*p=,func(p,4);,实际效果,:,将数组,b,中的每个元素都加了,1,真正的原因：,C,并不把,narr,这个参数看成是一个真正的数组，,narr,实际上被编译器当成了一个指针参数。,指针参数中能存放的是某种类型存储空间的地址。,0 x0012ff58,narr,5,nLen,该操作实际为指针操作的数组写法,42,例：将,a,数组的内容按颠倒的次序重放，在操作时，只能借助一个临时存储单元而不能另外开辟数组。,互换,偶数个元素,不动,奇数个元素,互换,43,void rev(int n,int a),int x,i,m=n/2;,for(i=0;i m;+i),x=ai;,ai=an-i-1;,an-i-1=x;,自己添加主程序,另一写法：,for(i=0,j=n-1;i j;+i,-j),x=ai;,ai=aj;,aj=x;,