C++语言程序设计：第5章 数组

1、1第5章 数 组 本章学习的目的：1、掌握数组的概念2、如何使用数组？ 包括三个部分：一维数组、二维数组和字符数组3、掌握基于数组的基本算法 2第5章 数 组 5.1 一维数组的定义和应用 5.2 二维数组 5.3 字符数组 5.4 程序设计举例3数组的基本概念一种复杂数据类型 数组元素的数据类型称为数组的基类型。可以是前述的简单类型，也可是指针或构造类型。 计算机系统根据数组定义给出的元素个数，为数组分配一段连续的内存空间。同一数组的所有元素均保存在此，又因为各元素同质，即所占内存字节数相等，故可以通过序号数组下标访问各数组元素。 在C语言中，数据的类型除基本类型（整型、实型、字符型）外，还

2、有构造类型（数组、结构和共用体）。数组是一种简单的构造类型同质构造类型。 所谓数组，实际为一组同质(相同数据类型)元素的有序集合。可通过相同的数组名和下标来唯一标识数组元素。类似：数组名下标那么，如何区分并标识这一组同类型的数据？4数组的四大要素： 数组的名字，同变量标识符。但数组名后 不可少。 数组的类型，既数组的基类型。 数组的结构，用于说明数组的维数和数组元素的个数。 数组的存储类型。 数组的四大要素通过定义数组的说明语句通知编译系统。如：static int array10; 在实际中，数组是用来保存一系列相关的、有序的数据，如：数列、矩阵、行列式、一个班各门课的成绩、字符串等。55.

3、1 一维数组的定义和应用 一维数组的定义方式为:存储类型 数据类型 数组名常量表达式;例如 : int a10;它表示数组名为a，数组有10个元素。数组必须先有定义，然后再使用。C+语言规定只能逐个引用数组元素而不能一次引用整个数组。数组的长度数组的长度6说明:C+语言中引用数组元素时，下标从0开始，下标必须是整型量。 数组在内存中存储时，是按下标递增的顺序连续存储各元素变量的值。a0表示第一个元素a1表示第二个元素a9表示第十个元素7数组名表示数据存储区域的首地址。数组的首地址也是第一个元素变量的地址。例如: int a5;首地址：a 或 &a0 重点注意：数组名是一个地址常量（常量指针），

4、不能给它赋值，也不能对它自加自减等对变量进行操作的运算，因为它不是变量，不能作为左值 。错误案例： a=1,2,3,4,5；数组使用之前，必须定义其数据类型和存储类型。static long array20;以上定义语句中，数组array共有20个long型元素，数据类型long决定了相邻两个元素内存空间首地址差值为4存储类型static决定了数组空间在静态全局数据区分配，而且在程序运行一开始就分配scanf(“%d”,a);/给元素a0输入整数a+;a a1；/语法错误 &a/错误，不是变量则不能取地址，因为没有内存。注意数组的内存是指a0、a1等元素的内存，而没有给a这个地址常量分配内存。

5、查看内存映像8数组作为一个整体不能参加各种运算，参加数据处理的只能是数组的元素变量。例5.1 编程实现给数组按序输入数据，再反序输出。 #include void main( ) int i,a10; for(i=0;iai; / scanf(%d,&ai); for(i=9;i=0;i-) /反相输出数组中的元素 coutai; / printf(%d,ai); 循环变量同时作为数组下标，可以理解成“索引”或 “指挥棒”95. 数组定义时可以给出对应元素的初值。对于外部参照类和static类数组叫做初始化，对auto类数组则是赋初值。如: static int data5=2,4,6,8,1

6、0;其作用是在程序运行第一条指令之前分别给5个元素分配静态全局数据区的内存，并将对应数据以初始化方式写入分配的内存。auto int data5=2,4,6,8,10;其作用是在程序运行过程中，动态分配内存空间（分配在栈内存）给数组元素，然后执行赋值语句，完成给元素赋初值的动作。二者区别在确定初值的时刻点和内存种类均不同。若定义数组时给出初值列表，则定义中可以不指定数组长度, 即: int data=2,4,6,8,10;for ( i = 0 ; i sizeof ( data ) / sizeof ( int ) ; i + ) cout c i end ; 若被定义的数组长度与提供初值的

