C++课件第6章 数组

第6章数组本章主要介绍数组的定义及应用，包括一维数组、多维数组和字符数组以及字符串处理函数等。VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳2数组C++除提供基本数据类型外，还提供了构造数据类型，如数组、结构体、共同体和类。具有相同类型的若干个元素组成的有序集合称为数组。如：intscore[30];数组拥有一个公共的名字，称之为数组名。一个数组由若干个元素组成，数组内的每个元素的类型必须相同，它们在内存中占据的地址空间也是连续的。VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳3一维数组的定义一维数组定义的一般形式为：[存储类别]数据类型数组名[常量表达式]如：autointa[10];或staticinta[10];则定义了一个包含十个元素的数组，分别为a[0]，a[1]，a[2]，……a[9]。C++语言中数组的下标从0开始；[]为下标运算符；“常量表达式”中不能包含变量；数组名的命名必须符合标识符的命名规则。VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳4一维数组的定义对于数组定义应注意以下几点：相同作用域内，数组名不能与其它变量名相同，例如：voidmain(){inta;floata[10];……}//是错误的。方括号中的常量表达式必须有确定的正整数值(不能为变量或实数)，可以是符号常量。例如：#defineFD5voidmain(){inta[3+2],b[7+FD];……}//是合法的。但是下述说明方式是错误的：voidmain(){intn=5;inta[n],b[5.5];……}//是错误的。允许在同一个类型说明中，说明多个数组和多个变量。例如：inta,b,c,d,k1[10],k2[20];VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳5一维数组的初始化1、一维数组的初始化：指在定义数组的同时，给数组元素赋值。如：inta[5]={1,2,3,4,5};2、如果对全部数组元素赋初值，可以不指定数组长度。例如：inta[]={1,2,3,4,5};和inta[5]={1,2,3,4,5};相同3、可以只给部分数组元素赋初值。例如：inta[10]={0,1,2,3,4};表示只给a[0]～a[4]5个元素赋值，而后5个元素自动赋0值。4、当将数组定义为全局数组或静态数组时，如不给数组赋初值，则元素的值全部为0。5、只能给元素逐个赋值，不能给数组整体赋值。例如：给数组元素全部赋1,只能写为:inta[5]={1,1,1,1,1};而不能写为：inta[5]=1;VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳6一维数组的使用只能逐个使用数组元素，而不能一次使用整个数组。例如：输出有10个元素的数组必须使用循环语句for(i=0;i10;i++)couta[i];而不能用一个语句输出整个数组，下面的写法是错误的；couta;下面的程序也是错误的：inta[5],b[5]={1,2,3,4,5};a=b;同样，数组元素的赋值也只能逐个赋值。inta[3];a[0]=1;a[1]=2;a[2]=3;或for(inti=0;i3;i++)a[i]=i+1;VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳7一维数组应用实例(选择法排序)VisualC++程序设计基础例：把一组无序的数据(如15,8,4,13,6,1)放在数组a[0]~a[5]中，要求将其按升序排序(结果应为1,4,6,8,13,15)a[0]a[1]a[2]a[3]a[4]a[5]初始状态15841361第1次81541361第2次41581361a[0]a[1],交换a[0]a[2],交换第3次41581361a[0]a[3],不交换第4次41581361a[0]a[4],不交换第5次11581364a[0]a[5],交换2020/9/20版权所有©南京理工大学王芳8一维数组应用实例(选择法排序)VisualC++程序设计基础经过第1轮循环后，找到了最小的数1，并将其放到了a[0]中，下面将找次小的数，并将其放到a[1]中。a[0]a[1]a[2]a[3]a[4]a[5]第1轮后11581364第1次18151364第2次18151364a[1]a[2],交换a[1]a[3],不交换第3次16151384a[1]a[4],交换第4次14151386a[1]a[5],交换第1轮比较结束后的状态：第2轮开始：2020/9/20版权所有©南京理工大学王芳9一维数组应用实例(选择法排序)VisualC++程序设计基础经过第2轮循环后，找到了次小的数4，并将其放到了a[1]中，依此类推，经过5轮后即可完成排序工作。a[0]a[1]a[2]a[3]a[4]a[5]14681315第5轮后最终结果为：for(i=0;i5;i++)for(j=i+1;j6;j++)if(a[i]a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}完成该选择法排序的程序段为：2020/9/20版权所有©南京理工大学王芳10一维数组应用实例(选择法排序)VisualC++程序设计基础另一种快速的选择法排序算法为：a[0]a[1]a[2]a[3]a[4]a[5]初始状态15841361第1轮循环1841361514813615146138151468131514681315第2轮循环第3轮循环第4轮循环第5轮循环将a[0]和最小的数a[5]交换将a[1]和次小的数a[2]交换下一步a[2]和a[4]交换下一步a[3]和a[4]交换2020/9/20版权所有©南京理工大学王芳11一维数组应用实例(选择法排序)在a[0]至a[n-1]中找出一个最小值，假定是a[t]，把a[t]与a[0]交换，使得a[0]最小；再在a[1]至a[n-1]中找出一个最小值a[t]，把a[t]与a[1]交换，使得a[1]最小依次类推，直到从a[n-2]和a[n-1]中找出最小值。VisualC++程序设计基础一般情况下，对于N个数据的排序问题，该算法可描述为：for(i=0;iN-1;i++){t=i;for(j=i+1;jN;j++)if(a[t]a[j])t=j;if(t!=i){temp=a[i];a[i]=a[t];a[t]=temp;}}2020/9/20版权所有©南京理工大学王芳12例：把一列无序数据(如15841361)放在数组a[0]~a[5]中，要求按升序排列。一维数组应用实例(冒泡法排序)VisualC++程序设计基础a[0]a[1]a[2]a[3]a[4]a[5]15841361初始状态第1次：a[0]a[1]，交换a[0]和a[1]81541361第2次：a[1]a[2]，交换a[1]和a[2]84151361第3次：a[2]a[3]，交换a[2]和a[3]84131561第4次：a[3]a[4]，交换a[3]和a[4]84136151第5次：a[4]a[5]，交换a[4]和a[5]84136115这是第1轮排序后的结果，最大的数沉到了最下面，小数则向上移动2020/9/20版权所有©南京理工大学王芳13经过第1轮5次比较，找出了最大的数15并将其保存到a[5]中，其它数上浮。在第2轮比较中，将a[0]~a[4]按前述方法进行4次交换后，可得到第2个比较大的数13，存放于a[4]中。依此类推，可得到排序结果。一维数组应用实例(冒泡法排序)VisualC++程序设计基础a[0]a[1]a[2]a[3]a[4]a[5]84136115第1轮第2轮48611315第3轮46181315第4轮4168131514681315第5轮2020/9/20版权所有©南京理工大学王芳14一般的，对于N个数据的冒泡法排序，该算法可描述为：一维数组应用实例(冒泡法排序)VisualC++程序设计基础a[0]与a[1]比较,若a[0]a[1],两数交换；然后a[1]与a[2]比较，重复上述步骤。结果大数沉底，小数上升，a[n-1]中为最大的数。a[0]到a[n-2]，两两比较。依次类推，直到从a[0]和a[1]中找出最大值沉底。for(i=0;iN-1;i++)for(j=0;jN-i-1;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}2020/9/20版权所有©南京理工大学王芳15二维数组的定义格式：类型说明数组名[常量表达式1][常量表达式1]例如：inta[2][3];说明：定义了一个2行3列的二维数组，数组元素个数为(常量表达式1)*(常量表达式2)的值，即共有6个整型数据，在内存开辟了连续24个字节存储单元。数组每一维的下标都从0开始。对于二维数组，逻辑上可以把它看成是一个表格结构，第一个下标代表“行号”，第二个下标代表列号。VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳16二维数组的定义在C++中，二维数组元素在内存中的存放方式为按行存放，称为行主顺序。C++语言把二维数组看成是一种特殊的一维数组，即由a[0]，a[1]两个元素组成，而a[0]、a[1]又是由一维数组组成。例如上例中数据在内存中的存放顺序为：a：a[0]：a[1]：必须强调的是，a[0],a[1]不能当作下标变量使用，它们是数组名，不是一个单纯的下标变量。VisualC++程序设计基础a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]2020/9/20版权所有©南京理工大学王芳17多维数组的定义对于三维数组来说，可以依据二维数组的定义方法来定义：如inta[2][3][4];其中第一个下标称为“页下标”，第二个下标称为“行下标”，第三个下标称为“列下标”。这个三维数组在内存中同样要占据连续的内存空间。上面定义的三维数组在内存中将先放第0页中的数组元素，然后放第一页中的数组元素，每页中的元素还是按“行主顺序”存放。VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳18二维(多维)数组的引用对二维数组的引用可通过双重循环来实现。例如要引用a[3][4]数组中的元素：for(i=0;i3;i++)for(j=0;j4;j++)a[i][j]=0;使数组中的全部元素赋0或：for(i=0;i3;i++)for(j=0;j4;j++)cina[i][j];从键盘输入数据给数组元素VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳19二维(多维)数组的初始化对二维数组进行初始化的方式有：1、分行赋初值例如：inta[2][3]={{1,3,5},{2,4,6}};2、按数组在内存中的排列顺序赋初值例如：inta[2][3]={1,2,5,2,4,6};在对二维数组赋初值时(全部数据)，可以省略对第一维长度的说明，这时第一维的长度由所赋初值的行数所决定，但第二维不能省略。例如：inta[2][3]={1,3,5,2,4,6};可以表示为：inta[][3]={1,3,5,2,4,6};和inta[][3]={{1,3,5},{2,4,6}};3、可以对部分元素赋初值例如：inta[2][3]={{1},{2}};或inta[2][3]={{1},{0,4}}则未赋初值的其余元素值自动为0。VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳20二维(多维)数组实例例：要求输出如下的杨辉三角(要求输出10行)11112113311464115101051161520156117213535217118285670562881193684126126843691VisualC++程序设计基础2020/9/20版权所有©南京理工大学王芳21数组和函数数组可以作为函数的参数进行数据传送。