第7章 用数组保存数据.ppt

1、第第7章章 算法和数据结构基础算法和数据结构基础用数组保存数据用数组保存数据哈尔滨工业大学哈尔滨工业大学为什么使用数组为什么使用数组(Array)?n读入两个学生的成绩，求其平均分读入两个学生的成绩，求其平均分 int score1,score2;scanf(%d,&score1);scanf(%d,&score2);aver=(score1+score2)/2;n问题：一批数据来了怎么办？问题：一批数据来了怎么办？int score1,score2,score100;scanf(%d,&score1);scanf(%d,&score2);scanf(%d,&score100);int sco

2、re100,i;for(i=0;i100;i+)scanf(%d,&scorei);保存大量同类保存大量同类型的相关数据型的相关数据 int score,i,sum=0;for(i=0;i100;i+)scanf(%d,&score);sum=sum+score;aver=sum/100;7.1 数组的定义、引用和初始化数组的定义、引用和初始化n数组（数组（ArrayArray）一组具有相同类型的变量的集合。由于数组是聚合了一组相同类一组具有相同类型的变量的集合。由于数组是聚合了一组相同类型的变量，因此数组是一种构造数据类型。型的变量，因此数组是一种构造数据类型。一副扑克牌可以看成一个一维数组

3、，将一副扑克牌按照花色和牌面分开摆一副扑克牌可以看成一个一维数组，将一副扑克牌按照花色和牌面分开摆放，那么就可以看成一个二维数组。若将放，那么就可以看成一个二维数组。若将5252张牌按花色排就是一个张牌按花色排就是一个4 4行行1313列的二维数组，按牌面排就是一个列的二维数组，按牌面排就是一个1313行行4 4列的二维数组。列的二维数组。就像用梁山好汉称呼就像用梁山好汉称呼水浒传水浒传中的一百单八将一样，对于数组中的一百单八将一样，对于数组中的这一组相同类型的数据，我们会使用一个统一的名字来标识中的这一组相同类型的数据，我们会使用一个统一的名字来标识它们，这个名字就称为数组名。它们，这个名字

4、就称为数组名。构成数组的每个数据项称为数组元素（构成数组的每个数据项称为数组元素（ElementElement）。）。n 一维一维数组的定义数组的定义 a9a8a7 a1a0n定义一个有定义一个有10个个int型元素的一维数组型元素的一维数组在内存中分配连续的存储在内存中分配连续的存储空间给此数组空间给此数组n为什么数组下标从为什么数组下标从0开始？开始？使编译器的实现简化一点，且下标的运算速度少量提高使编译器的实现简化一点，且下标的运算速度少量提高基类型基类型（Base Type）数组长度数组长度数组元素的下标从数组元素的下标从0 0开始开始数组名数组名a a代表首地址代表首地址7.1 数组

5、的定义、引用和初始化数组的定义、引用和初始化n如果希望下标从如果希望下标从1到到10而非从而非从0到到9，怎么办？，怎么办？a9a8a7 a1a0n最好用宏定义最好用宏定义#define N 10 int aN;a10#define N 11 int aN;7.1 数组的定义、引用和初始化数组的定义、引用和初始化7.1 数组的定义、引用和初始化数组的定义、引用和初始化n一维数组一维数组用用1 1个下标个下标表示数组元素表示数组元素n二维数组二维数组用用2 2个下标个下标表示数组元素表示数组元素n三维数组三维数组用用3 3个下标个下标表示数组元素表示数组元素 声明一个有声明一个有8个元素的一维数

6、组：个元素的一维数组：#define N 8int aN;声明一个有声明一个有2行行4列的二维数组：列的二维数组：#define M 2#define N 4int bMN;声明一个有声明一个有2*2*2的三维数组：的三维数组：#define M 2#define N 2#define L 2int bLMN;7.1 数组的定义、引用和初始化数组的定义、引用和初始化n数组在内存中的物理存储结构数组在内存中的物理存储结构按行线性存储按行线性存储 7.1 数组的定义、引用和初始化数组的定义、引用和初始化n访问（引用）数组中的元素访问（引用）数组中的元素 for(i=0;i2;i+)/行下标值变化行

7、下标值变化 for(j=0;j4;j+)/列下标值变化列下标值变化 scanf(%d,&aij);for(i=0;i2;i+)/行下标值变化行下标值变化 for(j=0;j4;j+)/列下标值变化列下标值变化 printf(%4d,aij);printf(n);/输出换行输出换行n未初始化的数组元素值是什么？未初始化的数组元素值是什么？静态静态数组和数组和全局全局数组自动初始化为数组自动初始化为0 0值，否则，是随机数值，否则，是随机数n一维数组的初始化一维数组的初始化 int a5=62,74,56,88,90;int a5=62,74;int a=62,74,56,88,90;n更高效的数