7、个数不相等，则数组长度不能省掉。 int b20=1,2,3,4,5;/只初始化前5个元素，多余的元素都是0 或残值（取决于存储类型） 。 106 . 数组定义时【】内为常量表达式，不能包含可变的量，编译时，编译器必须能够确定该表达式的取值。但定义后引用某个元素时用数组名下标，下标可以是任何量。例如，下面这样定义是错误的: (1) int n ; scanf(%d,&n); int an; (2) int n=20; int an;：C语言不支持动态数组定义(数组定义时必须预先指定数组的长度，数组的长度不能依赖于程序运行过程中变量的值，因此常量表达式中不能有变量和函数调用)11【应用说明】C语

8、言中最常见的错误之一是数组元素的越界使用(访问数组元素的下标超出了对数组进行定义时规定的界限。下标越界将会非法地改变其它存储单元的内容，有时还会造成严重的错误。【例】#include void main( ) int i ,a10;/auto局部数组定义 for (i=0; i10; i+) ai = i;/引用之前先赋初值 for (i=0; i10; i+) printf(“a%2d=%dn”, i, ai);若不小心写成：for (i=0; i数组首地址9876.3210aa+1*Ia+2*Ia+8*Ia+9*Ia0a1a2a8a9退出查看a10a+10*Ib注意：a10语法正确，但不是

9、数组a的元素，也就是说，a10的存储空间不在数组a的连续空间里，实际上a10就存放在数组a 的连续内存空间的下一个内存空间。下标的含义？a i 中i代表前面有i个元素13小节学习了数组的基本概念四大要素学习了一维数组的定义、初始化以及元素的引用定义数组的长度必须是一个常数，不能出现变量名或函数调用引用单个元素时的下标表示法越界的了解14#include char str = “SSSWILTECH1111W1WALLMP1”;void main( ) int k; char c; for( k=2; (c=strk) !=0 ; k+) switch(c) case A: putchar(a)

10、; continue; case 1: break; case 1 : while( (c=str+k ) !=1 & c!=0) ; case 9: putchar(#); case E: case L: continue; default: putchar(c); continue ; putchar(*); puts(“”) ;15例5.2 编程将一个从键盘输入的整数序列按逆序重新存放并显示，整数个数首先从键盘输入; 如要求输入5个数，原来的顺序为8，6，5，4，1，要求改为1，4，5，6，8。#include void main( ) int a100; int i,j,n,temp;

11、 scanf(%d,&n); /输入整数个数 printf(input the numbers:n); for(i=0;in;i+) /输入整数序列 scanf(%d,&ai); /*将整数序列依次从首尾向中间交换元 素, 从而实现逆序排列*/ for( i=0 , j=n-1; ij; i+ , j- ) temp=aj; aj=ai; ai=temp; printf(now the numbers are:n); /输出重排后的整数序列 for(i=0;in;i+) printf(%5d,ai); 该程序的运行结果为：5input the numbers:8 6 5 4 1now the

12、numbers are :1 4 5 6 8数组应用i头指挥棒j尾指挥棒ij2指挥棒未相遇，则循环16例5.4 编一程序要求对已知的N个数，按从小到大进行排序 (1) 选择排序法思想:分为n-1轮次。每一轮次确定一个元素。具体如下:第一轮次，在a0an-1找出最小值，放在a0;第二轮次，在a1an-1找出最小值，放在a1; 第n-1轮次,在an-2和an-1之中找最小值,放进an-2,余下an-1下面以5个数为例,用两种方法实现选择排序：17第一种方法（直接选择法）:假设已知数据序列为: 10 12 7 6 8，则实现排序的操作情况见右图:总结: 对N个数要进行N-1轮次排序，每一轮次比较次数

13、随轮次数的增加而减小，(轮次数+次数=N)依此可设计出程序：18算法描述 for( i=0; in-1; i + )/升序排序，i表示“轮次号”，0n-2共n-1轮次 固定ai元素,从ai+1元素开始（直至元素an-1）逐个元素与ai比较大小，值小者放入ai元素空间中，完成第i轮次操作每处理一轮次，待比较元素的个数少1 上面的循环体对应第i轮次操作，需要比较(n-1)-(i+1)+1次2数比较判断： for( j=i+1; jaj ) a i 与a j 交换 for( j=i+1; ja j ) a i 与a j 交换19#include #define N 10void main( ) in

14、t i,j,t; int a10; for ( i=0 ;i 10 ;i+) scanf(%d,&ai); for ( i=0 ;iN-1;i+) /N-1轮次 /以ai为基准数对剩下的进行搜索 for (j=i +1 ; jaj) t = ai; ai = aj; aj = t; for ( i=0 ;i 10 ;i+) printf(%dt, ai);直接选择法从ai+1开始逐个比较，直至aN-1特点：固定ai为比较和交换对象，交换次数多，低效！固定ai20第二种方法(设标签选择法)已知数据序为:12 7 6 8 ,则实现排序的操作情况见右图:标签标签21总结: 对N个数要进行N-1轮排序

15、，每一轮的比较次数随轮次数增加而减小(遍数+次数=N)，相对上一种情况，比较次数一样，交换次数减少。对应的程序如下 ：22#include #define N 10void main() int i, j, min,t; int a10; for ( i=0 ;i 10 ;i+) scanf(%d,&ai); /min为标签，含义：最小元素下标 for ( i=0 ;iN-1; i+) min=i; /初始默认第一元素最小 for ( j = i+1;jN;j+) /*遍历后续所有元素，将其与amin而不是ai进行比较*/ if(aj amin) min =j; if(min!=i) t =

16、ai; ai = amin; amin = t; for ( i=0 ;i 10 ;i+) printf(%dt, ai); 比较对象不固定联想：丢手绢游戏场景，在某人背后丢一个手绢做记号（标签），表明其是最小值元素找到标签所指元素和第一个元素交换23(2) 交换排序法（分为冒泡 & 沉底）思想：基本操作是比较相邻两个数，通过交换操作实现前小后大（或反之）分为n-1轮次。每一轮次确定一个元素。具体如下：第一轮次，在a0an-1找出最大值，放在an-1;第二轮次，在a0an-2找出最大值，放在an-2; 第n-1轮次,在a0和a1之中找最大值,放进a1 ,余下a0沉底冒泡法：第一轮次，在an-1

17、a0中找出最大值，放在a0第二轮次，在an-1a1中找出最大值，放在a1第n-1轮次,在an-1an-2中找出最大值，放进an-2,余下的放进an-124已知数据序为:10 12 7 6 8,则实现排序操作情况见图： 25总结: 对N个数要进行N-1轮次排序，每轮次比较次数随轮次数的增加而减小(轮次号+比较次数=N)，比较的顺序是从前往后。根据算法描述可以写出程序如下： 26算法描述 for( i=1; i=n-1; i + )/升序排序，i表示“轮次号”，总轮次数为n-1 从a0元素开始两两相邻数比较大小，按先小后大交换次序，把当前这组数中最大值交换至最后元素an-i 中，完成第i轮次每处理

18、一轮次，当前这组数个数少1 上面的循环体对应的第i轮次操作，需要频繁的相邻数比较判断： for( j=1; jaj )/不满足先小后大条件，则交换 aj-1与aj交换 for( j=1; jaj ) aj-1与aj交换27#include #define N 10void main() int i,j,t; /定义变量和数组 int a10; for ( i=0 ;i 10 ;i+) /依次输入10个数 scanf(%d,&ai); for (i=1; i=N 1; i+) /*对剩下的数据冒泡排序，将该次最大值放到上次排序最大值之前*/ for (j=1; jaj) / 递减用 t = aj

19、; aj = aj-1; aj-1 = t; for ( i=0 ;i 10 ;i+) printf(%dt, ai); 第 i 轮对应 Ni 次两两比较进行排序，外层循环 N1轮( 轮次号i 从1开始 )相邻项下标为j-1，j28#include #define N 10void main() int i,j,t; /定义变量和数组 int a10; for ( i=0 ;i 10 ;i+) /依次输入10个数 scanf(%d,&ai); for ( i=0 ;iN-1; i+) for (j=0;jaj+1) t = aj; aj = aj+1; aj+1 = t; for ( i=0

20、;i 10 ;i+) /输出排序后的数 /组 printf(%dt, ai); 进行排序，外层循环 N1轮( 轮次号i 从0开始 )第 i 轮对应 N-i -1次两两比较相邻项下标为j，j+129沉底法： for (i=1; i=N 1; i+) for (j=1; jitemj) / 递减时改为 temp = itemj-1; itemj-1 = itemj; itemj = temp; 冒泡法： for (i=1; i=i; j-) if (itemj-1itemj) / 递减时改为 temp = itemj-1; itemj-1 = itemj; itemj = temp; for (i

21、=0; iN - 1; i+) for (j=0; jitemj+1) 。 for (i=0; ii ; j+) if (itemjitemj+1) 。 小结305.2 二维数组 将一维概念推广，可得多维数组。存储类型 数据类型 数组名常量表达式1常量表达式2 ;【例】 char a23; /2 维，23=6个元素 int b234; /3 维，23 4=24个元素 C语言表示多维数组的方法与有些语言不同，每一维单独用一个 表示，这种表示方法有助于把多维数组理解为特殊的一维数组。如：int a23=int a03, a13;/两个一维数组，数组名a0,a1类似int a234理解为：2个二维数

22、组a0,a1(各有3*4个元素)6个一维数组a00,a01,a02,a10,a11,a12,各有4个元素 315.2 二维数组几个问题：1、多维数组的“维”不止一个，访问时对应有多个下标，每一维下标的含义是什么？2、在内存中按照什么样的顺序来存储数组中的元素？（即谁先存储在低地址内存，谁后存储在高地址内存？）3、如何通过多维数组名与每一维下标一起使用来获取元素的内存地址？32对于多维数组第一个 代表第一维，第二个 代表第二维，依次类推。按照下标的变化顺序来理解多维数组的存储顺序：最右边的下标最先变化（或者说变化最快）最左边的下标最后变化。对于二维数组我们可以理解为行列式或矩阵排列，对于第一维可

23、以理解为行，第一维长度表示行数；第二维可以理解为列，第二维长度表示列数；对于二维数组 int a33：第一列 第二列 第三列每一行数据可以理解为一维数组第一行a00 a01 a02 int a0 3第二行a10 a11 a12 int a1 3第三行a20 a21 a22 int a2 3 33a22a21a20a12a11a10a02a01a00计算机的内存为一维空间。对于C语言的数组，其在内存中的存储顺序如右图所示，按行存放，先顺序存放第一行的元素，再顺序存放第二行的元素，依次类推。每行的元素存放顺序是按表示列号的下标递增顺序排列。下标变化规律：先变列下标，再变行下标推而广之：先变最高维的

24、下标，再变次高维下标, . , 最后变第一维下标。对二维数组来讲，行下标含义为前面已经存储的行数，列下标含义为当前行中已经存储的列数。元素aij的内存单元的地址计算为： a i*一行的字节数 当前行前面j个元素字节数34对于三维数组 int a233在内存中的存储顺序： a022a021a020a012a011a010a002a001a000a122a121a120a112a111a110a102a101a100第1个一维数组，名字a00第2个一维数组，名字a01第3个一维数组，名字a02第4个一维数组，名字a10第5个一维数组，名字a11第6个一维数组，名字a1235多维数组的初始化： 按行

25、对全部元素赋初值 static int a33 = 1, 2, 3, 4, 5, 6, 7, 8, 9；/用表示一行，每一行相当于一维数组，用括起来。 按数组元素的存储顺序依次对全部元素赋初值 static int a33 = 1, 2, 3, 4, 5, 6, 7, 8, 9；1-a00,2-a01,4-a10.多维数组的引用：同一维数组的引用类似，如：a2*m-12*n-1, b33.多维数组仍不允许整体引用。注意：下标取值范围为 0每维长度 1，不要越界。36 对部分元素赋初值 static int a33 = 1, 5, 9；等效于 static int b32=0,2,3;/第三行全

26、部为0 static int c32=0,1,2,3;/隔行赋值，若不写，/则后面行被认为是第二行 static int d4=1,2,3,4,5,6,7,8,9,10,11,12;/若提供了初值，则第一维长度可省略，这里表示有三行（因为每行有4个数据） static int e4=0,0,3,0,10;/表示三行37 static int c234= 0,1,2,3,4,5,6,7,8,9,10,11, 0,1,2,3,4,5,6,7,8,9,10,11 ;/两个二维数组 注：可以缺省第一维的长度（前提是提供全部初始化数据），不可缺省第二维甚至更高维的长度，全缺省则不知几行几列。由于二维数组

27、与行对象紧密相连，在后面要讲到二维数组名就是行指针。注意由于是静态类型(static)，故其元素不给初始值时初始值默认为0(对于整型数)。若非静态类型或非外部参照类型，则其元素的初始值随机。38【例】将 2 维数组a23中的元素按其存储顺序复制到 1 维数组b6中。 #include void main ( ) static int a23 = 1, 2, 3, 4, 5, 6; int b6, i, j; for (i=0; i2; i+) /对于三维数组a234，有 /bi*3*4+j*4+k=aijk for (j=0; j3; j+) bi*3+j = aij; for (i=0; i

28、6; i+) printf(“b%2d = %dn”, i, bi); 39#include void main( ) int a234, d1,d2,d3, i, j, k, minnum; / 3 维数组a for (i=0; i2; i+) for (j=0; j3; j+) for (k=0; k4; j+) scanf(“%d”, &aijk); / 为数组赋值 minnum = a000;d1=0,d2=0,d3=0; for (i=0; i2; i+)/可以与上一个循环共用同一个循环变量， for (j=0; j3; j+) /但要注意循环变量清零（初值问题） for (k=0;

