第7章 用数组保存数据

第7章算法和数据结构基础——用数组保存数据哈尔滨工业大学为什么使用数组(Array)?读入两个学生的成绩，求其平均分

intscore1,score2;

scanf("%d",&score1); scanf("%d",&score2);

aver=(score1+score2)/2;问题：一批数据来了怎么办？

intscore1,score2,……,score100;

scanf("%d",&score1); scanf("%d",&score2);…… scanf("%d",&score100);

intscore[100],i;for(i=0;i<100;i++){scanf("%d",&score[i]);}……保存大量同类型的相关数据

intscore,i,sum=0; for(i=0;i<100;i++){scanf("%d",&score);sum=sum+score;

}aver=sum/100;7.1数组的定义、引用和初始化数组（Array）一组具有相同类型的变量的集合。由于数组是聚合了一组相同类型的变量，因此数组是一种构造数据类型。一副扑克牌可以看成一个一维数组，将一副扑克牌按照花色和牌面分开摆放，那么就可以看成一个二维数组。若将52张牌按花色排就是一个4行13列的二维数组，按牌面排就是一个13行4列的二维数组。就像用梁山好汉称呼《水浒传》中的一百单八将一样，对于数组中的这一组相同类型的数据，我们会使用一个统一的名字来标识它们，这个名字就称为数组名。构成数组的每个数据项称为数组元素（Element）。

一维数组的定义

a[9]a[8]a[7]a[1]a[0]…inta[10];定义一个有10个int型元素的一维数组在内存中分配连续的存储空间给此数组为什么数组下标从0开始？使编译器的实现简化一点，且下标的运算速度少量提高基类型（BaseType）数组长度数组元素的下标从0开始数组名a代表首地址7.1数组的定义、引用和初始化如果希望下标从1到10而非从0到9，怎么办？a[9]a[8]a[7]a[1]a[0]…最好用宏定义

#define

N10

inta[N];a[10]

#define

N11

inta[N];7.1数组的定义、引用和初始化7.1数组的定义、引用和初始化一维数组用1个下标表示数组元素二维数组用2个下标表示数组元素三维数组用3个下标表示数组元素

声明一个有8个元素的一维数组：#defineN8inta[N];声明一个有2行4列的二维数组：#defineM2#defineN4intb[M][N];声明一个有2*2*2的三维数组：#defineM2#defineN2#defineL2intb[L][M][N];7.1数组的定义、引用和初始化数组在内存中的物理存储结构按行线性存储

7.1数组的定义、引用和初始化访问（引用）数组中的元素

for(i=0;i<2;i++) //行下标值变化{

for(j=0;j<4;j++) //列下标值变化

{

scanf("%d",&a[i][j]);}}for(i=0;i<2;i++) //行下标值变化{

for(j=0;j<4;j++) //列下标值变化

{

printf("%4d",a[i][j]);}printf("\n");//输出换行}未初始化的数组元素值是什么？静态数组和全局数组自动初始化为0值，否则，是随机数一维数组的初始化 inta[5]={62,74,56,88,90}; inta[5]={62,74}; inta[]={62,74,56,88,90};更高效的数组初始化方法

memset(a,0,sizeof(a));

memcpy(a,b,sizeof(a));用sizeof(a)来获得数组a所占的内存字节数#include<string.h>inta[5]={62,74,0,0,0};7.1数组的定义、引用和初始化参数的传递方式有两种：按值传递（Pass-by-value）按引用传递（Pass-by-reference）7.2.1传值调用与模拟传引用调用7.2.2一维数组的参数传递——以筛法求素数为例【例7.1】请编写程序，用筛法计算并输出1~n之间的所有素数之和。

voidSiftPrime(inta[],intn){for(inti=2;i<=n;++i){a[i]=i;

}for(inti=2;i<=sqrt(n);++i){for(intj=i+1;j<=n;++j){if(a[i]!=0&&a[j]!=0&&a[j]%a[i]==0){ a[j]=0; }}}}7.2.2一维数组的参数传递——以筛法求素数为例【例7.1】请编写程序，用筛法计算并输出1~n之间的所有素数之和。

