C---第六章-数组PPT课件

第章数组,问题的引入,例：输入10个学生某门学科的成绩,求平均成绩。,1、当读入下一分数时，前一分数值是否还能找到？2、如何将低于平均成绩的分数打印出来？,在程序设计中存储单个数据时，需要根据数据的类型定义相应的变量来保存。如存储一个整数时需要定义一个整数变量来保存，存储一个实数时需要定义一个单精度或双精度变量来保存，存储含有多个成分的一个记录数据时，需要定义该类型的一个结构变量来保存。,若在程序设计中需要存储同一数据类型的、彼此相关的多个数据时，如存储数学上使用的一个数列或一个矩阵中的全部数据时，显然采用定义简单变量的方法是不行的，这就要求定义出能够同时存储多个值的变量，这种变量在程序设计中称为数组（相同类型的若干个元素所组成的有序集合）。,在实际应用中，一组相关的数据之间可能存在着一维关系，也可能存在着二维关系，等等。如下表：,概述,C+数据类型：基本类（简单类）字符型/整型/实型/枚举型构造类（组合类）数组/结构体/共用体指针类空类型（void）基本类型单个出现的变量，每个变量可以代表一个确定的数据（变量值），且具有一定属性。如staticintx,y;但变量间不存在确定的相互关系。构造类型由基本类型按一定规则组成。其中数组：由一组有序数据（数组元素）组成,这些数据保存在连续的内存空间，每个元素具有相同类型,因此占有相同大小的存储单元，具有统一数组名，用下标确定其顺序，但可以取各自值。,如staticinta5;其中：1.表示a是个数组，而不是一个简单变量a2.5表示该数组共有5个元素3.元素编号即下标从0开始，a0表示第一个元素，a4表示第5个元素（最后一个）一般化：假设m和n是常量，则数组am的第一个元素是a0,最后一个元素是am-1;数组amn的第一个元素是a00,最后一个元素是am-1n-1,以此类推。,数组的用处很多。简单例子：要读入某班全体50位同学某科学习成绩，然后进行简单处理（求平均成绩、最高分、最低分）,分析：若用简单变量，需50个不同变量名，如stu1,stu2,stu50，要用很多个cin命令。而用数组，可共用一个cin命令，并利用循环结构读取。,同变量一样，数组也必须先定义，后使用。定义内容：数组名：必须是合法标示符类型（存储属性/数据类型）大小（维数/元素个数）定义的一般形式：存储属性数据类型数组名常量表达式常量表达式常量表达式：常量或符号常量，其值必须为正，不能为变量！如：intn=5;intan;这样定义是错误的，如下为正确的：inta10,b54;charname8,ch23;staticfloatx8*2+1,table234;#defineNUM40intaNUM,bNUM+2;,数组定义,数组的初始化,可以在定义数组的同时赋初值，如：,可以省略第一维数组大小，如：inta=,b3=;,省略元素值，如：,inta5=0;intb32=0;(全部元素初始化为0),inta3=1,2,3,4,5,6,7;(思考第一维的大小?),静态/外部数组未初始化,默认初值是0（数值）或0（字符）.auto数组未初始化，初值为不可预料的数。,只能逐个引用数组元素,不能一次引用整个数组.引用数组元素要注意下标不要越界(编译程序不检查是否“越界”).引用示例:a23a2-12*3-1ax(x为整型表达式或变量)inta5;for(i=0;i5;i+)(注意下标不要越界)coutai;,数组元素的引用,用一维数组来处理Fibonicci数列的前20项。f1=1n=1f2=1n=2fn=fn-1+fn-2n3,voidmain()inti;intf20=1,1;/*f1、f2已知*/for(i=2;i20;i+)fi=fi-1+fi-2;for(i=0;i20;i+)if(i%5=0)coutendl;coutsetw(12)fi;,#include#include,【例】以下程序的运行结果是什么？#includevoidmain()inta3=1,2,3,4,5,6,0;couta11a21a31;,结果：500,123450600000,【例】显示如下图形:1000021000321004321054321,a55分析:a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34a40a41a42a43a44,voidmain()inta55=1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,i,j;for(i=0;i=4;i+)for(j=0;j=4;j+)coutaij;coutn;,例：读入某班全体50位同学某科学习成绩，然后进行简单处理（求平均成绩、最高分、最低分）,例:找出一个二维数组的鞍点,即该位置上的元素在该行上最大,在该列上最小,也可能没有鞍点.,【例】有一34矩阵，编程求其元素最大值并输出其行、列号。voidmain()inti,j,x,y,max;inta4=3,5,8,1,6,9,7,12,-6;max=a00;for(i=0;imax)max=aij;x=i;y=j;coutmaxisaxy=maxn;,358169712-6000,结果：maxisa13=12,用数组元素作函数实参此时可把数组元素看作普通变量(单向值传递).特点：主调函数中的实参数组元素(带下标)被调函数中的形参普通变量调用结果：形参值的变化对实参值无影响(二者分占不同内存）,数组作为函数参数,【例】voidmain()inta=1,2,3,4,5,6;staticintb6=2,3,0,4;inti;sum(int,int,int);for(i=0;i6;i+)sum(ai,bi,i);couta=ai,b=bi;voidsum(intx,inty,intz)x=z;y=z;,结果：a=1,b=2a=2,b=3a=3,b=0a=4,b=4a=5,b=0a=6,b=0,用数组名作函数实参若inta6;则数组名a表示数组的起始地址.此时,是把实参数组的起始地址“传给”形参数组.本质：对应的数组元素(不是形参与实参)共享同一内存单元(所谓“双向的地址传送”).特点：主调函数中的实参数组名(不带下标)被调函数中的形参数组名或数组定义式调用结果：两数组同下标者为同值.,数组作为函数参数,【例】voidmain()inta=1,2,3,4,5,6;staticintb6=2,3,0,4;inti;sum(int,int,int);for(i=0;i6;i+)sum(a,b,i);couta=ai,b=c;注意：此法输入的字符串以空格或回车结束,即输入的字符串不可能包括空格！如输入：abcdef回车后,c对应的字符串为“abc”,而不是“abcdef”.另外此法输入的字符串串长有可能比数组长度要长，应引起注意！要想输入带空格的字符串,可使用函数cin.get或者cin.getline.此例对应cin.get(c,6,n)或者cin.getline(c,6,n),字符数组charc5;的输出法一：inti;for(i=0;i5;i+)coutci;法二：coutc;输出一个字符串，直到遇到0为止，因此输出的字符串有可能和数组不一样。,【例】比较以下字符数组长度是否相同：chara=”ABCD”;charb=“ABCD”;charc=A,B,C,D;,(5),(5),(4),【例】下列程序段的运行结果是：chara5=a,b,0,d,0;coutwordi;coutwordi-2;运行时，输入：12345（回车）abcdef（回车）ABCDEFG（回车）,结果：abcdef,将一个字符串直接给一个字符数组只能够出现在初始化中,不能够出现在赋值语句中！也不能把一个字符数组直接赋值给另一个字符数组，如：charc5,d5;c=“abc”;d=c;是错误的！要使用string.h的函数strcpy(to字符数组1,from字符数组2)如:strcpy(c,”abc”);strcpy(d,c);,字符串处理函数,【例】以下程序的输出结果是。#include“string.h”voidmain()chars10,sp=”HELLO”;strcpy(s,sp);s0=h;s6=!;couts;,hELLO,strcat()字符串连接函数形式：strcat(目的字符数组，源字符串)；作用：将源字符串连接到目的字符数组后面。函数返回值：目的字符数组的地址。注意：目的字符数组要定义得足够大。,【例】以下程序的输出结果是_。#includestring.hvoidmain()chara=abcde;charb=12345;strcat(b,a);couta,b;,abcde,12345abcde,【例】以下程序的输出结果是_。#includestring.hvoidmain()chara80=”AB”,b80=”LMNP”;inti=0;strcat(a,b);while(ai+!=0)bi=ai;cout字符串2；strcmp函数返回值0时,字符串1str;if(strcmp(temp,str)0)strcpy(temp,str);cout0,i=2,Control,GAME,0,GAME,i=3,GAME,PAGE,0,PAGE,求字符串实际长度可使用string.h的函数strlen(字符数组),它不包括字符串的结束符0.如:chara10=“abcde”;则strlen(a)=5,sizeof(a)=10,【例】以下程序段的运行结果是什么？chara=”tr0willn”;coutsizeof(a)tstrlen(a);,结果：103,数组元素的排序,一输入10个数，用“冒泡法”对10个数排序（由小到大）。“冒泡法”算法：以六个数9、8、5、4、2、0为例。第1趟比较,第一次：8、9、5、4、2、0,第二次：8、5、9、4、2、0,第三次：8、5、4、9、2、0,第四次：8、5、4、2、9、0,第五次：8、5、4、2、0、9,第1趟比较产生第一个最大数：9,对剩下的五个数：8、5、4、2、0进行第2趟比较,第一次：5、8、4、2、0,第二次：5、4、8、2、0,第三次：5、4、2、8、0,第四次：5、4、2、0、8,第2趟比较产生第二个最大数：8依此类推，便可实现排序。,第1趟比较后，剩5个数未排好序；两两比较5次第2趟比较后，剩4个数未排好序；两两比较4次第3趟比较后，剩3个数未排好序；两两比较3次第4趟比较后，剩2个数未排好序；两两比较2次第5趟比较后，全部排好序；两两比较1次,算法结论：对于n个数的排序，需进行n-1趟比较，第i趟比较需进行n-i次两两比较。,for(i=1;iaj+1)t=aj;aj=aj+1;aj+1=t;,改进后的算法for(i=1;iaj+1)t=aj;aj=aj+1;aj+1=t;flag=1;if(flag=0)break;,二输入10个数，用“选择法”对10个数排序（由小到大）。“选择法”算法：以六个数9、8、5、4、2、0为例。第1趟比较,第一次：8、9、5、4、2、0,第二次：5、9、8、4、2、0,第三次：4、9、8、5、2、0,第四次：2、9、8、5、4、0,第五次：0、9、8、5、4、2,第1趟比较产生第一个最小数：0,对剩下的五个数：9、8、5、4、2进行第2趟比较,第一次：8、9、5、4、2,第二次：5、9、8、4、2,第三次：4、9、8、5、2,第四次：2、9、8、5、4,第2趟比较产生第二个最小数：2依此类推，便可实现排序。,算法总结：对于n个数的排序，需进行n-1趟比较，第i趟比较时要将第i+1个开始的元素依次与第i个元素进行两两比较，后者小于前者就进行交换。,for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ajai)t=ai;ai=aj;aj=t;,for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(ajak)k=j;if(k!=i)t=ai;ai=ak;ak=t;,改进后的选择排序算法,三插入排序基本思想：（假定从小到大排序）依次从后面拿一个数和前面已经排好序的数进行比较，比较的过程是从已经排好序的数中最后一个数开始比较，如果比这个数，继续往前面比较，直到找到比它大的数，然后就放在它的后面，如果一直没有找到，肯定这个数已经比较到了第一个数，那就放到第一个数的前面。那么一般情况下，对于采用插入排序法去排序的一组数，可以先选取第一个数做为已经排好序的一组数。然后把第二个放到正确位置,voidmain()inti,j,t,a=12,11,2,3,6,67,89,0,1,3;for(i=1;i=0;j-)if(taj)aj+1=aj;elsebreak;aj+1=t;for(i=0;i10;i+)coutait;,四合并排序基本思想：将a、b两个数组看成两个队列，比较队首的两个元素，将较小者放入c队列尾部，如果队首的两个元素相等，则先选择a队列首部元素加入c队列尾部。循环执行以上过程，直到a