29、 k aijk) minnum = aijk; / 选择最小值 d1=i, d2=j, d3=k; printf(“min = %d, x=%d,y=%d,z=%dn”, minnum,d1,d2,d3);【例】查找数组a234中的最小元素，及相应坐标。将 改为 ，则选择最大值40例5.6 输入一个44的整数矩阵,然后将之转置并显示这个转置后的矩阵。 分析:以主对角线为对称轴，交换所有对称点元素。如下图所示: 41 程序如下:#include#define SIZE 4void main( ) int dataSIZESIZE,i,j,d; for(i=0;iSIZE;i+) /输入矩阵中的值

30、 for(j=0;jSIZE;j+) scanf(%d,&dataij); for(i=0;iSIZE-1;i+) /矩阵转置 for(j=i+1;jSIZE;j+) /交换所有对称点元素 d=dataij; dataij=dataji; dataji=d; for(i=0;iSIZE;i+) printf(n); for(j=0;jSIZE;j+) printf(%4d,dataij); const int SIZE=4;42例5.7 计算如下所示两个矩阵的乘积: 分析: 在编程之前，我们必须了解下面的数学常识:(1)第一个矩阵的列数必须等于第二个矩阵的行数，一个m行n列的矩阵乘以一个n行p

31、列的矩阵，其结果是一个m行p列的矩阵。 (2)若矩阵A乘以矩阵B，则结果矩阵C中每个元素的值为: Cij = 43根据分析可编写程序如下:#includevoid main( ) int valueA34=2,3,-5,0, /数组初化 12,-1,27,8, 91,22,-32,1; int valueB45= 25,13,65,0,5, -2,0,18,10,45, 53,33,3,9,0, 7,61,26,-37,-1; int valueC35=0; /VC6初始化结果矩阵 int i,j,k; /按照公式将矩阵相乘 for(i=0;i3;i+) for(j=0;j5;j+) for(

