第5章
利用数组处理批量数据
接标题2接正文5.1为什么需要用数组
如果有100个互不关联的数据,可以分别把它们存放到100个变量中。但是如果这些数据是有内在联系的,是具有相同属性的(如100个学生的成绩),就可以把这批数据看作一个整体,称为数组(array)。所谓数组,就是用一个统一的名字代表这批数据,而用序号或下标来区分各个数据。例如用s代表学生成绩这组数据,s就是数组名,用s1,s2,s3分别代表学生1、学生2、学生3的成绩,s右下角的数字1,2,3用来表示该数据在数中的序号,称为下标(subscript)。数组中的数据称为数组元素。
概括地说: 数组是有序数据的集合。要寻找一个数组中的某一个元素必须给出两个要素，即数组名和下标。数组名和下标唯一地标识一个数组中的一个元素。
数组是有类型属性的,例如可以定义a是整型数组,b是单精度型数组等。同一数组中的每一个元素都必须图5.1
属于同一数据类型。例如，一个数组不能由9个整型数据和1个单精度型数据组成。一个数组在内存中占一片连续的存储单元。如果有一个整型数组a,假设数组的起始地址为2000,则该数组在内存中的存储情况如图5.1所示。
引入数组就不需要在程序中定义大量的变量,大大减少程序中变量的数量,使程序精练,而且数组含义清楚,使用方便,明确地反映了数据间的联系。许多好的算法都与数组有关。熟练地利用数组,可以大大地提高编程和解题的效率,加强了程序的可读性。
由于在程序中无法用下角表示下标,因此在计算机高级语言中都用括号来表示下标,在BASIC,Pascal,FORTRAN,COBOL等语言中用圆括号来表示下标,如s(1),s(2),s(3)。C和C++用方括号来表示下标,如用s\[1\],s\[2\],s\[3\] 分别代表s1,s2,s3。5.2定义和引用一维数组[4/5]5.2.1定义一维数组定义一维数组的一般形式为
类型名数组名\[常量表达式\];
例如: 表示数组名为a,此数组为整型,有10个元素。
说明: 
(1) 数组名定名规则和变量名相同,遵循标识符定名规则。
(2) 用方括号括起来的常量表达式表示下标值,如下面写法是合法的: //假设前面已定义了n为常变量  (3) 常量表达式的值表示元素的个数,即数组长度。例如,在“int a\[10\];”中,10表示a数组有10个元素,下标从0开始,这10个元素是a\[0\],a\[1\],a\[2\],a\[3\],a\[4\],a\[5\],a\[6\],a\[7\], a\[8\],a\[9\]。注意最后一个元素是a\[9\]而不是a\[10\]。
(4) 常量表达式中可以包括常量、常变量和符号常量,但不能包含变量。也就是说,不允许对数组的大小作动态定义,即数组的大小不依赖于程序运行过程中变量的值。例如,下面这样定义数组是不行的: // 输入a数组的长度
int a\[n\];// 试图根据n的值决定数组的长度 如果把第1,2行改为下一行就合法了。// 用const定义n为常变量5.2.2引用一维数组的元素
数组必须先定义,然后使用。只能逐个引用数组元素的值而不能一次引用整个数组中的全部元素的值。
数组元素的表示形式为
数组名\[下标\]
下标可以是整型常量或整型表达式。例如: 例5.1定义一个整型数组a,把0～9共10个整数赋给数组元素a\[0\]～a\[9\] ,然后按a\[9\]，a\[8\]，…，a\[0\] 的顺序输出。
利用循环来处理这类问题是轻而易举的。
编写程序: #include <iostream>
using namespace std;
int main()
{int i,a\[10\];
for (i=0;i<=9;i++)
a\[i\]=i;//使a\[0\]~a\[9\]的值为0～9
 for (i=9;i>=0;i--)
cout<<a\[i\]<<" ";//按a\[9\],a\[8\],…,a\[0\] 的顺序输出
cout<<endl;//换行
return 0;
}运行结果:  9 8 7 6 5 4 3 2 1 05.2.3一维数组的初始化
对数组元素的初始化可以用以下方法实现。
(1) 在定义数组时对全部数组元素赋予初值。例如: 将数组元素的初值依次放在一对花括号内。经过上面的定义和初始化之后,a\[0\]=0,a\[1\]=1,a\[2\]=2,a\[3\]=3,a\[4\]=4,a\[5\]=5,a\[6\]=6,a\[7\]=7,a\[8\]=8,a\[9\]=9。
(2) 可以只给一部分元素赋值。例如: 定义a数组有10个元素,但花括号内只提供5个初值,这表示只给前面5个元素赋初值,后5个元素值默认为0。
(3) 在对全部数组元素赋初值时,可以不指定数组长度。例如: 可以写成在第2种写法中,花括号中有5个数,系统就会据此自动定义a数组的长度为5。但若被定义的数组长度与提供初值的个数不相同,则数组长度不能省略。
5.2.4一维数组程序举例
通过本章的一些例题,读者可以了解不同问题的算法,并学会怎样思考和处理问题,举一反三。
例5.2用数组来处理求Fibonacci数列问题。
求Fibonacci数列问题已在例3.13中接触过,现在用数组来处理,可以用20个元素代表数列中的20个数,从第3个数开始,可以直接用表达式f\[i\]=f\[i-2\]+f\[i-1\]求出各数。请读者比较用数组和不用数组时的两种算法。
编写程序: #include <iostream>
#include <iomanip>
using namespace std;
int main()
{ int i;
int f\[20\]={1,1};//f\[0\]=1,f\[1\]=1
for(i=2;i<20;i++) 
f\[i\]=f\[i-2\]+f\[i-1\];//在i的值为2时,f\[2\]=f\[0\]+f\[1\],以此类推
for(i=0;i<20;i++)//此循环的作用是输出20个数
{if(i%5==0) cout<<endl;// 控制换行,每行输出5个数据 
 cout<<setw(8)<<f\[i\];// 每个数据输出时占8列宽度 
}
cout<<endl;// 最后执行一次换行 
return 0;
}运行结果:  (空一行)
11235
813213455
89144233377610
9871597258441816765例5.3编写程序,用起泡法对10个数排序(由小到大)。
解题思路: 
将相邻两个数比较,将小的调到前头。若有6个数(8,9,5,4,2,0)。第1次比较第1个数和第2个数(8和9)的大小,如果第1个数大于第2个数,就把两个数位置交换,第2次将第2个数和第3个数(9和5)进行比较和交换……如此共进行5次,得到8,5,4,2,0,9的顺序，见图5.2。可以看到，最大的数9已“沉底”,成为最下面一个数,而小的数“上升”。最小的数0已向上“浮起”一个位置。经第1轮(共5次)后,已得到最大的数(在最下面)。
然后进行第2轮比较,对余下的前面5个数按上法进行比较,见图5.3。经过4次比较,得到次大的数8(在5个数中最下面的位置)。再进行第3轮比较,对余下的前面4个数进行比较……如此进行下去。不难看出,对6个数要比较(和交换)5轮,才能使6个数按大小顺序排列好。在第1轮中要对两个数之间的比较(和交换)进行5次,在第2轮中为4次……第5轮为1次。
图5.2
图5.3