#include<stdio.h>#include<math.h>#defineN100voidSiftPrime(inta[],intn);intSumofPrime(intn);intmain(void){intn;printf("Inputn:");scanf("%d",&n);printf("sum=%d\n",SumofPrime(n));return0;}voidSiftPrime(inta[],intn){for(inti=2;i<=n;++i){a[i]=i;

}for(inti=2;i<=sqrt(n);++i){for(intj=i+1;j<=n;++j){if(a[i]!=0&&a[j]!=0&&a[j]%a[i]==0){ a[j]=0; }}}}intSumofPrime(intn){intm,sum=0;inta[N+1];SiftPrime(a,n);for(sum=0,m=2;m<=n;++m){if(a[m]!=0)//素数判定

{

sum+=m;}}returnsum;}7.2.3二维数组元素的参数传递——以杨辉三角形为例【例7.2】杨辉三角形。杨辉三角是中国数学史上的一个伟大成就，是中国古代数学的杰出研究成果之一，早在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中就详细记载了杨辉三角形表，书中还说明此表引自11世纪中叶（约公元1050年）贾宪的《释锁算术》，因此杨辉三角也被称为“贾宪三角”。在欧洲，帕斯卡（1623~1662）于1654年才发现这一规律，称其为帕斯卡三角形。帕斯卡的发现比杨辉要晚393年，比贾宪晚600年，所以有些书上也称其为“中国三角形”（Chinesetriangle）。7.2.3二维数组元素的参数传递——以杨辉三角形为例【例7.2】杨辉三角形//函数功能：计算杨辉三角形前n行元素的值voidCalculateYH(inta[][N],intn){for(inti=0;i<n;++i){a[i][0]=1;a[i][i]=1;}for(inti=2;i<n;++i){for(intj=1;j<=i-1;++j){a[i][j]=a[i-1][j-1]+a[i-1][j];}}}#include<stdio.h>#defineN20voidCalculateYH(inta[][N],intn);voidPrintYH(inta[][N],intn);intmain(void){inta[N][N]={0},n;printf("Inputn(n<20):");scanf("%d",&n);CalculateYH(a,n);PrintYH(a,n);return0;}//函数功能：以直角三角形形式输出杨辉三角形前n行元素的值voidPrintYH(inta[][N],intn){for(inti=0;i<n;++i){for(intj=0;j<=i;++j){printf("%-4d",a[i][j]);//输出结果左对齐

}

printf("\n");}}7.2.3二维数组元素的参数传递——以杨辉三角形为例【例7.2】杨辉三角形//函数功能：计算杨辉三角形前n行元素的值voidCalculateYH(inta[][N],intn){for(inti=0;i<n;++i){for(intj=0;j<=i;++j){if(j==0||i==j){a[i][j]=1;}else{a[i][j]=a[i-1][j-1]+a[i-1][j];}}}}//函数功能：以直角三角形形式输出杨辉三角形前n行元素的值voidPrintYH(inta[][N],intn){for(inti=0;i<n;++i){for(intj=0;j<=i;++j){printf("%-4d",a[i][j]);//输出结果左对齐

}

printf("\n");}}#include<stdio.h>#defineN20voidCalculateYH(inta[][N],intn);voidPrintYH(inta[][N],intn);intmain(void){inta[N][N]={0},n;printf("Inputn(n<20):");scanf("%d",&n);CalculateYH(a,n);PrintYH(a,n);return0;}7.2.3二维数组元素的参数传递——以杨辉三角形为例当形参被声明为二维数组时，可以不指定数组第一维的长度，用另一个整型形参来指定数组第一维的长度，但是第二维的长度必须指定，不能省略。为什么必须指定数组第二维的长度呢？7.3.1一维数组的下标越界实例分析【例7.3】一维数组下标越界访问的程序示例。请运行下面程序，观察运行结果并分析原因。#include<stdio.h>intmain(void){inti,a=1,c=2,b[5]={0};printf("%p,%p,%p\n",b,&c,&a);//打印数组b、变量c和a的首地址

for(i=0;i<=8;i++)//让下标值越界访问数组的元素

{b[i]=i;printf("%4d",b[i]);}printf("\nc=%d,a=%d,i=%d\n",c,a,i);return0;}7.3.2二维数组的下标越界实例分析【例7.4】二维数组下标越界访问的程序示例。请运行下面程序，观察运行结果并分析原因。#include<stdio.h>intmain(void){inti,j;inta[2][3]={0};for(i=0;i<=2;i++)//行下标越界

{for(j=0;j<=3;j++)//列下标越界

{printf("%d\t",a[i][j]);}printf("\n");}return0;}7.3.2二维数组的下标越界实例分析【例7.5】二维数