第5章数组
数组通常用来存放成批的具有相同类型的数据。在实际问题中,如果涉及批量数据
的顺序或位置关系,或者要多次使用同一批量数据等情况时,就要使用数组。例如,在统
计学生成绩时经常要统计高于平均成绩的人数或者按成绩排名次时,就需要使用数组
处理。
数组是指一批具有相同类型数据的有序集合,用一个名字(称为数组名)来表示,数组
属于构造数据类型。数组中的元素用位置号(称为下标)表示它的顺序。有一个下标的数
组称为一维数组,有两个下标的数组称为二维数组,多个下标的数组称为“多维数组”。
应用本章的知识可以完成学生成绩管理的程序,根据输入的学生成绩统计每个人、每
门课程的最高分、最低分、平均成绩、超过平均成绩的人数以及按每个人的平均成绩排序,
查找不及格的学生的成绩等。
5.一维数组
1
一维数组通常用来表示具有相同数据类型的一组数,可以对这组数进行排序和查询
等。一维数组的常用算法包括顺序排序法、选择排序法和冒泡排序法等排序的算法,以及
数组逆序存放和二分查找法等。
1.一维数组的定义和引用
5.1
1.
一维数组的定义
数组必须先定义后使用。定义一维数组的一般形式是:
类型标识符数组名[数组长度]
【说明】方括号[] 内的数组长度表示数组中元素的个数,必须是整数或整型常量表
达式,不能包含变量。
例如,20];, 都是合法的数组定义。而i
intcj[30],a[10];floatb[ntn=10;int
a[n];, 这个数组a的定义是不合法的。
数组在内存中占据一片连续的存储单元。若有定义inta[10];, 则表示数组a中包括
10 个元素,分别为a[0]~a[9]。这10 个元素在内存中是连续存放的,如图5.1所示。只
要知道数组a的起始元素a[0]的地址,后面元素的相应地址就可以计算出来。由于C语
言中用数组名代表数组的起始地址,所以此处的数组名a也代表数组a的起始地址,与
a[0]的地址相同。
数组的下标从0开始。若有数组定义inta[10];, 则数组a的最小下标为0,最大可
数组引例
一组数组的
定义和引用
64
图5.1 数组中10个元素在内存中连续存放
用下标为9,C的编译器不对下标越界进行检查,因此编程者必须保证程序中所用数组的
下标是不越界的。
2.一维数组的引用
引用一维数组元素的一般形式是:
数组名[下标]
【说明】 []内的下标必须是整型表达式,可以只是一个常量、变量,也可以是表达式。
例如,a[1],a[i],a[9-i](i是整型)等都是合法的数组元素的引用,数组元素也称为
下标变量。
数组元素的处理往往与循环分不开,输入和输出都要结合循环进行。假设int型数
组cj有30个元素,输入所有元素时可以使用下面的循环语句对cj的所有元素进行遍历。
for(i=0;i<30;i++)
scanf("%d",&cj[i]);
如果数组中的数组元素的值是有某种计算规律的,有时也可以使用循环直接给数组
元素赋值,不必一个一个地输入。
【例5-1】 数组元素的引用。
#include "stdio.h"
main()
{ int i,b[10];
for(i=0;i<10;i++) /*通过循环遍历数组元素*/
b[i]=i+1; /*赋值后,数组b 中各元素的值依次为1,2,3,…,10*/
for(i=0;i<10;i++) /*再次遍历数组元素*/
printf("%5d",b[i]); /*格式%5d 的作用是控制每个数据占5 列*/
/*如果使用格式%d,输出的数将连在一起*/
printf("\n");
}
运行结果:
1 2 3 4 5 6 7 8 9 10
5.1.2 一维数组的初始化
定义数组时直接给数组的一些元素赋值,称为对数组的初始化,也可称为对数组赋
65
初值。对
数组的初始化可以用以下3种方法实现。
(1)定义数组时,对全部数组元素赋以初值。例如:
int a[10]={1,2,3,4,5,6,7,8,9,10};
(2)定义数组时,只给一部分元素赋初值。例如:
int a[10]={1,2,3,4,5};
表示只给数组a的前5个元素赋初值,后边元素自动被赋值为0。
(3)在对全部数组元素赋初值时,可以不指定数组长度。例如:
int a[]={1,2,3,4,5,6,7,8,9,10};
与下面的写法等价:
int a[10]={1,2,3,4,5,6,7,8,9,10};
【注意】 许多情况下,赋初值是针对循环变量、累加(累乘)变量、数列的初始项等而
言的,所以对数组、变量赋初值的方法不是唯一的,既可以通过定义时的初始化实现,也可
以通过其他方法(如赋值语句、for语句中的表达式1等)实现。
【例5-2】 用数组求Fibonacci数列的前20项。
【分析】 例4-13求Fibonacci数列时,在循环中求出一项输出一项,不能同时保存20
项的数据;而用数组表示Fibonacci数列时,则可以同时保存求出的所有的数。
#include "stdio.h"
main( )
{ int i;
long int f[20]={1,1}; /*前两项都赋初值1*/
for(i=2;i<20;i++) /*循环18 次,循环变量i 从2 到19*/
f[i]=f[i-2]+f[i-1]; /*后一项等于前两项的和*/
for(i=0;i<20;i++) /*对数组中的20 个元素遍历*/
{ printf("%12ld",f[i]); /*输出元素f[i]*/
if((i+1)%5==0)printf("\n"); /*控制每行输出5 个数*/
}
}
运行结果:
1 1 2 3 5
8 13 21 34 55
89 144 233 377 610
987 1597 2584 4181 6765
【说明】 程序中采用每输出5个数换一次行的方法,也可以用以下程序段先换行后
再输出5个数(输出第一个数前先换一次行)的方法。
一组数组
的初始化
66
for(i=0;i<20;i++)
{ if(i%5==0)printf("\n");
printf("%12ld",f[i]);
}
编程时,一般采用先输出若干个数再换行的方法并且列对齐输出。
5.1.3 随机函数rand和random
可以用随机函数产生一组随机整数赋值给数组中的各个元素,C 中用rand()函数
实现。
1.rand函数
rand函数的一般形式是:rand()。它产生0到整型最大值之间的一个随机整数,如
要产生[a,b]的随机整数可以使用rand()%(b-a+1)+a实现。
rand函数位于标准库stdlib.h 中,使用该函数时要先用文件包含命令#include
"stdlib.h"(或#include<stdlib.h>)。
2.random 函数
在TurboC中,random 是包含在头文件stdlib.h中的宏定义:
#define random(num) (rand()%(num))
宏定义(详见6.7.1节)的参数用一对括号括起来,使用时和函数类似,所以也可把
random 当作函数使用。使用random 函数时也需要文件包含命令#include"stdlib.h",
调用的一般形式是:random(n)。它产生[0,n-1]的随机整数,如要产生[a,b]的随机整
数可以使用random(b-a+1)+a实现。
在TurboC中可以用random 函数代替rand函数,但在VisualC++中只能使用rand
函数,不能使用random 函数。
3.srand 函数和randomize函数
srand函数的一般形式是:srand(unsignedseed)。它产生随机整数的种子,能使程序中
每次运行srand函数时得到不同的随机整数序列。通常的使用方法是:srand(time(0)),
用当前的时间作为随机数的初始种子。time函数在时间库time.h中,srand函数在标准
库stdlib.h中。
在TurboC中,randomize是包含在头文件stdlib.h中带参数的宏定义:
#define randomize() srand((unsigned)time (NULL))
调用形式是:randomize(),类似于一个无参函数。在TurboC中可以用randomize
函数代替srand函数,但在VisualC++中只能使用srand函数,不能使用randomize函数。
随机函数
产生随机整数的具体方法参见例5-6和例5-7。由于random 和randomize函数不是
C中真正意义的库函数,为了通用,建议使用rand和srand函数。
5.4
一维数组的简单应用
1.
考虑设计一个学生成绩管理系统,可以完成成绩统计、查询、排序等功能。例如,成绩
统计包括求平均成绩、最高分、最低分等。
当要解决一个实际问题时,首先要研究采用什么样的解决方案,使用什么样的算法,
以及是否使用过类似的算法等,要把实际问题变成计算机能够解决的问题。
1)选择或者创造一个抽象
例如,通过抽象,可以将学生的成绩用一组数据表示,然后选择合适的数据结构来处
理它。显然,学生成绩的数据用数组来表示比较恰当。
2)采用逐步求精的方法设计解决问题的方案
解决问题需要遵循一定的过程或规则,培养解决问题的能力是伴随着整个程序设计
的过程逐步实现的。简单地说,解决问题的方法就是采用逐步求精、各个击破的思想。当
面对比较复杂的问题时,要设法将其分解为若干个比较简单的问题,并逐步分解,使这些
比较简单的问题最终分解成为简单的、最好是与已经解决的问题类似的基本问题。把这
些基本问题逐一解决之后,再拼接在一起去解决原来的复杂问题。
以此成绩管理系统为例,可将它分解为成绩统计、成绩排序、成绩查询等若干个较小
的问题。当较小的问题还不够简单时就继续简化,例如成绩统计这个问题可以再细分为
求平均成绩、求最高分、求最低分等更小的问题,由此形成各种基本问题。当这些基本问
题解决之后,可以逐步拼接成较大的程序去解决原来的复杂问题。本章将逐步介绍这些
基本问题的程序设计方法,最后组成解决综合性问题的例5-30 。
3)按照算法编写程序代码实现
同样的问题可以采用不同的程序设计语言编程实现,采用的算法也会有细微差别,但
应尽量使用通用的算法。
4)运行测试结果
采取各种测试方法对程序输入各类数据进行测试性运行,以保证程序的正确性。
下面给出一些基本问题的解决方法,从这些例子中体会用数组解决问题的大致思路。
【例5-3】求10 个学生成绩的平均成绩。
【分析】在例4-9中编程求解过若干个学生的平均成绩。本例中已知学生个数为
10,这样就可以定义一个包含10 个元素的一维数组,同时也不必使用终止标记法输入数
据了。例5-
3
编程解决具体问题时,为了保证程序的易读性,一般将程序划分为3个部分。
(1)输入数据,或用其他方式给数组、变量等赋值。
(2)处理数据,也就是计算过程,例如求和、比较大小等。
(3)输出数据,即输出计算结果。
67
68
#include "stdio.h"
main( )
{ int i,a[10];
float average,sum;
for(i=0;i<=9;i++) /*循环变量i 从0 到9,遍历10 个元素*/
scanf("%d",&a[i]); /*输入第i 个成绩放到a[i]中*/
sum=0; /*sum 存放成绩和,赋初值为0*/
for(i=0;i<10;i++) /*for 循环用于累加10 个元素*/
sum+=a[i]; /*将a[i]累加到sum 中*/
average=sum/10; /*for 循环结束之后再求平均值*/
printf("平均成绩=%7.2f\n",average); /*输出平均成绩*/
}
运行结果:
63 88 89 90 66 73 61 92 72 78 ↙
平均成绩= 77.20
【说明】 如果sum 是整型的变量,求平均成绩的语句要改为
average=sum/10.0;
【例5-4】 求10个数的最小值和最大值。
【分析】 求最大值的算法和例4-8类似,只是把10个数都保存在数组中。
#include "stdio.h"
main( )
{ int i,a[10],min,max; /*用数组a 存放10 个数,min、max 分别存放最小值和最大值*/
for(i=0;i<=9;i++) /*循环变量i 从0~9,遍历10 个元素*/
scanf("%d",&a[i]);
max=min=a[0]; /*a[0]为最大值和最小值的初值*/
for(i=1;i<10;i++) /*遍历a[1]到a[9],求最大值和最小值*/
{ if(a[i]<min) min=a[i]; /*若a[i]比min 还小,到目前为止a[i]是最小值*/
if(a[i]>max) max=a[i]; /*若a[i]比max 还大,到目前为止a[i]是最大值*/
}
printf("最大值=%d,最小值=%d\n", max,min);
}
运行结果:
63 88 89 90 66 73 61 92 72 78 ↙
最大值=92,最小值=61
【说明】 例5-3和例5-4程序的功能不用数组也可以实现,但是下面例5-5的问题如
果不用数组仅用变量是不好实现的,因为它不但涉及要记住一个数在一组数中的位置,而
且求出该位置后还要再次使用这批数。
例5-4
69
【例5-5】 求10个数的最小值,并将该最小值与最前面的元素互换。
【分析】 因为要将最前面的数换到原来最小值所在的位置,所以求最小值时要记住
图5.2 例5-5算法的N-S图
最小值的位置,数组中的位置通常指的就是其下标。
此问题的核心部分可以分解为两个问题:
(1)求最小值min,并记下最小值在原数组中的
位置k。
(2)将最小值a[k]和a[0]交换。
第(1)个问题只是比例5-3中的程序多一步,所以
在例5-3中的程序中将求最小值部分改为if(a[i]<
min){min=a[i];k=i;},同时在循环之前给k赋初
值为0。
注意到程序中min和a[k]都是表示最小值,而
且一直相等,所以只要记住一个k就够用了。例5-5
算法的N-S图如图5.2所示。
#include "stdio.h"
main( )
{ int i,t,a[10],k;
for(i=0;i<=9;i++)
scanf("%d",&a[i]);
k=0; /*设a[0]最小,k 为最小值的下标,所以k 赋初值为0*/
for(i=1;i<10;i++) /*a[0]已设为最小,所以循环从下标1 开始*/
if(a[i]<a[k])k=i; /*如果a[i]比当前最小值a[k]还小,就将i 赋值给k*/
printf("最小值是:%d\n",a[k]); /*第9 行*/
printf("最小值的下标为:%d\n",k);
if(k!=0) /*如果k=0,最小值就是a[0],不必交换*/
{t=a[0]; a[0]=a[k]; a[k]=t;} /*将a[0]和a[k]交换,即将最小值换到最前面*/
for(i=0;i<=9;i++) /*用for 循环输出变化后的数组*/
printf("%3d",a[i]);
printf("\n");
}
运行结果:
67 98 76 64 89 58 52 69 91 87 ↙
最小值是:52
最小值的下标为:6
52 98 76 64 89 58 67 69 91 87
【说明】 程序的一般步骤是输入数据、处理数据和输出数据,但三者也常常交叉。例
如,本例中输出数据和处理数据(a[0]和a[k]交换)就交叉了。把程序中从第9行开始的
4行用以下程序段替换:
if(k!=0)
例5-5
70
{t=a[0]; a[0]=a[k]; a[k]=t;}
printf("最小值是:%d\n",a[0]);
printf("最小值的下标为:%d\n",k);
就可以避免输出数据和处理数据部分的交叉,但输出的最小值应是交换后的a[0],其易
读性弱了。可见,程序总体上分成3步就可以,没有必要一定划分为严格的3步,还需要
具体问题具体对待。
【问题扩展】 这个程序完成了将10个数的最小值交换放到a[0]中的功能。按照同
样的做法,可以找出从a[1]到a[9]中的最小值交换放到a[1]的位置,再找出从a[2]到a
[9]中的最小值交换放到a[2]的位置,以此类推,最后从a[8]到a[9]中找出最小值交换放
到a[8]中,剩下的a[9]就是10个数中的最大值。这样,就完成了将10个数按照由小到
大的次序排序的任务,这种排序的方法称为选择排序法。简单地说,对10个数的选择排
序法,就是重复9轮次求最小值的位置,并将该位置的最小值交换放到相应位置的过程。
对n个数选择排序的算法描述:
(1)给数组a中元素输入数据。
(2)对i=0,1,…,n-2做
① k=i;
② 对j=i+1,…,n-1做
如果a[j]<a[k],则k=j;
③ 交换a[k]和a[i]。
(3)输出数组a。
【例5-6】 产生10个[40,100]的随机整数,并用选择排序法按由小到大的顺序排序
后输出。
【分析】 使用例5-5问题扩展中讨论的方法排序。
#include "stdio.h"
#include "stdlib.h" /*函数rand、srand 包含在stdlib.h 中*/
#include "time.h" /*函数time 包含在time.h 中*/
main( )
{ int i,j,t,a[10],k;
srand(time(0)); /*用时间作为随机数的种子,每次运行得到不同的随机数序列*/
for(i=0;i<10;i++)
{ a[i]=rand()%61+40; /*产生[40,100]的随机整数赋给数组元素a[i]*/
printf("%5d",a[i]); /*输出随机产生的数据(排序前的)*/
}
printf("\n");
for(i=0;i<9;i++) /*循环变量i 从0~8,共9 轮*/
{ k=i; /*求a[i]~a[9]中最小值的位置k,先假定a[i]最小,将k 赋初值i*/
for(j=i+1;j<10;j++) /*遍历a[i+1]~a[9],求最小值下标赋值给k*/
if(a[j]<a[k]) k=j;
if(k!=i) /*如果k=i,最小值就是a[i],不必交换*/
{t=a[i]; a[i]=a[k]; a[k]=t;}
例5-6
71
/*将a[i]与此轮求出的最小值a[k]交换位置*/
}
for(i=0;i<10;i++) /*输出排序后的10 个随机整数*/
printf("%5d",a[i]);
printf("\n");
}
某一次运行结果:
67 82 63 45 100 58 99 71 84 51
45 51 58 63 67 71 82 84 99 100
【说明】 此程序在VisualC++和TurboC环境下都可正常运行,在TurboC环境下
还可以使用random 函数和randomize函数组合,具体用法参考例5-7。
对一组数排序的方法有很多种,除了选择排序法外,还有顺序排序、冒泡排序、插入排
序和快速排序等方法。
【例5-7】 用顺序排序法实现例5-6的排序功能。
【分析】 顺序排序法的循环变量的变化过程与选择排序相同。按升序进行顺序排序
时,也是先安排好第一个数,即设法将最小的数交换到第一个数的位置(元素的下标为0),
方法是将后面的每一个数都和第一个数比较,如果后面的数比第一个数还小就立即交换
相比较的两个数,一轮循环完成后就将最小的数放在了最前边。第二轮循环按照同样的
方法将剩下的9个数(第一个数不再参与比较)中的最小数交换放在第二个数的位置(元
素的下标为1)。以此类推,直到将最后两个数中较小的数交换到倒数第二个数的位置
(元素的下标为8),整个顺序就排好了。
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
main()
{ int i,j,t,a[10];
randomize(); /*随机数种子,保证每次运行得到不同的随机数序列*/
for(i=0;i<10;i++)
{ a[i]=random(61)+40; /*随机产生[40,100]的随机整数*/
printf("%5d",a[i]); /*排序前输出一次*/
}
printf("\n");
for(i=0;i<9;i++) /*通过9 轮比较排序*/
for(j=i+1;j<10;j++) /*遍历a[i]~a[9]找最小值,交换到a[i]中*/
if(a[j]<a[i]) / * 如果a[j]比a[i]小*/
{t=a[i]; a[i]=a[j]; a[j]=t;} /*将a[j]和a[i]交换*/
for(i=0;i<10;i++) /*输出排好序的数组*/
printf("%5d",a[i]);
printf("\n");
}
例5-7
72
某一次运行结果:
78 69 100 99 74 89 41 95 86 64
41 64 69 74 78 86 89 95 99 100
【说明】 本例程序在TurboC上运行。
【例5-8】 将一维数组中的n(n≤50)个数按逆序存放。
【分析】 当处理的数据个数n不确定时,可以先定义一个足够大的数组,再输入n,
通过n来控制输入n个数。数组逆序存放的方法可以采用前后对应元素对换的方法,例
如,当n=8时,a[0]和a[7]交换,a[1]和a[6]交换,a[2]和a[5]交换,a[3]和a[4]交换。
为了防止同一对数据交换两次(等于没交换),只需要遍历其中一半元素,即循环变量i从
0到(n-1)/2变化时,a[i]和a[n-1-i]交换。
#include "stdio.h"
main()
{ int a[50],t,n,i; /*最多有50 个数,所以定义用int a[50]*/
scanf("%d",&n); /*输入元素个数n*/
for(i=0;i<n;i++) /*循环n 次,遍历a[0]~a[n-1]*/
{ scanf("%d",&a[i]); /*输入第i 个数,放到a[i]中*/
printf("%5d",a[i]); /*输出逆序前的每一个数*/
}
printf("\n");
for(i=0;i<=(n-1)/2;i++) /*遍历数组a 的前一半元素,让前一半和后一半交换*/
{ t=a[i]; /*这3 行完成a[i]和a[n-1-i]交换*/
a[i]=a[n-1-i];
a[n-1-i]=t;
}
for(i=0;i<n;i++) /*输出逆序后的数*/
printf("%5d",a[i]);
printf("\n");
}
运行结果:
8 ↙
1 2 3 4 5 6 7 8 ↙
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
【说明】
(1)第一个for语句既用于输入n个数,也做了逆序前的数据输出。如果n比较大时
有些不方便,也容易使输入和输出数据交叉在一起,所以最好将这个for语句分成两个:
一个用于输入n个数,另一个用于输出逆序前的n个数。
(2)n是偶数时,数据正好成对地交换。n是奇数时,本程序遍历的最后一对数是自
己和自己交换。例如,n=7时,a[0]和a[6]交换,a[1]和a[5]交换,a[2]和a[4]交换,最
例5-8