可以推知,如果有n个数,则要进行(n-1)轮比较(和交换)。在第1轮中要进行(n-1)次两两比较,在第j轮中要进行(n-j)次两两比较。
根据以上思路写出程序,今设n=10,本例定义数组长度为11,a\[0\]不用,只用a\[1\]~a\[10\],以符合人们的习惯。从前面的叙述可知,应该进行9轮比较和交换。
编写程序：#include <iostream>
using namespace std;
int main()
{
int a\[11\];
int i,j,t;
cout<<"input 10 numbers :"<<endl;
for (i=1;i<11;i++)//输入a\[1\]~a\[10\]
cin>>a\[i\];
cout<<endl;
for (j=1;j<=9;j++)//共进行9轮比较
for(i=1;i<=10-j;i++)//在每轮中要进行(10-j)次两两比较
 if (a\[i\]>a\[i+1\])//如果前面的数大于后面的数
 {t=a\[i\];a\[i\]=a\[i+1\];a\[i+1\]=t;} //交换两个数的位置,使小数上浮
cout<<"the sorted numbers :"<<endl;
for(i=1;i<11;i++)//输出10个数
cout<<a\[i\]<<" ";
cout<<endl;
return 0;
}运行结果: input 10 numbers:
3 5 9 11 33 6 -9 -76 100 123↙
the sorted numbers:
-76 -9 3 5 6 9 11 33 100 1235.3定义和引用二维数组
具有两个下标的数组称为二维数组。有些数据要依赖于两个因素才能唯一地确定,例如有3个学生,每个学生有4门课的成绩,显然,成绩数据是一个二维表,如表5.1所示。表5.1学生成绩数据表学 生 序 号课程1课程2课程3课程4课程5学生18578999688学生27689759775学生36492907356想表示第3个学生第4门课的成绩,就需要指出学生的序号和课程的序号两个因素,在数学上以S3，4表示整数73。
5.3.1定义二维数组
定义二维数组的一般形式为
类型名 数组名\[常量表达式\]\[常量表达式\]
例如: 定义a为3×4(3行4列)的单精度数组,b为5×10(5行10列)的单精度数组。注意不能写成“float a\[3,4\],b\[5,10\];”。C++对二维数组采用这样的定义方式,使我们可以把二维数组看作一种特殊的一维数组: 它的元素又是一个一维数组。例如,可以把a看作一个一维数组,它有3个元素: a\[0\],a\[1\],a\[2\],每个元素又是一个包含4个元素的一维数组，见图5.4。a\[0\],a\[1\],a\[2\]是3个一维数组的名字。
上面定义的二维数组可以理解为定义了3个一维数组,即相当于a\[0\]\[4\],a\[1\]\[4\],a\[2\]\[4\]此处把a\[0\],a\[1\],a\[2\]作一维数组名,这3个一维数组各有4个元素。C++的这种处理方法在数组初始化和用指针表示时显得很方便,这在以后会体会到。
C++中,二维数组中元素排列的顺序是: 按行存放,即在内存中先顺序存放第1行的元素,再存放第2行的元素。图5.5表示对a\[3\]\[4\]数组存放的顺序。
图5.4
图5.5