8、组初始化方法更高效的数组初始化方法 memset(a,0,sizeof(a);memcpy(a,b,sizeof(a);用用sizeof(a)来获得数组来获得数组a所占的内存字节数所占的内存字节数#include int a5=62,74,0,0,0;7.1 数组的定义、引用和初始化数组的定义、引用和初始化n参数的传递方式有两种：参数的传递方式有两种：按值传递（按值传递（Pass-by-value）按引用传递（按引用传递（Pass-by-reference）7.2.1传值调用与模拟传引用调用传值调用与模拟传引用调用7.2.2一维数组的参数传递一维数组的参数传递以筛法求素数为例以筛法求素数为例n

9、【例例7.17.1】请编写程序，用筛法计算并输出请编写程序，用筛法计算并输出1n1n之间的所有素数之和。之间的所有素数之和。void SiftPrime(int a,int n)for(int i=2;i=n;+i)ai=i;for(int i=2;i=sqrt(n);+i)for(int j=i+1;j=n;+j)if(ai!=0&aj!=0&aj%ai=0)aj=0;7.2.2一维数组的参数传递一维数组的参数传递以筛法求素数为例以筛法求素数为例n【例例7.17.1】请编写程序，用筛法计算并输出请编写程序，用筛法计算并输出1n1n之间的所有素数之和。之间的所有素数之和。#include#in

10、clude#define N 100void SiftPrime(int a,int n);int SumofPrime(int n);int main(void)int n;printf(Input n:);scanf(%d,&n);printf(sum=%dn,SumofPrime(n);return 0;void SiftPrime(int a,int n)for(int i=2;i=n;+i)ai=i;for(int i=2;i=sqrt(n);+i)for(int j=i+1;j=n;+j)if(ai!=0&aj!=0&aj%ai=0)aj=0;int SumofPrime(int

11、n)int m,sum=0;int aN+1;SiftPrime(a,n);for(sum=0,m=2;m=n;+m)if(am!=0)/素数判定素数判定 sum+=m;return sum;7.2.3 二维数组元素的参数传递二维数组元素的参数传递以杨辉三角形为例以杨辉三角形为例n【例例7.2】杨辉三角形。杨辉三角是中国数学史上的一个伟大成就，是中国古代数学的杰出研杨辉三角形。杨辉三角是中国数学史上的一个伟大成就，是中国古代数学的杰出研究成果之一，早在中国南宋数学家杨辉究成果之一，早在中国南宋数学家杨辉1261年所著的年所著的详解九章算法详解九章算法一书中就详细记载了一书中就详细记载了杨辉三角

12、形表，书中还说明此表引自杨辉三角形表，书中还说明此表引自11世纪中叶（约公元世纪中叶（约公元1050年）贾宪的年）贾宪的释锁算术释锁算术，因，因此杨辉三角也被称为此杨辉三角也被称为“贾宪三角贾宪三角”。在欧洲，帕斯卡（。在欧洲，帕斯卡（16231662）于）于1654年才发现这一规年才发现这一规律，称其为帕斯卡三角形。帕斯卡的发现比杨辉要晚律，称其为帕斯卡三角形。帕斯卡的发现比杨辉要晚393年，比贾宪晚年，比贾宪晚600年，所以有些书上年，所以有些书上也称其为也称其为“中国三角形中国三角形”（Chinese triangle）。）。7.2.3 二维数组元素的参数传递二维数组元素的参数传递以杨辉

13、三角形为例以杨辉三角形为例n【例例7.2】杨辉三角形杨辉三角形/函数功能：计算杨辉三角形前函数功能：计算杨辉三角形前n行元素的值行元素的值void CalculateYH(int aN,int n)for(int i=0;in;+i)ai0=1;aii=1;for(int i=2;in;+i)for(int j=1;j=i-1;+j)aij=ai-1j-1+ai-1j;#include#define N 20void CalculateYH(int aN,int n);void PrintYH(int aN,int n);int main(void)int aNN=0,n;printf(Inp

14、ut n(n20):);scanf(%d,&n);CalculateYH(a,n);PrintYH(a,n);return 0;/函数功能：以直角三角形形式输出杨辉三角形前函数功能：以直角三角形形式输出杨辉三角形前n行元素的值行元素的值void PrintYH(int aN,int n)for(int i=0;in;+i)for(int j=0;j=i;+j)printf(%-4d,aij);/输出结果左对齐输出结果左对齐 printf(n);7.2.3 二维数组元素的参数传递二维数组元素的参数传递以杨辉三角形为例以杨辉三角形为例n【例例7.2】杨辉三角形杨辉三角形/函数功能：计算杨辉三角形前