32、k=0;k4;k+) valueCij+=valueAik*valueBkj; for(i=0;i3;i+) /输出结果矩阵 for(j=0;j5;j+) printf(%5d,valueCij); printf(n); 程序的运行结果：221 139 169 15 145 1789 1535 1051 63 7 542 188 6241 105 144444例5.8 输出下列形式的杨辉三角形的前10行。11 11 2 11 3 3 11 4 6 4 1 .分析：杨辉三角形是 展开后各项的系数，有以下规律：（1）各行的第一个数都是1,即ai0=1；（2）各行的最后一个数都是1,即aii=1；（

33、3）从第3行起，除上面指出的第一个数和最后一个数外，其余各数是上一行同列和前一列两个数之和，可以这样表示：aij=ai-1j-1+ai-1j，其中i为行数，j为列数。 aij=ai-1j-1+ai-1j45程序如下：include void main( ) int a1010; int i,j;/*将第一列和对角线上的元素赋值为1*/ for(i=0;i10;i+) ai0=1; aii=1; for (i=2;i10;i+) for (j=1;ji;j+) /按规律求数组元数aij的值 aij=ai-1j-1+ai-1j; for(i=0;i10;i+) for(j=0;j=i;j+) pr

34、intf(%5d,aij); printf(n); 465.3 字符数组 一维字符数组与单个字符串 存放字符的数组是字符数组，字符数组中每一个元素存放一个字符。可以这样定义： auto char string20; 对于一个长度为n的字符数组，它可以存储长度不超过n-1个字符的字符串，最后一个元素是为了在字符串末尾存入一个空字符0,这个空字符是字符串结束的标志，所以：字符串的最大长度不得超过数组长度减1 47字符数组的初始化可以：1）、逐个元素指出其初值char string20= s, t, r, o, n, g, 0;char string20= s, t, r, o, n, g ;如果要

