资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2024/9/13,49,/49,第,8,章 数组,哈尔滨工业大学,计算机科学与技术学院,苏小红,sxh,本章学习内容,对数组名特殊含义的理解,数组类型，数组的定义和初始化,向函数传递一维数组和二维数组,排序、查找、求最大最小值等常用算法,为什么使用数组,(Array)?,【,例,8.1】,要读入,5,人的成绩，然后求平均成绩,需定义,5,个不同名整型变量，需要使用多个,scanf(),int score1, score2, score3, score4, score5;,scanf(%d,scanf(%d,.,而用数组，可共用一个,scanf(),并利用循环语句读取,int score5,i;,for (i=0; i5; i+),scanf(%d,保存大量同类型的相关数据,8.1,一维数组的定义和初始化,一维数组的定义,存储类型 数据类型 数组名,整数,1 ,整数,2,整数,n;,a4,a3,a2,a1,a0,数组首地址,int,a5;,定义一个有,5,个,int,型元素的数组,系统在内存分配连续的,5,个,int,空间给此数组,直接对,a,的访问，就是访问此数组的首地址,基类型,下标从,0,开始,8.1,一维数组的定义和初始化,a4,a3,a2,a1,a0,int,a5;,数组大小必须是值为正的常量，不能为变量,一旦定义，不能改变大小,数组大小最好用宏来定义，以适应未来可能的变化,#define,SIZE,5,int,a,SIZE,;,一维数组的定义,存储类型 数据类型 数组名,整数,1 ,整数,2,整数,n;,8.1,一维数组的定义和初始化,数组定义后的初值仍然是随机数,一般需要进行初始化,int,a5 = 12, 34, 56 ,78 ,9 ;,int,a5 = 0 ;,int,a = 11, 22, 33, 44, 55 ;,8.1,一维数组的定义和初始化,数组的引用,数组名,下标,数组下标,(index),都是从,0,开始,使用,a,0,、,a1,、,a2,、,a3,、,a4,这样的形式访问每个元素,下标既可是常量，也可是整型表达式，允许快速随机访问，如,ai,可以像使用普通变量一样使用它们,如何使两个数组的值相等？,main(),int a5 = 1,2,3,4,5, b5;,b = a;,解决方法,方法,1:,逐个元素赋值,b0=a0;,b1=a1;,b2=a2;,b3=a3;,b4=a4;,方法,2:,通过循环赋值,int i;,for (i=0;i5;i+),bi = ai;,原因,:,数组名表示数组的首地址,其值不可改变,!,8.1,一维数组的定义和初始化,【,例,8.2】,编程实现显示用户输入的月份（不包括闰年的月份）拥有的天数,8.1,一维数组的定义和初始化,下标越界是,大忌,！,编译程序不检查是否越界,下标越界，将访问数组以外的空间,那里的数据是未知的，不受我们掌控，可能带来严重后果,b0,b1,b2,b3,b4,c,a,i,b8,【,例,8.3】,当下标值小于,0,或超过数组长度时,会出现什么情况？,运行程序或单步执行观察变量变化情况可以看到，变量,c,和,a,的值因数组越界而被悄悄破坏了,1,2,3,4,5,6,0,7,8,40,44,48,4c,50,54,58,5c,60,64,68,6c,#include ,int main(),int a = 1, c = 2, b5 = 0, i;,printf(%p, %p, %pn, b, ,for (i=0; i0 ? sum/n : -1;,更安全,【,例,8.6】,计算平均分,当输入负值时，表示输入结束,标记,控制的循环,负值作为输入结束标记,【,例,8.6】,计算平均分,当输入负值时，表示输入结束,标记,控制的循环,负值作为输入结束标记,【,例,8.7】,计算最高分,#include ,#define,N,40,int 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;,max(i=0),max(i=2),max(i=3),计算最大值算法,假设其中的一个学生成绩为最高,maxScore = score0;,对所有学生成绩进行比较，即,for (i=1; i maxScore,则修改,maxScore,值为,scorei,打印最高分,maxScore,【,例,8.7】,计算最高分,【,例,8.7】,计算最高分,8.4,排序和查找,排序（,Sorting,）算法,交换法排序,选择法排序,交换法排序,交换法排序,【,例,8.8】,交换法从高到低排序,交换法,排序,for,(i=0; in-1; i+),for,(j=,i+1,; j scorei),交换成绩,scorej,和,scorei,如何实现两数交换？,temp = scorej;,scorej = scorei;,scorei = temp;,temp,scorej,scorei,？,70,50,70,50,70,【,例,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;,选择法排序,k=1,k=2,k=0,k=1,选择法排序,k=3,k=4,k=3,k=4,选择法排序,选择法,排序,for,(i=0; in-1; i+),k = i;,for,(,j=i+1,; j score,k,),记录此轮比较中最高分的元素下标,k = j,;,若,k,中记录的最大数不在位置,i,，则,交换,成绩,score,k,和,score,i,，,交换,学号,numk,和,numi,；,void 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*/,temp,1,= scorek;,scorek = scorei;,scorei = temp,1,;,temp2 = numk;,numk = numi;,numi = temp2;,【,例,8.8】,成绩从高到低顺序,8.4,排序和查找,查找（,Searching,）算法,顺序查找,折半查找,【,例,8.10】,顺序查找学号,int,LinSearch(,long,num,long,x,int,n),int,i;,for,(i=0; in; i+),if,(numi = x),return,i;,return,-1;,哈，找到了！,事先不必排序,【,例,8.11】,折半查找学号,哈，找到了！,按升序排序,10122 10124 10126 10128 10130,【,例,8.11】,折半查找学号,唉，没找到！,10122 10124 10126 10128 10130,int,BinSearch(,long,num,long,x,int,n),int,low, high, mid;,low = 0;,high = n - 1;,while,(low nummid),low = mid + 1;,else,if,(x nummid),high = mid - 1;,else,return,mid;,return,-1;,找到时返回下标位置,找不到时 返回,-1,若未按学号排序，,则如何修改程序？,void 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;,按学号由小到大排序,8.5,向函数传递二维数组,a00,a01,a02,a10,a11,a12,a00,a01,a02,a10,a11,a12,实际传送的是数组第一个元素的地址,short a23;,8.5,向函数传递二维数组,在声明二维数组形参时，不能省略数组第二维的长度（列数），为什么？,想想数组在内存中是如何分布的？,元素,aij,在数组,a,中的位置是：,i * N + j,元素地址： 首地址,+,偏移量,a00,a01,a02,a10,a11,a12,a00,a01,a02,a10,a11,a12,实际传送的是数组第一个元素的地址,short aMN;,偏移,1*3+2,例,8.12,计算每门,课程,的总分和平均分,void,AverforCourse,(,int,scoreCOURSE_N,int,sum,float,aver,int,n),int,i, j;,for,(j=0;,jCOURSE_N,; j+),sum,j, = 0;,for,(i=0;,in,; i+),sum,j, = sum,j, + scoreij;,aver,j, = (float) sum,j, /,n,;,可省略数组第一维的长度,不能省略第二维的长度,例,8.12,计算每门,学生,的总分和平均分,void,AverforStud,(,int,scoreCOURSE_N,int,sum,float,aver,int,n),int,i, j;,for,(i=0;,in,; i+),sum,i, = 0;,for,(j=0;,jCOURSE_N,; j+),sum,i, = sum,i, + scoreij;,aver,i, = (float) sum,i, /,COURSE_N,;,例,8.12,计算每门的总分和平均分,Questions and answers,
展开阅读全文