C++允许使用多维数组。有了二维数组的基础,再掌握多维数组是不困难的。例如,定义三维数组的方法是定义float型三维数组a,它有2×3×4=24个元素。多维数组元素在内存中的排列顺序: 第1维的下标变化最慢,最右边的下标变化最快。例如,上述三维数组的元素排列顺序为a\[0\]\[0\]\[0\]→a\[0\]\[0\]\[1\]→a\[0\]\[0\]\[2\]→a\[0\]\[0\]\[3\]→a\[0\]\[1\]\[0\]→a\[0\]\[1\]\[1\]→
a\[0\]\[1\]\[2\]→a\[0\]\[1\]\[3\]→…→a\[1\]\[2\]\[3\]5.3.2引用二维数组的元素
引用二维数组的元素的一般形式为
数组名 \[下标\]\[下标\]
如a\[2\]\[3\]。下标可以是整型表达式,如a\[2-1\]\[22-1\]。不要写成a\[2,3\],a\[2-1,22-1\]形式。
数组元素是左值,可以出现在表达式中,也可以被赋值,例如: 在使用数组元素时,应该注意下标值应在已定义的数组大小的范围内。常出现的错误如://定义3行4列的数组

a\[3\]\[4\]=15;//引用a\[3\]\[4\]元素,错误定义a为3×4的数组,它可用的行下标值最大为2,列下标值最大为3。最多可以用到a\[2\]\[3\],用a\[3\]\[4\]就超过了数组的范围。
请读者严格区分在定义数组时用的a\[3\]\[4\]和引用元素时的a\[3\]\[4\]的区别。前者a\[3\]\[4\]用来定义数组的维数和各维的大小,后者a\[3\]\[4\]中的3和4是下标值,a\[3\]\[4\]代表某一个元素。
5.3.3二维数组的初始化
可以用下面的方法对二维数组初始化: 
（1） 按行给二维数组全部元素赋初值。如这种赋初值方法比较直观,把第1个花括号内的数据给第1行的元素,第2个花括号内的数据赋给第2行的元素……即按行赋初值。
（2） 可以将所有数据写在一个花括号内,按数组排列的顺序对全部元素赋初值。如效果与前相同。但以第1种方法为好,一行对一行,界限清楚。如果数据多,用第2种方法会写成一大片,容易遗漏,也不易检查。
（3） 可以对部分元素赋初值。如它的作用是只对各行第1列的元素赋初值,其余元素值自动置为0。赋初值后数组各元素为也可以对各行中的某一元素赋初值: 初始化后的数组元素如下:110这种方法对非0元素少时比较方便,不必将所有的0都写出来,只须输入少量数据。也可以只对某几行元素赋初值: 数组元素为 (4) 如果对全部元素都赋初值(即提供全部初始数据),则定义数组时对第1维的长度可以不指定,但第2维的长度不能省略。如可以写成系统会根据数据总个数分配存储空间,一共12个数据,每行4列,当然可确定为3行。
从本节的介绍中可以看到，C++在定义数组和表示数组元素时采用a\[\]\[\]这种两个方括号的方式,对数组初始化时十分有用,它使概念清楚,使用方便,不易出错。
5.3.4二维数组程序举例
例5.4将一个2×3的二维数组a的行和列元素互换,存到一个3×2的二维数组b中。例如:
a = 1 2 3
4 5 6行列互换后存放在b数组中b=14
25
36
编写程序:#include <iostream> 
using namespace std;
int main()
{
 int a\[2\]\[3\]={{1,2,3},{4,5,6}};
 int b\[3\]\[2\],i,j;
 cout<<"array a:"<<endl;
 for (i=0;i<=1;i++)
{for (j=0;j<=2;j++)
{cout<<a\[i\]\[j\]<<" ";//输出a\[i\]\[j\] 元素
b\[j\]\[i\]=a\[i\]\[j\];//将a数组j行i列元素的值赋给b数组i行j列元素
}
cout<<endl;
 }
 cout<<"array b:"<<endl;
 for (i=0;i<=2;i++)
{
for(j=0;j<=1;j++)
cout<<b\[i\]\[j\]<<" ";//按行输出b数组中各元素
cout<<endl; 
} 
return 0;
}运行结果: array a:
123
456
array b:
14
25
36例5.5有一个3×4的矩阵,要求编程序求出其中值最大的那个元素的值,以及其所在的行号和列号。
解题思路:
先考虑解此问题的思路。从若干数中求最大数的方法很多,现在采用“打擂台”的算法。如果有若干人比武,先有一人站在台上,再上去一人与其交手,败者下台,胜者留在台上。第3个人再上台与在台上者比,同样是败者下台,胜者留在台上。如此比下去，直到所有人都上台比过为止，最后留在台上的就是胜者。
程序模拟这个方法,开始时把a\[0\]\[0\]的值赋给变量max,max就是开始时的擂主,然后让下一个元素与它比较,将二者中值大者保存在max中,然后再让下一个元素与新的max比,直到最后一个元素比完为止。max最后的值就是数组所有元素中的最大值。
编写程序: #include <iostream>
using namespace std;
int main()
{int i,j,row=0,colum=0,max;
int a\[3\]\[4\]={{5,12,23,56},{19,28,37,46},{-12,-34,6,8}};
max=a\[0\]\[0\];//使max开始时取a\[0\]\[0\]的值
for (i=0;i<=2;i++)//从第0行到第2行
for (j=0;j<=3;j++)//从第0列到第3列
if (a\[i\]\[j\]>max)//如果某元素大于max
{max=a\[i\]\[j\];//max将取该元素的值
 row=i;//记下该元素的行号i
 colum=j;//记下该元素的列号j
}
cout<<"max="<<max<<",row="<<row<<",colum="<<colum<<endl;
return 0;
}运行结果:  max=56,row=0,colum=3 数组中最大值为56,位置在0行3列,即a\[0\]\[3\]的值是所有数中最大的。
5.4用数组作函数参数
常量和变量可以用作函数实参,同样数组元素也可以作函数实参,其用法与变量相同。数组名也可以作实参和形参,传递的是数组的起始地址。
1. 用数组元素作函数实参
由于实参可以是表达式,而数组元素可以是表达式的组成部分,因此数组元素当然可以作为函数的实参,与用变量作实参一样,将数组元素的值传送给形参变量。
例5.6用函数处理例5.5。有一个3×4的矩阵,要求编程序求出其中值最大的那个元素的值,以及其所在的行号和列号。
算法和例5.5是一样的,今设一函数max_value,用来进行比较并返回结果。
编写程序: #include <iostream>
using namespace std;
int main()
{int max_value(int x,int max);//函数声明
 int i,j,row=0,colum=0,max
 int a\[3\]\[4\]={{5,12,23,56},{19,28,37,46},{-12,-34,6,8}};//数组初始化
 max=a\[0\]\[0\];
 for (i=0;i<=2;i++)
 for (j=0;j<=3;j++)
{max=max_value(a\[i\]\[j\],max);//调用max_value函数