35、用这种字符数组存放字符串，在指定初值时，必须在最后一个值之后必须明确地写上0。 这样上面的初始化等效于下面的赋值语句： string0= s; string1= t; string2= r; . .string6= 0;482）、用字符串文字量初始化字符数组： char string =“hello“; 在内存处理中，它的存储状态如下：再例如：char string20=hello; printf(%s,string);虽然数组的元素个数变成了20，但也只能输出“hello”这几个字符，而不是输出20个字符，因为有字符串结束标志0 。 h e l l o 0“hello“; /花括号可以缺省4

36、9字符数组的引用、赋值和其它运算必须逐个元素进行 ,不过它可以通过字符数组名由函数scanf和函数printf函数用s输入和输出整个字符串。像上面定义的数组，我们可以这样输入：scanf(%s,string);输出字符串可以用这样的语句:printf(“%sn”,string); 由于string是数组 string20的首地址，所以前面不能加&符号 。回顾%s格式说明符的含义50 如果函数利用一个scanf函数输入多个字符串，则以空格分隔。例如： char string15,string25,string35; scanf(%s%s%s,string1,string2,string3);如果

37、输入为： How are you? 回车数组的存储状态如下图，未被赋值的元素的值依赖于数组的存储类型 。 51例 计算字符串的长度void main( void ) int i=0; char string20=“Hello C+:)”; /统计字符个数，如果字符不等于0则循环 while(stringi!=0) /计数i加1 i+; printf(“Total characters are %dn”,i); /输出个数计数值1052例5.9 计算字符串的长度int strlen(char string ) int i=0; /统计字符个数，如果字符不等于0则循环 while(stringi!

38、=0) /计数i加1 i+; return(i); /返回个数计数值 532. 二维字符数组与多个字符串 表示多个字符串的二维字符数组可以看成是以字符串为元素的一维数组。字符串数组是特殊的二维字符数组，它的每一行元素中都含有字符串结束符0。 54例5.11 下面的例子说明二维数组的定义和初始化以及和多个字符串的关系。有两种方法进行初始化，我们可以加以比较:【方法一】 char string310= pascal , cobol , fortran ;初始化后数组的存储状态如下：pascal0 cobol0 fortran0 注意：每一个字符串的长度不能超过9，因为还要留一个给字符串结束符0，这是系统自动添加的。55【方法二】如果没有显式初始化，则可以用scanf的s格式输入每个字符串。下面演示如何用二维字符数组名实现多个字符串输入和输出 char string320; int i; for(i=0;i3;i+) scanf(%s, stringi); for(i=0;ihelle， Cc, A0)Else 63(6) strlen(字符数组) strlen函数的功能是测试字符串的长度。函数的值为字符串中字符的实际长度，不包含0在内。如： char string20=hello; printf(“%dn”,strlen(string);/sizeo