C语言程序设计PPT课件第8章数组.ppt

第第第第8 8 8 8章章章章 数组数组数组数组2023/1/162/49本章学习内容本章学习内容 对数组名特殊含义的理解对数组名特殊含义的理解 数组类型，数组的定义和初始化数组类型，数组的定义和初始化 向函数传递一维数组和二维数组向函数传递一维数组和二维数组 排序、查找、求最大最小值等常用算法排序、查找、求最大最小值等常用算法 2023/1/163/49为什么使用数组为什么使用数组(Array)?【例例例例8.18.18.18.1】要读入要读入要读入要读入10101010人的成绩，然后求平均成绩人的成绩，然后求平均成绩人的成绩，然后求平均成绩人的成绩，然后求平均成绩 需定义需定义需定义需定义10101010个不同名整型变量，需要使用多个个不同名整型变量，需要使用多个个不同名整型变量，需要使用多个个不同名整型变量，需要使用多个scanf()scanf()scanf()scanf()int score1,score2,score10;int score1,score2,score10;scanf(%d,&score1);scanf(%d,&score1);scanf(%d,&score2);scanf(%d,&score2);.而用数组，可共用一个而用数组，可共用一个而用数组，可共用一个而用数组，可共用一个scanf()scanf()scanf()scanf()并利用循环语句读取并利用循环语句读取并利用循环语句读取并利用循环语句读取 int score10,i;int score10,i;for(i=0;i10;i+)for(i=0;i10;i+)scanf(%d,&scorei);scanf(%d,&scorei);保存大量保存大量同类型的同类型的相关数据相关数据2023/1/164/498.1一维数组的定义和初始化一维数组的定义和初始化 一维数组的定义一维数组的定义一维数组的定义一维数组的定义 存储类型存储类型存储类型存储类型 数据类型数据类型数据类型数据类型 数组名数组名数组名数组名 整数整数整数整数1 1 1 1 整数整数整数整数2 2 2 2 整数整数整数整数n;n;n;n;a9a8a7 a1a0数组首地址数组首地址intint a10;a10;定义一个有定义一个有定义一个有定义一个有1010个个个个intint型元素的数组型元素的数组型元素的数组型元素的数组 系统在内存分配连续的系统在内存分配连续的系统在内存分配连续的系统在内存分配连续的1010个个个个intint空间给此数组空间给此数组空间给此数组空间给此数组 直接对直接对直接对直接对a a a a的访问，就是访问此数组的首地址的访问，就是访问此数组的首地址的访问，就是访问此数组的首地址的访问，就是访问此数组的首地址基类型基类型下标从下标从0开始开始2023/1/165/498.1一维数组的定义和初始化一维数组的定义和初始化a9a8a7 a1a0intint a10;a10;数组大小必须是值为正的常量，不能为变量数组大小必须是值为正的常量，不能为变量数组大小必须是值为正的常量，不能为变量数组大小必须是值为正的常量，不能为变量 一旦定义，不能改变大小一旦定义，不能改变大小一旦定义，不能改变大小一旦定义，不能改变大小 数组大小最好用宏来定义，以适应未来可能数组大小最好用宏来定义，以适应未来可能数组大小最好用宏来定义，以适应未来可能数组大小最好用宏来定义，以适应未来可能的变化的变化的变化的变化#define#define SIZESIZE 10 10 intint a aSIZESIZE;一维数组的定义一维数组的定义一维数组的定义一维数组的定义 存储类型存储类型存储类型存储类型 数据类型数据类型数据类型数据类型 数组名数组名数组名数组名 整数整数整数整数1 1 1 1 整数整数整数整数2 2 2 2 整数整数整数整数n;n;n;n;2023/1/166/498.1一维数组的定义和初始化一维数组的定义和初始化 数组定义后的初值仍然是随机数数组定义后的初值仍然是随机数 一般需要我们来初始化一般需要我们来初始化 int int a5=12,34,56,78,9;a5=12,34,56,78,9;int int a5=0;a5=0;int int a=11,22,33,44,55;a=11,22,33,44,55;2023/1/167/498.1一维数组的定义和初始化一维数组的定义和初始化 数组的引用数组的引用 数组名数组名数组名数组名 下标下标下标下标 数组下标数组下标数组下标数组下标(index)(index)(index)(index)都是从都是从都是从都是从0 0 0 0开始开始开始开始 使用使用使用使用aa0 0、a1a1、a2a2、a9a9这样的形式这样的形式这样的形式这样的形式访问每个元素访问每个元素访问每个元素访问每个元素 下标既可是常量，也可是整型表达式，允许快速下标既可是常量，也可是整型表达式，允许快速下标既可是常量，也可是整型表达式，允许快速下标既可是常量，也可是整型表达式，允许快速随机访问，如随机访问，如随机访问，如随机访问，如aiai可以像使用普通变量一样使用它们可以像使用普通变量一样使用它们可以像使用普通变量一样使用它们可以像使用普通变量一样使用它们2023/1/168/49如何使两个数组的值相等？如何使两个数组的值相等？main()int a4=1,2,3,4,b4;b=a;解决方法解决方法方法方法1:1:逐个元素赋值逐个元素赋值 b0=a0;b1=a1;b2=a2;b3=a3;方法方法2:2:通过循环赋值通过循环赋值 int i;for(i=0;i4;i+)bi=ai;原因原因:数组名表示数组的首地址数组名表示数组的首地址,其值不可改变其值不可改变!2023/1/169/498.1一维数组的定义和初始化一维数组的定义和初始化【例例例例8.28.28.28.2】编程实现显示用户输入的月份（不包括编程实现显示用户输入的月份（不包括编程实现显示用户输入的月份（不包括编程实现显示用户输入的月份（不包括闰年的月份）拥有的天数闰年的月份）拥有的天数闰年的月份）拥有的天数闰年的月份）拥有的天数 2023/1/1610/498.1一维数组的定义和初始化一维数组的定义和初始化 下标越界是下标越界是大忌大忌！编译程序不检查是否越界编译程序不检查是否越界编译程序不检查是否越界编译程序不检查是否越界下标越界，将访问数组以外的空间下标越界，将访问数组以外的空间下标越界，将访问数组以外的空间下标越界，将访问数组以外的空间那里的数据是未知的，不受我们掌控，可能带那里的数据是未知的，不受我们掌控，可能带那里的数据是未知的，不受我们掌控，可能带那里的数据是未知的，不受我们掌控，可能带来严重后果来严重后果来严重后果来严重后果2023/1/1611/49b0b0b1b1b2b2b3b3b4b4b5b5b6b6b7b7b8b8b9b9c ca a【例例8.3】当下标值小于当下标值小于0或超过数组长度时或超过数组长度时 会出现什么情况？会出现什么情况？运行程序或单步执行观察变量变化情况可以看到，运行程序或单步执行观察变量变化情况可以看到，变量变量c c和和a a的值因数组越界而被悄悄破坏了的值因数组越界而被悄悄破坏了12345612078910114040444448484c4c5050545458585c5c6060646468686c6c2023/1/1612/498.2二维数组的定义和初始化二维数组的定义和初始化 一维数组一维数组一维数组一维数组 用一个下标确定各元素在数组中的顺序用一个下标确定各元素在数组中的顺序用一个下标确定各元素在数组中的顺序用一个下标确定各元素在数组中的顺序 可用排列成一行的元素组来表示可用排列成一行的元素组来表示可用排列成一行的元素组来表示可用排列成一行的元素组来表示 如如如如 int a5;int a5;二维数组二维数组二维数组二维数组用两个下标确定各元素在数组中的顺序用两个下标确定各元素在数组中的顺序用两个下标确定各元素在数组中的顺序用两个下标确定各元素在数组中的顺序可用排列成可用排列成可用排列成可用排列成i i i i行，行，行，行，j j j j列的元素组来表示列的元素组来表示列的元素组来表示列的元素组来表示 如如如如 int b23;int b23;n n n n维数组维数组维数组维数组用用用用n n n n个下标来确定各元素在数组中的顺序个下标来确定各元素在数组中的顺序个下标来确定各元素在数组中的顺序个下标来确定各元素在数组中的顺序 如如如如 int c324;int c324;n3n3n3n3时，维数组无法在平面上表示其各元素的位置时，维数组无法在平面上表示其各元素的位置时，维数组无法在平面上表示其各元素的位置时，维数组无法在平面上表示其各元素的位置a0a0a1a1a2a2a3a3a4a4b00b00b01b01b02b02b10b10b11b11b12b122023/1/1613/49【例例例例】以下程序的运行结果是什么？以下程序的运行结果是什么？以下程序的运行结果是什么？以下程序的运行结果是什么？int main()int main()int a3=1,2,3,4,5,6,0;int a3=1,2,3,4,5,6,0;printf(%d,%d,%dn,a11,a21,a31);printf(%d,%d,%dn,a11,a21,a31);return 0;return 0;1 2 34 5 06 0 00 0 0结果：结果：5,0,0【例例】若若int a 3=1,2,3,4,5,6,7，则则a数组的第一维大小是多少？数组的第一维大小是多少？1 2 34 5 67 0 0二维数组的初始化二维数组的初始化2023/1/1614/49数组的数据类型和存储类型数组的数据类型和存储类型 根据数组的根据数组的根据数组的根据数组的数据类型数据类型数据类型数据类型，为每一元素安排相同长度的存储单元，为每一元素安排相同长度的存储单元，为每一元素安排相同长度的存储单元，为每一元素安排相同长度的存储单元 根据数组的根据数组的根据数组的根据数组的存储类型存储类型存储类型存储类型，将其安排在内存的动态存储区、静态，将其安排在内存的动态存储区、静态，将其安排在内存的动态存储区、静态，将其安排在内存的动态存储区、静态存储区或寄存器区存储区或寄存器区存储区或寄存器区存储区或寄存器区 用用用用sizeofsizeof(a)(a)来获得数组来获得数组来获得数组来获得数组a a所占字节数所占字节数所占字节数所占字节数shortshort2023/1/1615/49short int a23;a0a1a10 a11a12a00 a01a02存放顺序：存放顺序：存放顺序：存放顺序：按行存放按行存放按行存放按行存放先顺序存放第先顺序存放第先顺序存放第先顺序存放第0 0 0 0行元素，再存放第行元素，再存放第行元素，再存放第行元素，再存放第1 1 1 1行元素行元素行元素行元素a00a01a02a10a11a12需知道数组每行列数才能从起始地址开始正确读出数组元素需知道数组每行列数才能从起始地址开始正确读出数组元素二维数组的存储结构二维数组的存储结构二维数组的存储结构二维数组的存储结构2023/1/1616/49二维数组实例二维数组实例 【例例例例8.48.48.48.4】从键盘输入某年某月（包括闰年），编程输出该年从键盘输入某年某月（包括闰年），编程输出该年从键盘输入某年某月（包括闰年），编程输出该年从键盘输入某年某月（包括闰年），编程输出该年的该月拥有的天数的该月拥有的天数的该月拥有的天数的该月拥有的天数2023/1/1617/498.3向函数传递一维数组向函数传递一维数组 传递传递传递传递整个数组整个数组整个数组整个数组给另一个函数，可给另一个函数，可给另一个函数，可给另一个函数，可将数组的将数组的将数组的将数组的首地址首地址首地址首地址作为参数传过去作为参数传过去作为参数传过去作为参数传过去用用用用数组名数组名数组名数组名作函数参数作函数参数作函数参数作函数参数只复制一个地址只复制一个地址只复制一个地址只复制一个地址自然比复制全部数自然比复制全部数自然比复制全部数自然比复制全部数据效率高据效率高据效率高据效率高由于首地址相同，故实参数组与形由于首地址相同，故实参数组与形由于首地址相同，故实参数组与形由于首地址相同，故实参数组与形参数组参数组参数组参数组占用同一段内存占用同一段内存占用同一段内存占用同一段内存在该函数内，不仅可以在该函数内，不仅可以在该函数内，不仅可以在该函数内，不仅可以读读读读这个数组这个数组这个数组这个数组的元素，还可以的元素，还可以的元素，还可以的元素，还可以修改修改修改修改它们它们它们它们2023/1/1618/49 简单变量和数组作函数参数简单变量和数组作函数参数的区别的区别2023/1/1619/49【例例8.5】计算平均分计算平均分 计数计数计数计数控制的循环控制的循环控制的循环控制的循环2023/1/1620/49【例例8.5】计算平均分计算平均分 计数计数计数计数控制的循环控制的循环控制的循环控制的循环2023/1/1621/49【例例8.6】计算平均分计算平均分当输入负值时，表示输入结束当输入负值时，表示输入结束 标记标记标记标记控制的循环控制的循环控制的循环控制的循环负值作为输入结束标记负值作为输入结束标记负值作为输入结束标记负值作为输入结束标记2023/1/1622/49【例例8.6】计算平均分计算平均分当输入负值时，表示输入结束当输入负值时，表示输入结束 标记标记标记标记控制的循环控制的循环控制的循环控制的循环负值作为输入结束标记负值作为输入结束标记负值作为输入结束标记负值作为输入结束标记2023/1/1623/49【例例8.7】计算最高分计算最高分#include#define N 40int ReadScore(int score);int FindMax(int score,int n);int main()int scoreN,max,n;n=ReadScore(score);printf(Total students are%dn,n);max=FindMax(score,n);printf(The highest score is%dn,max);return 0;2023/1/1624/49max(i=0)max(i=2)max(i=3)计算最大值算法计算最大值算法计算最大值算法计算最大值算法2023/1/1625/49 假设其中的一个学生成绩为最高假设其中的一个学生成绩为最高假设其中的一个学生成绩为最高假设其中的一个学生成绩为最高maxScore=score0;maxScore=score0;对所有学生成绩进行比较，即对所有学生成绩进行比较，即对所有学生成绩进行比较，即对所有学生成绩进行比较，即 for(i=1;in;i+)for(i=1;i maxScorescorei maxScore则修改则修改则修改则修改maxScoremaxScore值为值为值为值为scoreiscorei 打印最高分打印最高分打印最高分打印最高分maxScoremaxScore【例例8.7】计算最高分计算最高分2023/1/1626/49【例例8.7】计算最高分计算最高分2023/1/1627/498.4排序和查找排序和查找排序（排序（Sorting）算法）算法交换法排序交换法排序选择法排序选择法排序2023/1/1628/49交换法排序交换法排序2023/1/1629/49交换法排序交换法排序2023/1/1630/49【例例8.8】交换法从高到低排序交换法从高到低排序交换法交换法排序排序 forfor(i=0;in-1;i+)(i=0;in-1;i+)forfor(j=(j=i+1i+1;jn;j+);j scorei)(scorej scorei)交换成绩交换成绩交换成绩交换成绩scorejscorej和和和和scoreiscorei 2023/1/1631/49如何实现两数交换？如何实现两数交换？temp=scorej;temp=scorej;scorej=scorei;scorej=scorei;scorei=temp;scorei=temp;tempscorejscorei？70507050702023/1/1632/49【例例8.8】交换法从高到低排序交换法从高到低排序void DataSort(int score,int n)/*交换法排序交换法排序*/int i,j,temp;for(i=0;in-1;i+)for(j=i+1;j scorei)/*从高到低从高到低*/temp=scorej;scorej=scorei;scorei=temp;2023/1/1633/49选择法排序选择法排序k=1k=2k=0k=12023/1/1634/49选择法排序选择法排序k=3k=4k=3k=42023/1/1635/49选择法排序选择法排序选择法选择法选择法选择法排序排序排序排序 forfor(i=0;in-1;i+)(i=0;in-1;i+)k=i;k=i;forfor(j=i+1j=i+1;jn;j+);j score scorek k)记录此轮比较中最高分的元素下标记录此轮比较中最高分的元素下标记录此轮比较中最高分的元素下标记录此轮比较中最高分的元素下标 k=jk=j;若若若若k k中记录的最大数不在位置中记录的最大数不在位置中记录的最大数不在位置中记录的最大数不在位置i i，则，则，则，则 交换交换交换交换成绩成绩成绩成绩scorescorek k 和和和和scorescorei i，交换交换交换交换学号学号学号学号numknumk和和和和numinumi；2023/1/1636/49void DataSort(int score,long num,int n)/*选择法选择法*/int i,j,k,temp1;long temp2;for(i=0;in-1;i+)k=i;for(j=i+1;j scorek)k=j;/*记录最大数下标位置记录最大数下标位置*/if(k!=i)/*若最大数不在下标位置若最大数不在下标位置i*/temp1=scorek;scorek=scorei;scorei=temp1;temp2=numk;numk=numi;numi=temp2;2023/1/1637/49【例例8.8】成绩从高到低顺序成绩从高到低顺序2023/1/1638/498.4排序和查找排序和查找查找（查找（Searching）算法）算法顺序查找顺序查找折半查找折半查找2023/1/1639/49【例例8.10】顺序查找学号顺序查找学号intint LinSearch(LinSearch(longlong num,num,longlong x,x,intint n)n)intint i;i;forfor(i=0;in;i+)(i=0;in;i+)ifif(numi=x)(numi=x)return return(i);(i);returnreturn(-1);(-1);哈，找到了！哈，找到了！事先不必排序事先不必排序2023/1/1640/49【例例8.11】折半查找学号折半查找学号哈，找到了！哈，找到了！按升序排序按升序排序10122 10124 10126 10128 1013010122 10124 10126 10128 101302023/1/1641/49【例例8.11】折半查找学号折半查找学号唉，没找到！唉，没找到！10122 10124 10126 10128 1013010122 10124 10126 10128 101302023/1/1642/49intint BinSearch(BinSearch(longlong numnum,longlong x,x,intint n)n)intint low,high,mid;low,high,mid;low=0;low=0;high=n-1;high=n-1;whilewhile(low=high)(low nummid)(x nummid)low=mid+1;low=mid+1;elseelse ifif(x nummid)(x nummid)high=mid-1;high=mid-1;elseelse returnreturn(mid);(mid);returnreturn(-1);(-1);找到时返回找到时返回下标位置下标位置找不到时找不到时 返回返回-1-1若未按学号排序，若未按学号排序，则如何修改程序？则如何修改程序？2023/1/1643/49void DataSort(int score,long num,int n)/*选择法选择法*/int i,j,k,temp1;long temp2;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(numj numk)k=j;/*记录最大数下标位置记录最大数下标位置*/if(k!=i)/*若最大数不在下标位置若最大数不在下标位置i*/temp1=scorek;scorek=scorei;scorei=temp1;temp2=numk;numk=numi;numi=temp2;按学号由小按学号由小到大排序到大排序2023/1/1644/498.5向函数传递二维数组向函数传递二维数组a00a01a02a10a11a12a00a01a02a10a11a12实际传送的是数组第一个元素的地址实际传送的是数组第一个元素的地址short a23;short a23;2023/1/1645/498.5向函数传递二维数组向函数传递二维数组 在声明二维数组形参时，不能省略数组第二在声明二维数组形参时，不能省略数组第二在声明二维数组形参时，不能省略数组第二在声明二维数组形参时，不能省略数组第二维的长度（列数），为什么？维的长度（列数），为什么？维的长度（列数），为什么？维的长度（列数），为什么？想想数组在内存中是如何分布的？想想数组在内存中是如何分布的？想想数组在内存中是如何分布的？想想数组在内存中是如何分布的？元素元素元素元素aijaij在数组在数组在数组在数组a a中的位置是：中的位置是：中的位置是：中的位置是：i*N+j i*N+j 元素地址：元素地址：元素地址：元素地址：首地址首地址首地址首地址 +偏移量偏移量偏移量偏移量a00a01a02a10a11a12a00a01a02a10a11a12实际传送的是数组第一个元素的地址实际传送的是数组第一个元素的地址short aMN;short aMN;偏移偏移1*3+22023/1/1646/49例例8.12 计算每门计算每门课程课程的总分和平均分的总分和平均分voidvoid AverforCourseAverforCourse(intint scoreCOURSE_N,scoreCOURSE_N,intint sum,sum,floatfloat aver,aver,intint n)n)intint i,j;i,j;forfor(j=0;(j=0;jCOURSE_NjCOURSE_N;j+);j+)sumsumj j=0;=0;forfor(i=0;(i=0;inin;i+);i+)sumsumj j=sum=sumj j+scoreij;+scoreij;averaverj j=(float)sum=(float)sumj j/n n;可省略数组第一维的长度可省略数组第一维的长度不能省略第二维的长度不能省略第二维的长度2023/1/1647/49例例8.12 计算每门计算每门学生学生的总分和平均分的总分和平均分voidvoid AverforStudAverforStud(intint scoreCOURSE_N,scoreCOURSE_N,intint sum,sum,floatfloat aver,aver,intint n)n)intint i,j;i,j;forfor(i=0;(i=0;inin;i+);i+)sumsumi i=0;=0;forfor(j=0;(j=0;jCOURSE_NjCOURSE_N;j+);j+)sumsumi i=sum=sumi i+scoreij;+scoreij;averaveri i=(float)sum=(float)sumi i/COURSE_NCOURSE_N;2023/1/1648/49例例8.12计算每门的总分和平均分计算每门的总分和平均分2023/1/1649/49 Questions and answersQuestions and answers