15、函数功能：计算杨辉三角形前n行元素的值行元素的值void CalculateYH(int aN,int n)for(int i=0;in;+i)for(int j=0;j=i;+j)if(j=0|i=j)aij=1;else aij=ai-1j-1+ai-1j;/函数功能：以直角三角形形式输出杨辉三角形前函数功能：以直角三角形形式输出杨辉三角形前n行元素的值行元素的值void PrintYH(int aN,int n)for(int i=0;in;+i)for(int j=0;j=i;+j)printf(%-4d,aij);/输出结果左对齐输出结果左对齐 printf(n);#include#

16、define N 20void CalculateYH(int aN,int n);void PrintYH(int aN,int n);int main(void)int aNN=0,n;printf(Input n(n20):);scanf(%d,&n);CalculateYH(a,n);PrintYH(a,n);return 0;7.2.3 二维数组元素的参数传递二维数组元素的参数传递以杨辉三角形为例以杨辉三角形为例n当形参被声明为二维数组时，可以不指定数组第一维的长度，用另当形参被声明为二维数组时，可以不指定数组第一维的长度，用另一个整型形参来指定数组第一维的长度，但是第二维的长度必须

17、指一个整型形参来指定数组第一维的长度，但是第二维的长度必须指定，不能省略。为什么必须指定数组第二维的长度呢？定，不能省略。为什么必须指定数组第二维的长度呢？7.3.1 一维数组的下标越界实例分析一维数组的下标越界实例分析n【例例7.3】一维数组下标越界访问的程序示例。请运行下面程序，观察运行结果并一维数组下标越界访问的程序示例。请运行下面程序，观察运行结果并分析原因。分析原因。#include int main(void)int i,a=1,c=2,b5=0;printf(%p,%p,%pn,b,&c,&a);/打印数组打印数组b、变量、变量c和和a的首地址的首地址 for(i=0;i=8;i

18、+)/让下标值越界访问数组的元素让下标值越界访问数组的元素 bi=i;printf(%4d,bi);printf(nc=%d,a=%d,i=%dn,c,a,i);return 0;7.3.2 二维数组的下标越界实例分析二维数组的下标越界实例分析n【例【例7.4】二维数组下标越界访问的程序示例。请运行下面程序，观察运行结果并】二维数组下标越界访问的程序示例。请运行下面程序，观察运行结果并分析原因。分析原因。#include int main(void)int i,j;int a23=0;for(i=0;i=2;i+)/行下标越界行下标越界 for(j=0;j=3;j+)/列下标越界列下标越界 p

19、rintf(%dt,aij);printf(n);return 0;7.3.2 二维数组的下标越界实例分析二维数组的下标越界实例分析n【例例7.5】二维数组下标越界访问的另一个程序示例。请运行下面程序，观察运行二维数组下标越界访问的另一个程序示例。请运行下面程序，观察运行结果并分析原因结果并分析原因。#include int main(void)int i,j;int a23=0;a10=4;for(i=0;i2;i+)for(j=0;j3;j+)printf(%dt,aij);printf(n);a03=5;/a03与与a10实际是同一个元素实际是同一个元素 for(i=0;i2;i+)fo

20、r(j=0;j3;j+)printf(%dt,aij);printf(n);return 0;7.4 安全编码规范安全编码规范n在使用数组时，需要注意以下安全编码规范：在使用数组时，需要注意以下安全编码规范：（1）外部数据作为数组索引时必须确保在数组大小范围内。）外部数据作为数组索引时必须确保在数组大小范围内。（2）不要使用变长数组类型，若使用，则必须确保变长数组的大小在有效范）不要使用变长数组类型，若使用，则必须确保变长数组的大小在有效范围内。围内。（3）声明一个带有外部链接的数组时，必须显式指定它的大小。）声明一个带有外部链接的数组时，必须显式指定它的大小。（4）若无需修改数组元素的值，则应使用）若无需修改数组元素的值，则应使用const对数组类型的函数形参进行对数组类型的函数形参进行限定。限定。本章知识树本章知识树Q&A